Статистика пробок - предложение по улучшению

[КокаКола]

"В связи с этим есть такое предложение об улучшении пробочного сервиса.

Сейчас, насколько я понимаю, для улиц с неизвестным траффиком при расчете маршрута берется некая среднестатистическая скорость для данной улицы. Это уже неплохо, но можно, как мне кажется, сделать лучше.

Дело в том, что между пробками на улицах существует значительня корреляция - зная, с какой скоростью едет некоторая улица, можно предсказать, как едут соседние с ней. По этой корреляции можно собрать статистику (что-то вроде: если Шереметьевская свободна, то и на Алтуфьевском шоссе, вероятно, рабочее движение, а если на Варшавском шоссе пробка, то непременно стоит и съезд на него с 3-го кольца). Собранная статистика даст возможность предсказывать скорость на улицах, по которым нет данных, основываясь на тех улицах, по которым данные есть.

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

 

Собственно, чуть более примитивный, но легкий в практической реализации способ уже существует:http://www.findpatent.ru/patent/248/2484533.html

[sbelka]

"В связи с этим есть такое предложение об улучшении пробочного сервиса.

Сейчас, насколько я понимаю, для улиц с неизвестным траффиком при расчете маршрута берется некая среднестатистическая скорость для данной улицы. Это уже неплохо, но можно, как мне кажется, сделать лучше.

    ...

 

Собственно, чуть более примитивный, но легкий в практической реализации способ уже существует:http://www.findpatent.ru/patent/248/2484533.html  

 

 

Hi! Пожалуйста наберите в поиске "индекс Шпорта" и посмотрите, что там написано.   и когда

С уважением Serg.

Изменено 2 сентября, 2013 пользователем sbelka

[IШIN]

Hi! Пожалуйста наберите в поиске "индекс Шпорта" и посмотрите, что там написано.

Не совсем  согласен. Индекс Шпрота касался прежде всего, по-моему, отношения пробкоскоростей и скорости конкретного водилы (меня), то есть приведения статистических скоростей к моей манере езды (то ли я ездю на 20% быстрее среднего юзера, то ли ползу на буксире в среднем в два раза медленнее остальных). Либо этот индекс предлагался для пропорционального снижения скоростей на всех ребрах.

А то, о чем говорит КокаКола,  - касается определенных связок магистралей. Например, есть две одинаковае параллельные дороги. Люди не дураки, и дороги загружаются почти одинаково. Вот и предлагается, проанализировав статистику, связатиь некоторые ребра друг с другом определенными зависимостями.

"Но черт возьми, Холмс..."©Др.Ватсон

Не представляю себе реализацию.

Вот на одной из таких дорог вдруг датчики оставили 30 кмч, а на другой - 70.

И кого к кому приводить? считать, что раз одна свободна, то и на второй все чисто?

Или наоборот - на первой забито, наверняка и вторая стоит (или вот-вот забьется)?

Сейчас СГ считает правильнее - "может, на одной ДТП, а вторая как ехала, так и едет. Пока никто там не влип, считаем, что там все чисто".

Мне кажется, что "корреляцию" может быть целесообразно использовать в городах с 10 датчиками. Но не делать же для них отдельную программу.

 

ПС - естественно, мой старческий пессимизм не отменяет того, что над идеей стОит подумать.

[svlad2012]

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

 

А так, вначале я понял, что имели ввиду в первую очередь прогноз пробок, т.е. построение маршрута не по актуальным данным, а с учетом времени доезда до отдельных ребер.

Т.е. если я еду далеко, а где-то пробка растет, то:

1) прогнозируется скорость ребер на тот момент, когда я там могу быть, а не сейчас

2) если начинаются затруднения движения по одному ребру (индекс скорости падает), то существует некоторая вероятность, что на "параллельном" ребре индекс скорости тоже начнет падать к моему приезду.

[КокаКола]

Пожалуйста наберите в поиске "индекс Шпорта" и посмотрите, что там написано.   и когда

Некоторые варианты по сути весьма похожи.

А по поводу "когда" один умный человек сказал:"Если тебе в голову пришла хорошая идея, ты должен объяснить, почему никто не пришел к этому раньше. Если тебе не удалость это сделать, то - либо идея неправильная, либо ты плохо искал."    .  Видно, эта идея правильная. И вполне возможно, что уже используется в каких-нибудь навигационных системах.  

Изменено 2 сентября, 2013 пользователем КокаКола

[IШIN]

Предложение было для ребер с отсутствием данных

...

2) если начинаются затруднения движения по одному ребру (индекс скорости падает), то существует некоторая вероятность, что на "параллельном" ребре индекс скорости тоже начнет падать к моему приезду.

Да, я неудачно привел пример с оставленными скоростями, но сути это не меняет. Пусть по одному ребру скорость падает, но некоторая вероятность - это такая размытая штука... А еще - как связать эти изменения? Ведь не пропорционально же. Вот например, два параллельных ребра, абсолютно аналогичных по скоростным характеристикам. На одном - пробка со скоростью около 0 (ДТП, полностью перекрывшее движение). А на втором ребре? по логике, на нем скорость снизится в 2 раза (это ребро примет на себя вынужденних объездчиков). Но если где-то рядом есть еще ребра - то начинается некоторое распределение потоков...

Еще пример - два паралельных ребра.

На одном (1) "среднестатистическая скорость потока" aka скоростной индекс 40, на другом (2) - 60.

На ребре 2 была скорость датчиков 80, потом возникла пробка 20 км/ч.

Какую скорость поставить на ребро 1, предполагая, что там образуется аналогичная пробка?

20?

20/60*40=13? (пропорционально индексам)

20/80*40=10? 

(20/80)*(80/60*50)=16? (считая, что до коллапса по 1 ребру ехали с таким же превышением, как по 2).

А в итоге через 3 минуты какой-нибудь датчик оставит след, и будет реальная скорость. Вот и вопрос - нужно ли городить такой алгоритм, или проще дождаться данных.

При равномерном "запробочнивании" всего города - система "пропорционального торможения" ИМХО будет работать. А при фиксации локальных внезапных траблов - сомневаюсь.

[КокаКола]

При равномерном "запробочнивании" всего города - система "пропорционального торможения" ИМХО будет работать. А при фиксации локальных внезапных траблов - сомневаюсь.

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

[svlad2012]

 Вот и вопрос - нужно ли городить такой алгоритм, или проще дождаться данных.

 

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

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

 

Первоначально на ребре пробкоданных нет, а скоростной индекс равен статистики. Погрешность скоростного индекса - большая, охватывает весь диапазон возможных скоростей  (пусть она будет 60 км/ч).

Проехал какой-то датчик. 

Вначале проверяется его "истинность", т.е. лежит ли его скорость в заданном диапазоне - скоростной индекс с учетом погрешности. Если датчик не "истинен", например, его скорость 120 км/ч для центра города, то он отбрасывается. Если подходит, то рассчитывается новое значение скоростного индекса и его погрешность.

Расчет нового скоростного индекса ведется с учетом весовых коэффициентов, определяемых величиной погрешности - чем меньше погрешность, тем "более значимый вклад" дает эта величина в результирующее значение. К примеру, если исходный скоростной индекс был 30 км/ч с погрешностью 60 км/ч, а датчик проехал со скоростью 50 км/ч, причем его погрешность определена как 5 км/ч, то новый скоростной индекс будет 49,5 км/ч (цифры условны). А если первоначальная погрешность скоростного индекса была 30 км/ч, то новое значение будет 45 кмЧ. Т.е., если погрешности несоизмеримы, то берется самое точное значение, а если соизмеримы - то некоторое усредненное значение.

Аналогичным образом рассчитывается и погрешность нового скоростного индекса - он всегда меньше меньшего (если не принимаются дополнительные ограничения), но насколько опять зависит от соотношения исходных погрешностей: если несоизмеримы - фактически это наименьшая погрешность, если одинаковые - то результирующая погрешность в 1.41 раза меньше.

Далее, в процессе "ожидания" нового датчика погрешность растет во времени, например на 1 км/ч за каждые 10 мин для учета отсутствия данных (по идее, при этом и скорость должна "ползти" к статистике). Т.е. если мы имеем после проезда датчика скорость на ребре 45 км/ч и ее погрешность 15 км/ч, то через полчаса, когда проедет новый датчик, погрешность на ребре будет 18 км/ч.

Новый датчик проехал - скорости и погрешности уточнились.

 

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

 

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

 

Так что теоретически, идея вполне осуществима и самое сложное здесь - "снятие" кореляционных зависимостей, думаю, это как минимум на порядок сложнее сбора статистики.

 

Ну, как то так...