OpenStreetMap
На самом деле, схема рутинга, на которой основаны многие программы, а именно оптимизация по минимуму времени доезда годится только для мегаполисов на грани транспортного коллапса (в которых при этом есть тысячи датчиков, от которых система получает скорости).
Для остальной России нужен другой алгоритм - нужно искать кратчайший маршрут но с условием ЕДИНСТВЕННОГО максимума классности.
Например, маршрут из пункта А в пункт B должен выглядеть следующим образом
service->residential (unclassified) -> tertiary->secondary->primary->trunk->primary->secondary-> tertiary->residential (unclassified)->service
Не обязательно должен быть достигнут высший уровень классности (trunk), и некоторые уровни могут отсутствовать, но максимум все равно должен быть один.
Например:
service->residential -> secondary -> unclassified.
Такой маршрут как раз и будет оптимальным - самым удобным и быстрейшим.
Как пример, если на пути лежит некий город, и есть два варианта - транзитом через город или по объездной, маршрут проложится по объездной. И не потому что якобы так быстрее, о чем никто разумеется не имеет никакого понятия, да и иметь не может, а потому что рутер не захочет снижать классность.
讨论
Zverik 于 2011年08月 8日 17:05 的评论
По твоему алгоритму Печоры—Остров osm.org/?lat=57.574&lon=28.003&zoom=10&layers=M нужно будет ехать через Псков, а не напрямую по асфальтовому primary.
Zverik 于 2011年08月 8日 17:06 的评论
То есть, Печоры — Пушкинские Горы, например. Когда в маршруте посередине несколько транков, но они образуют острый угол.
Sergey Gladilin 于 2011年08月 8日 18:21 的评论
+1 к Зверику. Я тоже подумал о таких случаях. Мне кажется, правильнее ставить за понижение классности большой, но все-таки не бесконечный штраф.
Zkir 于 2011年08月 8日 18:26 的评论
Маршрут Печоры—Остров кладется правильно - с небольшим заездом на транк в срединке.
А вот Печоры — Пушкинские Горы будут да, зигзагом через Псков. Но в этом как раз сама суть идеи, :) маршрут по транку в чем-то более *Магистрален* чем по примари, почему я собственно должен с него съезжать?
Для практического использования алгоритма, конечно, придется поразмыслить, как составить классы дорог из тегов осм.
Zkir 于 2011年08月 8日 18:33 的评论
Sergey Gladilin,
// Мне кажется, правильнее ставить за понижение классности большой, но все-таки не бесконечный штраф.
Штраф-то поставить не сложно, вопрос в том, во что его оценить.
Zkir 于 2011年08月 8日 19:20 的评论
Маршрут Печоры — Пушкинские Горы (через Псков) на 20% длиннее, чем через Палкино. 20% это достаточное превышение для снижения классности?
Zverik 于 2011年08月 8日 19:48 的评论
Так там не только в скорости дело! Транк идёт через город, поэтому там ограничения скорости, светофоры, плотный трафик. Объездную достроят лет через десять только.
Zkir 于 2011年08月 8日 20:12 的评论
//Транк идёт через город, поэтому там ограничения скорости, светофоры, плотный трафик.
Это все понятно. Вот такое у нас хреновое
летотранк. Что поделаешь? )Классификация дорог по значимости основана на некоторых предположениях о структуре дорожной сети, которые, как мы видим, не всегда выполняются.
Zkir 于 2011年08月 8日 20:17 的评论
Хорошо, какой, по твоему мнению должен класться маршрут? Кратчайший? Быстрейший (по ожидаемой скорости)?
Zkir 于 2011年08月 8日 20:23 的评论
... Классификация дорог по значимости основана на некоторых предположениях о структуре дорожной сети ..., в частности, о том, что чем выше классность, тем больше привлекательность для рутинга. А когда магистрали нужно объезжать огородами, это транспортный коллапс и есть.
Это я собственно и делаю по вечерам. Объезжаю ТТК (primary) по residential. Получается не очень, поскольку связность дорог низкая.
Sergey Gladilin 于 2011年08月 9日 00:06 的评论
// ... Классификация дорог по значимости основана на некоторых предположениях о структуре дорожной сети ..., в частности, о том, что чем выше классность, тем больше привлекательность для рутинга. А когда магистрали нужно объезжать огородами, это транспортный коллапс и есть.
Помнится, когда спорили, что такое класс дорог, ты выступал несколько с иной позиции - что класс нужен для генерализации, а не для рутинга... Для генерализации ситуации пересечения под острым углом действительно нормальны.
Для рутинга, возможно, надо еще посчитать число светофоров помимо числа понижений классности - это усилит 20% до 30, например... Казалось бы, дальше надо подбирать коэффициенты - просить людей проложить маршруты вручную на разных примерах и сооружать какую-то самообучающуюся конструкцию, которая бы подбирала коэффициенты на основе данных примеров. Тогда можно будет при необходимости добавить еще примеров и пересчитать коэффициенты.
Я вот только подумал, что если Печоры - Пушкинские горы - это только часть длинного маршрута, то эти 20% выигрыша могут превратиться в 2% (если остальной маршрут будет в 10 раз длиннее) - т.е. налицо странная ситуация - что локально оптимальный маршрут не является частью глобально оптимального - оттого, что когда ты едешь из деревни в деревню, вполне можно поехать по низкоклассной дороге для экономии 15 минут, а когда ты едешь из Москвы во Владивосток, то проще потратить эти 15 минут, чем съезжать с трассы...
Sergey Gladilin 于 2011年08月 9日 00:13 的评论
Вот, кстати, еще пример, когда понижение классности необходимо: маршрут Большие Извалы ( osm.org/?lat=52.5469&lon=38.7601&zoom=13&layers=M ) - Тамбов
Я подумал, что штрафовать понижение классности надо тем сильнее, чем меньше отношение длины понижения к длине кусков максимальной классности.
Zkir 于 2011年08月 9日 14:43 的评论
Генерализация и рутинг вовсе не противоположны друг другу (хотя опять же, какая модель рутинга). Когда я планирую маршрут со своей дачи в МО в Уральскую глубинку и рассматриваю обзорную карту, я ожидаю, что маршрут проложится - по крайней мере в своей большей, средней части - по тем дорогам, которые на данном масштабе ВИДНЫ.
А иначе в чем смысл ее обзорности? Так что ситуация "локально оптимальный маршрут не является частью глобально оптимального" совсем не странная, а напротив, довольно закономерная. И ты правильно изложил ее причины: ~ когда ты едешь из Москвы во Владивосток, то проще потратить эти 15 минут, чем съезжать с трассы ~
//маршрут Большие Извалы - Тамбов
Это хороший пример, но он говорит скорее о том, что у М4 и Р119 положение в дорожном графе примерно одинаковое - для целей данного алгоритма.
Старший уровень классности не может состоять только из радиусов, а иначе в самом деле придется из Больших Извал в Тамбов ездить через Москву.
В навигаторах транку и примари и в самом деле присваивается "примерно одинаковый" предельный масштаб отображения.
Когда классификация по важности еще не была принята, и борьба за нее только начиналась, обзорные карты выглядели ужасно, была сплошная мешанина из обрезков дорог. Идею "важности" удалось внедрить, но нынешняя классификация основана не на какой-то конкретной модели, а на довольно смутных интуитивных представлениях, о том, что же такое "важность", и на формулировках, которые удалось изложить на бумаге (например, что транк - это дороги "федерального значения", межрегиональные трассы, формирующие опорную сеть автодорог страны, по которым идёт дальний межрегиональный трафик )
) Главное, что тогда хотелось, это чтобы дороги исчезали на тех же уровнях, что и населенные пункты, которые эти дороги соединяют. Этого удалось добиться и это было большим достижением.
Так что я не в коем случае не призываю менять классификацию, просто хотелось понять как ее можно было бы использовать для рутинга)
Sergey Gladilin 于 2011年08月 9日 19:42 的评论
На мой взгляд пример "Большие Извалы - Тамбов" - это пример того, что кратковременное повышение классности до транка не должно влиять на прокладку маршрута - т.к. просто транки в этом примере используются не как транки, а просто как подъездные пути к населенным пунктам... Будь параллельно этим транкам низкоклассные дублеры - можно было бы отказаться от транков без особой потери качества. Это отличается от маршрута типа "Воронеж - Москва", где транк используется именно как транк.
Zkir 于 2011年08月 9日 20:18 的评论
//транки используются ... как подъездные пути к населенным пунктам
Используются - на здоровье, вопрос не в этом.
Вопрос - почему маршрут скажем Орел -> Тамбов "по транку" лежит через Москву. Спрашивается, какое особое свойство транка это выражает?
Sergey Gladilin 于 2011年08月10日 04:36 的评论
Я согласен, что транки - это, прежде всего, дороги в Москву. Но я не пойму, какой вывод ты из этого делаешь?
Еще одна пришедшая мне в голову мысль - отличать случаи кратковременного понижения классности (ехал по транку, срезал по грунтовке, продолжил по транку) от случаев кратковременного повышения (ехал по грунтовке, выехал на развязку транка, съехал с развязки на другую грунтовку - и поехал дальше по грунтовке).
Так вот, случаи кратковременного повышения, ИМХО, не должны наказываться в твоем "алгоритме единственного максимума классности".