Труды КНЦ (Технические науки вып. 3/2024(15))

Труды Кольского научного центра РАН. Серия: Технические науки. 2024. Т. 15, № 3. С. 61-68. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2024. Vol. 15, No. 3. P. 61-68. Научная статья УДК 004.832 doi:10.37614/2949.1215.2024.15.3.005 РЕШЕНИЕ ЗАДАЧ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ В РАМКАХ ПАРАДИГМЫ ПРОГРАММИРОВАНИЯ В ОГРАНИЧЕНИЯХ Алексей Владимирович Шестаковш , Александр Анатольевич Зуенко 2 12Институт информатики и математического моделирования имени В. А. Путилова Кольского научного центра Российской академии наук, Апатиты, Россия 1a.shestakov@ksc.ruB, https://orcid. org/0000-0002-9052-2579 2a.zuenko@ksc.ruB, https://orcid.org/ 0000-0002-7165-6651 Аннотация Статья посвящена аналитическому обзору возможностей решения задач маршрутизации транспортных средств в рамках парадигмы программирования в ограничениях. Сначала в статье приводится обзор различных постановок задачи маршрутизации транспортных средств. Затем данные постановки, для облегчения понимания, формулируются на языке целочисленного линейного программирования. После чего дается описание технологии программирования в ограничениях и приводятся типовые глобальные ограничения, полезные в различных постановках задачи маршрутизации транспортных средств. Сделан вывод о том, что гибкость в формулировке ограничений, возможность интеграции с другими методами оптимизации, а также способность учитывать неопределенности делают программирование в ограничениях одним из наиболее востребованных средств для решения задач маршрутизации. Ключевые слова: программирование в ограничениях, задача удовлетворения ограничений, задача маршрутизации транспортных средств Финансирование: работа выполнена в рамках НИР «Разработка теоретических и организационно-технических основ информационной поддержки управления жизнеспособностью региональных критических инфраструктур Арктической зоны Российской Федерации» (регистрационный номер 122022800547-3). Для цитирования: Шестаков А. В., Зуенко А. А. решение задач маршрутизации транспортных средств в рамках парадигмы программирования в ограничениях // Труды Кольского научного центра РАН. Серия: Технические науки. 2024. Т. 15, № 3. С. 61-68. doi: 10.37614/2949.1215.2024.15.3.005. Original article SOLVING VEHICLE ROUTING PROBLEMS IN THE FRAMEWORK OF THE CONSTRAINT PROGRAMMING PARADIGM Aleksey V. Shestakov1B, Alexander A. Zuenko 2 1Putilov Institute for Informatics and Mathematical Modeling o f the Kola Science Centre o f the Russian Academy o f Sciences, Apatity, Russia 1a.shestakov@ksc.ruB, https://orcid. org/0000-0002-9052-2579 2a.zuenko@ksc.ruB, https://orcid.org/ 0000-0002-7165-6651 Abstract The article is devoted to an analytical survey of the possibilities of solving vehicle routing problems within the framework of the constraint programming paradigm. First, the article provides an overview of the various formulations of the vehicle routing problem. Then, to facilitate understanding, these statements are formulated in the language of integer linear programming. After that, a description of the constraint programming technology is given and typical global constraints are given that are useful in various formulations of the vehicle routing problem. It is concluded that flexibility in the formulation of constraints, the possibility of integration with other optimization methods, as well as the ability to take into account uncertainties make programming in constraints one of the most popular tools for solving vehicle routing problems. Keywords: Constraint programming, constraint satisfaction problem, vehicle routing problem © Шестаков А. В., Зуенко А. А., 2024 61