Вот заинтересовался, чисто для себя, как можно замутить прокладку маршрута.
Подскажите, что можно почитать на эту тему, что уже есть готового? Может кто-то делает что-то свое?
В общем, не нужно готового (только если для примера), а нужен пинок в нужную сторону 
ИМХО, волновой алгоритм на графе.
Ну и конечно http://en.wikipedia.org/wiki/Pathfinding и далее по ссылкам.
Для волнового алгоритма нужна весовая функция - в случае графа для карты обычно берут расстояние как вес ребра для кратчайшего маршрута. Для минимального по времени уже придётся считать скорость - с учётом транспортного средства, типа дороги, поверхности и т.п.
Не знаю, насколько волновой алгоритм хорош 1) для огромного графа, коим является OSM, 2) для поиска не только наилучшего, но и 2-3-го маршрута.
Сам делал в основном на сетках (лабиринты и т.п.)
почти все проекты ОСМ иль рядом стоящие опен сорс.
тот же http://map.project-osrm.org/ The Open Source Routing Machine (OSRM)
оооо… OSRM - мощная штука…
Алгоритмы для прокладки кратчайшего маршрута на взвешенном графе представлены двумя вариантами:
- Алгоритм Дейкстры
- Алгоритм A*
A* использует предсказание оставшегося пути, за счет чего работает быстрее (но неточно).
Гугл знает много на обе темы.
- Сейчас тоже обдумываю задачу построения маршрута.
Собственно, с учетом весов нужен не волновой алгоритм, а алгоритм Дейкстры. В свое время делал такое как раз с учетом разных весов ребер - на Pentium MMX 166 заливал все поле расстояниями до заданной точки за 30 мс. А ребер там было более 130 тысяч. У ОСМ в пределах local.osm т.е. PA+Украина+Беларусь+…+…+… порядка 10 млн ребер. Исходя из того, что процессоры сейчас примерно раз в 10-20 быстрее, максимальное воремя построения маршрута по полному графу можно оценить 0.2 с. На мобильных устройсвах - порядка секунды.
Это, правда, при условии хорошо оптимизированного алгоритма на Ассемблере. В противном же случае имеет смысл строить 2 дорожных графа - полный и только primary&trunk и решать задачу по шагам:
1a. Нахождение ближайшей точки в графе p&t к началу маршрута.
1b. Нахождение ближайшей точки в графе p&t к концу маршрута.
1с. Нахождение части пути в пределах p&t. - Соавнение длины 1c с некоторой эмпирической константой (порядка размера области), после чего решение, что делать дальше: 3 или 4. (Примечание - с некоторой долей приближения можно выполнить 1-й шаг и без построения маршрута - только по расстоянию между точками и этот результат использовать на шаге 2)
- При малой длине маршрута пересчитать его по полному дорожному графу - благо, в расчетах будет использована лишь малая часть последнего.
- При большой длине рассчитать несколько фрагментов маршрутов по полному графу от каждой из конечных точек до нескольких узлов маршрута p&t, начиная от ближайшей и приближаясь к противоположной точке, оптимизируя при этом полную длину: исходная точка - въезд на p&t - маршрут по p&t - съезд с него - конечная точка.
Навитель, в атласе OSM на PNA 600МГц, прокладывает маршрут между 2-мя областями расстоянием около 400 км
ну очень долго. Где-то на 3-и! порядка дольше секунды.
Osmand на “Андроиде” 1000МГц строит тот-же маршрут быстрее, но то-же порядка на 2-а дольше секунды.
…
20 минут и 1,5 минуты?
Сейчас специально перепроверил.
Osmand~, одна из последних “ночных сборок”, маршрут между 2-мя точками, от С-Пб до н/п в Вологодской обл.
с расстоянием по прямой в 307 км, прокладывал 4-е минуты, но … так и не проложил.
Раньше прокладывал. 
От н/п Юшково (на трассе М18) Лен. обл. , с расстоянием по прямой 214 км, маршрут прокладывался 75 с .
Но ведь порядки бывают не только десятичные. :3
Имелись ввиду именно десятичные порядки (относительно секунды).
…
Вот, рассмотрено несколько алгоритмов: Задача о кратчайших путях
Считается mauvais ton отвечать на сообщение, не дочитав его до конца.
Цитирую ту часть своего сообщения, до которой Вы не дочитали:
В принципе один порядок могу накинуть за счет памяти:
- время доступа к памяти динамического типа сократилось за рассматриваемый интервал времени гораздо менее чем выросла чакстота процессора,
- при на 2 порядка больших объемах данных существенно меньшая часть обмена приходится на быструю кэш-память и большая - на медленную из основного объема.
Зря паритесь. Дочитал я сообщение.
Просто привел примеры из реальности. На поп программах каждый владелец может проверить скорость
прокладки маршрута, в разных местах и на разные расстояния.
А часть вашего сообщения процитировал для масштаба, тык скыть для соизмерения возможного и реального.
Вполне возможно, что графы не оптимальны или алгоритмы не оптимизированы.
В Навителе скорость по родным картам в формате NM3 выше, чем по картам OSM в формате NM2.
Хотя родные карты по дефолту в PNA вне городов менее детальны, чем OSMовские.
Соответственно у них и граф может быть попроще.
…
(Помнится в программе “Rusa 3D” маршрут прокладывался довольно шустро. Без проблем прокладывал
маршрут от С-Пб до Тюмени. Правда в те времена и карта OSM была попроще. К востоку от Москвы.)
Там начали генерализировать граф, как испокон веков делалось во взрослых программах (например томтом, сиджик, igo). Народ жаловался на скорость прокладки маршрута - они и реализовали. С попутным отрезанием формата nm2, чтобы больше не было жалоб “ваша программа медленно работает”.
OSRM может и хорош, но не умеет прокладывать маршрут с промежуточными точками, что сильно расстраивает.
До этого пользовался гуглокартами, но так как на навигаторе использую карты OSM , которые достаточно хороши, но все же не особо имеют данных о маленьких городах.
Решил по участвовать в заполнении карт OSM, ну и соответственно перейти на планировку маршрутов по картам OSM.
Вот мои выводы:
map.project-osrm.org - не умеет работать с промежуточными точками
http://www.yournavigation.org - умеет работать с промежуточными точками , имеет экспорт в форматы .gpx и .wpt , но нельзя изменить маршрут перетаскивая проложенную дорогу как в гугле.
http://www.openrouteservice.org/ - вроде как можно устанавливать промежуточные точки, но прокладка почему то идет все равно по 2м точкам
http://mgorka.info/by/router.html - не умеет работать с промежуточными точками
http://open.mapquest.com - умеет работать с промежуточными точками, умеет изменять маршрут перетаскиванием
http://maps.cloudmade.com/ - не вызывается меню поиска
В общем я для себя нашел что искал, это сервис http://open.mapquest.com, надеюсь и вам пригодится
Почему не умеет? Тыкаете в линию маршрута и тянете в сторону - получается промежуточная точка.
А что подразумевается под “не умеет прокладывать маршрут с промежуточными точками”?
http://osrm.at/6Sq
ну скажем когда в моем случае нужно отметить
Отправка Ошмяны
Загрузка Вильнюс
Растаможка Браслав
Назначение Ошмяны
Проложите мне такой маршрут, когда в OSRM можно только 2 точки задать изначально, а в гугле и open.mapquest.com все 4 задаешь, да и если нужно маршрут движение от точки к точке можно изменить перетягиванием выбирая нужную мне дорогу.
Ну перетягиванием можно и в осрм поменять маршрут, а то что нет авто добавления еще одной строчки при введенных двух - не догадались видимо что это нужно.
BuxarNET, эт мы не к тому что вы что-то не так делаете, нравится мапквест - пользуйте мапквест.