Rights statement: For the purpose of open access, the author(s) has applied a Creative Commons attribution (CC BY) licence to any Author Accepted Manuscript version arising.
Accepted author manuscript, 17.5 MB, PDF document
Available under license: CC BY: Creative Commons Attribution 4.0 International License
Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
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 -