Paper Title
A Novel Framework for Optimizing the Routes of Drones During the Last Mile Delivery Process

Abstract
The growing e-commerce industry and demand for fast deliveries have led to the exploration of alternative lastmile delivery methods, including drone delivery systems. Optimising the routes for drone delivery presents a formidable challenge due to the intricate nature of the problem. This research paper introduces a novel solution that combines the Vehicle Routing Problem (VRP) and the Travelling Salesman Problem (TSP) to tackle the last-mile drone delivery issue. A mathematical model and a heuristic algorithm are devised, incorporating clustering of delivery locations, TSP routing for the truck, and VRP routing for the drones. Two approaches are employed to determine the most efficient truck-drone route. The first approach is the flying sidekick Travelling Salesman Problem (FSTSP), which employs a single drone alongside the truck. The second approach is the parallel drone scheduling Travelling Salesman Problem (PDSTSP), which involves two or more drones. Each drone can fly between its designated delivery location and the depot. In both variations, the objective is to deliver packages from a warehouse to a group of customer locations using a truck and a cluster of drones. To enhance the PDSTSP, we propose a modified approach where the truck serves as a dynamic drone depot, releasing drones at each cluster of delivery locations. The proposed solution is evaluated using real-world data, and the results demonstrate a significant optimization in terms of distance travelled and delivery time compared to traditional delivery methods. Keywords - Drone Delivery, Travelling Salesman Problem, Vehicle Routing Problem, Last Mile Delivery

Author - Archit Agarwal, Ayush Goyal, Dinesh Kumar Vishwakarma

Published : Volume-10,Issue-6  ( Jun, 2023 )

	|		PDF	|	Viewed - 13	|	Published on 2023-10-18