Как стать автором
Обновить

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

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

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

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

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

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

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

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

image

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

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

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

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

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

image

Читать дальше →
Всего голосов 62: ↑50 и ↓12 +38
Просмотры 18K
Комментарии 25

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

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


Слайды к докладу
Всего голосов 43: ↑41 и ↓2 +39
Просмотры 17K
Комментарии 16

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

Блог компании Яндекс Data Mining *Геоинформационные сервисы *Машинное обучение *

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



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


Всего голосов 55: ↑53 и ↓2 +51
Просмотры 17K
Комментарии 22

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

Автомобильные гаджеты Урбанизм
Перевод

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

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

Ненормальное программирование *Python *Математика *Урбанизм
image

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

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

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

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

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

Математика *Научно-популярное Физика
Перевод

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

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

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

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

Блог компании ua-hosting.company Математика *Научно-популярное Биотехнологии Экология


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