Труды КНЦ (Технические науки вып. 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. g) ai, bi — временные окна клиентов i 6 N; h) K — целое число. Главная цель задачи VRP - - минимизировать сумму затрат (1): m in im ise z VRP = £й 6 м £ і 6 м Е / 6 М cijx ij k . ( 1 ) Определим ограничения для задачи VRP. Каждый клиент должен быть посещен ровно один раз (2): 'Zk6M'Zj6Nx ijk = 1 Vj 6 С. (2) Пропускная способность (в предположении неоднородного парка траноторта): Е / 6 С ri^]6N x ijk — Qk Vk 6 М. (3) Ограничение (4-6) для обеспечения потока транспортных средств от начального склада, через 0 или более клиентов к конечному складу: l]6NXojk = 1 V k 6 M , (4) 'LieNx ihk - 'Zj6NXhjk = 0 V h 6 C , V k 6 M , (5) 2 ( 6 N x i(n+l)k = 1 V^ 6 M. ( 6 ) Обеспечение отсутствия подтуров (циклов, не включающих депо) описывается ограничениями (7-8): T.ijesXijk — I S I - 1 V S Q C , (7) x ijk 6 {0,1} V i,j 6 N ,V k 6 М. ( 8 ) Ограничение для определения времени прибытия к каждому клиенту (9): tik + Tij — ^ ( 1 — x ijk) — tjk V i j ’ 6 N ^ k 6 М. (9) Обеспечение соблюдения временных окон происходит при помощи ограничения (10): а; — tik — bi Vi 6 N ,V k 6 М. (10) Формулирование задач маршрутизации в форме задач удовлетворения ограничений В данной формулировке [13], аналогично ситуации с ILP, рассматривается n заказов от клиентов и парк из m транспортных средств. Термин «визит» используется для обозначения момента, когда транспортное средство осуществляет остановку. Каждому клиенту соответствует одно посещение, в то время как на каждое транспортное средство приходится два специальных визита для моделирования начальной и конечной точек маршрута транспортного средства. Пусть C = {1, ..., n} — множество клиентов, M = {1, ..., m} — множество транспортных средств и V = {1, ..., n + 2m} — множество визитов. Первый и последний визит транспортного средства k обознается fk и lk соответственно. Визит fk = n + k соответствует первому визиту транспортного средства k, а lk = n + m + k — последнему. F = {n + 1, ..., n + m} и L = {n + m + 1, ..., n + 2m} — множества первых и последних визитов соответственно. C = {1, ..., n} — клиенты. Также введем обозначения: a) qi > 0 — количество товаров в транспортном средстве после выполнения визита i; b) Qk — грузоподъемность транспортного средства k; c) Vi — транспортное средство, выполняющее визит i; d) Г і Ф 0 — количество товаров, которое нужно забрать во время визита i; e) Si — прямой приемник визита i; f) ti > 0 — время начала обслуживания визита i; g) pi — целочисленная переменная, моделирует прямого предшественника каждого визита i 6 V. © Шестаков А. В., Зуенко А. А., 2024 65