On a Pickup to Delivery Drone Routing Problem: Models and algorithms
Date
2022-09-06
item.contributor.advisor
item.page.orcidurl
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
item.page.isbn
item.page.issn
0360-8352
item.page.issne
item.page.doiurl
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.
Description
item.page.coverage.spatial
item.page.sponsorship
The 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.
Citation
Gó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.