УЗАГАЛЬНЕННЯ ЗАДАЧІ КОМІВОЯЖЕРА ТА АНАЛІЗ ЕФЕКТИВНОСТІ МЕТОДІВ ЇЇ РОЗВ’ЯЗАННЯ

Анотація

Задача комівояжера (задача про кільцевий маршрут): визначення найкоротшого шляху по замкненому маршруту досить часто виникає при розробці логістичних програм, зокрема при організації транспортних перевезень. Методи її розв’язання досить широко висвітлені в багатьох монографіях та в навчальній літературі. Однак, на практиці зустрічається ряд задач, які не можуть бути розв’язані в межах класичних підходів. У даній роботі розглянуто два класи задач, які можуть бути зведені до класичної задачі комівояжера і запропоновані методи зведення до неї. Також проаналізовано методи розв’язання запропонованих задач. У першому з класів задач про кільцевий маршрут розглянуто варіант, коли транспортний засіб (судно) за необхідністю має відвідати один або кілька пунктів двічі. Показано, що дана задача розпадається на дві або більше окремих задач про кільцевий маршрут і її розв’язання є сумою розв’язків відповідних класичних задач. Другий клас задач - це задачі з пріоритетними маршрутами: маршрутами, які в силу певних причин повинні бути пройдені першими або останніми. У даному випадку вихідна задача може бути розв’язана двома способами. Перший з них полягає у виділенні пріоритетних ділянок і подальшому розв’язанні задачі про найкоротший шлях для решти непріоритетних ділянок. Другий спосіб полягає в редукції матриці перевезень за допомогою введення фіктивних часу або витрат для пріоритетних ділянок. Подальше розв’язання проводиться за класичною схемою розв'язання задачі комівояжера. У статті також проведено порівняння трьох методів розв’язання задачі про кільцевий маршрут. Зроблено висновок про те, що при невеликій кількості пунктів найбільш ефективним є прямий комбінаторний метод. При збільшенні кількості відвідуваних пунктів ефективнішим стає метод розгалужень і меж. Зауважено, що ефективність даного методу знижується в разі наявності декількох оптимальних розв’язків. Метод розв’язання виродженої транспортної задачі, незважаючи на свою алгоритмічність, є прийнятним тільки в разі єдиності або пошуку одного з оптимальних розв’язків.