Как GraphHopper обрабатывает точку на пересечении шоссе?

Question

У меня 2750 городских центров в Бельгии. Мне нужно знать расстояния между каждыми 2 центрами города. Но в результате получается матрица размером 57 МБ, просто для запоминания этих расстояний (даже маршрутов), поэтому они ужасно масштабируются.

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

Таким образом, расстояние от 1 города А до другого города, не находящегося поблизости, можно рассчитать по расстоянию cityA -> hubX -> hubY -> cityB, Поскольку в большинстве городов обычно есть 3 хаба, мне может понадобиться просмотреть все 9 комбинаций и выбрать самую короткую. Но в любом случае лучше масштабировать память.

Теперь проблема:могу ли я описать пересечение шоссе как одну точку? Подумайте об этом: шоссе состоит из 2 дорог (по одной в обоих направлениях), поэтому центр пересечения шоссе имеет 4 дороги (даже не считая объездных дорог).

Answer 1

Некоторые идеи:

1. Вы можете хранить эти расстояния вне кучи или на диске через MapDB или GraphHopper, его упрощенные реализации DataAccess, делающие его независимым от RAM
2. Вы можете использовать float, который должен быть всего ~30 МБ или даже коротким, и просто использовать километры
3. Вы можете попробовать маршрутизацию по требованию без сохранения, так как для расчета маршрута требуется всего несколько мс. Отключение инструкций и начисление очков делает его еще в два раза быстрее. Вы даже можете отключить вычисление расстояния и просто использовать path.weight - это даст вам еще одно хорошее ускорение, но требует немного более низкого уровня использования GraphHopper и рекомендуется только в том случае, если вы знаете, что делаете.

Теперь к вашему вопросу. GraphHopper использует модель графа, состоящую из узлов (перекрестков) и ребер (улиц, соединяющих перекрестки). Тем не менее кольцевая развязка состоит из нескольких узлов. Но в целом должна быть возможность использовать такой "уходящий" узел, как "hub-id".

Я вижу два подхода для расчета этих узлов:

• либо запустив Contraction-Hierarchy и выбрав 1000 старших узлов и определив их как концентраторы - это будет похоже на то, что описано в документе " Маршрутизация транзитных узлов"
• или вы рассчитываете маршруты из одного города, например, во все другие города (или просто 8 географических направлений), и находите последние общие узлы двух маршрутов, чтобы идентифицировать некоторые

Для обоих подходов вам придется углубиться в GraphHopper, и вам, вероятно, понадобится API более низкого уровня.