Оптимизация маршрута для нескольких транспортных средств

12

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

Я использую PostgreSQL и PostGIS и хотел использовать pgrouting, но я не уверен, что он подходит для нескольких транспортных средств - из-за моего ограниченного знания Dijkstra и т. Д. Я думаю, что они предназначены для одного транспортного средства.

Есть мысли о том, может ли pgrouting решить эту проблему, и если да, то какие примеры кода? Если нет, есть ли альтернативы с открытым исходным кодом, которые могут это сделать?

routing pgrouting RichW
источник
У меня такая же потребность, как и у тебя. Я управляю бизнесом NEMT (Non-Emergency Medical Transportation). нам нужно перевезти пациентов на прием к врачу с временными интервалами для пикапа или доставки. Большинство запросов получены заранее, остальные на месте. DARP кажется хорошим алгоритмом. Вам нужен решатель DARP по той же причине? Ник
Ник Бацци

Ответы:

10

В pgRouting есть функция, которая называется DARP (Решение проблем с Dial-a-Ride) :

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

Подробнее о DARP и pgRouting:

Чтобы использовать эту новую функцию, вам нужно установить ветвь darp pgRouting .

Ответы на этот вопрос о stackexchange могут предоставить дополнительную информацию: алгоритм маршрутизации для нескольких транспортных средств с несколькими сбрасываниями .

Подземье
источник
Сначала я увидел алгоритм DARP, но перебрал его, так как не знал, что его можно использовать для курьеров. Похоже, это хорошо сработает! Жаль, что на странице документации нет примеров использования, хотя это может быть случай поиска исходного кода, чтобы увидеть, как он работает.
RichW
2

В pgRouting появилась новая функция для решения DARP: http://www.pgrouting.org/docs/1.x/darp.html.

dkastl
источник
Смотрите также некоторые объявления здесь: openvrp.com/blog/darp-algorithm-in-pgrouting
dkastl
Спасибо Дэниел, это отличная функция, которую вы там создали. Я не знал, что это может быть использовано для доставки, но это определенно выглядит осуществимым. Благодарность!
RichW
1

Хотя ESRI ArcLogistics явно не соответствует вашим конкретным потребностям использования PostGIS или открытого исходного кода, для тех, кто может не иметь навыков программирования или времени для реализации собственных решений, это хорошее готовое платное расширение для ArcGIS, которая предназначена для выполнения задач, которые вы описали.

В настоящее время они также предлагают 30-дневную бесплатную пробную версию, если вы хотите проверить это.

RyanKDalton
источник
На прошлой неделе я посетил ESRI HQ, чтобы обсудить это программное обеспечение для них, но оно, похоже, не отвечает нашим потребностям (требуется для работы на сервере, а также довольно дорого). Отличная часть комплекта, хотя!
RichW
Наш продукт FleetEngine работает как сервер с интерфейсом SOAP. 100 направлений, 5 автомобилей и временных окон определенно в пределах возможностей. Это очень близко к готовности к производству, свяжитесь со мной для получения тестовой лицензии. Он не с открытым исходным кодом и не бесплатный, но, с другой стороны, не такой дорогой, как ArcLogistics.
Uffe Kousgaard
1
Привет Уффе, может ли он учитывать ограничения транспортного средства (вес и габариты) и соответственно сортировать пакеты на транспортные средства? Кроме того, он работает в Великобритании и использует данные истории дорог для определения скорости и т.д.?
RichW
Да на все ваши вопросы. Он использует простые дополнения веса / объемов. Он также не может делать 3D-упаковку, на это было бы слишком много надежд. Полная поддержка уличных сетей также в любой стране, но вам необходимо предоставить уличную сеть. К сожалению, я не видел ответа раньше, я думал, что это обсуждение закончилось. Пингуйте мне по адресу uffe@routeware.dk, если хотите обсудить это дальше.
Уффе Кусгаард