Abstract. This paper considers routing for a group of unmanned aerial vehicles within a promising last-mile delivery system. The routing problem is reduced to the bi-criteria single-depot multiple traveling salesman problem and formalized using a directed graph. Being NP-hard, this problem cannot be efficiently solved by standard exact optimization methods. Therefore, heuristic algorithms should be applied to obtain good approximate solutions in a short time. The problem is solved using NSGA-II, the widespread elitist non-dominated sorting genetic algorithm that demonstrates good results in multicriteria optimization. Some chromosome representation and crossing and mutation operators are implemented in the algorithm. A simulation software tool is presented to investigate the influence of the crossing operators used on the convergence speed of the algorithm. Finally, several genetic crossing operators (Partially-Mapped Crossover, Order Crossover, Cycle Crossover, and Combined Hierarchical Crossover) are compared in terms of efficiency.
Keywords: last-mile delivery, multiple traveling salesman problem, multicriteria optimization, genetic algorithm, crossover.
PDF (English)
Cite this paper
Sosedov, V.A., Combined Hierarchical Crossover in a Genetic Algorithm for Last-Mile Delivery: Efficiency Analysis. Control Sciences 1, 18–27 (2024). http://doi.org/10.25728/cs.2024.1.3
PDF (Russian)
Combined Hierarchical Crossover in a Genetic Algorithm for Last-Mile Delivery: Efficiency Analysis