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

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

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

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

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

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

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

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

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

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

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

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

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

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

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