članak: 1 od 1  
Computer Science and Information Systems / ComSIS
2010, vol. 7, br. 4, str. 789-811
jezik rada: engleski
članak
doi:10.2298/CSIS090710024A
An evolutionary solution for multimodal shortest path problem in metropolises
(naslov ne postoji na srpskom)
Abbaspour Rahim A., Samadzadegan Farhad
Surveying Department, University College of Engineering, University of Tehran, Tehran, Iran

e-adresa: abaspour@ut.ac.ir, samadz@ut.ac.ir

Sažetak

(ne postoji na srpskom)
This paper addresses the problem of time-dependent shortest multimodal path in complex and large urban areas. This problem is one of the important and practical problems in several fields such as transportation, and recently attracts the research focus due to developments in new application areas. An adapted evolutionary algorithm, in which chromosomes with variable lengths and particularly defined evolutionary stages were used, was employed to solve the problem. The proposed solution was tested over the dataset of city of Tehran. The evaluation consists of computing shortest multimodal path between 250 randomly selected pairs of origins and destination points with different distances. It was assumed that three modes of walking, bus, and subway are used to travel between points. Moreover, some tests were conducted over the dataset to illustrate the robustness of method. The experimental results and related indices such as convergence plot show that the proposed algorithm can find optimum path according to applied constraints.

Ključne reči

multimodal shortest path; genetic algorithm; metropolis

Reference

*** (2009) JPL: Journey Planner for London. http://journeyplanner.tfl.gov.uk, current July 2009

*** (2009) SCOTTY, multi-modal door-to-door route planner for Austria. http//fahrplan.oebb.at/bin/query.exe/dn?L=vs_addr

*** (2009) BayernInfo: Trip Information for all Modes of Transport. www.bayerninfo.de (current July 2009)

CrossRefKoBSON

Abdelghany, K., Mahmassani, H. (2001) Dynamic Trip Assignment-Simulation Model for Intermodal Transportation Networks. Transportation Research Record, 1771(1): 52-60

KoBSON

Aifadopoulou, G., Ziliaskopoulos, A., Chrisohoou, E. (2007) Multiobjective Optimum Path Algorithm for Passenger Pretrip Planning in Multimodal Transportation Networks. Transportation Research Record, vol. 2032, 26-34

Ashlock, D. (2006) Evolutionary computation for modeling and optimization. New York: Springer Science - Business Media

Ayed, H., Khadraoui, D., Habbas, Z., Bouvry, P., Merche, J.F. (2008) Transfer graph approach for multimodal transport problems. u: Hoai L.T., Bouvry P., Tao, P.D. (ur.) Modelling, Computation and Optimization in Information Systems and Management Sciences. Communications in Computer and Information Science, Berlin - Heidelberg: Springer, vol. 14, str. 538-547

CrossRefKoBSON2

Back, T., Hammel, U., Schwefel, H.P. (1997) Evolutionary computation: Comments on the history and current state. IEEE Transactions on Evolutionary Computation, vol. 1, br. 1, str. 3-17

Barrett, C.L., Bisset, K., Jacob, R., Konjevod, G., Marathe, M.V. (2002) Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSIMS router. u: Mohring R.H., Raman R. (ur.) Lecture Notes in Computer Science, Heidelberg: Springer, vol. 2461, 126- 138

Battista, M.G., Lucertini, M., Simeone, B. (1995) Path composition and multiple choices in a bimodal transportation network. u: World Conference on Transport Research Society (VII), Sydney, Proceedings

CrossRefKoBSON

Berube, J., Potvin, J., Vaucher, J. (2006) Time-dependent shortest paths through a fixed sequence of nodes: application to a travel planning problem. Computers & Operations Research, 33(6): 1838-1856

CrossRefKoBSON

Bielli, M., Boulmakoul, A., Mouncif, H. (2006) Object modeling and path computation for multimodal travel systems. European Journal of Operational Research, 175(3): 1705-1730

Chang, E., Floros, E., Ziliaskopoulos, A. (2007) An intermodal time-dependent minimum cost path algorithm with an application to hazmat routing. u: Zeimpekis V., Tarantilis C.D., Giaglis G.M., Minis I. (ur.) Dynamic Fleet Management, Concepts, Systems, Algorithms & Case Studies, Operations Research/Computer Science Interfaces Series, Springer, vol. 38. 113- 132

KoBSON1

Crainic, T.G., Rousseau, J. (1986) Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem. Transportation Research, vol. 20, str. 225-242

CrossRefKoBSON

Deo, N., Pang, C. (1984) Shortest-path algorithms: Taxonomy and annotation. Networks, 14(2): 275-323

1

Dreo, J., Siarry, P., Petrowski, A., Taillard, E. (2006) Metaheuritics for hard optimization. Berlin: Springer

KoBSON

Feillet, D., Dejax, P., Gendreau, M., Gueguen, C. (2004) An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks, vol. 44, br. 3, 216-229

Fragouli, M., Delis, A. (2005) Navigation and multimodal transportation with easytransport. Intelligent Systems, IEEE, vol. 20, br. 2, 54-61

30

Goldberg, D.E. (1989) Genetic algorithms in search: Optimization and machine learning. Reading, MA, itd: Addison-Wesley

VBS

Haupt, R.L., Haupt, S.E. (2004) Practical genetic algorithms. Hoboken: J. Wiley & Sons

VBS18

Holland, J.H. (1975) Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. Ann Arbor: The University of Michigan Press

Kaufmann, D.E., Smith, R.L. (1993) Fastest paths in time-dependent networks for intelligent vehicle, highway systems application. IVHS Journal, vol. 1, br. 1, 1- 11

Kramer, R., Modsching, M., ten Hagen, K. (2006) A City guide agent creating and adapting individual sightseeing tours based on field trial results. International Journal of Computational Intelligence Research, vol. 2, br. 2, 191-206

KoBSON

Lozano, A., Storchi, G. (2001) Shortest viable path in multimodal networks. Transportation Research Part A, vol. 35, br. 3, 225-241

CrossRefKoBSON

Lozano, A., Storchi, G. (2002) Shortest viable hyperpath in multimodal networks. Transportation Research Part B: Methodological, 36(10): 853-874

Meng, F.H., Lao, Y., Wai, L.H., Chuin, L.H. (1999) A multi-criteria, multi-modal passenger route advisory system. u: Proceedings of IES-CTR international symposium, Singapore

CrossRefKoBSON

Modesti, P., Sciomachen, A. (1998) A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks. European Journal of Operational Research, 111(3): 495-508

CrossRefKoBSON

Nguyen, S., Morello, E., Pallottino, S. (1988) Discrete time dynamic estimation model for passenger origin/destination matrices on transit networks. Transportation Research Part B: Methodological, 22(4): 251-260

KoBSON

Nguyen, S., Pallotino, S., Malucelli, F. (2001) A modeling framework for the passenger assignment on a transport network with timetables. Transportation Science, vol. 35, br. 3, 238-249

Pallottino, S., Scutella, M.G. (1998) Shortest path algorithms in transportation models: Classical and innovative aspects. u: Marcotte P., Nguyen S. (ur.) Equilibrium and Advanced Transportation Modeling, the Netherlands: Kluwer Academic, 245- 281

Pun-Cheng, L.S.C., Mok, E.C.M., Shea, G.Y.K., Yan, W.Y. (2007) EASYGO: A public transport query and guiding LBS. u: Gartner G., Cartwright W., Peterson M.P. (ur.) Location Based Services and Tele Cartography, Berlin: Springer Science, str. 545-556

Qu, L., Chen, Y.F. (2008) A hybrid MCDM method for route selection of multimodal transportation network. u: Sun F., Zhang J., Tan Y., Cao J., Yu W. (ur.) Advances in Neural Networks: Lecture Notes in Computer Science, Berlin - Heidelberg: Springer, vol. 5263, 374-383

KoBSON1

Sherali, H.D., Hobeika, A.G., Kangwalklai, S. (2003) Time-dependent, label-constrained shortest path problems with applications. Transportation Science, 37, (3), 278-293

CrossRefKoBSON

Souffriau, W., Vansteenwegen, P., Vertommen, J., Berghe, G.V., Oudheusden, D. (2008) A Personalized Tourist Trip Design Algorithm for Mobile Tourist Guides. Applied Artificial Intelligence, 22(10): 964-985

CrossRefKoBSON

Spiess, H., Florian, M. (1989) Optimal strategies: A new assignment model for transit networks. Transportation Research Part B: Methodological, 23(2): 83-102

Vansteenwegen, P., Oudheusden, D.V. (2007) The mobile tourist guide: An OR opportunity. OR Insight, vol. 20, br. 3, 21-27

CrossRefKoBSON

Ziliaskopoulos, A.K., Wardell, W. (2000) An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays. European Journal of Operational Research, 125(3): 486-502