Подготовка дорожного графа из OpenStreetMap

Геоданные OpenStreetMap состоят из точек с координатами и соединяющих их линий с атрибутами. Тебе предстоит отфильтровать лишние слои вроде тротуаров, железных дорог или лесных просек. Для автомобильной или скутерной доставки оставь только проезжие части с тегами highway со значениями primary, secondary, tertiary и residential. Обязательно обработай тег oneway. Если проигнорировать одностороннее движение, алгоритм построит маршрут по встречной полосе.

Математическая модель расчета веса ребер

Оптимизация доставки строится на минимизации времени, а не расстояния. Базовый вес ребра равен длине отрезка дороги в метрах, деленной на допустимую скорость движения. Скорость извлекается из тега maxspeed. Если тег отсутствует, принимай среднюю скорость потока по умолчанию, например 40 километров в час для жилой зоны и 60 километров в час для главных улиц.

Пробки моделируются через повышающие коэффициенты сопротивления. Для часа пик с 17:30 до 19:30 введи коэффициент замедления от 2,0 до 3,5 для центральных магистралей. Внутриквартальные проезды загружаются меньше, поэтому их коэффициент можно зафиксировать на отметке 1,1–1,3. Дополнительно добавь постоянную штрафную задержку в 15–30 секунд на перекрестках при совершении левого поворота и проезде светофоров.

Программная реализация алгоритма Дейкстры

Алгоритм Дейкстры последовательно находит наименьшее суммарное время пути от стартовой вершины до всех остальных узлов. В графе твоего района будет от 1 000 до 15 000 вершин. Линейный поиск вершины с минимальным расстоянием сделает работу программы медленной. Используй структуру данных «очередь с приоритетами» через модуль heapq в Python. Это обеспечит асимптотическую сложность O((V + E) log V) и мгновенный расчет трека.

Что преподаватель оценивает в этом проекте

  • Корректность структуры графа с учетом ориентированности ребер и правил дорожного движения
  • Обоснованность формулы вычисления веса ребра с разделением параметров времени суток и типа улицы
  • Эффективность программной реализации алгоритма Дейкстры без избыточного перебора элементов
  • Наглядность визуализации полученного пути на подложке интерактивной карты района
  • Сравнительный анализ времени доставки по геометрически кратчайшему и фактически быстрейшему маршрутам

Инструменты и источники реальных геоданных

Для работы подойдут открытые инструменты экосистемы Python. Библиотека OSMnx умеет напрямую загружать дорожные графы по названию района или координатному прямоугольнику. Библиотека NetworkX предоставляет готовые структуры для хранения графов, но сам алгоритм Дейкстры для защиты проекта лучше написать вручную. Для интерактивной отрисовки пути в формате HTML-файла отлично подходит библиотека Folium.

Частые вопросы

Нужно ли подключать реальный API Яндекс Пробок?

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

Почему Дейкстра, а не алгоритм A-star?

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