Задача и данные

Описание задачи

Задача конкурса «Интернет-математика 2010» — прогнозирование загруженности автомобильных дорог на основе предыдущих наблюдений. В рамках конкурса мы распространяем граф московских дорог и данные наблюдений — скорость транспортного потока на отрезках улиц в течение месяца. Задача участников — предсказать загруженность дорог в последний день месяца.

Данные

Данные, распространяемые в рамках конкурса, состоят из двух частей: граф дорог и данные о пробках (загруженности дорог).

Граф дорог

Перекрестки Москвы соответствуют вершинам графа, а отрезки улиц — дугам (улице с двусторонним движением соответствуют две разнонаправленных дуги). Граф дорог отличается от «естественного» графа улиц тем, что в нем продублированы некоторые вершины и дуги, чтобы учесть правила дорожного движения: запрещенные повороты и проезды. В преобразованном таким образом графе все маршруты разрешены. Описание графа содержится в трех файлах: vertices.txt (описание вершин), edges.txt (дуги) и edge_data.txt (характеристики улиц-дуг).

В файле vertices.txt перечислены все идентификаторы вершин (первая колонка) с указанием принадлежности группам вершин (вторая колонка), например:

0 0
1 1
2 2
3 3
40 42
41 42
42 42

В этом примере вершины 0, 1, 2, 3 — «обычные», а 40, 41, 42 являются «частями» одной вершины 42, т.е. соответствуют одному перекрестку. Всего в файле 146 625 идентификаторов вершин, что соответствует 40 420 группам (реальным перекресткам).

Файл edges.txt содержит информацию о дугах в таком формате:

317744 317744 42 44
317745 317744 41 44
317746 317746 46 40
317747 317746 45 40
317800 317800 135 136
317856 317856 224 226
317857 317856 222 226
317859 317859 229 221
317860 317859 227 221

В первой колонке — идентификатор дуги, во второй — идентификатор группы, которой принадлежит дуга (принадлежность одной группе означает совпадение физического расположения на карте), третья — идентификатор начальной вершины дуги, четвертая — идентификатор конечной вершины. Всего в графе 206 289 дуг, что соответствует 86 228 «реальным» дугам.

В файле edge_data.txt содержатся характеристики дуг (улиц). Например:

317744 39.93 30.0 
317746 39.93 30.0 
317800 14.41 20.0 
317856 170.42 30.0 
317859 170.42 30.0

Первая колонка — идентификатор группы дуг (у всех дуг в группе характеристики совпадают, так как физически это одна улица). Вторая колонка — длина отрезка улицы в метрах. Третья колонка — «штатная» скорость движения транспортного потока (км/ч) по этой улице, или «пропускная способность».

Данные о пробках

Данные о наблюдениях содержатся в файле jams.txt. Наблюдения охватывают 31 день. Для первых 30 дней в файле содержится информация о скорости движения потока автотранспорта с 16:00 до 22:00; для последнего дня — с 16:00 до 18:00. Формат файла:

317744 11 16:26 62
317744 11 16:30 62
317744 11 16:34 62
317744 11 16:40 63

Первая колонка — идентификатор группы дуг (для всех дуг одной группы скорость одинакова, так как это одна улица). Вторая колонка — время в формате «день часы:минуты». Третья колонка — скорость потока (км/ч), ноль соответствует стоящему транспорту.

Задача участников — заменить «??» в файле task.txt на оценки скорости потока автомобилей на определенных дугах в определенные моменты времени:

317744 41 18:22 ??
317744 41 18:26 ??
317744 41 18:30 ??
317744 41 18:34 ??

Всего в этом файле 691 641 строка, то есть участникам надо сделать 691 641 оценку скорости.

Оценка

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

Оценка качества результатов рассчитывается по формуле:

, где

n — общее количество предсказаний,
k_l — «коэффициент длины»: длина улицы, отнесенная к средней длине улиц (120 м),
k_t — «временной коэффициент»: 1 + 0.1*порядковый номер четырехминутного интервала, считая от 18:00 (например, для 18:56 k_t = 1 + 0.1*14 = 2.4),
v* — наблюдаемая скорость,
v — предсказанная скорость.

По результатам участников конкурса считается две оценки качества: публичная оценка по 62 377 предсказаниям и финальная оценка по остальным 629 264 предсказаниям. Публичная оценка используется для составления текущего рейтинга результатов. Финальная оценка используется для подведения итогов конкурса. Рейтинг, полученный на основе публичной оценки, может не совпадать с финальным рейтингом.

Скачать данные

Данные предоставляются исключительно для личного использования и предназначены для выполнения заданий конкурса «Интернет-математика 2010»

Скачать архив в формате .zip (100 МБ)