SavedAdd your journal

Journals / Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi / 2019 / Cilt: 25 Sayı: 4

Public transportation graph: A graph theoretical model of public transportation network for efficient trip planning

Toplu taşıma çizgesi: Etkin seyahat planlaması için toplu taşıma ağının çizge teorisi tabanlı bir modeli

Faruk Serin, Süleyman Mete

Pages
468–472
Publication Date
2019-08-28
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗

Abstract

Normal 0 false false false TR X-NONE X-NONE /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Normal Tablo"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin-top:0cm; mso-para-margin-right:0cm; mso-para-margin-bottom:10.0pt; mso-para-margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri",sans-serif; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi; mso-ansi-language:TR;} The presentation and usage of traditional graphs is very important for effective and fast solution of routing in public transportation. However, the traditional graph approach is unable to consider the passenger requests such as total travel time, minimum number of transfer and total distance of travel without pre-processing and/or post-processing. Moreover, the vehicles are not represented on traditional graph. In this paper, after analyzing the different kind of graphs, we propose a novel graph named as public transportation graph. The proposed graph models the public transportation system and considers distance, waiting time, travel time, self-transportation and number of transfers simultaneously for efficient trip planning. In this way, passenger requests can be met without pre-processing and post-processing. In addition, the vehicles are also considered and demonstrated in the proposed graph.

Keywords
🔖

Cite This Article

Serin, F., Mete, S. (2019). Public transportation graph: A graph theoretical model of public transportation network for efficient trip planning. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, Cilt: 25 Sayı: 4, 468–472. https://ajindex.com/articles/1058596

📄 Full Text PDF Viewer

References (19)

  1. Celik E, Bilisik ON, Erdogan M, Gumus AT, Baracli H. “An integrated novel interval type-2 fuzzy MCDM method to improve customer satisfaction in public transportation for Istanbul”. Transportation Research Part E: Logistics and Transportation Review, 58, 28-51, 2013.
  2. Liu L, Mu H, Yang X, He R, Li Y. “An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems”. Applied soft computing, 12(1), 506-515, 2012.
  3. Modesti P, Sciomachen A. “A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks”. European Journal of Operational Research, 111(3), 495-508, 1998.
  4. Ziliaskopoulos A, Wardell W. “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, 2000.
  5. Skriver AJ, Andersen KA. “A label correcting approach for solving bicriterion shortest-path problems”. Computers & Operations Research, 27(6), 507-524, 2000.
  6. Lozano A, Storchi G. “Shortest viable path algorithm in multimodal networks”. Transportation Research Part A: Policy and Practice, 35(3), 225-241, 2001.
  7. Bielli M, Boulmakoul A, Mouncif H. “Object modeling and path computation for multimodal travel systems”. European Journal of Operational Research, 175(3), 1705-1730, 2006.
  8. Galvez-Fernandez C, Khadraoui D, Ayed H, Habbas Z, Alba E. “Distributed approach for solving time-dependent problems in multimodal transport networks”. Advances in Operations Research, 2009,1-15, 2009.
  9. Raith, A, Ehrgott M. “A comparison of solution strategies for biobjective shortest path problems”. Computers & Operations Research, 36(4), 1299-1331, 2009.
  10. Abbaspour RA, Samadzadegan F. “An evolutionary solution for multimodal shortest path problem in metropolises”. Computer Science and Information Systems, 7(4), 789-811, 2010.
  11. Liu L, Mu H, Luo H, Li X. “A simulated annealing for multi-criteria network path problems”. Computers & Operations Research, 39(12), 3119-3135, 2012.
  12. Liu L, Yang J, Mu H, Li X, Wu F. “Exact algorithms for multi-criteria multi-modal shortest path with transfer delaying and arriving time-window in urban transit network”. Applied Mathematical Modelling, 38(9-10), 2613-2629, 2014.
  13. Bowen G, Ciyun L. “A personalized urban multicriteria shortest path stochastic optimization algorithm”. Mathematical Problems in Engineering, 2015(1-8), Article ID 987358, 2015.
  14. Idri A, Oukarfi M, Boulmakoul A, Zeitouni K, Masri A. “A distributed approach for shortest path algorithm in dynamic multimodal transportation networks”. Transportation Research Procedia, 27, 294-300, 2017.
  15. Liu L, Mu H, Yang J. “Toward algorithms for multi-modal shortest path problem and their extension in urban transit network”. Journal of Intelligent Manufacturing, 28(3), 767-781, 2017.
  16. Weisstein EW. "Simple Graph.". http://mathworld.wolfram.com/SimpleGraph.html (15.05.2018).
  17. Post JV. "Multiple Edge." http://mathworld.wolfram.com/MultipleEdge.html (15.05.2018).
  18. Sizemore AE, Bassett DS. “Dynamic graph metrics: Tutorial, toolbox, and tale”. NeuroImage, 180, 417-427, 2018
  19. Delling D, Katz B, Pajor T. “Parallel computation of best connections in public transportation networks”. Journal of Experimental Algorithmics, 17, 1-4, 2012.