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

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

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

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

EDIT:

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

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

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

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

Voila! получил две мини-туры, которые покрывают вершины ровно один раз.

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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