COMBINED HIERARCHICAL CROSSOVER IN A GENETIC ALGORITHM FOR LAST-MILE DELIVERY: EFFICIENCY ANALYSIS
- 作者: Sosedov V.A1
-
隶属关系:
- Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
- 期: 编号 1 (2024)
- 页面: 23-34
- 栏目: Mathematical Problems of Control
- URL: https://journals.rcsi.science/1819-3161/article/view/264566
- DOI: https://doi.org/10.25728/pu.2024.1.3
- ID: 264566
如何引用文章
全文:
详细
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.
参考
- Baur, S. Cargo drones: A potential gamechanger in the logistics industry // Roland Berger. – 2022. – URL: https://www.rolandberger.com/en/Insights/Publications/Cargo-drones-A-potential-gamechanger-in-the-logistics-industry.html (дата обращения: 23.09.2023). [Accessed September 23, 2023.]
- Moadab, A., Farajzadeh, F., Fatahi Valilai, O. Drone routing problem model for last-mile delivery using the public transportation capacity as moving charging stations // Scientific Reports. – 2022. – Vol. 12, no. 1. – P. 1–16.
- Khoufi, I., Laouiti, A., Adjih, C. A Survey of Recent Extended Variants of the Traveling Salesman and Vehicle Routing Problems for Unmanned Aerial Vehicles // Drones. – 2019. – Vol. 3, no. 3. – Art. no. 66.
- Германчук М.С., Лемтюжникова Д.В., Лукьяненко В.А. Метаэвристические алгоритмы для задач многоагентных задач маршрутизации // Проблемы управления. – 2020. – № 6. – С. 3–13. [Germanchuk, M.S., Lemtyuzhnikova, D.V., Lukianenko, V.A. Metaheuristic Algorithms for Multi-Agent Routing Problems // Control Sciences. – 2020. – No. 6. – P. 3–13. (In Russian)]
- Bektas, T. The multiple traveling salesman problem: an overview of formulations and solution procedures // Omega. – 2006. – Vol. 34, no. 3. – P. 209–219.
- Necula, R., Breaban, M., Raschip, M. Tackling the bi-criteria facet of multiple traveling salesman problem with ant colony systems // IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI). – Vietri sul Mare, 2015. – P. 873–880.
- Bolanos, R., Echeverry, M., Escobar, J. A multiobjective non-dominated sorting genetic algorithm (NSGA-II) for the Multiple Travelling Salesman Problem // Decision Science Letters. – 2015. – Vol. 4. – P. 559–568.
- Alves, R.M.F., Lopes, C.R. Using Genetic Algorithms to minimize the distance and balance the routes for the multiple Travelling Salesman Problem // IEEE Congress on Evolutionary Computation (CEC). – Sendai, 2015. – P. 3171–3178.
- Carter, A.E., Ragsdale, C. A new approach to solving the multiple traveling salesperson problem using genetic algorithms // European Journal of Operational Research. – 2005. – Vol. 175, no. 1. – P. 246–257.
- Саймон Д. Алгоритмы эволюционной оптимизации. – М.: ДМК Пресс, 2020. – 1002 с. [Simon, D. Evolutionary Optimization Algorithms. – New York: John Wiley & Sons, 2013. – 784 p.]
- Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. 2-е изд., испр. и доп. – М.: ФИЗМАТЛИТ, 2010. – 368 с. [Gladkov L.A., Kureichik V.V., Kureichik V.M. Geneticheskie algoritmy. 2-e izd., ispr. i dop. – M.: FIZMATLIT, 2010. – 368 s. (In Russian)]
- Shuaia, Y., Yunfengaand, S., Kai, Z. An effective method for solving multiple travelling salesman problem based on NSGA-II // Systems Science & Control Engineering. – 2019. – Vol. 7, no. 2. – P. 108–116.
- Soni, N., Kumar, T. Study of Various Mutation Operators in Genetic Algorithms // International Journal of Computer Science and Information Technologies. – 2014. – Vol. 5, no. 3. – P. 4519–4521.
- Deb, K., Pratap, A., Agarwal, S., Meyarivan, T. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II // IEEE Transactions on Evolutionary Computation. – 2002. – Vol. 6, no. 2. – P. 182–197.
- Benchmark data for the Single-Depot Multiple Traveling Salesman Problem (multiple-TSP). – Iaşi: Alexandru Ioan Cuza University (UAIC). – URL: https://profs.info.uaic.ro/~mtsplib/ (дата обращения: 23.09.2023).
- TSPLIB. Symmetric Traveling Salesman Problem (TSP). – Heidelberg: University of Heidelberg. – URL: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/ (дата обращения: 23.09.2023). [Accessed September 23, 2023.]
- TSPLIB. – Capacitated Vehicle Routing Problem (CVRP). Heidelberg: University of Heidelberg. – URL: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/vpr (дата обращения: 23.09.2023). [Accessed September 23, 2023.]
补充文件
