Определение узлов, которые не нужно посещать

Question

Я хотел бы определить проблему маршрутизации с помощью RoutingModel включая узлы, которые освобождены от ограничения обязательного посещения, но имеют влияние на измерение емкости при посещении. Есть ли у вас какие-либо предложения, как это сделать?

Answer 1

Вы можете использовать ограничения дизъюнкции, чтобы сделать ваши узлы необязательными. Вы должны добавить каждый узел в свою собственную группу дизъюнкции, каждый из которых имеет отдельный элемент:

    for node in [0, 1, 2, 3, 4]:
        routing.AddDisjunction(
            nodes=[node],
            penalty=1)

Почему это работает?

В группе дизъюнктов решатель попытается включить в решение точно max_cardinality узлы из этой группы.

• Если penalty отрицательно, это будет рассматриваться как жесткое ограничение, что означает, что решатель не вернет правильное решение, если ограничение не выполнено.
• Однако если penalty положительно, это будет мягкое ограничение, означающее, что нарушение добавит штраф к глобальной переменной стоимости.

Поэтому, чтобы минимизировать штрафы, решатель попытается включить в решение как можно больше узлов, но при этом ему будет разрешено не использовать некоторые из них.