Preview

Труды Института системного программирования РАН

Расширенный поиск

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

https://doi.org/10.15514/ISPRAS-2019-31(3)-12

Полный текст:

Аннотация

Задача маршрутизации – одна из широко известных задач комбинаторной оптимизации. Она состоит в отыскании оптимального множества маршрутов для транспортных средств с целью однократного обслуживания определенного множества клиентов. В данной работе исследуется подвид задачи маршрутизации – задача маршрутизации с ограничением по грузоподъемности, в которой каждое транспортное средство имеет свою грузоподъемность. Задача является NP-трудной, поэтому вместо точных алгоритмов решения исследуются только эвристические алгоритмы, позволяющие получить приближенные решения за полиномиальное время. Задача работы – провести экспериментальное исследование точности решения различных конструктивных эвристик, так как в других источниках не было найдено подобных сравнений.  В большинстве случаев, лидером можно признать эвристику «Clarke and Wright Savings», однако существуют отдельные наборы данных, описанные в тексте, на которых лучше работают другие алгоритмы. Также в статье рассмотрены и другие интересные факты. В целом работа проделана с целью дальнейшего использования полученных знаний в экспериментальном исследовании наиболее известных и современных метаэвристических алгоритмов решения задачи маршрутизации с ограничением по грузоподъемности, для которых будут получены предварительные решения на основе выявленных лучших эвристических методов конструирования маршрута.

Об авторах

Сергей Михайлович Авдошин
Национальный исследовательский университет “Высшая школа экономики”
Россия
Профессор, руководитель департамента программной инженерии факультета компьютерных наук


Екатерина Николаевна Береснева
Национальный исследовательский университет “Высшая школа экономики”
Россия
Факультет компьютерных наук, Департамент программной инженерии


Список литературы

1. P. Toth and D. Vigo, "Branch-and-Bound algorithms for the capacitated VRP," in The Vehicle Routing Problem, Philadelphia, SIAM, 2002, pp. 29-51.

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

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

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

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

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

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

8. M. Reed and B. Simon. Methods of modern mathematical physics. London: Academic Press, 1972.

9. G. Laporte and F. Demet. Classical heuristics for the Capacitated VRP. In The Vehicle Routing Problem, SIAM, 2002, pp. 109-128.

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

11. P. Yellow. A computational modification to the savings method of vehicle scheduling, Operational Research Quarterly, no. 21, 1970, pp. 281-283.

12. T. Gaskell. Bases for vehicle fleet scheduling. Operational Research Quarterly, no. 18, 1967, pp. 281-295.

13. B. Golden, T. Magnanti, and H. Nguyen. Implementing vehicle routing algorithms. Networks, no. 7, 1977, pp. 113-148.

14. M. L. Fisher and R. Jaikumar. A generalized assignment heuristic for vehicle routing. Networks, vol. 11, no. 3, 1981, pp. 109-124.

15. T. Sultana, M. Akhand and M. Rahman. A variant Fisher and Jaikuamr algorithm to solve capacitated vehicle routing problem. In Proc. of the 8th International Conference on Information Technology (ICIT), 2017, pp. 710-716.

16. I. Xavier. CVRPLIB. [Online]. Available: http://vrp.atd-lab.inf.puc-rio.br/index.php/en/. [Accessed 09 07 2019].

17. Heidelberg University. TSPLIB. [Online]. Available: https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/. [Accessed 09 07 2019].

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


Для цитирования:


Авдошин С.М., Береснева Е.Н. Эвристические методы конструирования маршрута для решения задачи маршрутизации с ограничением по грузоподъемности. Труды Института системного программирования РАН. 2019;31(3):145-156. https://doi.org/10.15514/ISPRAS-2019-31(3)-12

For citation:


Avdoshin S.M., Beresneva E.N. Constructive heuristics for Capacitated Vehicle Routing Problem: a comparative study. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2019;31(3):145-156. https://doi.org/10.15514/ISPRAS-2019-31(3)-12

Просмотров: 358


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)