Метод розв'язання задачі оптимальних вантажних перевезень

Размещено на http://www.allbest.ru/

Хмельницький національний університет

МЕТОД РОЗВ'ЯЗАННЯ ЗАДАЧІ ОПТИМАЛЬНИХ ВАНТАЖНИХ ПЕРЕВЕЗЕНЬ

Атаманюк А.В., аспірант

Гольденгорін Б.І., д.е.н., д.т.н., професор

Анотація

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

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

Annotation

Atamaniuk A. THE METHOD TO SOLVE THE OPTIMAL FREIGHT TRANSPORTATIONS PROBLEM

In this paper a method to solve the optimal freight transportations problem is being present, which is based on the tolerance.

Keywords: vehicle routing problem, upper tolerance, lower tolerance, bottleneck tolerance.

Аннотация

Атаманюк А.В. МЕТОД РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНЫХ ГРУЗОВЫХ ПЕРЕВОЗОК

В статье приведен метод решения задачи оптимизации грузовых перевозок, основанный на допусках.

Ключевые слова: задача маршрутизации транспортного средства, верхний допуск, нижний допуск, горлышковый допуск

Постановка проблеми у загальному вигляді і її зв'язок з важливими науковими та практичними завданнями

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

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

Цілі статті

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

Аналіз останніх досліджень, у яких започатковано вирішення проблеми

вантажний перевезення транспортний маршрутизація

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

Однією із таких задач є задача маршрутизації транспортного засобу, що належить до класу NP - складних задач [1] (тобто, обчислювальна складність задачі залежить від розміру вхідних даних експоненціально) комбінаторної оптимізації, яка розв'язується за допомогою евристичних алгоритмів [2].

Відомий точний алгоритм розв'язання задачі маршрутизації транспортного засобу на основі методу гілок та меж, у зв'язку із величезною швидкістю часу обчислень, неможливо застосовувати для задач із більш ніж 25-30 вершинами.

Один із перших наближених методів розв'язання задачі маршрутизації транспортного засобу був запропонований у 1964 р. (G. Clarke та J.W. Wright). У 1970 та 1980 роках була сформована група класичних алгоритмів розв'язання задачі маршрутизації транспортного засобу (J..B. Bramel, N. Christofides [3], B..E. Gillett, J. Renaud та інші). З середини 1990 років дослідження зосередились у напрямку евристичних методів, серед яких цікавими є метаевристики: пошук з виключеннями (M. Gendreau, A. Hertz, G. Laporte, I.H. Osman та інші), модельований та детермінований віджиг (I. H. Osman та інші), генетичний алгоритм (J.L. Blanton, G. Jeon та інші), алгоритм на основі мурашиних колоній (B. Bullnheimer та інші) та нейронні мережі (Y. Matsuyama та інші). За останні десятиріччя дослідження проводяться в сторону обробки складних видів обмеження.

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

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

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

Виклад основного матеріалу дослідження з повним обґрунтуванням отриманих результатів

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

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

Одним з видів задачі маршрутизації транспортного засобу є задача маршрутизації транспортного засобу з часовими вікнами.

На площині задана деяка кількість споживачів з їхніми потребами, заданий час обслуговування та час від отримання замовлення до поставки, а також депо з однаковими транспортними засобами і з відомими обмеженнями на ємність транспортного засобу. Потрібно знайти оптимальну множину шляхів від початкової вершини (депо) до кінцевої вершини, таку що кожен споживач обслуговується тільки одним транспортним засобом. Очевидно, що деякий маршрут не повинен порушувати обмеження ємності транспортного засобу. Крім того кожен споживач повинен обслуговуватися в своєму так званому часовому вікні. Часове вікно точно визначає ранній та самий пізній час, за який доставка має початися. Якщо транспортний засіб прибуває до клієнта до відкриття часового вікна, то повинен очікувати. Прибуття після кінця часового вікна не дозволяється.

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

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

Опишемо роботу методу гілок та меж, що базується на допусках.

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

1. Використовуємо несиметричну задачу комівояжера як релаксацію задачі маршрутизації [5].

2. Побудуємо еквівалентну задачу, в залежності від кількості транспортних засобів добавляємо k ? 1 копію депо.

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

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

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

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

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

8. Далі серед таких верхніх допусків для всіх циклів, що не обслуговуються, вибирається найбільший, який називається точним верхнім горлишковим допуском [4]. Як і для задачі маршрутизації називатимемо наближеним верхнім горлишковим допуском верхній допуск самого маленького (за кількістю вершин) циклу, що не обслуговується. Будемо називати нижнім допуском циклу, що не обслуговується, найменший з нижніх допусків всіх дуг, виходять з вершин циклу і, що не належать цьому циклу (або рівних йому), найменший з нижніх допусків всіх дуг, що входять у вершини циклу, і не належать цьому циклу. Точний нижній горлишковий допуск [4] визначається як найбільший з нижніх допусків всіх циклів, що не обслуговується, а наближений горлишковий нижній допуск [4] - як нижній допуск самого маленького (за кількістю вершин) циклу, що не обслуговується.

Мають місце наступні твердження:

1. Сума оптимального значення цільової функції релаксованої задачі про призначення і точного верхнього горлишкового допуску є нижньою межею для невідомого оптимального значення задачі маршрутизації.

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

3. Сума оптимального значення цільової функції задачі про призначення і точного нижнього горлишкового допуску є нижньою межею для невідомого оптимального значення задачі маршрутизації.

4. Сума оптимального значення цільової функції задачі про призначення та наближеного нижнього допуску є нижньою межею для невідомого оптимального значення задачі маршрутизації.

5. Значення точного верхнього горлишкового допуску не перевищує значення точного нижнього горлишкового допуску.

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

Висновки

Метод гілок та меж для розв'язання задачі маршрутизації, що базується на допусках, володіє найбільш сильним та стійким синергетичним ефектом [6] від використання допусків для обчислення меж і для вибору гілок, дозволяє зменшити розміри дерева пошуку. Цей метод відрізняється від всіх інших алгоритмів перебору тим, що він будує локально-оптимальні дерева пошуку, а саме: у випадку багатьох оптимальних рішень релаксованої задачі, алгоритм допусків вибирає не порожній перетин всіх можливих дерев пошуку, а якщо перетин порожній, то вибирається те релаксоване оптимальне рішення і дерево пошуку, які дають швидку побудову допустимого розв'язку для вихідної задачі і мінімальний додатковий пошук з метою доведення оптимальності знайденого рішення. Цей метод дозволить оптимізувати вантажні перевезення, покращити роботу логістичних підприємств.

Література

1. Гери М. Вычислительные машины и труднорешаемые задачи / М. Гери, Д. Джонсон. М.: Мир, 1982. 416 с.

2. Polacek M. A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows / M. Polacek, R. F. Hartl, K. Doerner. // Journal of Heuristics, 10. 2004. P. 613-627.

3. Christofides N. The vehicle routing problem / N. Christofides, A. Mingozzi, P. Toth, C. Sandi (Eds.) // Combinatorial Optimization. Wiley, Chichester, 1979. P. 315-338.

4. Goldengorin B. Tolerances Appllied in Combinatorial Optimization / B. Goldengorin, G. Jager, P. Molitor // Journal of Computer Science 2 (9). 2006. P. 716-734.

5. Атаманюк А. В. Новий підхід до розв'язання задачі маршрутизації / А. В. Атаманюк. // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. праць / Кам'янець-Подільський національний університет, імені Івана Огієнка ; [редкол.: Ю. Г. Кривонос (відп. ред.) та ін.]. ? Кам'янець-Подільський: Кам'янець-Подільський національний університет, 2010. Вип. 4. С. 11-17.

6. Goldengorin B. Tolerance Based Algorithms for the ATSP / B. Goldengorin, G. Sierksma, M. Turkensteen // Lecture Notes in Computer Science, 3353. 2004. P. 222-234.

Размещено на Allbest.ru