An improved approximation algorithm for optimal routes generation in public transport network

• Autorzy: Koszelew J.

Warianty tytułu

PL

Poprawiona wersja pewnego aproksymacyjnego algorytmu generującego optymalne trasy w sieci transportu publicznego

• Języki publikacji: EN

Abstrakty

EN

This paper presents a new version of Routes Generation Matrix Algorithm, called Routes Generation Matrix Improved Algorithm (RGMIA), for determining routes with optimal travel time in public transport network. The method was implemented and tested on the real public transport network in Warsaw city. This network was completed with walk links and therefore resultant routes are more practical and can perform various users’ preferences. Effectiveness of the improved method was compared in two aspects: time complexity and quality of results, with another two algorithms - previous version of Routes Generation Matrix Algorithm (RGMA) and Routes Generation Genetic Algorithm (RGGA). RGMA and RGGA algorithms were described in previous author’s papers [9,10].

PL

Artykuł zawiera opis poprawionej wersji algorytmu generującego optymalne trasy w sieci transportu publicznego uzupełnionej o linki piesze, nazywanego przez autora Routes Generation Matrix Improved Algorithm (RGMIA). Trasy generowane przez RGMIA są optymalne pod względem czasu realizacji i mogą zawierać odcinki piesze, co sprawia, że wynikowe ścieżki są bardziej praktyczne i mogą spełniać określone preferencje użytkowników środków transportu. Algorytm został zaimplementowany i przetestowany na danych realnej sieci transportowej. Efektywność poprawionej metody została porównana w dwóch aspektach: złożoności czasowej i jakości wynikowych tras, z poprzednią wersją algorytmu nazwaną Routes Generation Matrix Algorithm (RGMA) oraz z metodą genetyczną Routes Generation Genetic Algorithm (RGGA). Algorytmy RGMA oraz RGGA zostały opisane w poprzednich artykułach autora.

Słowa kluczowe

EN

genetic algorithm; public transport network; time-dependent shortest path; optimal routes

PL

sieć transportu publicznego; optymalna trasa; algorytm genetyczny

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Zeszyty Naukowe Politechniki Białostockiej. Informatyka
• Rocznik: 2010
• Tom: Z. 5
• Strony: 5--17
• Opis fizyczny: Bibliogr. 16 poz., rys., tab., wykr.

Twórcy

autor

Koszelew J.

• Politechnika Białostocka, Wydział Informatyki, Białystok

Bibliografia

• [1] Ahuja, R. K., Orlin, J. B., Pallotino, S., Scutella, M.G.: Dynamic shortest path minimizing travel times and costs, Networks, 41 (4), 2003, pp. 197-205.
• [2] Ahuja R. K., Magnanti T. L., Orlin, J. B.: Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 2008.
• [3] Bellman R. E.: On a Routing Problem, Journal Quarterly of Applied Mathematics 16, 1958, pp. 87-90.
• [4] Chabini I.: Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time, Journal Transportation Research Records, 1998, pp. 170-175.
• [5] Cooke K.L., Halsey, E.: The shortest route through a network with timedependent intermodal transit times, Journal Math. Anal.Appl., 14, 1996, pp. 493-498.
• [6] Dreyfus, S.E.: An Appraisal of Some Shortest-path Algorithms, In Journal Operations Research, vol.17, 1969, pp. 395-412.
• [7] Hansen P.: Bicriterion path problems. In Multicriteria decision making: theory and applications, Lecture Notes in Economics and Mathematical Systems 177, Eds. G. Fandel, T. Gal. Heidelberg, Springer-Verlag 1980, pp. 236-245.
• [8] Koszelew, J.: The Theoretical Framework of Optimization of Public Transport Travel, In: Proceedings of 6th International Conference on Computer Information Systems and Industrial Management Applications: CISIM 2007, IEEE Computer Society, 2007, pp. 65-70.
• [9] Koszelew, J.: Approximation method to route generation in public transportation network, Polish Journal Environment Studies, Vol.17, Nr 4C, 2008, pp. 418-422.
• [10] Koszelew, J., Piwonska, A.: A new genetic algorithm for optimal routes generation in public transport network, Proceedings of 13th International Conference on System Modelling Control: SMC’2009, Lodz University of Technology, 2009.
• [11] Lawler, E. L.: A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem, Management Science 18, 1972, pp. 401-405.
• [12] Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs WNT, Warsaw, 1996.
• [13] Orda, A. and Rom, R.: Shortest path and minimum - delay algorithms in networks with time-dependent edge-length, In Journal Assoc. Computer Mach, 37(3), 1990, pp. 607-625.
• [14] Sung, K., Bell, M.G.H., Seong, M. and Park, S.: Shortest paths in a network with time-dependent flow speeds, European Journal Operational Research, 121(1), 2000, pp. 32-39.
• [15] WU, Q., Hartley J. K.: Accommodating User Preferences in the Optimization of Public Transport Travel, International Journal of Simulation Systems, Science and Technology: Applied Modeling and Simulation, Vol.5, No 3-4, 2004, pp. 12-25.
• [16] Wikipedia, the free encyclopedia [http://en.wikipedia.org/wiki/ Intelligent_transportation_system].