Volume 55, Number 4, July-August 2021
|Page(s)||2265 - 2283|
|Published online||02 August 2021|
A construction heuristic for finding an initial solution to a very large-scale capacitated vehicle routing problem
Department of Mechanical Engineering, Velagapudi Ramakrishna Siddhartha Engineering College, Vijayawada 520007, India.
2 Department of Mechanical Engineering, Andhra University, Visakhapatnam 530003, India.
* Corresponding author: firstname.lastname@example.org
Accepted: 6 July 2021
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.
Mathematics Subject Classification: 90C27 / 90C59 / 90B06 / 68T20
Key words: Capacitated Vehicle Routing Problem / construction heuristic / modified sweep algorithm / extremely large-scale problems
© The authors. Published by EDP Sciences, ROADEF, SMAI 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.