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

Каждый «первый» визит транспортного средства имеет в качестве предшественника «последний» визит транспортного средства (Vk6M pjk = lk). Таким образом, переменные-предшественники образуют перестановку V и подчиняются глобальным ограничениям alldiffconstraint (11): P i ^ P j V i , j 6 V A i < j . (11) Переменные-преемники поддерживаются «когерентными» (согласованными) с переменными- предшественниками с помощью глобальных ограничений element constraint ( 1 2 ): Sp^ = i Vi 6 V — F ps. = i Vi 6 V — L. (12) Для первого и последнего визитов накладываются ограничения: Vk 6 M vfk = vlk = k. На маршруте все визиты выполняются одним и тем же транспортным средством (13): Vi = vpi Vi 6 V —F v t = vs. Vi 6 V —L. (13) Ограничения пути (path constraint) (14) гарантирует, что количество товаров на борту транспортного средства остается в допустимых пределах: Чі = ЧРі + гі V i 6 V —F Ц і = Ц3 і —Г і V i 6 V —L. (14) Ограничение вместимости транспортного средства (15): q t < QVl Vi 6 V. (15) Для задачи VRPTW добавляется ограничение времени движения транспортных средств по маршрутам (16): ti > tp . + Tpi i i 6 V —F ti < ts. —Ti,s. i 6 V —L. (16) Временные окна для клиентов задаются путем добавления ограничений на переменные t . Ограничение a < ti < b означает, что клиент i должен быть посещен в промежуток времени между a и b. Для моделирования нескольких временных окон используется ограничение (17) [4]: a < t i < d и Ь і < b V ti > с. (17) Ограничения (17) означают, что клиент i должен быть посещен либо в промежуток времени между a и b , либо в промежуток времени между c и d (a < b < c < d ). Различные транспортные средства могут иметь различные доступные временные окна. Введем следующие обозначения: a) Ok — самое раннее время маршрута начала движения транспортного средства k; b) Hk — его самое позднее время окончания движения, или горизонт; c) Sij — расстояние от визита i до j; d) Ck - - это стоимость единицы расстояния для транспортного средства k . Ограничения на время доступности транспортных средств (18): Ov . < t i < Hv . Vi 6 V . (18) Функция затрат обычно представляет собой общее пройденное расстояние d (19): d = % iev-F 8pi,i d = % iev-L ^i,st- (19) Если стоимость километра зависит от используемого транспортного средства, функция затрат определяется как ( 2 0 ): d = 2 i6V-F^Vi^pi,i d = £ i6V-L^Vi^i,Si . (20) Для задачи VRPPD: a) Г і < 0 — для доставки товара; Труды Кольского научного центра РАН. Серия: Технические науки. 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 66