Путешествующий продавец с повторяющимися узлами и динамическими весами

Question

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

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

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

У кого-нибудь есть идеи, как решить эту проблему?Моей первой идеей было использовать метод эволюционной оптимизации, такой как GA или ACO , чтобы решить точку 2, и просто отрегулировать вес ребер при оценке целевой функции на основе того, содержит ли маршрут возврат /рейсы туда и обратно, но, возможно, у кого-то есть идея получше.

(Примечание: я использую MATLAB, но я не ищу конкретно кодовые решения, а просто идеи высокого уровня о том, какие алгоритмы можно использовать.)

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

Answer 1

Я не проверял это сам; тем не менее, у меня есть read , что реализация Simulated Annealing для решения TSP (или его вариантов) может дать отличные результаты. Ключевым моментом здесь является то, что имитация отжига очень проста в реализации и требует минимальной настройки, в то время как алгоритмы аппроксимации могут выполняться намного дольше и, вероятно, более подвержены ошибкам. У Skiena также есть страница , посвященная определенным решателям TSP.

Answer 2

Вы хотите почти оптимальное решение или оптимальное решение?

Для оптимального решения все еще есть хорошая грубая сила.Из-за требования 1, касающегося повторяющихся узлов, вам нужно будет убедиться, что вы выполняете поиск в ширину, а не в dept-first.В противном случае вы можете оказаться в бесконечном цикле.Вы можете медленно отбрасывать все маршруты, которые превышают ваш текущий минимум, пока все маршруты не будут исчерпаны и минимальный маршрут не обнаружен.

Answer 3

Если вы ограничиваете проблему круговыми поездками (т. Е. Продавец может покупать только билеты туда и обратно), то она может быть представлена ​​неориентированным графиком, и проблема сводится к нахождению минимального связующего дерева . 1002 *, что можно сделать эффективно.

В общем случае я не знаю умного способа использовать эффективные алгоритмы; ГА или аналогичный может быть хорошим способом.

Answer 4

Решение TSP - сложная задача NP для ограничений исключения субциклов, если вы удаляете какой-либо из них (для городов-концентраторов), вы просто облегчаете проблему.

Но будьте осторожны: TSP имеет сходствос проблемой ассоциации в том смысле, что вы можете получить недействительные маршруты, такие как:

Города: Нью-Йорк, Бостон, Даллас, Торонто

Путь:

Бостон- Нью-Йорк Нью-Йорк - Бостон

---

Даллас - Торонто Торонто - Даллас

, что явно неверно, так как мы проходим не все города.

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

Удачи

Answer 5

Во-первых, какое приблизительное количество городов в вашей задаче установлено? (До 100? Больше 100?) У меня довольно большой опыт работы с GA (не с ACO), и, как говорит Эпитафия, у нее есть игровой аспект. Для некоторого ввода это могло бы остановиться на грубо неэффективном решении. Итак, в прошлом я использовал GA в качестве первого варианта, сравнил ответ с некоторой нижней границей и, если это кажется «далеко», запустил второй (обычно менее эффективный) алгоритм.

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

1. нижняя граница - конечно, в этом случае MST будет нижней границей.
2. "Way Off" - если выполняется неравенство треугольника, то верхняя граница равна UB = 2 * MST. Хорошим «выходом» в этом контексте будет 2 * UB.
3. Второй алгоритм - в этом случае и подход на основе линейного программирования, и Christofides были бы хорошим выбором.

Answer 6

Если вы хотите, чтобы стоимость решения, полученного с помощью алгоритма, была в пределах 3/2 от оптимальной, тогда вам нужен алгоритм Christofides. ACO и GA не имеют гарантированной стоимости.