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

Программирование в ограничениях в первую очередь направлено на сокращение множества допустимых значений переменных решения, которые соответствуют всем установленным ограничениям. Когда происходит установление факта невозможности присвоения определенных значений переменной решения, данная информация распространяется через ограничения, что может способствовать формированию дополнительных выводов. Для достижения окончательного решения применяются различные стратегии поиска, которые продолжаются до тех пор, пока для каждой переменной не будет назначено значение. По завершении первого успешного поиска продолжается работа над нахождением новых решений, которые обладают более оптимальными целевыми значениями. Ключевым элементом CP является возможность представления задач в компактной и понятной форме. Однако по мере увеличения сложности проблем, связанных с множеством переменных и ограничений, возникает необходимость в более высокоуровневых конструкциях, которые могут облегчить процесс моделирования и упростить решение. Одним из наиболее эффективных инструментов, используемых для этого, являются глобальные ограничения [ 1 1 ]. Глобальные ограничения представляют собой специальные классы ограничений в рамках программирования в ограничениях, которые фиксируют связь между заранее не известным числом переменных. В отличие от простых ограничений, которые обычно накладываются на одну или две переменные и имеют специфическую форму, глобальные ограничения охватывают более широкий спектр взаимосвязей, позволяя формулировать более сложные условия. Такие ограничения характеризуются высокой степенью абстракции, представляя сложные отношения между группами переменных в компактной форме. Они могут быть заданы различными способами. Примером может служить ограничение alldifferent(x\,...,xn), которое определяет, что значения, присваиваемые переменным xi,...,xn, должны быть попарно различными. Многие глобальные ограничения могут быть связаны с внутренними структурами, которые представляют возможные значения и правила для переменных (например, конечные автоматы в случае регулярных ограничений). Ключевыми характеристиками глобальных ограничений являются: возможность моделировать сложные взаимоотношения, которые не могут быть адекватно выражены с помощью простых ограничений; оптимизированные решатели могут использовать глобальные ограничения для сокращения пространства поиска и устранения неэффективных подмножеств. Обычные ограничения, как правило, ограничиваются парами переменных или незначительными группами, и их выражение может потребовать большого количества отдельных условий для описания более сложных взаимосвязей. Например, для обеспечения уникальности значений в группе из 10 переменных с помощью отдельных ограничений потребуется 45 простых ограничений (поскольку необходимо убедиться в уникальности каждой пары), в то время как с помощью глобального ограничения alldifferent эта задача может быть выражена одной строкой. Представление VRP в виде задачи целочисленного линейного программирования (ILP) Рассмотрим формулировку ILP из [12]. Пусть задано множество клиентов C = {1, ..., n} и транспортных средств M = {1, ..., m}. Для индексации склада в начале маршрута используется 0, а для индексации склада в конце маршрута — n+1. N = C U {0, n+1}. В рассматриваемой постановке используются следующие обозначения: a) в качестве переменных выступают Хф ( i j 6 N, k 6 M), причем Хф равна 1, если автомобиль k едет напрямую от клиента i к клиенту j, 0 — в противном случае; b) Cij — стоимость путешествия из i в j , i j 6 N; c) Tij — время в пути от i до j, i,j 6 N, включающее в себя время обслуживания у клиента i; d) Sij — расстояние от i до j, i j 6 N; e) Г і — спрос для клиента i 6 N; f) Qk — вместимость транспортного средства k 6 M; Труды Кольского научного центра РАН. Серия: Технические науки. 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 64