Коммивояжер

Question

Я работаю над проблемой коммивояжера и не могу понять, как ее решить.Задача состоит из десяти рабочих, десяти рабочих мест, куда они должны ехать, и одного автомобиля, который водит их одного за другим.Существует стоимость 1,5 доллара за км.Кроме того, все узлы (как рабочие, так и рабочие места) расположены в матрице 10 * 10, а расстояние между каждым блоком в матрице составляет 1 км.
Проблема должна быть решена с использованием AMPL.

Я уже рассчитал расстояния между каждой координатой в Excel и скопировал и вставил матрицу в файл данных в AMPL.

 This is my mod.file so far (without the constrains): 

    param D > 0;
    param D > 0;
    set A = 1..W cross 1..D; 

    var x{A};   # 1 if the route goes from person p to work d, 
               # 0 otherwise

    param cost;
    param distance;

    minimize Total_Cost:
        sum {(w,d) in A} cost * x[w,d]; 

Answer 1

ОК, ваш маршрут выглядит следующим образом: начальный рабочий 1-рабочий 1-рабочий 2-рабочий 2-рабочий 3-рабочий-3 -...- задание 10-конец (дать или взять начальную и конечную точки, в зависимости ото том, как вы формулируете проблему.

В этом случае части вашего маршрута «worker n-job n» предопределены. Вам не нужно включать затраты «worker n-job n» вОптимизация маршрута, потому что в этих частях маршрута нет выбора (хотя вам, конечно, нужно помнить их для расчета общей стоимости).

Так что у вас есть настоящий TSP с 10-дюймовыми адресатами«(каждый представляет отдельного работника и назначенную ему работу), но с асимметричной матрицей затрат (поскольку стоимость поездки с работы i на работника j не равна стоимости поездки от работы j до работника i).

Если у вас уже есть реализация для основного TSP, ее легко адаптировать. Если нет, то вам нужно написать ее и внести это небольшое изменение в матрицу асимметричной стоимости. Я видел два разных подхода к этому вAMPL.

2-D матрица принятия решений с устранением подуровня

Переменная решения x {1..10,1..10} определяется как: x [i, j] = 1, еслимаршрут идет от работы i к работе j, и 0 в противном случае.Ограничения требуют, чтобы в каждой строке и столбце этой матрицы был ровно один 1.

Сложной частью этого подхода является предотвращение переходов (т. Е. Созданный «маршрут» на самом деле представляет собой два или более отдельных цикла вместо одного большого цикла),Похоже, ваша текущая попытка находится на данном этапе.

Одним из решений проблемы субтур является итеративный подход:

1. Напишите реализацию, которая включает все требования, кроме предотвращения субтур.
2. Решите с помощью этой реализации.
3. Проверьте полученное решение на наличие подпочв.
4. Если подпочв не найдено, верните решение и завершите.
5. Если вынайти подпрограммы, добавить ограничение, которое предотвращает эту конкретную подпрограмму.(Определите дуги, участвующие в подтуре, и установите ограничение, которое подразумевает, что они не могут быть выбраны все.) Затем перейдите к # 2.

Для небольшого упражнения вы можете выполнитьликвидация подземных работ вручнуюДля более крупного упражнения, или если вашему лектору не нравится такой подход, вы можете создать .run, который автоматизирует его.См. Статью Боба Фурера от 31.07.2013 в этой теме для примера реализации.

Трехмерная матрица решений с измерением времени

При таком подходе выустановите переменную решения x {1..10,1..10,1..10}, где x [i, j, t] = 1, если маршрут идет от задания i к работнику j в момент времени t и 0 в противном случае.Тогда ваши ограничения требуют, чтобы маршрут проходил к и от каждой комбинации работы / работника ровно один раз, что если он переходит к работнику i в момент времени t, то он должен пройти от задания i во времяt + 1 (исключая первый / последний выпуски), что он делает ровно одну вещь в момент времени t и что конечная точка в момент времени 10 совпадает с начальной точкой в ​​момент времени 1 (при условии, что вам нужен канал).

Это предотвращаетsubtours, поскольку он инициирует маршрут, который начинается в какой-то момент времени 1, возвращается в этот момент в момент времени 10 и не посещает другие точки более одного раза - это означает, что он должен пройти все из них ровно один раз.