ГІБРИДНИЙ МЕТОД РІШЕННЯ ЗАДАЧІ МАРШРУТИЗАЦІЇ ТРАНСПОРТУ З УРАХУВАННЯМ ДОДАТКОВИХ ОБМЕЖЕНЬ
DOI:
https://doi.org/10.26906/SUNZ.2023.1.031Ключові слова:
граф, маршрут, задача маршрутизації транспорту, часові вікна, вантажопідйомність, жадібний алгоритм, метод гілок та меж, алгоритм збережень, генетичний алгоритм, кросовер, мутаціяАнотація
Актуальність. У сучасному світі є потреба у застосуванні автоматизованих систем в області транспортної логістики, з метою заощадження ресурсів. При побудові шляху переміщення транспорту виникають проблеми знаходження оптимального маршруту з врахуванням додаткових обмежень, таких як вантажопідйомність транспортних засобів або часові вікна клієнтів. У зв’язку з цим є необхідність вдосконалення існуючих засобів вирішення задачі маршрутизації транспорту. Метою даної роботи є створення гібридного методу рішення задачі маршрутизації транспорту з урахуванням додаткових обмежень. Об’єктом дослідження є процес пошуку оптимальних маршрутів в умовах обмеження вантажопідйомності та врахування часових вікон. Предметом дослідження є алгоритми для рішення задач маршрутизації транспорту з урахуванням заданих обмежень. Результати. У даній роботі розглядаються особливості застосування гібридного підходу, заснованого на використанні генетичного та класичних алгоритмів, для вирішення задачі маршрутизації транспорту з урахуванням додаткових обмежень. Представлені результати експериментальних досліджень, що демонструють переваги та недоліки кожного з розглянутих алгоритмів для рішення поставленої задачі. Висновок. Найбільшу точність та швидкодію забезпечує запропонований гібридний підхід на основі генетичного алгоритму та модифікованого жадібного алгоритму.Завантаження
Посилання
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
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
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
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
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
Кораблев Н.М., Иващенко Г.С., Кушнарев М.В. (2012) “Агентно-ориентированный подход на основе искусственных имунных систем для решения задачи коммивояжера”, Біоніка інтелекту, №2(79), С. 33-37, available at: http://openarchive.nure.ua/handle/document/572
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
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
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
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
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
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
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
