On a pickup to delivery drone routing problem: models and algorithms

Vista sencilla de ítem
dc.contributor.authorGómez-Lagos, Javieres
dc.contributor.authorRojas-Espinoza, Benjamínes
dc.contributor.authorCandia-Véjar, Alfredoes
dc.date.accessioned2022-10-12T11:32:29Z
dc.date.available2022-10-12T11:32:29Z
dc.date.issued2022-09-06
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.en
dc.identifier.citationComputers and Industrial Engineering, Vol. 172, Part B, N° 108632 (2022)
dc.identifier.doihttps://doi.org/10.1016/j.cie.2022.108632
dc.identifier.issn0360-8352
dc.identifier.orcidhttps://orcid.org/0000-0003-2953-6522
dc.identifier.urihttp://hdl.handle.net/20.500.12254/2569
dc.language.isoenen
dc.publisherElsevieres
dc.subject.otherPickup and Delivery Problemen
dc.subject.otherNetwork optimizationen
dc.subject.otherMixed integer linear programmingen
dc.subject.otherDrone Routing Problemen
dc.subject.otherGRASPen
dc.titleOn a pickup to delivery drone routing problem: models and algorithmsen
dc.typeArtículoes
Archivos
Bloque original
Mostrando 1 - 1 de 1
Miniatura
Nombre:
On a pickup to delivery drone routing problem models and algorithms Resumen-1.pdf
Tamaño:
380.91 KB
Formato:
Adobe Portable Document Format
Descripción:
Texto completo
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
638 B
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar
Colecciones
Artículos de Revistas