The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery

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 aircraft, 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 leveraging 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. The authors 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.

• Record URL:
  • https://doi.org/10.1016/j.trc.2015.03.005
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S0968090X15000844
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/0968090X
• Supplemental Notes:
  • Abstract reprinted with permission of Elsevier.
• Authors:
  • Murray, Chase C
  • Chu, Amanda G
• Publication Date: 2015-5

Language

• English

Media Info

• Media Type: Digital/other
• Features: Appendices; Figures; Photos; References; Tables;
• Pagination: pp 86-109
• Serial:
  • Transportation Research Part C: Emerging Technologies
  • Volume: 54
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0968-090X
  • Serial URL: http://www.sciencedirect.com/science/journal/0968090X

Subject/Index Terms

• TRT Terms: Delivery service; Drones; Heuristic methods; Logistics; Optimization; Routing; Traveling salesman problem
• Uncontrolled Terms: Last mile
• Subject Areas: Aviation; Freight Transportation; Operations and Traffic Management; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01560570
• Record Type: Publication
• Files: TRIS
• Created Date: Apr 17 2015 1:56PM