Оптимизация коммивояжера

Question

Я пытаюсь решить вариант коммивояжера с неполным графиком.

РЕДАКТИРОВАТЬ: изменил описание (дважды) на основе обратной связи от @daniel_junglas.

Другими словами:

• Только 1 продавец
• Продавец может посетить каждый город только один раз
• Продавец может ездить в различных режимахтранспорта (например, поезд, автомобиль, лодка). Каждый вид транспорта меняет время, необходимое для поездки между городами
• Продавец может менять вид транспорта между городами (за плату), но не в городе. Это изменение можно рассматривать как еще одну грань между двумя городами с определенным весом
• , не каждый город может быть посещен каждым видом транспорта (например, только лодка может добраться до города D)
• график не полный, поэтому не все города связаны, но существует один или несколько гамильтоновых путей

На основе примера:

• 4 города (1-4), у каждого узла есть автостоянка (C), железнодорожная станция (T), порт для лодок (B).
• Начиная и заканчивая в 1C
• Каждый город должен быть посещен по одному
• Нет никакой связи от железнодорожного вокзала до гавани на стоянку, можно изменить только за пределамигорода (например, 1C до 2T).
• каждая ссылка имеет вес, связанный с ней, в зависимости от расстояния, скорости транспортного режима и штрафа времени за изменение транспортного режима
• Примеры путей:
  • 1C -> 2T -> 3T -> 4T -> 1C
  • 1C -> 2C -> 3T -> 4T -> 1C

Я планировал решить эту проблему с помощью concorde/ CPLEX.

Я попытался решить ее с помощью пиконкорда. Для этого я закодировал каждое параллельное ребро в тот же узел, что и новый узел (A, A ', A' '), но я не могу найти ограничение, чтобы сказать, что должен быть посещен только один A-узел. Я вижу много решений a-symetric TSP и multi-TSP, но ни одно из них не соответствует моим требованиям.

Мои вопросы: как мне подойти к этой проблеме (ссылка на учебник, предложение по встраиванию и т. Д.), Чтобы найти кратчайший маршрут, который посещает все города ровно один раз? Какой инструмент мне поможет?

PS Мне известны различные решения с одним алгоритмом, как вероятностные, так и точные. Однако я ищу инструмент, который сочетает в себе различные методы, такие как cplex, в надежде на лучшие результаты для моих конкретных данных.
PS2. Я знаю, что этот вопрос может быть широким. Я открыт для любых замечаний, чтобы улучшить свои вопросы

Answer 1

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

Однако вы сказали, что хотите решить concorde / cplex. Как насчет отбрасывания части конкорда? Вы могли бы принять MIP формулировку для TSP. Это должно быть легко расширить, чтобы включить ваши дополнительные ограничения. Например, вы можете вернуться к нескольким краям и добавить такие условия, как «если вы въезжаете в город A на машине, то вам нужно уехать на машине или заплатить дополнительный N». Затем вы можете передать это общему решению MIP, например, CPLEX.

Answer 2

На высоком уровне Concorde - это очень эффективная реализация генерации столбцов (ответвления, цены и сокращения) для TSP.

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

У Марко Любекке есть очень хороший универсальный учебник . Книга TSP является справочной работой по предмету.

Answer 3

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