Determining the shortest route with the use of public transport
Abstract
This paper describes an algorithm for determining the shortest transport route using public transport. Basic algorithm for determining the shortest route without using geo-referencing and with the possibility of one change is presented. The structure of the database enabling to use several nearby objects as a bus stop is considered. Based on this basic algorithm, algorithm for determining the shortest route with two or more bus changes is implemented. The possibility of expanding the functionality of the algorithm applied to different kinds of transport and geo-referencing is considered. It also considers the program and structural ways of accelerating the algorithm.
References
1. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ = Introduction to Algorithms. 2-е изд. М.: Вильямс, 2006.
2. Diestel R. Graph Theory, Electronic Edition. NY: Springer-Verlag, 2005.
3. Ананий В. Левитин. Алгоритмы: введение в разработку и анализ. М.: Вильямс, 2006.
4. Алексеев В. А., Таланов В. А. Графы. Модели вычислений. Структуры данных. Нижний Новгород: Издательство Нижегородского гос. университета, 2005.
5. M. Dorigo, V. Maniezzo, A. Colorni. Ant System: Optimization by a Colony of Cooperating Agents // IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996. 26 (1): P. 29-41.
6. Кажаров А. А., Курейчик В. М. Муравьиные алгоритмы для решения транспортных задач. Известия Российской академии наук. Теория и системы управления. 2010. № 1. С. 32-45.
7. Ватутин Э. И., Титов В. С. Анализ результатов применения алгоритма муравьиной колонии в задаче поиска пути в графе при наличии ограничений // Известия Южного федерального университета. Технические науки. 2014. № 12. С. 111-120.
8. Cauvery N. K., Viswanatha K. V Routing in Dynamic Network using Ants and Genetic Algorithm // International Journal of Computer Science and Network Security, Vol. 9. No. 3, 2000. P 36-41.
9. Longley P.A., Goodchild M. F., Maguire D. J., Rhind D. W. Geographic Information Systems and Science. John Wiley and Sons, 2nd edn. 2005.
10. Gade, Kenneth A non-singular horizontal position representation // The Journal of Navigation, 63, 2010, P. 395-417.
11. Центр интеллектуального управления транспорта Азербайджанской республики. (Naqliyyat Intellektual Idaraetma Markazi) http : //www.niim.az/marsrut-secimi
Review
For citations:
Geidarov P.Sh. Determining the shortest route with the use of public transport. The Herald of the Siberian State University of Telecommunications and Information Science. 2016;(2):51-62. (In Russ.)
Views:
746
Email this article 
