Pull to refresh

Алгоритм устранения пробок для автомобильного интернета

Decentralized networks *
Производители автомобилей вовсю ведут тестирование пиринговых систем связи между автомобилями по WiFi, на которых будет построены сети связи V2V (vehicle-to-vehicle). Подобные сети могут кардинально улучшить ситуацию на дорогах, если автомобили начнут передавать друг другу информацию о загруженности трасс, о пробках на дорогах, о сигналах светофора и т.д. На перекрёстках автомобили могут сверять свои траектории, обмениваясь данными в реальном времени. Создание сети V2V принципиально важно для нормальной работы автопилотов, которые в будущем заменят живых водителей и должны координироваться с другими автомобилями.

Технически сеть V2V можно поднять уже сейчас, но основная проблема — программное обеспечение. Каковы оптимальные алгоритмы и оптимальная скорость транспортных средств в потоке? Как должны координировать своё движение роботы-автомобили, если их на дороге будет большинство? Над одним из аспектов этой проблемы работают учёные из Сеульского университета, которые опубликовали научную работу Dissolution of traffic jam via additional local interactions (PDF). Они создали алгоритм для V2V, который гарантирует очень быстрое устранение пробок на дороге за счёт обмена информацией и мгновенного изменения скоростного режима всех автомобилей перед пробкой и после пробки.
Читать дальше →
Total votes 28: ↑24 and ↓4 +20
Views 3K
Comments 17

Как устроен краткосрочный прогноз на Яндекс.Пробках

Яндекс corporate blog Data Mining *Algorithms *
Информация о пробках появилась на Яндексе в 2006 году. Начинали мы с необходимого — научились строить схему загруженности городских улиц и учитывать текущую ситуацию при прокладывании маршрутов. Автомобилисты, ориентируясь перед выездом на эту информацию, уже могли сэкономить время в пути:
image

Затем, чтобы помогать водителям непосредственно во время движения, мы добавили в мобильные Яндекс.Карты (и, как следствие, в Яндекс.Навигатор) автоматическое перестроение маршрута. Приложения научились адаптировать маршрут при каждом заметном изменении ситуации в городе.

Собрав на десктопе и в мобильном информацию про «сейчас», мы перешли к решению вопроса «а как будет потом?»:
image

Первым шагом стала статистическая карта пробок — на ней можно посмотреть, как в среднем стоит и едет город в конкретный час конкретного дня недели. Мы предполагали, что у карты «обычных» пробок может быть полезный побочный эффект — возможность по ним спрогнозировать заторы на ближайшее время. Но практика показала, что усреднённая картина помогает примерно спланировать только, например, завтрашнюю поездку в аэропорт — но не помогает выезжающим сейчас избежать новых пробок. По нашим измерениям, даже в конце часового маршрута картина пробок на момент выезда обычно ближе к фактической, чем усреднение:

image

Неделю назад на Яндекс.Картах появилась возможность посмотреть изменения пробок в ближайший час — следующий наш шаг в решении вопроса про будущее. Для тех, кто в этом году не смог приехать на Yet another Conference, мы сегодня расскажем, что у нашего прогноза внутри, и как оно там оказалось.
Переходим к подробностям!
Total votes 133: ↑128 and ↓5 +123
Views 74K
Comments 131

Московские пробки с высоты месячного полета

Gadgets IT-companies
Мне захотелось пойти дальше и сделать нечто, что позволило бы оценить загруженность дорог не с позиции «здесь и сейчас», а в целом за месяц. Иначе говоря, ответить на вопрос «какова в целом дорожная ситуация и как она зависит от времени года».

В итоге получился график, который отражает что происходило с дорожной ситуацией в течении месяца. По горизонтальной оси расположены часы, по вертикальной даты. Цвет показывает загруженность дороги по 10-ти бальной шкале. Одна «строчка» этого графика соответствует общей дорожной ситуации в течении дня.

Например так выглядит октябрь:

image

Читать дальше →
Total votes 62: ↑50 and ↓12 +38
Views 18K
Comments 25

Математическая модель для прогнозирования пробок. Семинар в Яндексе

Яндекс corporate blog Algorithms *Geoinformation services *
Для качественного построения маршрутов в городских условиях нужно как можно более точно оценивать время движения по маршруту. При этом желательно учитывать не только текущую ситуацию, но и то, как она может измениться. Пару лет назад мы уже публиковали пост о прогнозировании ситуации на дорогах. Текст позволяет составить общее представление об этой теме. Более подробно вопрос прогнозирования пробок рассмотрел в своем докладе Михаил Хохлов. Он рассказал о различных математических подходах к прогнозированию дорожных затруднений на ближайшее время, в том числе и о методе линейной авторегрессии, который используется в Яндекс.Пробках. С тех пор многое изменилось, однако основные проблемы и методы их решения остались прежними и заслуживают внимания.


Слайды к докладу
Total votes 43: ↑41 and ↓2 +39
Views 17K
Comments 16

Выявление проблем дорожной сети с помощью Яндекс.Пробок. Лекция в Яндексе

Яндекс corporate blog Data Mining *Geoinformation services *Machine learning *

Яндекс.Пробки и связанные с ними функции в Навигаторе и Картах работают благодаря данным о скорости машин на разных участках дорог. Это совсем не новая, но по-прежнему эффективная схема. Вопрос, возникший уже по мере развития Пробок — можно ли использовать указанные данные как-нибудь ещё?



Аналитик Карт Леонид Медников рассказал о примере такого использования на конференции Яндекса «Пути Сообщения 2016». Под катом — расшифровка доклада и большинство слайдов.


Total votes 55: ↑53 and ↓2 +51
Views 17K
Comments 22

Одного автономного автомобиля достаточно, чтобы предотвращать фантомные пробки

Car Gadgets Urbanism
Translation

Фантомные пробки (заторы на дорогах, образующиеся без какой-либо видимой причины) — настоящее бедствие крупных городов. Некоторые предлагают бороться с ними сознательным методом, поддерживая постоянную среднюю скорость. Не знаю, как вы, но я каждый день убеждаюсь, что способ не работает. Возможно, проблему получится решить, только когда на дорогах станет больше подключенных автомобилей. Под катом — перевод статьи Wired о двух исследованиях, связанных с подключенными автомобилями и фантомными пробками.
Читать дальше →
Total votes 16: ↑15 and ↓1 +14
Views 18K
Comments 114

Снижает ли скорость снижение скорости?

Abnormal programming *Python *Mathematics *Urbanism
image

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

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

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

А когда наступает такая ситуация, нет ничего лучше, чем отбросить чужие эмоции и призвать двух беспристрастных помощников — матана и Питона.
Читать дальше →
Total votes 76: ↑70 and ↓6 +64
Views 42K
Comments 770

Почему дорожное движение внезапно превращается в пробку

Mathematics *Popular science Physics
Translation

Одним из самых непонятных явлений в автомобильной поездке становятся внезапно возникающие фантомные пробки. Большинство из нас с этим сталкивалось: машина перед вами внезапно тормозит, заставляя тормозить вас, что заставляет тормозить водителя за вами. Но вскоре вы и окружающие вас машины снова ускоряются до исходной скорости, и становится очевидно, что на дороге нет ни видимых препятствий, ни заметных причин для замедления.

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

Так что же происходит? Для ответа на этот вопрос математики, физики и инженеры-транспортники разработали множество различных видов моделей трафика. Например, микроскопические модели вычисляют пути отдельных автомобилей и хорошо подходят для описания взаимодействия единичных машин. Макроскопические модели описывают трафик в виде жидкости, а машины в ней интерпретируются как частицы жидкости. Они эффективны при изучении крупномасштабных явлений с участием множества автомобилей. Наконец, клеточные модели разделяют дорогу на сегменты и предписывают правила, по которым машины движутся из клетки в клетку, создавая структуру для описания неопределённости, присущей реальному дорожному движению.
Total votes 43: ↑42 and ↓1 +41
Views 26K
Comments 66

Коллективное движение: как ученые муравьиные пробки изучали

ua-hosting.company corporate blog Mathematics *Popular science Biotechnologies Ecology


Как сейчас помню, утро буднего дня, спешишь на учебу. Подходишь к остановке общественного транспорта, смотришь на толпу людей, напоминающую в своих движениях марш пингвинов. Смотришь на дорогу, где велосипедист идет рядом со своим велосипедом быстрее, чем движутся машины. Понимаешь, что ловить тут нечего, разворачиваешься и идешь пешком. Пробки есть везде: на дорогах они тренируют буддийское терпение у водителей, а в общественном транспорте позволяют провести занятие по йоге, хотите вы того или нет. Основной причиной задержек в движении является наличие слишком большого числа транспорта или людей для конкретного пути движения, который не может справиться с таким потоком. Среди представителей дикой природы тоже случаются большие скопления особей, и каждый вид борется с пробками своим уникальным методом. Одними из лучших в вопросах организованности и кооперации по праву называют муравьев. Эти маленькие трудоголики живут в многотысячных, а то и в многомиллионных колониях, но при этом не испытывают никаких «прелестей» пробок. Естественно, возникает вопрос — как они это делают? Именно на этот вопрос искали ответ ученые из университета Аризоны (США) и Тулузы (Франция). Как именно муравьи борются с пробками и какие из их методов можно применить нам, а какие — нет? Об этом мы узнаем из доклада исследовательской группы. Поехали.
Total votes 15: ↑14 and ↓1 +13
Views 4.7K
Comments 2