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

Question

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

Я пытаюсь придумать эвристику, и мне было интересно, может ли кто-нибудь помочь. Например, если у меня есть 20 городов с двумя продавцами, подход, о котором я подумал, - это двухэтапный подход. Во-первых, разделите 20 городов случайным образом на 10 городов по 2 продавца в каждом, и я бы нашел тур для каждого, как если бы он был независимым в течение нескольких итераций. После этого я хотел бы либо поменять местами, либо назначить город другому продавцу и найти тур. По сути, это будет TSP, а затем проблема минимальной продолжительности. Проблема в том, что это было бы слишком медленно, и хорошее поколение соседей поменять местами или присвоить город сложно.

Может кто-нибудь дать совет, как мне улучшить вышеперечисленное?

EDIT:

Географическое положение каждого города известно, и продавцы начинают и заканчивают в одном и том же месте. Цель состоит в том, чтобы свести к минимуму максимальное время в пути, создавая проблему минимального рабочего времени. Например, если продавец1 занимает 10 часов, а продавец2 - 20 часов, максимальное время в пути составит 20 часов.

Answer 1

TSP - сложная проблема. Multi-TSP, вероятно, намного хуже. Я не уверен, что вы можете найти хорошие решения с помощью специальных методов, подобных этому. Вы пробовали метаэвристические методы? Сначала я бы попробовал использовать метод Cross Entropy: его не должно быть слишком сложно для вашей проблемы. В противном случае ищите общие алгоритмы, оптимизацию колоний муравьев, имитацию отжига ...

См. «Учебное пособие по методу перекрестной энтропии» от Boer et al. Они объясняют, как использовать метод CE на TSP. Простая адаптация для вашей проблемы может заключаться в определении другой матрицы для каждого продавца.

Возможно, вы захотите предположить, что вы хотите только найти оптимальное распределение городов между продавцами (и назначить кратчайший тур для каждого продавца в классической реализации TSP). В этом случае в настройке Крестовой энтропии вы рассматриваете вероятность того, что каждый город Xi будет в туре продавца A: P (Xi в A) = pi. И вы работаете, на пространстве p = (p1, ... pn). (Я не уверен, что это будет работать очень хорошо, потому что вам придется решать многие проблемы TSP.)

Answer 2

Я бы не стал писать алгоритм для такой сложной проблемы (если только это не моя дневная работа - писать алгоритмы оптимизации).Почему бы вам не обратиться к универсальному решению, например http://www.optaplanner.org/?Вы должны определить свою проблему, и программа использует алгоритмы, которые ведущие разработчики потратили годы на создание и оптимизацию.

Answer 3

Почему бы вам не преобразовать несколько TSP в традиционный TSP?
Это хорошо известная проблема (преобразование TSP нескольких продавцов в TSP), и вы можете найти несколько статей по ней.

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

Вуаля!получил два минимальных тура, которые покрывают вершины ровно один раз.

Answer 4

Когда вы начинаете говорить о нескольких продавцах, я начинаю думать об оптимизации частиц. Я нашел большой успех с этим с помощью алгоритма гравитационного поиска. Вот (длинная) статья, которую я нашел на эту тему. http://eprints.utm.my/11060/1/AmirAtapourAbarghoueiMFSKSM2010.pdf

Answer 5

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

Answer 6

Моей первой мыслью при прочтении описания проблемы было бы использование стандартного подхода к проблеме продавца (поиск подходящего, так как мне никогда не приходилось писать код для него);Затем возьмите результат и разделите его пополам.Тогда ваш алгоритм может заключаться в том, чтобы решить, где находится «половина» - может быть, это половина городов, или, возможно, она основана на расстоянии или, возможно, какой-то комбинации.Или найдите в результате наибольшее расстояние между двумя городами и выберите его как расстояние между последним городом продавца № 1 и первым городом продавца № 2.Конечно, это не ограничивается двумя продавцами, вы бы разбили на x частей;Но в целом идея заключается в том, что ваше стандартное решение TSP для 1 продавца уже должно было располагать «соседние» города рядом друг с другом в графе путешествий, поэтому вам не нужно придумывать отдельный алгоритм группировки ...

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

Answer 7

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

Answer 8

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

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