Каково решение для TSP с несколькими продавцами и без возврата, но с известными вершинами и конечными точками?

Я не знаю, правильно ли я это сформулировал, и я не уверен, что это проблема TSP, но вот сценарий.

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

Что это за проблема и какие решения я должен искать? Я рассматривал его как мульти-TSP без возврата, но до сих пор не могу определить какие-либо близкие к оптимальным туры. Я также пробовал гамильтонов путь кратчайшей длины, но я быстро сталкиваюсь с блоком, как только ввожу второй драйвер.

Любые ресурсы, алгоритмы и эвристические предложения также приветствуются.


optimization algorithm graph-theory traveling-salesman heuristics
person Tendekai Muchenje    schedule 30.12.2013    source источник
comment
На SO уже есть ответы на вопросы об этой проблеме, а также много материалов, доступных в Интернете. Просто для начала....www-bcf.usc.edu/~maged /publications/MultiplePickup.pdf   -  person FeliceM    schedule 30.12.2013
comment
Благодарю за ваш ответ. Я предполагаю, что он не знал, как определить это правильно. Теперь я знаю, и это открыло совершенно новый набор ресурсов. :)   -  person Tendekai Muchenje    schedule 01.01.2014
comment
@FeliceM, можете ли вы указать на другие темы SO? Рассматривает ли статья, на которую вы ссылаетесь, невозвратное ограничение? Спасибо.   -  person Ciro Santilli 新疆再教育营六四事件ۍ    schedule 12.04.2014
comment
@CiroSantilli, если вы посмотрите на правую часть экрана, пока читаете этот комментарий, в разделе «Связанные» есть похожие темы на SO. Я не уверен насчет невозвратного ограничения в статье, на которую я указал. Это был просто пример, их много в сети.   -  person FeliceM    schedule 12.04.2014

Ответы (3)


arrow_upward
4
arrow_downward

Джеффри прав. Это проблема маршрутизации транспортных средств. Однако это не классическая емкость (CVRP) с одним депо, поскольку ваши водители, вероятно, начинают и заканчивают работу дома, а не в депо. Поэтому ваша проблема несколько усложняется и превращается в проблему самовывоза (VRPPD).

Короче говоря: если ваши водители просто начинают и заканчивают в депо, это CVRP. Если они начинаются и заканчиваются дома, это VRPPD.

Для CVRP вы можете найти ряд алгоритмов с открытым исходным кодом, например OptaPlanner, который написан на Java (Джеффри знает больше об этом) или VRPH, которая является библиотекой C++. Когда дело доходит до VRPPD, количество доступных алгоритмов с открытым исходным кодом сокращается. Вероятно, вы можете сделать это с помощью OptaPlanner (я не уверен на сто процентов). Но вы наверняка сможете решить эту проблему с помощью jsprit, который я реализовал на Java.

Если ваша проблема большая и вам нужно быстрое время отклика (время вычислений), вам может быть лучше превратить VRPPD в CVRP, предполагая, что водители сначала будут ездить из дома в депо, а затем снова из депо домой. Но так вы наверняка потеряете оптимизационный потенциал.

person Stefan Schröder    schedule 09.01.2014

arrow_upward
2
arrow_downward

Это называется Проблема выбора маршрута транспорта (VRP).

На эту тему доступно множество ресурсов, например видео (capacitated и/или окна времени) и документы.

Интернет VRP предлагает хорошее объяснение различных вариантов.

person Geoffrey De Smet    schedule 02.01.2014

arrow_upward
1
arrow_downward

  • В этой статье рассматривается точно такая же проблема: Windshicle "Ky- Rhicle Проблема почтальона».

    Авторы: Бенавент, Корбер, Санчис и Плана.

  • Несколько статей, таких как этот вызов варианта VRP без возврата с одним продавцом (ОВРП).

    Авторы: Д Аксен, З Озюрт и Н Арас2.

  • Документ 2013 г. о VRP без возврата: http://www.hindawi.com/journals/tswj/2013/874349/

    Авторы: Тантикорн Пичпибул Руенгсак Кавтуммачай.

person Ciro Santilli 新疆再教育营六四事件ۍ    schedule 12.04.2014