Constructive heuristics for Capacitated Vehicle Routing Problem: a comparative study
https://doi.org/10.15514/ISPRAS-2019-31(3)-12
Abstract
Vehicle Routing Problem (VRP) is concerned with the optimal design of routes to be used by a fleet of vehicles to serve a set of customers. In this study we analyze constructive heuristics for a subcase of VRP, where the vehicles have a limited capacity – Capacitated Vehicle Routing Problem (CVRP). The problem is NP-hard, therefore heuristic algorithms which provide near-optimal polynomial-time solutions are still actual. The aim of this work is to make a comparison of constructive heuristics as there were not found any such classification. Finally, the leader by a criterion of quality is admitted being a Clarke and Wright Savings heuristic; however, this algorithm cannot find the solution for all used instances. This fact and other ones are discussed in the paper. Our future goal is to make an experimental comparison of the most common and state-of-the-art metaheuristics using well suited constructive heuristic to build a suboptimal solution.
About the Authors
Sergey Mikhailovitch Avdoshin
National Research University Higher School of Economics
Russian Federation
Professor, Head of School of Software Engineering
Russian Federation
Professor, Head of School of Software Engineering
Ekaterina Nikolaevna Beresneva
National Research University Higher School of Economics
Russian Federation
School of Software Engineering, Faculty of Computer Science
Russian Federation
School of Software Engineering, Faculty of Computer Science
References
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. 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.
Review
For citations:
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
Email this article 