COMBINED HIERARCHICAL CROSSOVER IN A GENETIC ALGORITHM FOR LAST-MILE DELIVERY: EFFICIENCY ANALYSIS

Cover Page

Cite item

Full Text

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.

About the authors

V. A Sosedov

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

References

  1. 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.]
  2. 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.
  3. 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.
  4. Германчук М.С., Лемтюжникова Д.В., Лукьяненко В.А. Метаэвристические алгоритмы для задач многоагентных задач маршрутизации // Проблемы управления. – 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)]
  5. Bektas, T. The multiple traveling salesman problem: an overview of formulations and solution procedures // Omega. – 2006. – Vol. 34, no. 3. – P. 209–219.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. Саймон Д. Алгоритмы эволюционной оптимизации. – М.: ДМК Пресс, 2020. – 1002 с. [Simon, D. Evolutionary Optimization Algorithms. – New York: John Wiley & Sons, 2013. – 784 p.]
  11. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. 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)]
  12. 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.
  13. 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.
  14. 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.
  15. 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).
  16. 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.]
  17. 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.]

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).