Решение коллективной версии задачи выбора маршрута транспорта - PullRequest
Новая
       55

Решение коллективной версии задачи выбора маршрута транспорта

2 голосов
/ 12 июля 2020

У меня проблемы с поиском алгоритма для следующей проблемы:

В неориентированном взвешенном графе с весами w должен быть доставлен один пакет из s в t. Все узлы графа считаются станциями. Каждая станция имеет определенный c тип транспортных средств с заданной скоростью v и пройденным расстоянием d. Транспортные средства должны работать коллективом, чтобы доставить посылку. Таким образом, если транспортное средство с текущим расстоянием движения 10 едет по краю груза 4, расстояние проезда будет сокращено до 6. Транспортные средства должны останавливаться на станции, если они не могут проехать по всему краю. Посылку можно передать на любой станции.

Мне нужно найти максимально быстрый путь (путем оптимизации расстояния / скорости), чтобы доставить посылку от s до t.

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

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

1 Ответ

2 голосов
/ 13 июля 2020

Я бы кодировал «состояние» как

  • узел n с пакетом
  • время, когда он прибыл туда
  • скорость и дальность полета автомобиля который вы использовали, чтобы добраться туда

Начальное состояние - пакет в s, время 0, автомобиль из s с полным диапазоном. Чтобы найти последующие состояния для данного состояния, вы должны следовать этому logi c:

  • для каждого e, исходящего ребра от n; и только если диапазон текущего автомобиля достаточен, создайте 2 новых состояния-преемника, n1 и n2, с 
node[n1] = node[n2] = target[e]
time[n1] = time[n2] = time[n] + length[e] / car_speed[n]
car_speed[n1] = car_speed[n]
car_range[n1] = car_range[n] - length[e]
car_speed[n2] = target[e].car_speed
car_range[n2] = target[e].car_range

Затем вы используете A * на этом, используя time как стоимость и подходящая эвристика c, а в конце вы найдете оптимальный маршрут и время. Поскольку я не уверен в выборе лучшего heuristi c здесь (время - это расстояние / скорость, но скорость зависит от машины ...), вы можете использовать null heuristi c, который может расширить больше узлов, чем обычно, но никогда не будет переоценить.

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

С точки зрения памяти, предполагая, что вас интересует только минимальное время для достижения цели и что ваша selected heuristi c либо нулевое, либо одновременно допустимое и непротиворечивое, вам нужно только сохранить не более 2*V открытых состояний для графа с V узлами, так как уже посещенные узлы никогда не нужно будет посещать снова (отметьте их где-нибудь, чтобы избежать их повторной обработки в случае повторного достижения), и поэтому старые состояния могут быть отброшены без вредных последствий.

[в предыдущей версии я смешивал стоимость и эвристику; Я отредактировал, чтобы уточнить, что я рекомендую null heuristi c и время как стоимость]

...