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

dc.contributor.authorGómez-Lagos, Javier
dc.contributor.authorRojas-Espinoza, Benjamín
dc.contributor.authorCandia-Véjar, Alfredo
dc.description.abstractA 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.es
dc.description.sponsorshipThe authors thank Prof. Tolga Bektas for his helpful comments, and also the Area Editor and the two anonymous reviewers whose suggestions have improved the quality of this article. The work of Javier Gómez-Lagos was supported in part by the Chilean Agency of Research and Development (ANID) under Ph.D. Grant 21191364.es
dc.identifier.citationGómez-Lagos, J., Rojas-Espinoza, B., & Candia-Véjar, A. (2022). On a Pickup to Delivery Drone Routing Problem: Models and algorithms. Computers & Industrial Engineering, 108632.es
dc.relation.ispartofseriesComputers and Industrial Engineering;172 (2022)
dc.subject.otherPickup and Delivery Problemes
dc.subject.otherNetwork optimizationes
dc.subject.otherMixed integer linear programminges
dc.subject.otherDrone Routing Problemes
dc.titleOn a Pickup to Delivery Drone Routing Problem: Models and algorithmses
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
On a pickup to delivery drone routing problem models and algorithms Resumen-1.pdf
380.91 KB
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
638 B
Item-specific license agreed upon to submission