In this paper, a deterministic heuristic method is developed for obtaining an initial solution to an extremely large-scale capacitated vehicle routing problem (CVRP) having thousands of customers. The heuristic has three main objectives. First, it should be able to withstand the computational and memory problems normally associated with extremely large-scale CVRP. Secondly, the outputs should be reasonably accurate and should have a minimum number of vehicles. Finally, it should be able to produce the results within a short duration of time. The new method, based on the sweep algorithm, minimizes the number of vehicles by loading the vehicles nearly to their full capacity by skipping some of the customers as and when necessary. To minimize the total traveled distance, before the sweeping starts the customers are ordered based on both the polar angle and the distance of the customer from the depot. This method is tested on 10 sets of standard benchmark instances found in the literature. The results are compared with the results of the CW100 method by Arnold et al. [Comput. Oper. Res. 107 (2019) 32–42]. The results indicate that the new modified sweep algorithm produces an initial solution with a minimum number of vehicles and with reasonable accuracy. The deviation of the output from the best-known solution (BKS) is reasonable for all the test instances. When compared with the CW100 the modified sweep provides a better initial solution than CW100 whenever the capacity of the vehicle is more and the depot is located eccentrically. The heuristic does not face any memory problems normally associated with the solving of an extremely large-scale CVRP.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021100
Keywords: Capacitated Vehicle Routing Problem, construction heuristic, modified sweep algorithm, extremely large-scale problems
@article{RO_2021__55_4_2265_0,
author = {Vangipurapu, Bapi Raju and Govada, Rambabu},
title = {A construction heuristic for finding an initial solution to a very large-scale capacitated vehicle routing problem},
journal = {RAIRO. Operations Research},
pages = {2265--2283},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {4},
doi = {10.1051/ro/2021100},
mrnumber = {4293497},
zbl = {1479.90181},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021100/}
}
TY - JOUR AU - Vangipurapu, Bapi Raju AU - Govada, Rambabu TI - A construction heuristic for finding an initial solution to a very large-scale capacitated vehicle routing problem JO - RAIRO. Operations Research PY - 2021 SP - 2265 EP - 2283 VL - 55 IS - 4 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021100/ DO - 10.1051/ro/2021100 LA - en ID - RO_2021__55_4_2265_0 ER -
%0 Journal Article %A Vangipurapu, Bapi Raju %A Govada, Rambabu %T A construction heuristic for finding an initial solution to a very large-scale capacitated vehicle routing problem %J RAIRO. Operations Research %D 2021 %P 2265-2283 %V 55 %N 4 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021100/ %R 10.1051/ro/2021100 %G en %F RO_2021__55_4_2265_0
Vangipurapu, Bapi Raju; Govada, Rambabu. A construction heuristic for finding an initial solution to a very large-scale capacitated vehicle routing problem. RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2265-2283. doi: 10.1051/ro/2021100
[1] and , What makes a VRP solution good? The generation of problem-specific knowledge for heuristics. Comput. Oper. Res. 106 (2019) 280–288. | MR | Zbl | DOI
[2] , , and , Simulation of B2C e-commerce distribution in Antwerp using cargo bikes and delivery points., Eur. Trans. Res. Rev. 10 (2018) 1–13. | DOI
[3] , and , Efficiently solving very large-scale routing problems. Comput. Oper. Res. 107 (2019) 32–42. | MR | Zbl | DOI
[4] , A tabu search algorithm for the open vehicle routing problem. Eur. J. Oper. Res. 157 (2004) 552–564. | MR | Zbl | DOI
[5] and , Scheduling of vehicles from a central depot to number of delivery points. Oper. Res. 12 (1964) 568–581. | DOI
[6] , , and , Introduction to Algorithms. MIT Press (2009). | MR | Zbl
[7] and , The truck dispatching problem. Manage. Sci. 6 (1959) 80–91. | MR | Zbl | DOI
[8] and , A robust enhancement to the Clarke-Wright savings algorithm. J. Oper. Res. Soc. 62 (2011) 223–231. | DOI
[9] and , A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Comput. Ind. Eng. 140 (2020) 106242. | DOI
[10] and , A heuristic algorithm for the vehicle dispatch problem. Oper. Res. 22 (1974) 340–349. | Zbl | DOI
[11] , and , An auction for collaborative vehicle routing: models and algorithms. EURO J. Transp. Logistics 9 (2020) 100009. | DOI
[12] , , and , An efficient variable neighborhood search heuristic for very large-scale vehicle routing problems. Comput. Oper. Res. 34 (2007) 2743–2757. | Zbl | DOI
[13] , The Vehicle Routing Problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59 (1992) 345–358. | Zbl | DOI
[14] MATLAB, version 9.0.0.341360 (R2016a). The MathWorks Inc., Natick, MA (2016).
[15] PassMark Software, Cpu benchmarks. Accessed: 2021-04-08 (2018)https://www.cpubenchmark.net/.
[16] Test data source. http://neo.lcc.uma.es/vrp/vrp-instances/.
[17] and , editors, The Vehicle Routing Problem. Siam Monographs on Discrete Mathematics and Applications, Philadelphia, Pennsylvania (2001). | MR
[18] , Comparing descent heuristics and metaheuristics for the vehicle routing problem. Comput. Oper. Res. 28 (2001) 289–315. | Zbl | DOI
[19] , and , A new heuristic for solving vehicle routing problem with capacity constraints. J. Adv. Eng. Res. 6 (2019) 64–70.
[20] , and , A new heuristic for solving open vehicle routing problem with capacity constraints. In: Innovative Product Design and Intelligent Manufacturing Systems. Springer, Singapore (2020) 897–906. | DOI
Cité par Sources :
