Loughborough University
Browse

File(s) under embargo

Reason: Publisher requirement.

2

month(s)

21

day(s)

until file(s) become available

The multi-visit drone routing problem for pickup and delivery services

journal contribution
posted on 2022-12-19, 10:20 authored by Shanshan MengShanshan Meng, Xiuping Guo, Dong Li, Guoquan Liu

Unmanned aerial vehicles, commonly known as drones, have gained wide attention in recent years due to their potential of revolutionizing logistics and transportation. In this paper, we consider a variant of the combined truck-drone routing problem, which allows drones to serve multiple customers and provide both pickup and delivery services in each flight. The problem concerns the deployment and routing of a fleet of trucks, each equipped with a supporting drone, to serve all the pickup and delivery demands of a set of customers with minimal total cost. We explicitly model the energy consumption of drones by their travel distance, curb weight and the carrying weight of parcels, develop a mixed-integer linear programming model (MILP) with problem-customized inequalities, and show a sufficient condition for the benefit of the combined truck-drone mode over the truck-only mode. Considering the complexity of the MILP model, we propose a novel two-stage heuristic algorithm in which a maximum payload method is developed to construct the initial solutions, followed by an improved simulated annealing algorithm with problem-specific neighborhood operators and tailored acceleration strategies. Furthermore, two methods are developed to test the feasibility for both trucks and drones in each solution. The proposed algorithm outperforms two benchmark heuristics in our numerical experiments, which also demonstrate the considerable benefit of allowing multiple visits and both pickup and delivery operations in each drone flight.

Funding

Open Foundation of State Key Laboratory of Networking and Switching Technology of China [Grant SKLNST-2021-2-01]

Service Science and Innovation Key Laboratory of Sichuan Province of China [Grant KL2106]

History

School

  • Business and Economics

Department

  • Business

Published in

Transportation Research Part E: Logistics and Transportation Review

Volume

169

Publisher

Elsevier

Version

  • AM (Accepted Manuscript)

Rights holder

© Elsevier

Publisher statement

This paper was accepted for publication in the journal Transportation Research Part E: Logistics and Transportation Review published by Elsevier. The final publication is available at https://doi.org/10.1016/j.tre.2022.102990. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/

Acceptance date

2022-12-05

Publication date

2022-12-21

Copyright date

2022

ISSN

1366-5545

Language

  • en

Depositor

Dr Dong Li. Deposit date: 16 December 2022

Article number

102990