Genetic algorithm for scheduling of parcel delivery by drones

• HAZAMA Yohei

  Kyoto Institute of Technology

• IIMA Hitoshi

  Kyoto Institute of Technology

• KARUNO Yoshiyuki

  Kyoto Institute of Technology

• MISHIMA Kosuke

  Kyoto Institute of Technology

抄録

In recent years, efficient logistics has become indispensable, and using unmanned aerial vehicles (UAVs) or drones is promising for considerably reducing the cost and time required for parcel delivery. This paper addresses a parcel delivery scheduling problem. In this problem, a truck loaded with drones and parcels leaves a distribution center and stops at some points on a fixed route. At each point, the drones take off and deliver parcels to customers. We define this problem as finding the assignment of customers to both the drones and their takeoff points. Then, we propose a genetic algorithm (GA) for finding a near-optimal solution in a short time. In the proposed GA, a solution is represented using sets of customers assigned to the takeoff points, and a heuristic rule determines the assignment to the drones. The crossover operation enables offspring to inherit the customer sets. Experimental results show that the proposed GA can successfully find an optimal or a near-optimal solution faster than an integer programming solver for almost all instances. In addition, it significantly outperforms other GAs using a different crossover.

収録刊行物

• Journal of Advanced Mechanical Design, Systems, and Manufacturing

  Journal of Advanced Mechanical Design, Systems, and Manufacturing 15 (6), JAMDSM0069-JAMDSM0069, 2021

  一般社団法人 日本機械学会

キーワード

• Engineering optimization
• Scheduling
• Delivery
• Genetic algorithm
• Grouping

詳細情報

• CRID: 1390571194130416896
• NII論文ID: 130008104555
• DOI: 10.1299/jamdsm.2021jamdsm0069
• ISSN: 18813054
• Web Site: https://www.jstage.jst.go.jp/article/jamdsm/15/6/15_2021jamdsm0069/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可