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

— все параметры задачи (спрос клиентов, расстояния/время между узлами) являются детерминированными и известными заранее. В задаче маршрутизации с временными окнами (Vehicle Routing Problem with Time Windows, VRPTW) [7] к основным ограничениям CVRP также добавляется, что каждый клиент должен быть обслужен в определенный промежуток времени, называемый «временным окном». Таким образом, добавляются следующие ограничения: — транспортное средство должно прибыть к клиенту в пределах его временного окна; — время прибытия транспортного средства к клиенту плюс время его обслуживания не должно превышать время закрытия временного окна; — время в пути между клиентами и депо должно также учитываться при планировании маршрутов; — маршрут транспортного средства должен быть завершен до закрытия депо. Для задачи маршрутизации с ограничениями по ресурсам (Resource-Constrained VRP, RCVRP) добавляются ограничения на различные ресурсы, необходимые для выполнения маршрутов: — топливо/энергия — ограниченное количество топлива или энергии (заряд аккумулятора) для транспортных средств; — время — ограничения на общее время работы, время вождения, время нахождения в пути; — персонал — ограниченное количество водителей/экипажей для обслуживания маршрутов; — оборудование — ограниченное количество погрузочно-разгрузочных механизмов, холодильных установок и т. д. Задача маршрутизации транспортных средств со сбором и доставкой товаров (Vehicle Routing Problem with Pickups and Deliveries, VRPPD) [ 8 ]. В ней для каждого клиента требуется обеспечить не только доставку, но и вывоз товаров. В VRPPD необходимо определить оптимальные маршруты транспортных средств, которые обеспечивают сбор товаров у одних клиентов и их доставку другим клиентам, при этом соблюдая ограничения на грузоподъемность транспорта. Основная цель — минимизация общих затрат на перевозку. Ключевая особенность VRPPD — необходимость обеспечить соответствие между взятыми (собранными) и доставленными грузами: количество товаров, взятых у клиентов, должно соответствовать количеству товаров, доставленных другим клиентам. Суммарная загрузка транспортного средства на маршруте (сбор + доставка) не должна превышать его грузоподъемность. Роль программирования в ограничениях в решении VRP В последние годы методы программирования в ограничениях (Constraint Programming, CP) становятся все более популярными в решении задач VRP. CP позволяет формулировать задачи как системы ограничений, предоставляя гибкие и мощные инструменты для обработки сложных комбинаторных задач, к которым относятся задачи VRP. Основной особенностью CP является возможность интуитивного задания и моделирования ограничений, что позволяет адаптировать подход к конкретным условиям задачи [9]. Согласно CSP (Constraint Satisfaction Problem) [10], задача представляет собой набор переменных с определенной областью возможных значений (домен) и набор некоторых ограничений. Таким образом, ограничения представляют собой отношения между переменными, в то время как задача CSP формализует, какие именно отношения должны соблюдаться для заданного множества переменных решения. Исходя из вышеизложенного, задача удовлетворения ограничений может быть формализована в рамках инкрементного подхода следующим образом: — исходное состояние характеризуется отсутствием значений для всех переменных; — функция, обеспечивающая последовательность действий, требует, чтобы процесс присвоения значений исключал возможность возникновения конфликтов между переменными; — проверка достижения цели подразумевает, что присвоенные значения должны формировать полное и согласованное решение; — каждый этап этого процесса оценивается с фиксированной стоимостью, что упрощает анализ и оптимизацию алгоритмических процедур. Труды Кольского научного центра РАН. Серия: Технические науки. 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 63

RkJQdWJsaXNoZXIy MTUzNzYz