Крылов А.Д.
ИСПОЛЬЗОВАНИЕ ОТКРЫТЫХ КАРТОГРАФИЧЕСКИХ ДАННЫХ В ОБЪЕКТНОЙ МОДЕЛИ ДОРОЖНО-ТРАНСПОРТНОЙ СЕТИ ДЛЯ ЗАДАЧ ТРАНСПОРТНОЙ ОПТИМИЗАЦИИ
Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч-Бруевича
В данном докладе рассматривается подход к представлению модели дорожно-транспортной сети с использованием открытых картографических данных.
Ключевые слова: модель дорожно-транспортной сети, OpenStreetMap, задачи транспортной оптимизации.
This report reviews the approach to the representation of the road transport network model using open geospatial data.
Key words: model of road transport network, OpenStreetMap, transport optimization problem.
Задачи построения оптимальных маршрутов для транспортных средств изучаются и совершенствуются на протяжении последних десятилетий. Вводятся новые постановки задач, совершенствуются алгоритмы решения.
Решение данных задач позволяет организовывать маршруты для транспортных средств таким образом, что бы обеспечить объезд заданных пунктов назначения за требуемое время с минимальными затратами материальных ресурсов.
К наиболее известным задачам относятся: VRP (The Vehicle Routing Problem) – задача маршрутизации транспортных средств; VRPTW (The Vehicle Routing Problem with Time Windows) – задача маршрутизации транспортных средств с временными окнами; CVRP (Capacitated Vehicle Routing Problem) – задача маршрутизации транспортных средств с учетом грузоподъемности; SVRP (The Stochastic Vehicle Routing Problem) – стохастическая задача маршрутизации транспортных средств; DVRP (The Dynamic Vehicle Routing Problem) – динамическая задача маршрутизации транспортных средств.
Данные задачи относятся к классу NP-полных задач, то есть таких задач, время решения которых полиномиально не зависит от объема входных данных. Применение картографических данных в исследовании обозначенных задач позволяет: провести вычислительный эксперимент, получив результаты, соответствующие реальным условиям, а также оценить время выполнения тех или иных алгоритмов и методов решения.
До недавнего времени разработкой картографии занимались только организации, специализирующиеся в данной области. Соответственно, картографические данные были закрыты для широкого круга потребителей и предоставлялись только на коммерческой основе.