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

Мұқаба

Дәйексөз келтіру

Толық мәтін

Аннотация

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.

Авторлар туралы

V. Sosedov

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Әдебиет тізімі

  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.]

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу


Creative Commons License
Бұл мақала лицензия бойынша қолжетімді Creative Commons Attribution 4.0 International License.

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

 

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