Truck and rotary-wing drone routing problem considering flight-level selection

Abstract

Last-mile logistics is one of the most promising areas for rotary-wing drone (RWD) applications. In the literature, routing variants that use drones in collaboration with trucks assume that both drones and trucks move along arcs in two-dimensional networks. There is a need for methodological innovations to cater to more practical and general scenarios involving flight-level decisions of RWDs in the three-dimensional network. In this study, flight level is defined as the specified height at which an RWD is allowed to fly. We introduce the truck and RWD routing problem considering flight-level selection and time windows (TDRP-FT). The TDRP-FT is characterized by RWD flight-level selection, time windows, direct delivery, multiple trucks, and multiple RWDs carried by each truck. We develop a mixed-integer linear programming model and propose a hybrid algorithm based on a greedy randomized adaptive search procedure and an adaptive large neighborhood search. We experimentally evaluate the effectiveness of the TDRP-FT model and the applicability of the hybrid algorithm to small-, medium- and large-scale instances. The computational experiment results indicate that the TDRP-FT model can be used to determine how flight levels of RWDs should be selected.

Keywords:

• Vehicle routing
• truck and rotary-wing drone
• flight level
• time window
• integer programming
• heuristics

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by Research Grants from the National Natural Science Foundation of China (grant numbers 71972007).