Линейное программирование маршрутизации транспортных средств

Question

Нужна помощь для линейного программирования проблемы маршрута транспортного средства. В задаче маршрутизации транспортного средства (VRP) транспортное средство будет обслуживать набор узлов, так что общая стоимость поездки минимизируется. Моя переменная решения: Xij = 1, если узел j посещается после узла i. Параметр dij - это расстояние между узлами i и j. Итак, модель выглядит следующим образом:

обратите внимание, что транспортное средство начинает поездку со склада (узел № 0) и, наконец, возвращается на склад (ограничения 11 и 12). Все узлы должны быть посещены (ограничение 13), и при входе в узел он должен покинуть этот узел (ограничение 14). Но когда я решаю это в cplex для большого количества узлов, иногда решение оказывается недопустимым из-за таких циклов:

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

Answer 1

Хотя этот вопрос старый, в ответе @alex есть одна важная деталь, на которую нужно обратить внимание. Исключение подпроцесса (SE) в его ссылке реализуется на лету посредством ленивого обратного вызова ограничения. Это важно иметь в виду, поскольку в более крупных примерах создание всех ограничений SE может оказаться невозможным, и лучше их оценивать лениво.

Answer 2

в CPLEX_Studio128 \ opl \ examples \ opl \ models \ TravelingSalesmanProblem вы можете найти небольшой пример того, что вам нужно, что касается исключения из подполья

Answer 3

Спасибо за ответы.Я нашел формулировку Такера для устранения подпочвы, которая работает хорошо.Ui-щ + nXij <= п-1. </p>

Answer 4

Как упомянул @Erwin, вам нужно добавить ограничения на удаление подпочв.Кратко:

1. Решить проблему.
2. Анализировать решение.Если нет подуровней, то решение является оптимальным.В противном случае добавьте ограничения на подпрограммы, которые у вас есть, к исходной задаче (в вашем примере: x_01 + x_12 + x_20 <= 2 и x_34 + x_45 + x_53 <= 2).Перейти к 1. </li>