논문리뷰 - The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery

Abstract

Once limited to the military domain, unmanned aerial vehicles are now poised to gain widespread adoption in the commercial sector. One such application is to deploy these air-craft, also known as drones, for last-mile delivery in logistics operations. While significant research efforts are underway to improve the technology required to enable delivery by drone, less attention has been focused on the operational challenges associated with lever- aging this technology. This paper provides two mathematical programming models aimed at optimal routing and scheduling of unmanned aircraft, and delivery trucks, in this new paradigm of parcel delivery. In particular, a unique variant of the classical vehicle routing problem is introduced, motivated by a scenario in which an unmanned aerial vehicle works in collaboration with a traditional delivery truck to distribute parcels. We present mixed integer linear programming formulations for two delivery-by-drone problems, along with two simple, yet effective, heuristic solution approaches to solve problems of practical size. Solutions to these problems will facilitate the adoption of unmanned aircraft for last-mile delivery. Such a delivery system is expected to provide faster receipt of customer orders at less cost to the distributor and with reduced environmental impacts. A numerical analysis demonstrates the effectiveness of the heuristics and investigates the tradeoffs between using drones with faster flight speeds versus longer endurance.

Keywords : Unmanned aerial vehicle, Vehicle routing problem, Traveling salesman problem, Logistics,Integer programming, Heuristics

Summary

최근 물류 분야에서 드론을 활용한 배송에 관한 연구가 많이 이루어지고 있다. 특히, 드론을 통한 배송은 라스트 마일 문제를 해결하는 좋은 방안으로 제시되고 있다. 그러나 드론과 관련된 기술적 문제를 해결하기 위한 연구는 많이 이루어지는 반면 운영상의 문제를 해결하는 연구는 부족하다. 따라서 본 논문에서는 FSTSP와 PDSTSP에 대한 formulation을 제시하고 이에 대한 heuristic 방법을 제시한다.

Cite