abbr. SJ GMU
ISSN 2657-5841 (printed)
ISSN 2657-6988 (online)
DOI: 10.26408
Przegląd metod i algorytmów modelowania sieci transportowych opartych na teorii grafów
Review of Methods and Algorithms for Modelling Transportation Networks Based on Graph Theory
https://orcid.org/0000-0003-1635-19241
Gdynia Maritime University, 81-87 Morska, 81-225 Gdynia, Faculty of Navigation, Department of Mathematics, e-mail: s.guze@wn.umg.edu.pl
Abstract:
One of the best ways of modelling a transport network is to use a graph with vertices and edges. They represent nodes and arcs of such network respectively. Graph theory gives dozens of parameters or characteristics, including a connectivity, spanning trees or the different types of domination number and problems related to it. The main aim of the paper is to show graph theory methods and algorithms helpful in modelling and optimization of a transportation network. Firstly, the descriptions of basic notations in graph theory are introduced. Next, the concepts of domination, bondage number, edge-subdivision and their implementations to the transportation network description and modeling are proposed. Moreover, the algorithms for finding spanning tree or maximal flow in networks are presented. Finally, the possible usage of distinguishing concepts to exemplary transportation network is shown. The conclusions and future directions of work are presented at the end of the paper.
Streszczenie:
Jednym z najlepszych sposobów modelowania sieci transportowej jest użycie grafu z wierzchołkami i krawędziami. Reprezentują one odpowiednio węzły i łuki takiej sieci. Teoria grafów daje możliwość użycia dziesiątek parametrów lub charakterystyk, w tym spójności, drzew spinających lub różnych typów liczb dominowania i związanych z tym problemów. Głównym celem artykułu jest przedstawienie metod i algorytmów teorii grafów pomocnych w modelowaniu i optymalizacji sieci transportowej. Po pierwsze, wprowadzono opisy podstawowych pojęć w teorii grafów. Następnie zaprezentowano koncepcje dominowania, liczby zniewolenia czy podziału krawędzi grafu oraz ich implementacji do opisu i modelowania sieci transportowej. Ponadto przedstawiono algorytmy do wyszukiwania drzewa opinającego i maksymalnego przepływu w sieciach. Wreszcie pokazano możliwe sposoby wykorzystania wyróżnionych koncepcji do przykładu sieci transportowej. Na zakończenia przedstawiono wnioski i przyszłe kierunki prac.
Keywords:
knapsack problem, domination number, bondage-connected number, MST, maximal flow, transportation network, vulnerability
Słowa kluczowe:
problem plecakowy, liczba dominowania, liczba zniewolenia spójnego, MST, maksymalny przepływ, sieć transportowa, wrażliwość sieci
Issue:
Pages:
25
39
Doi:
Submitted:
01.11.2018
Accepted:
12.11.2018
Published:
28.12.2018
Download full text in pdf:
This article is an open access article distributed under a Creative Commoms Attribution (CCBY 4.0) licence
References:
Cascetta, E., 2001, Transportation Systems in Transportation Systems Engineering: Theory and Methods, Cascetta, E. (ed.), Springer US, Boston, MA, s. 1–22.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., 2009, Introduction to Algorithms, 3rd ed., MIT Press, s. 631–638.
Fink, J.F., Jacobson, M.S., Kinch, L.F., Roberts, J., 1990, The Bondage Number of Graph, Discrete Mathematics, vol. 86, no. 1–3, s. 47–57.
Guze, S., 2014a, Application of the Knapsack Problem to Reliability Multi-Criteria Optimization, Journal of Polish Safety and Reliability Association, Summer Safety and Reliability Seminars, vol. 5, no. 1, s. 85–90.
Guze, S., 2014b, The Graph Theory Approach to Analyze Critical Infrastructures of Transportation Systems, Journal of Polish Safety and Reliability Association, Summer Safety and Reliability Seminars, vol. 5, no. 2, s. 57–62.
Guze, S., 2014c, Graph Theory Approach to Transportation Systems Design and Optimization, TransNav, International Journal on Marine Navigation and Safety of Sea Transportation, vol. 8, no. 4, s. 571–578.
Guze, S., 2015, Numerical Application of the SPEA Algorithm to Reliability Multi-Objective Optimimization, Journal of Polish Safety and Reliability Association, Summer Safety and Reliability Seminars, vol. 6, no. 1, s. 101–114.
Guze, S., 2017, An Application of the Selected Graph Theory Domination Concepts to Transportation Networks Modelling, Zeszyty Naukowe Akademii Morskiej w Szczecinie, nr 52(124), s. 97–102.
Harrary, F., 1969, Graph Theory, Addison-Wesley, Reading, MA, USA.
Hartnell, B.L., Rall, D.F., 1994, Bounds on the Bondage Number of a Graph, Discrete Mathematics, vol. 128, no. 1, s. 173–177.
Haynes, T.W., Hedetniemi, S., Slater, P.J, 1998, Fundamentals of Domination in Graphs, CRC Press, New York.
https://www.hackerearth.com/practice/algorithms/graphs/minimum-cost-maxi... (access 30.10.2018).
Kołowrocki, K., Soszyńska-Budny, J. (2011), Reliability and Safety of Complex Technical Systems and Processes. Modeling – Identification – Prediction – Optimization, Springer-Verlag, London.
Kołowrocki, K., Soszyńska-Budny, J. (2013), Reliability Prediction and Optimization of Complex Technical Systems with Application in Port Transport, Journal of Polish Safety and Reliability Association, Summer Safety and Reliability Seminars – SSARS 2013, Gdańsk-Sopot, vol. 3, no. 1–2, s. 263–279,
Leeuwen van, J., 1990, Graph Algorithms, w: Leeuwen van, J. (ed.), Handbook of Theoretical Computer Science, vol. A, Elsevier Science Publisher B.V., Amsterdam, s. 525–631.
Martello, S., Toth, P., 1990, Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester, U.K.
Neumann, T., 2016, The Shortest Path Problem with Uncertain Information in Transport Networks, w: Mikulski J. (ed.), Challenge of Transport Telematics, Springer International Publishing, s. 475–486.
Newell, G.F., 1980, Traffic Flow on Transportation Networks, MIT Press Series in transportation studies, Monograph 5.
Parekh, A.K., 1991, Analysis of Greedy Heuristic for Finding Small Dominating Sets in Graphs, Information Processing Letters, vol. 39, no. 5, s. 237–240.
Rodrigue, J.P., Comtois, C., Slack, B., 2017, The Geography of Transport Systems, 4th ed., Routledge, Taylor & Francis Group, New York.
Syslo, M., 2011, Źródło programu “Algorytmy grafowe”, http://mmsyslo.pl/Materialy/Oprogramowanie /Algorytmy-grafowe (dostęp 30.10.2018).
Velammal, S., 1997, Studies in Graph Theory: Covering, Independence, Domination and Related Topics. Ph.D. Thesis, Manonmaniam Sundaranar University, Tirunelveli, India.
Zitzler, E., Thiele, L., 1999, Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach, IEEE Transactions on Evolutionary Computation, vol. 3, no. 4., s. 257–271.