Валерий Иванович Хабаров – доктор технических наук, профессор, академик Российской академии транспорта, декан факультета «Бизнес-информатика», заведующий кафедрой «Информационные технологии на транспорте», профессор кафедры теоретической и прикладной информатики
Новосибирск
Valery I. Khabarov – Doctor of Engineering, Professor, Academician of Russian Academy of Transport, Dean of the Information Technology in Business Faculty, Head of the Information Technologies in Transport Department, Professor of the Theoretical and Applied Information Science Department
Novosibirsk
Владислав Евгеньевич Квашнин – аспирант кафедры «Информационные технологии на транспорте»
Новосибирск
Vladislav E. Kvashnin – Postgraduate of the Information Technologies in Transport Department
Novosibirsk
В данной работе исследуются современные проблемы городской логистики, связанные с необходимостью адаптации маршрутов различных транспортных средств к изменяющимся условиям городской среды. Основное внимание уделяется задаче многих коммивояжеров (MTSP), которая формализована в мультиагентной постановке (MATSP) с обязательным посещением выделенных точек погрузки/разгрузки, поскольку задача в таком контексте позволяет рассматривать сценарии, приближенные к типичным для систем городского распределения. В статье анализируются различные методы решения: эволюционные алгоритмы, алгоритмы роевого интеллекта (пчелиного роя и муравьиной колонии) и алгоритм имитации отжига. В рамках проведенного исследования сформулирована математическая модель задачи MATSP, позволяющая определить основные ограничения, а также целевую функцию, подвергаемую оптимизации. Далее проведены сравнительные вычислительные эксперименты для задачи нескольких коммивояжеров с точками вывоза для определения оценки эффективности на тестовых наборах данных с выделенными областями обслуживания. Данные эксперименты позволяют наглядным образом выявить особенности каждого из алгоритмов, что дает основу для определения целевого алгоритма в зависимости от входных данных. Отдельное внимание уделено классификации задачи MATSP, которая содержит в себе следующие классы: базовый, сбалансированный, динамический и с выделенными точками погрузки/разгрузки. Исследуются как статические, так и динамические аспекты задачи, включая онлайн-добавление точек и перерасчет маршрутов в реальном времени. Полученные результаты исследования демонстрируют перспективность использования мультиагентного подхода для решения задач городской маршрутизации, особенно в условиях изменяющихся параметров и необходимости оперативного реагирования на изменения.
This paper investigates modern urban logistics problems related to the need to adapt the routes of different vehicles to the changing conditions of the urban environment. The main attention is paid to the many-to-many salesman problem (MTSP), which is formalized in a multi-agent setting (MATSP) with mandatory visits to dedicated loading/unloading points, since the problem posed in such a context allows us to consider scenarios close to those typical of urban distribution systems. The paper analyses different solution methods: evolutionary algorithms, swarm intelligence algorithms (bee swarm and ant colony) and simulated annealing algorithm. As part of the research conducted, a mathematical model of the MATSP problem is formulated to define the main constraints as well as the target function subjected to optimization. Further, comparative computational experiments are conducted for the multiple travelling salesman problem with drop-off points in order to determine the performance evaluation on test datasets with selected service areas. These experiments allow us to clearly identify the features of each algorithm, which provides a basis for determining the target algorithm depending on the input data. Special attention is paid to the classification of MATSP tasks, which contains the following classes: basic, balanced, dynamic and with dedicated loading/unloading points. Both static and dynamic aspects of the task are investigated, including online point addition and real-time route recalculation. The results of the study demonstrate the promise of using a multi-agent approach to solve urban routing problems, especially in the context of changing parameters and the need to respond quickly to changes.
The authors declare that there are no conflicts of interest present.