функционируют системы ЭКСПРЕСС — на железнодорожном транс-
порте, СИРЕНА — на воздушном транспорте [1].
К сожалению, существующие системы справочно-информацион-
ного обслуживания пассажиров далеки от совершенства. В настоя-
щее время в России даже в рамках отдельных видов транспорта от-
сутствует возможность поиска маршрута проезда с пересадкой. Ис-
ключение составляют автоматизированные информационные системы
на воздушном транспорте, которые способны находить маршруты с пе-
ресадкой. Но на железнодорожном транспорте (который обслуживает
автоматизированная система ЭКСПРЕСС) поиск сложного маршрута с
пересадками невозможен. Например, на запрос пассажира о маршруте
проезда из Калининграда во Владивосток, система ЭКСПРЕСС выдает
ответ: “Прямое сообщение отсутствует. Подготовьте ответ вручную”.
Данная задача гораздо более сложна для железнодорожного транс-
порта, чем для воздушного, так как число железнодорожных станций
превосходит число аэропортов в сотни раз.
В Европе наиболее распространена система HAFAS [2], которая
используется на железнодорожном транспорте в нескольких странах.
Система HAFAS выдает удовлетворительные результаты поиска, хотя
они не всегда оказываются оптимальными. Главной причиной этого
является то, что алгоритм поиска внутри системы использует эври-
стические методы, чтобы уменьшить пространство поиска. В прото-
типе HAFAS имелось два уровня сети:
статический
, состоявший из
ребер, стоимость которых определялась расстоянием, и
динамический
,
где ребра включали информацию о времени прибытия и отправления
поездов. Алгоритм использовал статический уровень, чтобы выявить
нужнуючасть графа, без учета информации о времени. Это может
приводить к потере оптимального пути.
Еще более фундаментальная задача — поиск интермодального
маршрута (пути проезда с использованием нескольких видов транс-
порта). Следует отметить, что транспортная сеть в Российской Фе-
дерации весьма неоднородна. Есть населенные пункты, куда можно
попасть только по воздуху. Имеются регионы, лишенные железно-
дорожного транспорта; есть населенные пункты, до которых можно
добраться только на поезде. Поэтому разработка информационной
системы, которая позволит объединить информациюиз действующих
автоматизированных систем на различных видах транспорта в целях
получения наиболее полной справочной информации о возможно-
сти проезда с учетом пересадок и наличия мест на разных видах
транспорта, является актуальной задачей.
Алгоритмы поиска оптимальных путей проезда на пассажир-
ском транспорте.
Существует два основных подхода к моделирова-
ниюинформации о расписаниях как задачи поиска кратчайшего пути:
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 4 99
