Форма идеальна для реального. Dijkstra в логистике

Question

У меня есть программа для транспортной компании, где оптимальный маршрут рассчитан компанией Dijkstra. Города как вершины и маршруты как ребра. Найти вес края. Я связал города на карте с линией и измерил ее. Тогда я принимаю это как вес края. Но в реальной жизни маршруты не прямые. Итак, как я могу это исправить? enter image description here

В моем проекте я должен решить проблему с созданием программного обеспечения. Может ли кто-нибудь дать мне понять, что решать?

Answer 1

Как вы уже выяснили, проблема не так проста, как может показаться. Прежде всего, соединение только крупных городов - плохая идея, поскольку они, вероятно, не связаны напрямую с автомагистралями (если это не США или что-то еще).

Это текущая идея:

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

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

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

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

• как-то отрезать некоторые данные о фактических способах достижения точки B от точки A; хорошие ссылки: Google Maps API или Bing Maps API;
• собирать небольшие города на пути с поиском реальных путей мира от точки А до Б;
• попытайтесь выяснить, что ограничение скорости, где (если есть база данных для него)

На самом деле, вы можете пойти на полный в любой Google Maps или Bing Maps и просто позволить им предоставить вам лучшие дороги возможных , У них обоих есть фактические данные о любой дороге, в которой вы нуждаетесь. Невозможно собрать столько данных, сколько они есть. У вас есть все на тарелке, если вы чувствуете, что так вы можете это сделать.

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