Вдосконалено методи оптимізації замкнених маршрутів на транспортних мережах, що включають в себе загальну, гамільтонову та симетричну задачі комівояжера (ЗЗК, ГЗК та СЗК відповідно). Запропоновано точний метод для розв’язання ЗЗК, в якому спочатку знаходяться найкоротші ланцюги між усіма парами вершин вхідного графа, а потім в отриманій матриці ваг алгоритмом Літла знаходиться розв’язок СЗК. Кожне ребро знайденого маршруту комівояжера заміняється на відповідний найкоротший ланцюг. Запропоновано метод розв’язання ЗЗК, яка піддається розбиттю на блоки; розв’язки ЗЗК в блоках об'єднуються в шуканий маршрут за поліноміальний час. Розроблено наближений метод ЗЗК. Запропоновано модифікацію методу Літла з поліпшеною процедурою обчислення нижньої межі, заснованої на алгоритмі розв’язання варіанта задачі про призначення. Одержана модифікація має кращу швидкодію та менші вимоги до оперативної пам’яті.

• Левченко Антон Юрійович (фізико-математичні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"