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

Acknowledgments: the study was carried out within the framework of the Putilov Institute for Informatics and Mathematical Modeling of the Kola Science Centre of the Russian Academy of Sciences state assignment of the Ministry of Science and Higher Education of the Russian Federation, research topic “ Development of theoretical and organizational and technical foundations of information support for managing the viability of regional critical infrastructures of the Arctic zone of the Russian Federation” (registration number of the research topic 122022800547-3). For citation: Shestakov A. V., Zuenko A. A. Local search in open pit mining planning searching // Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2024. Vol. 15, No. 3. P. 61-68. doi:10.37614/2949.1215.2024.15.3.005. Введение Проблема маршрутизации транспортных средств (Vehicle Routing Problem, VRP) является одной из центральных задач в области логистики и оптимизации распределения ресурсов [1]. VRP заключается в нахождении оптимальных маршрутов для группы транспортных средств, которые должны обслуживать множество клиентов с учетом различных ограничений таких, как грузоподъемность, временные окна и множество других факторов. Неправильное решение данной задачи может привести к значительным экономическим потерям, увеличению времени доставки и снижению уровня обслуживания клиентов. На данный момент разработано множество методов для решения VRP, включая классические оптимизационные техники такие, как линейное целочисленное программирование [ 2 ], а также различные эвристические и метаэвристические подходы [3]. Однако развитие методов программирования в ограничениях (Constraint Programming, CP) [4] значительно расширило инструментарий для решения данной задачи. Методы CP позволяют формулировать задачи в виде систем ограничений, что делает их особенно эффективными для комплексных и нестандартных сценариев, где традиционные методы могут испытывать трудности. Далее приводится аналитический обзор возможностей решения задач маршрутизации в форме задач удовлетворения ограничений. Постановка и классификация задач маршрутизации Задачи маршрутизации (Vehicle Routing Problems, VRP) относятся к классу комбинаторных задач оптимизации, которые связаны с поиском оптимальных маршрутов для парка транспортных средств, обслуживающих определенные объекты [5]. Основная цель VRP — минимизировать общие затраты на перевозку при выполнении всех необходимых заданий таких, как доставка товаров клиентам, сбор грузов, соблюдение временных ограничений и т. д. Типовая VRP-задача включает в себя: — парк транспортных средств (грузовиков, фургонов, курьеров и т. д.) с определенными характеристиками (вместимость, расход топлива, скорость); — набор пунктов назначения (клиенты, склады, точки сбора) с различными требованиями к доставке/сбору (погрузке/выгрузке товара); — дорожную сеть с известными расстояниями и/или временем в пути между пунктами. Задача заключается в построении оптимальных маршрутов, по которым транспортные средства должны посетить все пункты назначения, удовлетворяя разнообразным ограничениям, при этом минимизируя общие издержки (расстояние, время, расход топлива и т. п.). Классическая задача маршрутизации (Capacitated Vehicle Routing Problem, CVRP) [ 6 ] заключается в определении оптимальных маршрутов для обслуживания группы клиентов с помощью одного или нескольких транспортных средств, отправляющихся из общего депо. В CVRP выделяют следующие ограничения: — каждое транспортное средство имеет ограниченную грузоподъемность, которую оно не может превышать; — суммарный спрос клиентов, обслуживаемых одним транспортным средством, не должен превышать его грузоподъемность; — все клиенты должны быть обслужены в точности один раз. Нельзя пропустить ни одного клиента; — все маршруты начинаются и заканчиваются в одном общем депо; Труды Кольского научного центра РАН. Серия: Технические науки. 2024. Т. 15, № 3. С. 61-68. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2024. Vol. 15, No. 3. P. 61-68. © Шестаков А. В., Зуенко А. А., 2024 62