ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ КОМБИНИРОВАННОГО ИЕРАРХИЧЕСКОГО ОПЕРАТОРА СКРЕЩИВАНИЯ В ГЕНЕТИЧЕСКОМ АЛГОРИТМЕ РЕШЕНИЯ ЗАДАЧИ ДОСТАВКИ ПОСЛЕДНЕЙ МИЛИ
- Авторы: Соседов В.А1
-
Учреждения:
- Институт проблем управления им. В. А. Трапезникова РАН
- Выпуск: № 1 (2024)
- Страницы: 23-34
- Раздел: Математические проблемы управления
- URL: https://journals.rcsi.science/1819-3161/article/view/264566
- DOI: https://doi.org/10.25728/pu.2024.1.3
- ID: 264566
Цитировать
Полный текст
Аннотация
Рассматривается задача планирования маршрутов группы беспилотных летательных аппаратов в составе перспективной системы доставки последней мили, формализованная в виде двухкритериальной NP-трудной задачи многих коммивояжеров с одним депо. Применение стандартных методов оптимизации для получения точного решения неэффективно с точки зрения временны́х затрат на их реализацию, и в условиях реальной системы становится необходимым применение эвристических алгоритмов поиска приближенного решения. Для решения поставленной задачи был применен элитарный генетический алгоритм недоминирующей сортировки NSGA-II, хорошо зарекомендовавший себя в случае многокритериальной оптимизации. Для исследования эффективности применения комбинированного иерархического оператора скрещивания в сравнении со стандартными операторами скрещивания было реализовано программное средство имитационного моделирования и был проведен сравнительный анализ результатов применения различных операторов скрещивания в составе генетического алгоритма.
Список литературы
- 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.]
Дополнительные файлы
