BC/NW 2015 № 1 (26) 6:5

ОБ ОДНОМ ПОДХОДЕ К РЕШЕНИЮ ЗАДАЧИ ПОИСКА ОПТИМАЛЬНЫХ МАРШРУТОВ НА ТРАНСПОРТНЫХ СХЕМАХ

Юшанков С.В., Гольцов А.Г.

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

В докладе рассматривается один из способов реализации алгоритма автоматизированного поиска описанных выше маршрутов, основанного на алгоритме поиска кратчайшего пути методом Дейкстры [1].

Предлагаемый метод включает следующие основные этапы.

1. Схема Московского метрополитена представляется в виде взвешенного графа, где каждая станция является узлом, а связи между узлами – перегонами.

2. На основании алгоритма Дейкстры проводится поиск наикратчайшего пути по данному графу с учетом времени ожидания.

3. Проводится синхронизация полученного маршрута с текущим временем и составляется расписание движения пригородных поездов. Появляется несколько альтернативных вариантов маршрутов.

4. Проводится выбор оптимального по времени прибытия в конечную точку маршрута.

Литература

1. Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе. URL:http://habrahabr.ru/post/111361