ГІБРИДНИЙ МЕТОД РІШЕННЯ ЗАДАЧІ МАРШРУТИЗАЦІЇ ТРАНСПОРТУ З УРАХУВАННЯМ ДОДАТКОВИХ ОБМЕЖЕНЬ
Ключові слова:
граф, маршрут, задача маршрутизації транспорту, часові вікна, вантажопідйомність, жадібний алгоритм, метод гілок та меж, алгоритм збережень, генетичний алгоритм, кросовер, мутація
Анотація
Актуальність. У сучасному світі є потреба у застосуванні автоматизованих систем в області транспортної логістики, з метою заощадження ресурсів. При побудові шляху переміщення транспорту виникають проблеми знаходження оптимального маршруту з врахуванням додаткових обмежень, таких як вантажопідйомність транспортних засобів або часові вікна клієнтів. У зв’язку з цим є необхідність вдосконалення існуючих засобів вирішення задачі маршрутизації транспорту. Метою даної роботи є створення гібридного методу рішення задачі маршрутизації транспорту з урахуванням додаткових обмежень. Об’єктом дослідження є процес пошуку оптимальних маршрутів в умовах обмеження вантажопідйомності та врахування часових вікон. Предметом дослідження є алгоритми для рішення задач маршрутизації транспорту з урахуванням заданих обмежень. Результати. У даній роботі розглядаються особливості застосування гібридного підходу, заснованого на використанні генетичного та класичних алгоритмів, для вирішення задачі маршрутизації транспорту з урахуванням додаткових обмежень. Представлені результати експериментальних досліджень, що демонструють переваги та недоліки кожного з розглянутих алгоритмів для рішення поставленої задачі. Висновок. Найбільшу точність та швидкодію забезпечує запропонований гібридний підхід на основі генетичного алгоритму та модифікованого жадібного алгоритму.Завантаження
Дані про завантаження поки що недоступні.
Посилання
1. Aksen D., Zyurt Z., Aras N. (2006), “Open vehicle routing problem with driver nodes and time deadlines”, Journal of the Operational Research Society, Vol. 58(9), pp. 106-114, doi: https://doi.org/10.1057/palgrave.jors.2602249
2. Braekers K., Ramaekers K., Nieuwenhuese I. (2016), “The vehicle routing problem: State of the art classification and review”, Computers & Industrial Engineering, Vol. 99, pp. 300-313, doi: https://doi.org/10.1016/j.cie.2015.12.007
3. Caramia M., Guerriero F. (2010), “A heuristic approach for the truck and trailer routing problem”, Journal of the Operational Research Society, Vol. 61(7), pp. 1168-1180, doi: https://doi.org/10.1057/jors.2009.59
4. Clarke G., Wright J.W. (1964), “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, Vol. 12, No. 4, pp. 568-581, doi: https://doi.org/10.1287/opre.12.4.568
5. Theurich F., Fischer A., Scheithauer G. (2021), “A branch-and-bound approach for a Vehicle Routing Problem with Customer Costs”, EURO Journal on Computational Optimization, Vol. 9, pp. 29-40, doi: https://doi.org/10.1016/j.ejco.2020.100003
6. Кораблев Н.М., Иващенко Г.С., Кушнарев М.В. (2012) “Агентно-ориентированный подход на основе искусственных имунных систем для решения задачи коммивояжера”, Біоніка інтелекту, №2(79), С. 33-37, available at: http://openarchive.nure.ua/handle/document/572
7. Alvarez A., Munari P. (2017), “An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen”, Computers & Operations Research, Vol. 83, pp. 1-12, doi: https://doi.org/10.1016/j.cor.2017.02.001
8. Vidal T., Crainic T.G., Gendreau M., Prins C. (2013), “A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows”, Computers & Operations Research, Vol. 40(1), pp. 475-489, doi: https://doi.org/10.1016/j.cor.2012.07.018
9. Mohammed M.A., Ghani M.K., Hamed R.I., Mostafa S.A., Ahmad M.S., Ibrahim D.A. (2017), “Solving vehicle routing problem by using improved genetic algorithm for optimal solution”, Journal of Computational Science, Vol. 21, pp. 255-262, doi: https://doi.org/10.1016/j.jocs.2017.04.003
10. Bean J. C. (1994), “Genetic algorithms and random keys for sequencing and optimization”, ORSA Journal on Computing, Vol. 6, No. 2, pp. 154-160, doi: https://doi.org/10.1287/ijoc.6.2.154
11. Caceres-Cruz J., Arias P., Guimarans D., Riera D., Juin A. (2015), “Rich vehicle routing problem: Survey”, ACM Computing Surveys (CSUR), Vol. 47(2), No. 32, pp. 1-28, doi: https://doi.org/10.1145/2666003
12. Alba E., Dorronsoro B. (2004), “Solving the vehicle routing problem by using cellular genetic algorithms”, European Conference on Evolutionary Computation in Combinatorial Optimization, Vol. 3004, pp. 11-20, doi: https://doi.org/10.1007/978-3-540-24652-7_2
13. Cheng C., Wang K. (2009), “Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm”, Expert Systems Applications, Vol. 36(4), pp. 7758-7763, doi: https://doi.org/10.1016/j.eswa.2008.09.001
2. Braekers K., Ramaekers K., Nieuwenhuese I. (2016), “The vehicle routing problem: State of the art classification and review”, Computers & Industrial Engineering, Vol. 99, pp. 300-313, doi: https://doi.org/10.1016/j.cie.2015.12.007
3. Caramia M., Guerriero F. (2010), “A heuristic approach for the truck and trailer routing problem”, Journal of the Operational Research Society, Vol. 61(7), pp. 1168-1180, doi: https://doi.org/10.1057/jors.2009.59
4. Clarke G., Wright J.W. (1964), “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, Vol. 12, No. 4, pp. 568-581, doi: https://doi.org/10.1287/opre.12.4.568
5. Theurich F., Fischer A., Scheithauer G. (2021), “A branch-and-bound approach for a Vehicle Routing Problem with Customer Costs”, EURO Journal on Computational Optimization, Vol. 9, pp. 29-40, doi: https://doi.org/10.1016/j.ejco.2020.100003
6. Кораблев Н.М., Иващенко Г.С., Кушнарев М.В. (2012) “Агентно-ориентированный подход на основе искусственных имунных систем для решения задачи коммивояжера”, Біоніка інтелекту, №2(79), С. 33-37, available at: http://openarchive.nure.ua/handle/document/572
7. Alvarez A., Munari P. (2017), “An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen”, Computers & Operations Research, Vol. 83, pp. 1-12, doi: https://doi.org/10.1016/j.cor.2017.02.001
8. Vidal T., Crainic T.G., Gendreau M., Prins C. (2013), “A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows”, Computers & Operations Research, Vol. 40(1), pp. 475-489, doi: https://doi.org/10.1016/j.cor.2012.07.018
9. Mohammed M.A., Ghani M.K., Hamed R.I., Mostafa S.A., Ahmad M.S., Ibrahim D.A. (2017), “Solving vehicle routing problem by using improved genetic algorithm for optimal solution”, Journal of Computational Science, Vol. 21, pp. 255-262, doi: https://doi.org/10.1016/j.jocs.2017.04.003
10. Bean J. C. (1994), “Genetic algorithms and random keys for sequencing and optimization”, ORSA Journal on Computing, Vol. 6, No. 2, pp. 154-160, doi: https://doi.org/10.1287/ijoc.6.2.154
11. Caceres-Cruz J., Arias P., Guimarans D., Riera D., Juin A. (2015), “Rich vehicle routing problem: Survey”, ACM Computing Surveys (CSUR), Vol. 47(2), No. 32, pp. 1-28, doi: https://doi.org/10.1145/2666003
12. Alba E., Dorronsoro B. (2004), “Solving the vehicle routing problem by using cellular genetic algorithms”, European Conference on Evolutionary Computation in Combinatorial Optimization, Vol. 3004, pp. 11-20, doi: https://doi.org/10.1007/978-3-540-24652-7_2
13. Cheng C., Wang K. (2009), “Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm”, Expert Systems Applications, Vol. 36(4), pp. 7758-7763, doi: https://doi.org/10.1016/j.eswa.2008.09.001
Опубліковано
2023-03-17
Як цитувати
Ivashchenko Heorhii Гібридний метод рішення задачі маршрутизації транспорту з урахуванням додаткових обмежень / Heorhii Ivashchenko, Artem Skliarov, Olesia Barkovska // Системи управління, навігації та зв’язку. Збірник наукових праць. – Полтава: ПНТУ, 2023. – Т. 1 (71). – С. 31-35. – doi:https://doi.org/10.26906/SUNZ.2023.1.031.
Розділ
Автомобільний, річковий, морський та авіаційний транспорт
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
