Drone-based delivery: a concurrent heuristic approach using a genetic algorithm

Abstract

Purpose

The purpose of this study is to solve NP-Hard drone routing problem for the last-mile distribution. This is suitable for the multi-drones parcel delivery for the various items from a warehouse to many locations.

Design/methodology/approach

This study conducts as a mission assignment of the single location per flight with the constraint satisfactions such as various payloads in weight, drone speeds, flight times and coverage distances. A genetic algorithm is modified as the concurrent heuristics approach (GCH), which has the knapsack problem dealing initialization, gene elitism (crossover) and gene replacement (mutation). Those proposed operators can reduce the execution time consuming and enhance the routing assignment of multiple drones. The evaluation value of the routing assignment can be calculated from the chromosome/individual representation by applying the proposed concurrent fitness.

Findings

This study optimizes the total traveling time to accomplish the distribution. GCH is flexible and can provide a result according to the first-come-first-served, demanded weight or distance priority.

Originality/value

GCH is an alternative option, which differs from conventional vehicle routing researches. Such researches (traveling time optimization) attempt to minimize the total traveling time, distance or the number of vehicles by assuming all vehicles have the same traveling speed; therefore, a specific vehicle assignment to a location is neglected. Moreover, the main drawback is those concepts can lead the repeated selection of best quality vehicles concerning the speed without considering the vehicle fleet size and coverage distance while this study defines the various speeds for the vehicles. Unlike those, the concurrent concept ensures a faster delivery accomplishment by sharing the work load with all participant vehicles concerning to their different capabilities. If the concurrent assignment is applied to the drone delivery effectively, the entire delivery can be accomplished relatively faster than the traveling time optimization.

Citation

Thida San, K. and Chang, Y.S. (2022), "Drone-based delivery: a concurrent heuristic approach using a genetic algorithm", Aircraft Engineering and Aerospace Technology, Vol. 94 No. 8, pp. 1312-1326. https://doi.org/10.1108/AEAT-07-2020-0138