Home > Research > Publications & Outputs > The multi-visit drone-assisted pickup and deliv...

Electronic data

Links

Text available via DOI:

View graph of relations

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

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

The multi-visit drone-assisted pickup and delivery problem with time windows. / Meng, Shanshan; Chen, Yanru; Li, Dong.
In: European Journal of Operational Research, Vol. 314, No. 2, 16.04.2024, p. 685-702.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

Meng, S, Chen, Y & Li, D 2024, 'The multi-visit drone-assisted pickup and delivery problem with time windows', European Journal of Operational Research, vol. 314, no. 2, pp. 685-702. https://doi.org/10.1016/j.ejor.2023.10.021

APA

Meng, S., Chen, Y., & Li, D. (2024). The multi-visit drone-assisted pickup and delivery problem with time windows. European Journal of Operational Research, 314(2), 685-702. https://doi.org/10.1016/j.ejor.2023.10.021

Vancouver

Meng S, Chen Y, Li D. The multi-visit drone-assisted pickup and delivery problem with time windows. European Journal of Operational Research. 2024 Apr 16;314(2):685-702. Epub 2023 Dec 27. doi: 10.1016/j.ejor.2023.10.021

Author

Meng, Shanshan ; Chen, Yanru ; Li, Dong. / The multi-visit drone-assisted pickup and delivery problem with time windows. In: European Journal of Operational Research. 2024 ; Vol. 314, No. 2. pp. 685-702.

Bibtex

@article{c6b3902199ad4b629c74b86284c405db,
title = "The multi-visit drone-assisted pickup and delivery problem with time windows",
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{\textquoteright} 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",
author = "Shanshan Meng and Yanru Chen and Dong Li",
year = "2024",
month = apr,
day = "16",
doi = "10.1016/j.ejor.2023.10.021",
language = "English",
volume = "314",
pages = "685--702",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science B.V.",
number = "2",

}

RIS

TY - JOUR

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

AU - Meng, Shanshan

AU - Chen, Yanru

AU - Li, Dong

PY - 2024/4/16

Y1 - 2024/4/16

N2 - 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.

AB - 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.

KW - Routing

KW - Multi-visit drone routing problem

KW - Pickup and delivery

KW - Time windows

KW - Adaptive large neighbourhood search

U2 - 10.1016/j.ejor.2023.10.021

DO - 10.1016/j.ejor.2023.10.021

M3 - Journal article

VL - 314

SP - 685

EP - 702

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -