Вариант TSP / CPP - ограничение подземного хода

Question

Я разрабатываю задачу оптимизации, которая является вариантом на Traveling Salesman.В этом случае вам не нужно посещать все города, есть обязательная начальная и конечная точка, есть минимальная и максимальная граница для длины тура, вы можете пересечь каждую дугу несколько раз, если хотите, и у вас есть нелинейныйЦелевая функция, которая связана с пройденными дугами (и сколько раз вы проходите по каждой дуге).Переменные решения - это целые числа, сколько раз вы проходите каждую дугу.

Я разработал нелинейную целочисленную программу на Pyomo и получаю результаты с сервера NEOS.Тем не менее, я не вставлял ограничения для подуровня, и мои результаты - это два отсоединенных подпроцесса.

Я могу найти целочисленные программные формулировки TSP, в которых говорится, как формулировать ограничения подуровня, но это немного отличается от стандартного TSP иЯ пытаюсь понять, как начать.Любая помощь, которая может быть предоставлена, будет принята с благодарностью.

РЕДАКТИРОВАТЬ: формулировка проблемы

50 дуг, а не исчерпывающие пары между узлами.50 Решающие переменные N_ab являются целыми числами> = 0 и соответствуют тому, сколько раз вы переходили от a к b.Существует длина и прибыль, связанные с каждым N_ab.Есть два ограничения, что сумма length_ab * N_ab для всех ab находится между минимальным и максимальным расстоянием.У меня есть ограничение, что сумма N_ab в каждом узле равна сумме N_ab из узла, вы можете либо вообще не посещать узел, либо посещать его несколько раз.Объективная функция является нелинейной и связана с взаимодействием между парами дуг (не имеет отношения к подземному ходу).

Subtours: взгляд на math.uwaterloo.ca/tsp/methods/opt/subtour.htm, формулировка isn 'Это применимо, поскольку я не обязан посещать все города и, возможно, не смогу.Например, допустим, у меня 20 узлов и 50 дуг (длина всех дуг 10).Ограничения по расстоянию предназначены для обхода точно длиной 30, что означает, что я могу посетить не более трех узлов (начиная с A -> B -> C -> A = длина 30).Поэтому я не буду посещать другие узлы вообще.Удаление подпроцесса TSP потребовало бы, чтобы у меня были ребра от подгруппы узлов ABC до подгруппы не посещенных узлов - что не нужно для моей проблемы

Answer 1

Вот подход, который адаптирован из TSP, собирающего призы (например, этот документ ). Пусть V будет множеством всех узлов. Я предполагаю, что V включает в себя узел depot , назовите его узлом 1, который должен быть в туре. (Если нет, вы, вероятно, можете добавить фиктивный узел, который выполняет эту роль.)

Пусть x[i] будет переменной решения, равной 1, если мы посетим узел i хотя бы один раз, и 0 в противном случае. (Возможно, у вас уже есть такая переменная решения в вашей модели.) Добавьте эти ограничения, которые определяют x[i]:

x[i] <= sum {j in V} N[i,j]    for all i in V
M * x[i] >= N[i,j]             for all i, j in V

Другими словами: x[i] не может быть равно 1, если ребра не выходят из узла i, и x[i] должно равняться 1, если есть ребра, выходящие из узла i. (Здесь N[i,j] равно 1, если мы переходим от i к j, а M - достаточно большое число, возможно, равное максимальному числу раз, которое вы можете пройти через один край.)

Здесь приведено ограничение удаления субтуров, определенное для всех подмножеств S из V, так что S включает в себя узел 1, а для всех узлов i в V \ S:

sum {j in S} (N[i,j] + N[j,i]) >= 2 * x[i]

Другими словами, если мы посетим узел i, который не находится в S, то должно быть как минимум два ребра в или из S. (Подземный обход нарушил бы это ограничение для S, равного узлам, которые находятся на подземном обходе, который содержит 1.)

Нам также нужно ограничение, требующее, чтобы узел 1 находился в туре:

x[1] = 1

Возможно, я играю немного быстро и свободно с индексами направления, т. Е. Я не уверен, что ваша модель устанавливает N[i,j] = N[j,i] или что-то в этом роде, но, надеюсь, идея достаточно ясна, и вы можете изменить мой подход как необходимо.