Анализ математических постановок задачи маршрутизации с ограничением по грузоподъемности и методов их решения

Задача маршрутизации является одной из важнейших NP-трудных задач комбинаторной оптимизации. Она заключается в нахождении множества оптимальных замкнутых маршрутов с целью развозки товаров клиентам, используя ограниченное количество транспортных средств. В данной работе анализируется особый вид задачи маршрутизации - задача маршрутизации с ограничением по грузоподъемности, в которой у каждого транспортного средства есть лимит на максимальный вес (объем) груза. Целью данной работы является составление классификации различных типов задачи маршрутизации с ограничением по грузоподъемности. В первой части работы дана общая информация о проблеме, указаны рамки, в которых проводилось исследование - не рассматривались динамические и стохастические подвиды задачи маршрутизации. Во второй части представлена впервые предложенная авторами работы математическая постановка трех классических вариантов задачи маршрутизации с ограничением по грузоподъемности. В третьей части работы представлен список подклассов рассматриваемой задачи, включающий описание, математические модели для некоторых задач, а также наиболее перспективные метаэвристики, с помощью которых можно решать поставленную задачу. В четвертой части приведено упоминание об алгоритме LKH-3, способном решать некоторые подклассы задач с меньшим отклонением от оптимального значения по сравнению с другими алгоритмами. В заключении, приведена таблица, объединяющая все методы, описанные ранее, и схема с взаимосвязями задачи маршрутизации с ограничением по грузоподъемности и её подклассами. В будущем авторы работы планируют расширить классификацию, включив в неё подклассы стохастических и динамических вариантов данной проблемы.

задача маршрутизации с ограничением по грузоподъемности, математическая постановка, метаэвристики, классификация задач маршрутизации

1. P. Toth and D. Vigo. An overview of vehicle routing problems, In The Vehicle Routing Problem, SIAM, 2002.

2. G. B. Dantzig and J. H. Ramser. The Truck Dispatching Problem. Management Science, vol. 6, no. 1, 1959, pp. 80-91.

3. M. Reed and B. Simon. Methods of Modern Mathematical Physics, London: Academic Press, 1972.

4. B. Golden, S. Raghavan and E. Wasil. The vehicle routing problem: Latest advances and new challenges, New York: Springer, 2008.

5. P. Pisinger and S. Ropke. A general heuristic for vehicle routing problems. Computers & Operations Research, vol. 34, no. 8, 2007, pp. 2403-2435.

6. Y. Nagata and O. Braysy. Edge assembly-based memetic algorithm for the capacitated vehicle routing problem. Networks, vol. 54, no. 4, 2009, pp. 205-215.

7. T. Vidal, T. Crainic, M. Gendreau, N. Lahrichi and W. Rei. A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems. Operations Research, vol. 60, no. 3, 2012, pp. 611-624.

8. M. Salari, P. Toth and A. Tramontani. An ILP improvement procedure for the Open Vehicle Routing Problem. Computers & Operations Research, vol. 37, no. 12, 2010, pp. 2106-2120.

9. P. Repoussis, C. Tarantilis, O. Braysy and G. Ioannou. A hybrid evolution strategy for the open vehicle routing problem. Computers & Operations Research, vol. 37, no. 3, 2010, pp. 443-455.

10. K. Fleszar, I. Osman and K. Hindi. A variable neighbourhood search algorithm for the open vehicle routing problem. European Journal of Operational Research, vol. 195, no. 3, 2009, pp. 803-809.

11. E. Zachariadis and C. Kiranoudis. An open vehicle routing problem metaheuristic for examining wide solution neighborhoods. Computers & Operations Research, vol. 37, no. 4, 2010, pp. 712-723.

12. S. MirHassani and N. Abolghasem. A particle swarm optimization algorithm for open vehicle routing problem. Expert Systems with Applications, vol. 38, no. 9, 2011, pp. 11547-11551.

13. G. Laporte, Y. Nobert and M. Desrochers. Optimal routing under capacity and distance restrictions. Operations Research, vol. 33, no. 5, 1985, p. 1050–1073.

14. C. Li, D. Simchi-Levi and M. Desrochers. On the distance constrained vehicle routing problem. Operational Research, vol. 40, 1992, pp. 790-799.

15. P. Repoussis, C. Tarantilis and G. Ioannou. Arc-guided evolutionary algorithm for the vehicle routing problem with time windows. IEEE Transactions on Evolutionary Computation, vol. 13, no. 3, 2009, pp. 624–647.

16. E. Prescott-Gagnon, G. Desaulniers and L. Rousseau. A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows. Networks, vol. 54, no. 4, 2009, pp. 190–204.

17. Y. Nagata, O. Bräysy and W. Dullaert. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Computers & Operations Research, vol. 37, no. 4, 2010, pp. 724–737.

18. T. Vidal, T. Crainic, M. Gendreau and C. Prins. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & Operations Research, vol. 40, no. 1, 2013, pp. 475–489.

19. K. Braekers, K. Ramaekers and I. Nieuwenhuyse. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, vol. 99, 2016, pp. 300-313.

20. S. Ropke and D. Pisinger. A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, vol. 171, no. 3, 2006, pp. 750–775.

21. E. Zachariadis and C. Kiranoudis. An effective local search approach for the vehicle routing problem with backhauls. Expert Systems with Applications, vol. 39, no. 3, 2012, pp. 3174–3184.

22. Y. Gajpal and P. Abad. Multi-ant colony system (MACS) for a vehicle routing problem with backhauls. European Journal of Operational Research, vol. 196, no. 1, 2009, pp. 102–117.

23. S. Thangiah, J.-Y. Potvin and T. Sun. Approaches to Vehicle Routing with Backhauls and Time. Windows International Journal of Computers and Operations Research, vol. 23, no. 11, 1996, pp. 1043-1057.

24. I. Küçükoğlu and N. Öztürk. An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows. Computers and Industrial Engineering, vol. 86, no. 3, 2015, pp. 60-68.

25. S. Parragh, K. Doerner and R. Hartl. A survey on pickup and delivery problems. Journal für Betriebswirtschaft, vol. 58, 2008, pp. 81-117.

26. A. Subramanian, Drummond, C. Bentes, L. Ochi and R. Farias. A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, vol. 37, no. 11, 2010, pp. 1899-1911.

27. E. Zachariadis and C. Kiranoudis. A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Systems with Applications, vol. 38, no. 3, 2011, pp. 2717-2726.

28. M. Souza, M. Silva, M. Mine, L. Ochi and A. Subramanian. A hybrid heuristic, based on iterated local search and GENIUS, for the vehicle routing problem with simultaneous pickup and delivery. International Journal of Logistics Systems Management, vol. 10, no. 2, 2010, pp. 142-156.

29. A. Subramanian and M. Battarra. An iterated local search algorithm for the travelling salesman problem with pickups and deliveries. Journal of the Operational Research Society, vol. 64, 2013, pp. 402-409.

30. A. Subramanian, E. Uchoa and L. Ochi. A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research, vol. 40, no. 10, 2013, pp. 2519-2531.

31. 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, pp. 455–472.

32. R. Bent and P. Van Hentenryck. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Computers & Operations Research, vol. 33, no. 4, 2006, pp. 875–893.

33. Y. Nagata and S. Kobayashi. A memetic algorithm for the pickup and delivery problem with time windows using selective route exchange crossover. In Proceedings of PPSN’11, vol. 6238, 2011, pp. 536– 545.

34. D. Pisinger and S. Ropke. A general heuristic for vehicle routing problems. Computers & Operations Research, vol. 34, no. 8, 2007, pp. 2403–2435.

35. 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.

36. A. Olivera and O. Viera. Adaptive memory programming for the vehicle routing problem with multiple trips. Computers & Operations Research, vol. 34, no. 1, 2007, pp. 28–47.

37. J.-F. Cordeau and M. Maischberger. A Parallel Iterated Tabu Search Heuristic for Vehicle Routing Problems. Computers & Operations Research, vol. 39, no. 9, 2012, pp. 2033–2050.

38. V. Hemmelmayr, K. Doerner and R. Hartl. A variable neighborhood search heuristic for periodic routing problems. European Journal of Operational Research, vol. 195, no. 3, 2009, pp. 791–802.

39. D. Gulczynski, B. Golden and E. Wasil. The period vehicle routing problem : New heuristics and real-world variants. Transportation Research Part E: Logistics and Transportation Review, vol. 47, no. 5, 2011, pp. 648-668.

40. S. Chen, B. Golden and E. Wasil. The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results. Networks, vol. 49, 2007, pp. 318–329.

41. D. Gulczynski, B. Golden and E. Wasil. The split delivery vehicle routing problem with minimum delivery amounts. Transportation Research Part E, vol. 46, 2010, pp. 612–626.

42. C. Archetti and M. Speranza. The split delivery vehicle routing problem: a survey. In The Vehicle Routing Problem Latest Advances and New Challenges, Operations Research, Computer Science Interfaces Series, 2008, pp. 103-122.

43. M. Jin, K. Liu and B. Eksioglu. A column generation approach for the split delivery vehicle routing problem. Operations Research Letters, vol. 36, 2008, pp. 265-270.

44. S. Ngueveu, C. Prins and C. Wolfler. An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Computers & Operations Research , vol. 37, no. 11, 2010, pp. 1877–1885.

45. G. Ribeiro and G. Laporte. An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research, vol. 39, no. 3, 2012, pp. 728–735.

46. L. Ke and Z. Feng. A two-phase metaheuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research, vol. 40, no. 2, 2013, pp. 633-638.

47. J. Sze, S. Salhi and N. Wassan. The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search. Transportation Research Part B: Methodological, vol. 101, 2017, pp. 162-184.

48. K. Helsgaun. An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems. Technical Report, Roskilde University, 2017.