ABSTRACT
In this paper, we consider the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is used to model many real-world applications, especially in the area of supplying humanitarian aid after a natural disaster. Interestingly, in this study, Unmanned Aerial Vehicles (UAVs) so-called drones are used to assist the trucks in delivering parcels to customers. Each of them travels to different locations to perform specified tasks and meet periodically with the vehicle from which it takes off to swap its battery. In this paper, a mathematical model is formulated which is then tested with small-sized problems using CPLEX software. Due to the difficulty of solving large instances to optimality, we propose a heuristic algorithm based on a well-established type of cluster-first, route-second approach. Then, it is enhanced by some proposed properties. Hereafter, we develop a minimum spanning tree based-lower bound. Finally, extensive computational experiments are carried out by using instances from the literature. They show the good performance of the proposed heuristic algorithm to solve large instances in a very competitive running time.
Disclosure statement
No potential conflict of interest was reported by the author(s).
Data availability statement
The dataset is available from the corresponding author on reasonable request.
Additional information
Notes on contributors
Imen Hamdi
Imen Hamdi is currently an Assistant Professor at the High Institute of Transport and Logistics,University of Sousse, Sousse, TUNISIA. She obtained her PhD Thesis with high mention in 2015 from the University of Sfax,Sfax, TUNISIA. Her research interests include production scheduling, combinatorial optimization, cross-docking scheduling, supply chain management, and vehicle routing problem.