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

Question

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

Вот примерная спецификация того, что яищу ..

• Маршруты должны быть рассчитаны быстрым и эффективным способом
• 100 + фургоны / 1000+ пакетов / 1000+ точек сброса могут быть обработаны за один раз
• Каждый фургон может быть разного размера и иметь разные ограничения по весу
• Каждый пакет может быть разного размера и веса
• Пакеты должны быть организованы на фургоны в честном и экономичномобразом, с учетом маршрутов, ограничений по весу и размеру
• Маршруты, по которым должны ездить фургоны, должны быть экономичными и максимально короткими (или настраиваемый баланс между ними)
• Фургоны могут бытьограничено определенными дорогами (низкие мосты, ширина, высота и вес ограничения)
• Некоторым пакетам могут быть предоставлены временные интервалы для доставки

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

Любые мыслибыл бы оценен!

Rich

Answer 1

У меня сложилось впечатление, что такого рода проблемы обычно возникают в Operations Research, и стандартный подход заключается в использовании решения для смешанного целочисленного программирования.Вот пример кодирования задачи планирования грузоперевозок с использованием MIP

. Очевидно, 15-летний опыт последних исследований в области MIP сделал современные решатели * в 1005 * 30000 раз быстрее, чем оригинальные.

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

Answer 2

pgRouting имеет новую функцию, реализующую генетический алгоритм для задачи Dial-a-Ride: http://www.pgrouting.org/docs/1.x/darp.html

Это расширение PostgreSQL / PostGIS, и вы можете с его помощью создать приложение.Он также имеет функции для поиска кратчайшего пути и т. Д.

Answer 3

Любой такой алгоритм будет закрытым, и вам, вероятно, придется что-то покупать.Однако это звучит подозрительно, как проблема, которую можно решить с помощью генетического алгоритма.Вот некоторые исследования, которые я нашел:

http://www.ijimt.org/papers/38-M415.pdf

http://www.springerlink.com/content/w3165x33n24v8610/ (книга, которая выглядит так, как будто она сфокусирована на вашей проблеме)1011 *

То, что алгоритм старый, не означает, что он неэффективен.