Integrated Scheduling Of Multiple Trucks, Multiple Drones Constrained By Time Window And Drop-Pick Up.

Abstract

Over the past few years, the recent advancements in unmanned aerial vehicles technology, known as drones, has recently risen in the emergence of e-commerce in retail store. 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 to adapt the demand in industry. The new variant of the Traveling Salesman Problem, called TSP with Drone (TSP-D), aims to minimize the times at which truck and drone finish the service. 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.