Кратчайший маршрут без заданного пункта назначения в Google Maps V3?

Так что я просто изучаю javascript, чтобы связываться с API Google Maps. Мне было интересно, есть ли у кого-нибудь элегантное решение этой проблемы, с которой я сталкиваюсь.

Запрос маршрута Google Maps должен содержать три вещи (отправную точку, пункт назначения и режим перемещения). Мой режим путешествия всегда будет ВОЖДЕНИЕМ. Источник всегда будет там, где находится пользователь.

Однако пункт назначения должен варьироваться. У меня есть несколько путевых точек, и пользователь посетит их, и я хотел бы обеспечить максимально короткую поездку в зависимости от того, какие путевые точки выбраны и где находится пользователь, заканчивая маршрут в одной из путевых точек (например, ABC или ACB, но всегда Axx. ..Икс).

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

редактировать: с предложенным флагом optimizeWaypoints, установленным в true, это становится проблемой O (n) вместо O (n!), Но теперь у меня проблемы с выдачей слишком большого количества запросов за слишком короткий период времени.


google-maps javascript shortest-path driving-directions
person Crag    schedule 27.10.2010    source источник

Ответы (3)


arrow_upward
7
arrow_downward

В Google Directions есть настройка для предоставления оптимизированного маршрута (optimizeWaypoints — http://code.google.com/apis/maps/documentation/javascript/services.html#Directions), вы просто устанавливаете значение true в своем объекте маршрутов.

person Michal    schedule 27.10.2010
comment
Я сделал это, но я все еще вынужден установить пункт назначения. Я не могу просто установить для этого параметра значение true и отправить запрос на все мои путевые точки. Сейчас я работаю над тем, чтобы просто создать n маршрутов для n путевых точек, подав запрос A в качестве отправной точки, b-n в качестве пунктов назначения и все путевые точки за вычетом пункта назначения для каждого маршрута. Это дает мне маршрут, для которого я могу рассчитать расстояние, и сейчас собираюсь провести серьезное тестирование, чтобы увидеть, работает ли это для любого приличного количества путевых точек. - person Crag; 28.10.2010
comment
Хорошо, решение, которое я использовал, было основано на этом ответе, поэтому оно получает галочку. То, что у меня есть сейчас, это мои путевые точки, а также какое-то ДЕЙСТВИТЕЛЬНО далекое место. Я отправляю все свои путевые точки в своем запросе, позволяю Google найти оптимальный маршрут для этих путевых точек от моей начальной позиции до дальнего пункта назначения, а затем вывожу вновь заказанные путевые точки. Затем я устанавливаю конечную путевую точку в качестве нового пункта назначения и запускаю другой запрос с набором путевых точек, теперь содержащим на одну путевую точку меньше. Это дает мне маршрут, который я ищу. - person Crag; 28.10.2010
comment
У меня та же проблема, мне нужно рассчитать лучший пункт назначения вместе с другими точками. Мне понравилось ваше решение. Спасибо. - person Douglas Lise; 30.01.2013
comment
@Crag Разве расположение дальнего пункта назначения не влияет на порядок, в котором путевые точки возвращаются в первом запросе? Например. если дальний пункт назначения находится на юге, не будет ли последняя путевая точка самой южной? - person JobJob; 23.05.2013
comment
Я просто хотел добавить свои 2 цента к этому обсуждению. Я столкнулся с похожей ситуацией, и я думаю сначала использовать API матрицы расстояний для оценки самой дальней путевой точки от моего источника. Я думаю, что это может быть лучшим кандидатом для установки в качестве пункта назначения, чтобы все другие путевые точки могли идеально вписаться в исходную и самую дальнюю путевую точку. Надеюсь, это сработает для меня. - person Mudasser Mian; 07.03.2017

arrow_upward
3
arrow_downward

Если вам нужен кратчайший маршрут, вы можете сначала позвонить в Google DistanceMatrix API и получить список остановок.

Затем вызовите направления API со списком сортировки.

person oskarko    schedule 19.09.2016

arrow_upward
0
arrow_downward

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

person Raffael Cavaliere    schedule 05.04.2019