Расчет времени в пути с использованием доступных географических API для адресов 5k +

Question

Я работаю над моделью транспортировки и собираюсь составить матрицу времени в пути между 5000 точками. Есть ли бесплатный, полу-надежный способ рассчитать время в пути между всеми моими узлами?

Я думаю, что у Google Maps есть ограничение на количество запросов / хитов, которые я могу достичь.

EDIT

Я хотел бы использовать API, такие как карты Google или аналогичные, поскольку они включают такие данные, как направление дороги, количество полос движения, указанную скорость, тип дороги и т. Д. *

РЕДАКТИРОВАТЬ 2

Обращаем ваше внимание на то, что данные карт openstreet неполные и доступны не для всех юрисдикций за пределами США.

Answer 1

Google Directions API ограничивает вас 2500 звонками в день . Кроме того, условия обслуживания предусматривают, что вы должны использовать эту услугу только «в сочетании с отображением результатов на карте Google».

Вас может заинтересовать OpenTripPlanner , проект в стадии разработки, который может выполнять мультимодальную маршрутизацию, и Graphserver , на котором построен OpenTripPlanner.

Один из подходов заключается в использовании OpenStreetMap данных с Graphserver для генерации деревьев кратчайшего пути из каждого узла.

Answer 2

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

Я знаю, что это грязно, но эй, вы пытаетесь оценить 12,5 миллионов точек данных (или любую другую сумму:)

Вы также можете постепенно добавлять знания из уже извлеченных "реальных""время в пути, находя точки, близкие к тем, которые вы ищете:

• получите ближайшие точки StartApprox, EndApprox к начальной и конечной позиции, так что у вас есть время перемещения между StartApprox и EndApprox
• вычисление расстояний StartError, EndError между start и StartApprox, end и EndApprox
• , если StartError + EndError> Distance (StartApprox, EndApprox) * 0.10 (или независимо от вашего порога) -> вычислить расстояние через API (и сохранитьэто), иначе используйте известное время в пути плюс время накладных расходов, основанное на StartError + EndError

(если у вас 100 адресов в Нью-Йорке и 100 в SF, все значения будут более или менее одинаковыми(т.е. разница между ними, вероятно, ниже, чем неопределенность, связанная с этими прогнозами) и такой подходбудет удерживать вас от выдачи 10000 запросов, где 1 будет делать)

Answer 3

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

Я бы, однако, немного поинтересовался вашей проблемой:

• Вам действительно нужны все 5000!расстояния в базе данных?Что делать, если вы запросили их у Google, так как они вам нужны, а затем кэшировали их (если позволили).У меня были такие веб-приложения, что из-за медленного нарастания трафика я смог использовать бесплатные сервисы на ранней стадии, чтобы проверить идею.
• Вам действительно нужны все 5000 баллов?Или вы могли бы выбрать 100 лучших и иметь более поддающуюся решению проблему?
• Возможно, есть какой-то гибрид, где вы храните расстояния между большими городами и делаете больше оценок для более коротких расстояний.

ОпятьЯ действительно не знаю, в чем ваша проблема, но, возможно, нестандартное мышление поможет вам найти более простое решение.

Answer 4

Поскольку это 12 502 500 подключений, я почти уверен, что вы достигнете какого-то ограничения, если попытаетесь использовать карты Google для всех из них. Насколько точные результаты вам нужны / как далеко вы путешествуете?

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

Answer 5

Многие программные пакеты ГИС имеют алгоритмы маршрутизации, если у вас есть данные ... Транспортные данные могут быть довольно затратными.

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

Вот несколько других вариантов быстрого поиска в Google: Wikipedia Route66 Грузовые мили