Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm

Shan Huen Huang, Ying Hua Huang, Carola A. Blazquez, Chia Yi Chen

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

E-commerce and logistics companies are facing important challenges to satisfy the rapid growth of customer demands. Unmanned aerial vehicles such as drones are an emerging technology that are very useful to cope with rising customer expectations of fast, flexible, and reliable delivery services. Drones work in tandem with trucks to perform parcel delivery, which have proven to reduce costs, CO2 emissions, and delivery times. This research proposes a mixed integer programming formulation to address the Vehicle Routing Problem with Drone (VRPD) by assigning customers to drone-truck pairs, determining the number of dispatching drone-truck units, and obtaining optimal service routes while the fixed and travel costs of both vehicles are minimized. Given the NP-hard nature of the VRPD, an ant colony optimization (ACO) algorithm is elaborated to solve this problem. Two novel methods are proposed to investigate the efficiency of the drone-truck combination by allowing the drones to perform additional delivery services to only one feasible customer and also multiple feasible customers while the truck waits at a customer location. Experimental results show that the proposed ACO algorithm can effectively solve the VRDP for different size instances and different customer location distributions, and is successful in providing timely solutions for small test instances within 1% of the optimal solutions. Finally, experimentation also reveals that the ACO algorithm outperforms the classical VRP by obtaining cost-savings of over 30% for large instances.

Original languageEnglish
Article number101536
JournalAdvanced Engineering Informatics
Volume51
DOIs
Publication statusPublished - Jan 2022

Keywords

  • Heuristic
  • Optimization
  • Unmanned aerial vehicle
  • Urban delivery
  • Vehicle routing problem

ASJC Scopus subject areas

  • Information Systems
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm'. Together they form a unique fingerprint.

Cite this