Конкуренты не дремлют!

[sashaan]

как использовать статистку и расчетные данные при наличии живых пробкоданных - это ИМХО очень большой вопрос.

 

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

[svlad2012]

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

А вот как использовать статистку и расчетные данные при наличии живых пробкоданных - это ИМХО очень большой вопрос.

 

 

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

Здесь По и Пд - соответственно погрешности скорости на ребре до проезда датчика и погрешность датчика, Vo и Vд - скорость на ребре до проезда датчика и скорость датчика.

Погрешность скорости на ребре после проезда датчика можно определить как:

 

Т.е. степенью "доверия" выступают погрешности - чем больше погрешность, тем менее можно доверять.

 

Из этих формул можно видеть, что если погрешность на ребре до проезда датчика была очень гораздо больше погрешности датчика, то новая скорость на ребре будет равна скорости датчика, а новая погрешность скорости на ребре - погрешности датчика. 

Если же скорость на ребре уже определена очень точно (т.е. ее погрешность гораздо больше погрешности датчика), то скорость на ребре и ее погрешность не изменяться.

Если погрешности одинаковы, то новая скорость - среднее арифметическое, а погрешность (точнее дисперсия) уменьшается в два раза.

 

Т.е. новая скорость и погрешность определяются в зависимости от степеней доверия и статистика здесь фактически - точка отсчета, "генетическая память".

 

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

 

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

[Vlad_SP]

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

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

[timvetrov]

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

Ну, про соломку, которую надо подстелить в нужных местах (как и про прикуп и Сочи), мы все с детства и без Пирса знаем.

Вопрос в том, как это сделать. И статистика в смысле пробок, боюсь, такого прогноза не дает.

 

Неожиданные пробки никто не отменял. А они-то как раз далеко выходят за доверительные интервалы.

Так что живые пробкоданные все равно приоритетны (ну, хотя бы в горизонте доезда 30-60 минут).

[faceless]

У 2ГИС датчиками являются машины автотранспортных предприятий-партнёров, так что там не только статистика. На мой вопрос о добавлении функционала решения задачи коммивояжера ничего конкретного не ответили.

[Vlad_SP]

Так что живые пробкоданные все равно приоритетны (ну, хотя бы в горизонте доезда 30-60 минут).

Ой, нет... Вот тут я бы не согласился.

Бесспорно, в интервале доезда 0...10 минут - безусловный приоритет у "живых" пробкоданных. Это, скажем так, для ближних ребер. Вероятность того, что за 5 минут ситуация на ребре в корне изменится - очень и очень мала. Она может немного улучшиться или ухудшиться, но - в подавляющем большинстве случаев немного..... В районе получаса - хм, не знаю.... А ближе к часу (т.е. для достаточно удаленных ребер) - никакого проку от "живых" пробкоданных уже нет. Через час, когда я туда доеду - пробкоданные давным-давно "протухнут". И либо средняя скорость на ребре вообще не изменится (назовем такие ребра "статическими", для них все равно, что использовать при расчете - статистическую скорость или "живые" пробкоданные, результат почти не изменится), либо - изменится очень сильно; а тогда от якобы "живых" пробкоданных, на основании которых час назад маршрут был построен именно через это ребро - проку никакого, эти пробкоданные давно устарели и не отражают текущую ситуацию. Вот здесь в предсказании будущего - и могла бы помочь статистика. У 2ГИС, кстати, в этом отношении грамотно сделано.

[arctec]

Хорошо, что над прогнозом работа идет (или запланирована)

Sent from my GT-N7000 using Tapatalk 4

[timvetrov]

Ой, нет... Вот тут я бы не согласился.

Ну, не будем спорить о конкретных цифрах. Не важно, 20-30 минут, 30-40 или даже 30-60. Тут вопрос принципа, насколько живые пробки нужны.

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

 

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

Допустим, с дачи два варианта - Киевское шоссе - КАД - Софийская либо Московское шоссе - Колпинское шоссе - Софийская. И до КАД ехать более часа.

По статистике, понятно, КАД между Пулковским шоссе и Софийской свободен. А по факту там, допустим, мега-пробка (ремонт).

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

 

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

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

[bushmen]

А по факту там, допустим, мега-пробка (ремонт).

 А может там, допустим, сейчас ДТП, которое разгребут за 20-30 минут и все там понесется? Пока что здесь больше вопросов, чем ответов. Да и статистика порой может уже коренным образом отличаться от действительности, особенно в крупных городах, где постоянно увеличивается количество транспорта или вводятся новые пункты в ПДД, которые влияют на дорожную ситуацию (например, введение выделенной полосы на дороге).

[sergeyastakhov]

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

 

Не то чтобы не годятся, просто для адекватного роутинга нужны данные именно из будущего. Когда мы просто приравниваем текущие данные этому будущему мы вносим соответствующую вероятность ошибки. И чем больше дистанция по времени - тем больше эта вероятность. Её можно попробовать уменьшить математическими методами с использованием статистики - собственно об этом и речь.

[svlad2012]

 

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

Слишком просто, чтобы работало  . Прогноза то нет!

 

Мы просто берем вариант по наихудшим скоростям на данный момент времени и строим неизвестно какой маршрут. Причем, не важно, что мы берем "будущую" статистику. Это всё равно, что при нынешнем алгоритме взять и заменить все зеленые улицы на желтые. Что мы получим? Этот маршрут будет еще чаще перестраиваться, т.к. кроме "локального" изменения пробочной информации, к пересчету будут приводить и замена статистики на пробочную информацию при подъезде к удаленному ребру. "Стратегически" этот маршрут будет более похож на прямую, чем нынешний, но совершенно не факт, что быстрее, т.к. изначально поведет "напролом", совсем не учитывая "повышенную" скорость на окраинах.

 

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

 

Если уж прогнозировать, то учитывая возможные причины пробок, например

1) слишком много транспорта развелось, неоптимальная работа светофора, ежедневный проезд кортежа по Петроградской в 8:50 и т.п.

2) Аварии, ремонты дорог, непериодический проезд слуга народа и т.п.

М.б. плюс к тому иметь модели нарастания/спада пробок, причем с разными параметрами для разных районов, например время приезда ГИБДД может отличаться в разы для разных улиц - на КАД 20 мин, в какой нибудь переулок - 4 часа.

 

Учет п.1 - это и есть статистика. Однако в голом виде ее тоже применять нельзя, т.е. нужна автокореляционная функция "статистики" во времени - степень зависимости средней скорости на ребре в момент времени X от средней скорости на этом же ребре в момент Y.

 

C авариями и пр. чуть сложнее - попал в пробку, делать нечего - такова судьба. Зато используя взаимокореляционные  функции скоростей на ребрах в пространстве и времени (степень зависимости скорости на ребре X в момент Y от скорости на ребре Z в момент W) можно предугадать нарастание/спад пробок на соседних с затором улицам. Например, если на КАД авария и пробка, то через 15 мин пробка уже на улицах около съезда, затем, если авария не устранена, она расползается далее по улицам. И наоборот, если пробка на улицах рядом со съездом уменьшается, значит и на КАД пробка рассасывается.

 

Но это уже слишком сложно, чтобы работало

[timvetrov]

Почему нет прогноза?

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

 

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

 

Приведу пример.

Допустим, есть альтернатива из Пулково на Чайковского - Пулковское шоссе/Московский или КАД/Витебский.

В 8:00 Витебский еще свободен, пробки перед Лиговским нет, поэтому тащит на него. А потом, когда формируется пробка после Благодатной, тащит на Московский всякими Цветочными улицами, - вместо того, чтобы сразу вести по Московскому.

Так вот.

Если в 8:00 скачаются пробки на участке после Благодатной на Московском и на Витебском, и они будут в рамках текущей статистики, то программа применит статистику на время прибытия (8:35), по которой Московский предпочтительнее. И СГ сразу поведет правильно.

А если данные по Московскому пр. (после Благодатной) на 8:00 будут значимо хуже и статистики на 8:00, и статистической ситуации на Витебском на 8:35, то они будут учтены, и программа поведет на Витебский.

[bushmen]

Если в 8:00 скачаются пробки на участке после Благодатной на Московском и на Витебском, и они будут в рамках текущей статистики

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

[svlad2012]

Почему нет прогноза?

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

 

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

 

Приведу пример.

Допустим, есть альтернатива из Пулково на Чайковского - Пулковское шоссе/Московский или КАД/Витебский.

В 8:00 Витебский еще свободен, пробки перед Лиговским нет, поэтому тащит на него. А потом, когда формируется пробка после Благодатной, тащит на Московский всякими Цветочными улицами, - вместо того, чтобы сразу вести по Московскому.

Так вот.

Если в 8:00 скачаются пробки на участке после Благодатной на Московском и на Витебском, и они будут в рамках текущей статистики, то программа применит статистику на время прибытия (8:35), по которой Московский предпочтительнее. И СГ сразу поведет правильно.

А если данные по Московскому пр. (после Благодатной) на 8:00 будут значимо хуже и статистики на 8:00, и статистической ситуации на Витебском на 8:35, то они будут учтены, и программа поведет на Витебский.

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

[IШIN]

Да и к тому же надо учитывать данные не "сейчас" и не "через час", а гибко - 

пробки на Пулковском берем текущие (без прогнозирования), на КАДе или Московском - на "через 10 минут", на Витебском на "через20 минут" и т.д. 

Офигенный пересчет получится...

 

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

Изменено 13 сентября, 2013 пользователем IШIN

[SMitri4]

Коллеги, что-то вы затроллили конкурентов в данной теме

обсуждение даже близко названию не соответствует.

Отправлено с моего Garmin-Asus A50 через Tapatalk

[timvetrov]

svlad2012, Вы сказали, что прогноза нет в моем алгоритме. Я лишь пытался показать, что прогноз есть, он основан на статистике.

Я не претендую ни на что, меня и так все устраивает.

 

Да, в офф-топик залезли, правда. 

[zoran]

Это не оффтоп.

Мы же не знаем, как конкуренты улучшают свои алгоритмы...

Если глобально, то направлений всего два:

Напихать датчиков во все, что движется. (Либо в дороги повсеместно)

И двигаться в сторону искусственного интеллекта, чтобы обрабатывал информацию от этих датчиков.

Это как раз побочный вариант деятельности Гугла, если у них получится.

[Kikujiro]

 тем временем вышло обновление NN для WM (8.5.0.35) 

[MonoRAil.kz]

и чо там? карты для замкадья появились приличные? поддержка "любительских" воскресла из пепла? нет?

досвиданья.

[SMitri4]

Появилась подписка на карты. Для разовых поездок по заграницам интересное предложение.

Отправлено с моего Garmin-Asus A50 через Tapatalk

[MonoRAil.kz]

подписка это супер. а карты, карты-то где? :lol:

[Kikujiro]

поддержка "любительских" воскресла из пепла?

одна бабка сказала, что таки ДА…

самое смешное, что уже давно вернули возможность использование самопальных карт. ЕМНИП, с версии 7.0.0.0... Попробуй. Мне не с чем.

 http://4pda.ru/forum/index.php?s=&showtopic=213964&view=findpost&p=26310217 

[MonoRAil.kz]

возможность вернули - хорошо. осталось картописателей вернуть

[Гость]

кому интересно тут могут почитать про бубны с нм2 -http://4pna.com/showthread.php?t=12364