Модуль расчета оптимального маршрута движения на общественном транспорте

Abstract

This article describes software realization and implementation for the problem of finding the most efficient route between two different points "A" to point "B" using public transport system. The developed program is intended to be used inside complex information system, informing about public transport routes. Using set lists of start and end points (the terminals installed at bus stops and connected to the information system are used as start points; stopping complexes or sights of the city are used as end pints) and public transport motion data, the program identifies and analyzes the route between all pairs of start and end points. The best routes are displayed on the terminal of bus stops at the request of residents and guests of the city by means of an integrated information system. The algorithm and the solution to a problem of finding the shortest way are considered in this article. The description of the search algorithm and data structures are provided.

Настоящая статья посвящена программной реализации задачи поиска оптимального маршрута движения на общественном транспорте из пункта «А» в пункт «Б». Разработанная программа предназначена для использования в составе комплексной информационной системы информирования о маршрутах общественного транспорта. По заданным перечням начальных и конечных точек (в качестве начальных точек выступают терминалы, устанавливаемые на остановочных комплексах и подключенные к информационной системе; в качестве конечных – остановочные комплексы или достопримечательности города) и данным о движении общественного транспорта программа рассчитывает оптимальный маршрут между всеми парами начальных и конечных точек. Оптимальные маршруты средствами комплексной информационной, системы отображаются на терминалах остановочных комплексов по запросам жителей и гостей города. В статье рассматриваются алгоритм и реализованное решение задачи поиска кратчайшего пути. Приведено описание алгоритма поиска и структур данных.