A competitive heuristic algorithm for vehicle routing problems with drones

Xuan Ren, Aurélien Froger, Ola Jabali and Gongqian Liang

European Journal of Operational Research, 2024, vol. 318, issue 2, 469-485

Abstract: We propose a heuristic algorithm capable of handling multiple variants of the vehicle routing problem with drones (VRPD). Assuming that the drone may be launched from a node and recovered at another, these variants are characterized by three axes, (1) minimizing the transportation cost or minimizing the makespan, (2) the drone is either allowed or not allowed to land while awaiting recovery, and (3) single or multiple trucks each equipped with a drone. In our algorithm, we represent a VRPD solution as a set of customer sequences and evaluate it via local search procedures solving for each sequence a problem that we refer to as the fixed route drone dispatch problem (FRDDP). Given a sequence of customers to be served by a single truck and its drone, the FRDDP selects a subset of customers to be served by the drone and determines drone launch and recovery nodes, while ensuring that each such customer is positioned between two nodes in the initial sequence. We introduce a heuristic dynamic program (HDP) to solve the FRDDP with reduced computational complexity compared to an exact solution algorithm for the problem. We reinforce our algorithm by developing filtering strategies based on the HDP. We benchmark the performance of our algorithm on nine benchmark sets pertaining to four VRPD variants resulting in 932 instances. Our algorithm computes 651 of 680 optimal solutions and identifies 189 new best-known solutions.

Keywords: Routing; Heuristics; Drones; Dynamic programming; Variable neighborhood search (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724003904
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:318:y:2024:i:2:p:469-485

DOI: 10.1016/j.ejor.2024.05.031

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().