The multi-visit drone-assisted pickup and delivery problem with time windows

Shanshan Meng, Yanru Chen and Dong Li

European Journal of Operational Research, 2024, vol. 314, issue 2, 685-702

Abstract: We consider a new combined truck–drone routing problem with time windows in the context of last-mile logistics. A fleet of trucks, each equipped with an identical drone, is scheduled to provide both pickup and delivery services to a set of customers with minimum cost. Some customers are paired, in that the goods picked up from one must be delivered to the other on the same route. Drones are launched from and retrieved by trucks at a pool of designated stations, which can be used multiple times. Each drone can serve multiple customers in one flight. We formulate this problem as a large-scale mixed-integer bilinear program, with the bilinear terms used to calculate the load-time-dependent energy consumption of drones. To accelerate the solution process, multiple valid inequalities are proposed. For large-size problems, we develop a customised adaptive large neighbourhood search (ALNS) algorithm, which includes several preprocessing procedures to quickly identify infeasible solutions and accelerate the search process. Moreover, two feasibility test methods are developed for trucks and drones, along with an efficient algorithm to determine vehicles’ optimal waiting time at launch stations, which is important to consider due to the time windows. Extensive numerical experiments demonstrate the effectiveness of the valid inequalities and the strong performance of the proposed ALNS algorithm over two benchmarks in the literature, and highlight the cost-savings of the combined mode over the truck-only mode and the benefits of allowing multiple drone visits.

Keywords: Routing; Multi-visit drone routing problem; Pickup and delivery; Time windows; Adaptive large neighbourhood search (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723007968
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:314:y:2024:i:2:p:685-702

DOI: 10.1016/j.ejor.2023.10.021

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 ().