Intergrated Traveling Salesman Problem of Multiple Trucks, and Multiple Drones Constrained By DROP-PICKUP

Abstract

Over the past few years, with an effort to provide high responsiveness, faster and more cost-efficient delivery for goods ordered online, companies are looking for new innovation technologies to across last-mile to their customers. The earlier papers research the collaborative of a fleet of trucks and a fleet of drones, which is called Traveling Salesman Problem with Drone (TSP-D), aims to adapt the demand. This study extends the problem by considering two different types of drone tasks: drop and pickup. After a drone complete a drop, the drone can fly directly to next customer to pick up the returned parcel. Two approaches are proposed to solve the problem. The first algorithm is k-Means Clustering converts hundreds of customers into cluster, or known as initial TSP solution. Then the optimal TSP solution is converted to a feasible TSP-D by local search. The second algorithm, a Greedy Randomized Adaptive Search Procedure (GRASP), generates TSP-D solution from TSP solution and continuously improve the solution through local search. The experiments show this concept are possible applied comparison to traditional truck delivery. Keywords: Traveling Salesman Problem with Drone, GRASP, Unmanned aerial vehicle, Vehicle routing problem, k-Means Clustering