Эвристические методы конструирования маршрута для решения задачи маршрутизации с ограничением по грузоподъемности
https://doi.org/10.15514/ISPRAS-2019-31(4)-8
Аннотация
Задача маршрутизации – одна из широко известных задач комбинаторной оптимизации. Она состоит в отыскании оптимального множества маршрутов для транспортных средств с целью однократного обслуживания определенного множества клиентов. В данной работе исследуется подвид задачи маршрутизации – задача маршрутизации с ограничением по грузоподъемности, в которой каждое транспортное средство имеет свою грузоподъемность. Задача является NP-трудной, поэтому вместо точных алгоритмов решения исследуются только эвристические алгоритмы, позволяющие получить приближенные решения за полиномиальное время. Данная работа является продолжением исследования, посвященного алгоритмам конструирования маршрута; оно позволяет получить первоначальные решения для данной задачи. Было выяснено, что эвристика Clarke and Wright Savings (CWS) является одной из лучших, за исключением наборов данным с геометрическим расположением точек, для которых лучшим является алгоритм Nearest Neighbor (NN). Целью работы является сравнение локально-оптимальных метаэвристических алгоритмов решения задачи маршрутизации с ограничением по грузоподъемности по двум критериям: точность и время решения, для получения начального решения используются алгоритмы CWS и NN. Выявлено пять Парето оптимальных групп алгоритмов для различных типов входных данных. Интересно, что алгоритм «Lin, Kernighan and Helsgaun heuristic» (LKH-3), входящий во все Парето оптимальные группы для смежной задачи (задача коммивояжера), в данном случае вошел только в четыре группы из пяти.
Об авторах
Сергей Михайлович АвдошинРоссия
Профессор, руководитель департамента программной инженерии факультета компьютерных наук
Екатерина Николаевна Береснева
Россия
Преподаватель департамента программной инженерии, аспирант, факультет компьютерных наук,
Список литературы
1. E. Beresneva and S. Avdoshin. Analysis of Mathematical Formulations of Capacitated Vehicle Routing Problem and Methods for their Solution. Trudy ISP RAN/Proc. ISP RAS, vol. 30, no. 3, 2018, pp. 233-250. DOI: 10.15514/ISPRAS-2018-30(3)-17.
2. K. Braekers, K. Ramaekers, and I. Nieuwenhuyse. The vehicle routing problem: State of the art classification and review. Computers and Industrial Engineering, vol. 99, 2016, pp. 300-313.
3. B. Golden, S. Raghavan, and E. Wasil. The vehicle routing problem: Latest advances and new challenges. New York: Springer, 2008, 591 p.
4. P. Toth and D. Vigo. Vehicle Routing Problems, Methods, and Applications. Philadelphia: SIAM, 2014, 481 p.
5. F. Arnold, M. Gendreau, and K. Sorensen. Efficiently solving very large-scale routing problems. Computers and Operations Research, vol. 107, 2019, pp. 32-42.
6. K. Helsgaun. An effective implementation of the Lin–Kernighan traveling salesman heuristic. European Journal of Operational Research, vol. 12, issue 1, 2000, pp. 106-130.
7. E. Zachariadis and C. Kiranoudis. An open vehicle routing problem metaheuristic for examining wide solution neighborhoods. Computers and Operations Research, vol. 37, no. 4, 2010, pp. 712-723.
8. E. Taillard, G. Laporte and M. Gendreau. Vehicle routeing with multiple use of vehicles. Journal of the Operational Research Society, vol. 47, no. 8, 1996, pp. 1065-1070.
9. S. Ropke and D. Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, vol. 40, no. 4, 2006, p. 455–472.
10. P. Toth and D. Vigo. An overview of vehicle routing problems. In The Vehicle Routing Problem, SIAM, 2002, pp. 1-26..
11. K. Helsgaun. An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems. Technical Report, Roskilde University, 2017, 60 p.
12. P. Schittekat and K. Sorensen. Deconstructing record-to-record travel for the capacitated vehicle routing problem. Operational Research and Management Science Letters, vol. 1, no. 1, 2018, pp. 17-27.
13. F. Li, B. Golden, and E. Wasil. Very large-scale vehicle routing: new test problems, algorithms, and results. Computers and Operations Research, vol. 32, issue 5, 2005, p. 1165–1179.
14. G. Laporte and F. Demet. Classical Heuristics for the Capacitated VRP. In The Vehicle Routing Problem, SIAM, 2002, pp. 109-128.
15. C. Voudouris, E. Tsang, and A. Alsheddy. Guided local search. In Handbook of metaheuristics, Springer, 2010, pp. 321-361.
16. D. Mester and O. Braysy. Active-guided evolution strategies for large-scale capacitated vehicle routing problems. Computers and Operations Research, vol. 34, no. 10, 2007, pp. 2964–2975.
17. F. Arnold and K. Sorensen. Knowledge-guided local search for the Vehicle Routing Problem. Computers and Operations Research, vol. 105, 2019, pp. 32-46.
18. F. T. E. Glover. A User’s Guide to Tabu Search. Operations Research, vol. 41, no. 1, 1993, pp. 1-28.
19. E. Zachariadis and C. Kiranoudis.A strategy for Reducing the Computational Complexity of Local Search-Based Methods for the Vehicle Routing Problem. Computers and Operations Research, vol. 37, 2010, pp. 2089–2105.
20. S. Kirkpatrick, C. Gelatt, and M. Vecchi. Optimization by simulated annealing. Science, vol. 220, no. 4598, 1983, pp. 671– 680.
21. NEO. Simulated Annealing. [Online]. Available: http://neo.lcc.uma.es/vrp/solution-methods/metaheuristics/simulated-annealing/. Accessed 27 02 2019.
22. Osman. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, vol. 41, 1993, pp. 421-451.
23. S. Avdoshin and E. Beresneva. The Metric Travelling Salesman Problem: The Experiment on Pareto-optimal Algorithms. Trudy ISP RAN/Proc. ISP RAS, vol. 29, no. 4, pp. 123-138, 2017. DOI: 10.15514/ISPRAS-2017-29(4)-8.
24. K. Helsgaun. LKH-3. 2. [Online]. Available: http://akira.ruc.dk/~keld/research/LKH-3/. Accessed 01 2019.
25. Xavier. CVRPLIB. [Online]. Available: http://vrp.atd-lab.inf.puc-rio.br/index.php/en/. Accessed 09 05 2018.
26. Heidelberg University. TSPLIB. [Online]. Available: https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/. Accessed 09 05 2018.
Рецензия
Для цитирования:
Авдошин С.М., Береснева Е.Н. Эвристические методы конструирования маршрута для решения задачи маршрутизации с ограничением по грузоподъемности. Труды Института системного программирования РАН. 2019;31(4):121-138. https://doi.org/10.15514/ISPRAS-2019-31(4)-8
For citation:
Avdochin S.M., Beresneva E.N. Local search metaheuristics for Capacitated Vehicle Routing Problem: a comparative study. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2019;31(4):121-138. https://doi.org/10.15514/ISPRAS-2019-31(4)-8