Optimal routing and scheduling of unmanned aerial vehicles for delivery services

ABSTRACT

In the logistics industry, unmanned aerial vehicles (UAVs) are mostly used for last-mile delivery, in combination with other types of vehicles. There is currently no operator in Taiwan that is completely reliant upon the usage of UAVs for cargo delivery services. Therefore, this study proposes a routing and scheduling model for UAVs by utilizing the network flow technique and mathematical programming methods. All advance requests must be satisfied, and the related operating constraints ensured in the model. The model aims to minimize the total operating cost. To effectively solve large problems that may occur in practice, this study develops a relax-and-fix heuristic. Numerical tests are conducted to preliminarily examine whether the model, coupled with the heuristic algorithm, could be applied in practice. The test results indicate that the proposed model and solution algorithm are effective and thus could be useful for UAV operators to perform delivery routing and scheduling.

KEYWORDS:

• UAV (Unmanned Aerial Vehicle)
• advanced request
• delivery routing and scheduling
• network
• relax-and-fix heuristic

Acknowledgments

This study was supported by National Science and Technology Council, Taiwan under grant NSTC-110-2221-E-008-025-MY3. The authors are grateful to the UAV company for providing the test data and valuable opinions. The authors also extend their gratitude to the three anonymous reviewers for their valuable comments and suggestions, which have greatly contributed to improving the presentation of the paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The work was supported by the National Science and Technology Council, Taiwan [MOST-110-2221-E-008-025-MY3].