The multi-visit drone-assisted routing problem with soft time windows and stochastic truck travel times

Shanshan Meng, Dong Li, Jiyin Liu and Yanru Chen

Transportation Research Part B: Methodological, 2024, vol. 190, issue C

Abstract: We consider a combined truck-drone delivery problem with stochastic truck travel times and soft time windows. A fleet of homogeneous trucks and drones are deployed in pairs to provide delivery services to customers. Each drone can be launched from and retrieved to its truck multiple times, and in each flight, a drone can serve one or more customers. Our objective is to determine the truck routes and drone flights that minimise the total cost, including time window violation penalties. We formulate this problem into a two-stage stochastic model with recourse action in the second stage to optimise the truck waiting time at each node. We approximate the stochastic model with a large-scale mixed-integer program using the sample average approximation (SAA) framework, which is computationally intractable. To this end, we propose a hybrid metaheuristic approach that incorporates SAA. The waiting times of each truck obtained in the planning phase are optimal against the sampled or estimated travel times along the entire route, but the actual values are known only once the truck has returned to the depot. To this end, we reformulate the second-stage model in a rolling-horizon manner, which can be easily implemented and efficiently solved in the execution phase. Extensive numerical experiments demonstrate the strong performance of the proposed metaheuristic approach and rolling-horizon model. The results also highlight the clear benefits of the stochastic modelling approach over its deterministic counterpart, with a pronounced reduction in the total cost in various scenarios.

Keywords: Multi-visit drone routing; Two-stage stochastic model; Soft time windows; Stochastic truck travel times; Hybrid metaheuristic (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/S019126152400225X
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:transb:v:190:y:2024:i:c:s019126152400225x

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2024.103101

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().