Анотація до роботи:

Плечистий Д.Д. Моделі та ефективні методи організації циклічних процесів в класі задач типу комівояжера.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. – Харківський національний університет радіоелектроніки, Харків, 2005.

Дисертацію присвячено вивченню моделей циклічних процесів та розвитку методів їх оптимізації. З ними пов’язана необхідність упоряд-кування послідовностей операцій, які періодично повторюються, таким чином, щоб досягти оптимуму відносно обраного критерію. Велика кількість задач циклічного упорядкування може бути зведеною до відомої задачі комівояжера. Алгоритмічні властивості даної проблеми обмежують застосування точних методів її розв’язання для вхідних даних, що використовуються на практиці. Тому проблема розробки ефективних наближених методів розв’язання ЗК залишається актуальною.

В роботі набув розвитку метод побудови локальних послідовностей для розв’язання загальної ЗК та задачі складання конвеєрного розкладу. Показано, як отримані результати можуть бути застосовані на практиці.

У дисертації наведено теоретичне узагальнення та новий підхід до вирішення наукової задачі, що полягає в розробці та удосконаленні математичних методів оптимізації циклічних процесів, які описуються в термінах проблеми комівояжера.

Основні наукові і практичні результати роботи полягають у наступному.

1. На основі аналізу сучасних досягнень в області побудови методів упорядкування та призначення визначено актуальність подальшого розвитку математичних методів оптимізації циклічних процесів, який полягає в побудові ефективних комбінованих підходів до розв’язання ЗК великих розмірностей.

2. Одержано ефективну схему утворення всіх локальних циклічних перестановок заданої розмірності. На основі даного підходу розроблено ефективний метод розв’язання задачі комівояжера, що надав подальшого розвитку схемі побудови локальних послідовностей, дозволяючи знаходити допустимий розв’язок ЗК за час . Проаналізовано засоби підвищення точності методу, які представлено двома процедурами локального пошуку. В кожній з них спроба наблизити допустимий розв’язок ЗК до оптимального виконується за допомогою операції -заміни. Обґрунтовано вибір операції 3-заміни для загальної ЗК.

3. Запропонована модифікація методу побудови , в якій передбачені засоби, що обмежують зростання вартості локального розв’язку, отриманого для підматриці матриці вартостей ЗК, . Розглянуто підходи до збільшення точності розв’язання загальної ЗК за поліноміальний час у вигляді комбінації схеми послідовного утворення локальних розв’язків та процедур локального пошуку.

4. Вперше метод локальних послідовностей використано для ефективного розв’язування часткового случаю задачі побудови розкладу конвеєрної системи. Доведено, що у випадку, коли матриця тривалостей є упорядкованою по рядкам, представлений підхід знаходить оптимальний розв’язок. Побудова оптимального розв’язку виконується за час , так саме, як і для найкращого з відомих алгоритмів, що розв’язує задачу за допомогою рекурентних співвідношень.

5. Спроектовано та розроблено програмний засіб TS Explorer, в склад якого включено алгоритм Літла, алгоритм „йди до найближчого”, алгоритм „найближчого міста” та розроблені алгоритми з їх модифікаціями.

6. Проведено обчислювальний експеримент, в ході якого досліджувались програмні реалізації розроблених методів. Аналіз результатів проведеного експерименту виявив доцільність застосування представлених методів для розв’язання ЗК великих розмірностей, а також часткових випадків складання розкладу конвеєрних систем.

Результати досліджень є внеском у подальший розвиток і удоскона-лення методів розв’язання задач організації циклічних процесів, здебільшого пов’язаних з проблемами ефективної організації транспортного процесу. На практиці їх можна застосовувати у моделюванні і у проектуванні автоматизованих систем управління виробничими підприємствами, в системах управління транспортом, системах штучного інтелекту та інших. Отримані результати набули впровадження в системах автоматизованого проектування та системах керування виробництвом в Житомирському СКТБ засобів моделювання в енергетиці НАН України та в ТзОВ REC, а також застосовуються в навчальному процесі Житомирського державного технологічного університету.

Публікації автора:

1. Панішев А.В., Плечистий Д.Д. До питання побудови маршруту комівояжера // Вісник Житомирського інженерно-технологічного інституту. – 2002. – №20. – С. 120–124.

   Плечистий Д.Д. Задача комівояжера: застосування, розв’язання, дослідження // Вісник Житомирського інженерно-технологічного інституту. – 2002. – №23. – С. 217–221.

   Панишев А.В., Плечистый Д.Д., Костикова М.В. Комбинация локального поиска и схемы построения оптимальных подпоследовательностей в задачах выбора и назначения // Штучний Інтелект. – Донецьк: IПШI, 2003. - №4. – С. 25–31.

   Панішев А.В., Плечистий Д.Д., Скачков В.О. Вузлові питання задачі комівояжера. 1 // Вісник Житомирського державного технологічного університету. – 2004. – №29. – С. 198–204.

   Костікова М.В., Панішев А.В., Плечистий Д.Д. Вузлові питання задачі комівояжера. 2 // Вісник Житомирського державного технологічного університету. – 2004. – №30. – С. 99–108.

   Панишев А.В., Плечистый Д.Д., Скачков В.А. Об эффективно разрешимых случаях задачи коммивояжера и их приложениях // Штучний Інтелект. – Донецьк: IПШI, 2004. – №4. – С. 169–174.

   Панишев А.В., Плечистый Д.Д., Скакалина Е.В. Схема построения локальных оптимальных последовательностей в решении обобщений задачи о назначениях // Матеріали V Міжнар. наук.-практ. конф. „Наука і освіта – 2002”. – Дніпропетровськ: Наука і освіта, 2002. – Т.20. – С. 54–55.

   Панишев А.В., Данильченко А.М., Плечистый Д.Д. Эффективное построение решений в задачах оптимального назначения и составления расписаний // «Искусственный интеллект – 2002», Материалы Междунар. науч.-техн. конф. – Таганрог: Изд-во ТРТУ, 2002. – Т.1. – С. 336–339.

   Панішев А.В., Плечистий Д.Д. Про один ефективний метод роз-в’язання проблеми комівояжера. // Проблеми математичного моделювання сучасних технологій. Міжнар. конф.: Тези доповідей. – Хмельницький: ТУП, 2002. – С. 103.

   Плечистый Д.Д. Об одном эвристическом подходе к решению задачи коммивояжера // Материалы 7-го Междунар. молодежного форума «Радиоэлектроника и молодежь в ХХI веке»: Сб. материалов форума. – Харьков: ХНУРЭ, 2003. – С. 572.

   Панишев А.В., Плечистый Д.Д. Развитие и совершенствование метода локального поиска в задачах оптимизации дискретных процессов // Труды четвертой междунар. науч.-практ. конф. «Современные инфор-мационные и электронные технологии». – Одесса: ДП «Нептун-Технология», 2003. – С. 162.

   Panishev A.V., Plechystyy D.D. An effective exact algorithm for one particular case of the traveling-salesman problem // International Journal “Information Theories & Applications”. – 2003. – Vol.10. – P. 355–359.

   Панишев А.В., Плечистый Д.Д. Алгоритм 3-кратной замены в методе локального поиска // Труды пятой междунар. науч.-практ. конф. «Современные информационные технологии». – Одесса: ДП «Нептун-Технология», 2004. – С. 118.

   Панишев А.В., Плечистый Д.Д. Актуальные вопросы оптимизации моделей циклических процессов для задач типа коммивояжера // 10-я Юбилейная междунар. науч. конф. «Теория и техника передачи, приема и обработки информации». Сб. Тезисов докладов. Ч.2. – Харьков: ХНУРЭ, 2004. – С. 22–23.