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

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

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

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

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

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

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

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

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

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

Path:

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

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

что явно неверно, поскольку мы не пересекаем все города.

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

Удачи.

Ответ 5

Если вы ограничиваете проблему округлением (т.е. продавец может покупать только билеты туда и обратно), то он может быть представлен ненаправленным графом, и проблема сводится к поиску минимальное остовное дерево, которое можно сделать эффективно.

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

Ответ 6

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

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