On a Pickup to Delivery Drone Routing Problem: Models and algorithms

Abstract

A new variant of the Pickup and Delivery Routing problem is presented. Given a set of customers, facilities, a depot, and a homogeneous fleet of drones, the Pickup to Delivery Drone Routing Problem (PDDRP) aims to find a drone scheduling such that a drone serves the customer’s order from a set of available facilities. Each drone starts in the depot, flies to pickup the customer’s order in a facility, and continues its flight to deliver the parcel to a customer. Then, the drone begins another service, and once its last service is completed, it returns to the depot. The objective is to minimize the makespan associated with the drone fleet. The layer of facilities forcing drones to visit one of them to pickup the parcel makes the problem different from traditional pickup and delivery routing problems. Three mixed-linear programming models are presented to obtain optimal solutions for the problem. The first model is related to the multiple Traveling Salesman Problem (m-TSP), the second is associated with the Parallel Machine Scheduling Problem (PMS), and the third was developed specifically for the new problem. Given the high computational complexity of the PDDRP, a Greedy Randomized Adaptive Search Procedure (GRASP) was designed to find near-optimal solutions when exact approaches cannot achieve (near) optimal solutions. Computational experiments show that a commercial solver could solve only small problem instances. GRASP can find reasonable solutions in a short time when medium and large instance sizes need to be solved. Finally, is shown that some routing problems for delivery, allowing truck-drone collaboration, could be formulated as an extension of PMS.