An Approach to the Analysis of Critical Elements of Transport and Logistics Networks Using Graph Theory

ABSTRACT: The article's primary purpose is to develop methods for determining critical nodes, arcs, and routes of transport and logistics networks. One of the proposed algorithms resolves a problem in finding the critical elements of the transport network. The second gives solutions to make alternative paths based on this criticality of the network. These tools should be helpful for transport planners, especially for dangerous, oversized, and important goods. The basis of the developed method is the domination in graphs. The proposed analysis methodology is verified on the existing infrastructure in northeastern Poland.

KEYWORDS: Graph Theory, Applied Graph Theory, Traffic Flow, Critical Infrastructure, Trans-European Transport Networks TEN-T, Transport Logistics System (TLS), Critical Analysis, After COVID-19 Era

REFERENCES

Albert, R., Baraba´ si, A.-L., 2002, Statistical mechanics of complex networks. Reviews of Modern Physics 74, 47–97. - doi:10.1103/RevModPhys.74.47

Akandwanaho S.M., Adewumi A.O., Adebiyi A.A., 2015, Solving Dynamic Traveling Salesman Problem Using Dynamic Gaussian Process Regression, Journal of Applied Mathematics, vol. 2014, Article ID 818529, 10 pages. - doi:10.1155/2014/818529

Appert M., Chapelon L., 2013, Measuring Urban Road Network Vulnerability using Graph Theory: The Case of Montpellier’s Road Network. Working Paper, halshs-00841520, Version 1-8.

Applegate D.L., Robert E., Bixby R.E., Vasek Chvátal V., Cook W.J., 2007, The Traveling Salesman Problem: A Computational Study, Princeton Series in Applied Mathematics.

Arora S., 1998, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM, 45 (5): 753–782, CiteSeerX 10.1.1.23.6765, doi:10.1145/290179.290180. - doi:10.1145/290179.290180

Asakura Y., 1996, Reliability measures of an origin and destination pair in a deteriorated road network with variable flows,” in Proceedings of the 4th Meeting of the EURO Working Group in Transportation, pp.398–412, University of Newcastle, UK.

Babin G., Deneault S., Laporte G., 2007, Improvements to the Or-Opt Heuristic for the Symmetric Travelling Salesman Problem. The Journal of the Operational Research Society, 58(3), pp. 402–407. - doi:10.1057/palgrave.jors.2602160

Bai S., Zhu J., 2016, Connectivity Reliability Analysis of Road Network of Multiple OD Pairs based on the Structural Reliability of Joint Failure Modes, Journal of Engineering Science and Technology Review 9 (6) (2016s), pp. 69–75. - doi:10.25103/jestr.096.09

Barab´asi A.L., 2009, Scale-free networks: a decade and beyond,” Science, vol. 325, no. 5939, pp. 412–413. - doi:10.1126/science.1173299

Barab´asi A.L., Albert R., 1999, Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512. - doi:10.1126/science.286.5439.509

Barlow R.E., 1982, Set theoretic signed domination for coherent systems, Operation Research Center Report No 82–1, Berkeley: University of California. - doi:10.21236/ADA112699

Bazlamaccl C.F., Hindi K.S., 2001, Minimum - weight spanning tree algorithms a survey and empirical study, Computer & Operations Research, vol. 28, pp.767–785. - doi:10.1016/S0305-0548(00)00007-1

Bell M.G.H., Cassir C., 2012, Reliability of transport networks, Research Studies Press.

Bell M.G.H., Iida Y., 1997. Transportation Network Analysis. Wiley, Chichester, West Sussex.

Bell M.G.H., Schmoker J.-D., 2002, Public transport network reliability topological effects. In: Proceedings of the 3rd International Conference on Transportation and Traffic Studies, Guanxi People’s Press, Guilin, China. - doi:10.1061/40630(255)63

Berdica K., 2002a, An introduction to road vulnerability: what has been done, is done and should be done. Transp. Policy 9, 117–127 - doi:10.1016/S0967-070X(02)00011-2

Berdica K., 2002b, Vulnerability: a model-based case study of the road network in Stockholm. In: TraVIS for Roads: Examples of Road Transport Vulnerability Impact Studies. PhD thesis, Department of Infrastructure, KTH, Stockholm, TRITA-INFRA 02-029.

Berdica K., Eliasson J., 2004, Regional accessibility analysis from a vulnerability perspective. In: Nicholson, A., Dantas, A. (Eds.), Proceedings of the Second International Symposium on Transportation Network Reliability (INSTR). Christchurch, New Zealand, pp. 89–94.

Berge C., 1962, The theory of graphs and its applications, Translated by Alison Doig. Methuen & Co. Ltd., London.

Blokus, A. Multistate System Reliability with Dependencies, 1st ed.; Elsevier Academic Press: London, UK, 2020. - doi:10.1016/B978-0-12-821260-8.00001-4

Blokus A, Dziula P. Relations of Imperfect Repairs to Critical Infrastructure Maintenance Costs. Sustainability. 2021; 13(9):4917. - doi:10.3390/su13094917

Bogalecka M. 2020. Consequences of Maritime Critical Infrastructure Accidents. Environmental Impacts Modeling—Identification—Prediction—Optimization—Mitigation. Elsevier, Amsterdam, Oxford, Cambridge (MA), (ISBN 9780128196755, DOI 10.1016/B978-0-12-819675-5.00010-3). - doi:10.1016/B978-0-12-819675-5.00003-6

Cascetta E., 2001, Transportation Systems in Transportation Systems Engineering: Theory and Methods, E. Cascetta, Ed. Boston, MA: Springer US, pp. 1–22. - doi:10.1007/978-1-4757-6873-2_1

Chen A., Yang H., Lo H.K., Tang W.H., 2002, Capacity reliability of a road network: an assessment methodology and numerical results, Transportation Research Part B: Methodological, Volume 36, Issue 3, 2002, Pages 225–252, ISSN 0191-2615, - doi:10.1016/S0191-2615(00)00048-5

Chen A., Yang H., Lo H.K., Tang W. H., 2010, A capacity Related Reliability for transportation Networks, Journal of Advanced Transportation, vol. 33, no, 2, pp. 183–200. - doi:10.1002/atr.5670330207

Commission of the European Communities, 2006, Communication from the Commission on a European Programme for Critical Infrastructure Protection, Brussels.

Cormen T.H., Leierson C.E., Rivest R.L., Stein C., 2009, Introduction to Algorithms, Third Edition. MIT Press, ISBN 0-262-03384-4. Section 23.2: The algorithms of Kruskal and Prim, pp. 631–638.

Council Directive 2008/114/EC of 8 December 2008 on the identification and designation of European critical infrastructures and the assessment of the need to improve their protection. Official Journal of the European Union L 345/75 (23.12.2008).

Cui D., Gao Z.Y., Zhao X.M., 2007, Cascades in small-world modular networks with ’CML’s method, Physica B, vol. 17, pp. 1703–1710.

Delavina E., Pepper R., Waller B., 2010, Lower bounds for the domination number, Discussiones Mathematicae Graph Theory 30 , pp. 475-487. - doi:10.7151/dmgt.1508

D’Este G.M., Taylor M.A.P., 2003. Network vulnerability: an approach to reliability analysis at the level of national strategic transport networks. In: Bell, M.G.H., Iida, Y. (Eds.), The Network Reliability of Transport. Proceedings of the 1st International Symposium on Transportation Network Reliability (INSTR). Pergamon, Oxford, England, pp. 23–44. - doi:10.1108/9781786359544-002

Diestel R., 2000, Graph Theory. Nowy Jork, ISBN 0-387-95014-1.

Du Z.P., Nicholson A., 1997, Degradable transportation systems: Sensitivity and reliability analysis, Transportation Research Part B: Methodological, Volume 31, Issue 3, pp. 225-237, ISSN 0191-2615, - doi:10.1016/S0191-2615(96)00023-9

Einarsson S., Rausand M., 1998, An approach to vulnerability analysis of complex industrial systems. Risk Analysis 18 (5), pp. 535–546. - doi:10.1023/B:RIAN.0000005928.84074.e4

Ford L.R., Fulkerson D.R., 1962, Flows in Networks, Princeton University Press, Princeton, NJ.

Gross J. L., Yellen J., 2004, Handbook of graph theory, CRC Press. ISBN 978-1-58488-090-5.

Gutin G., Punnen A.P., 2006, The Traveling Salesman Problem and Its Variations, Springer US. - doi:10.1007/b101971

Guze S.: Graph Theory Approach to Transportation Systems Design and Optimization. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 8, No. 4, doi:10.12716/1001.08.04.12, pp. 571-578, 2014

Guze S., 2017, An application of the selected graph theory domination concepts to transportation networks modelling, Zeszyty Naukowe Akademii Morskiej w Szczecinie, 52 (124), pp. 97–102.

Guze S. Graph Theory Approach to the Vulnerability of Transportation Networks. Algorithms. 2019; 12(12):270. - doi:10.3390/a12120270

Harrary F., 1969, Graph Theory, Addison-Wesley, Reading, MA.

Hartnell B. L., Firefighter! an application of domination, Presentation, in: 20th Conference on Numerical Mathematics and Computing, University of Manitoba in Winnipeg, Canada, September 1995.

Haynes T.W., Hedetniemi M., Hedetniemi T., 2000, Domination and independence subdivision numbers of graphs, Discussiones Mathematicae Graph Theory 20 , pp. 271–280. - doi:10.7151/dmgt.1126

Haynes T.W., Hedetniemi S., Slater P., 1998, Fundamentals of Domination in Graphs. CRC Press. - doi:10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F

Hensher D.A., Button K., 2008, Handbook of transport modelling, Elsevier. - doi:10.1108/9780857245670

Hongwei M., Xizhao Z., 2015, An evaluation method for the Connectivity Reliability Based on the Transportation Network of Critical Links, International Journal of Transportation vol.3, no.2, pp.45–52 http://dx.doi.org/10.14257/ijt.2015.3.2.04 - doi:10.14257/ijt.2015.3.2.04

Holmgren A., 2004, Vulnerability analysis of electrical power delivery networks. Licentiate thesis TRITA-LWR LIC 2020, Department of Land and Water Resources Engineering, KTH, Stockholm.

Holmgren J., 2004. Efficient updating shortest path calculations for traffic assignment. Master thesis LITH-MAI-EX-2004-13, Department of Mathematics, Linko¨ping Institute of Technology, Linko¨ping.

Iida Y., 1999, Basic concepts and future directions of road network reliability analysis, Journal of Advanced Transportation, vol. 33, no2, 125–134. - doi:10.1002/atr.5670330203

Immers L.H., Stada J.E., Yperman I., Bleukx A., 2004, Robustness and resilience of transportation networks. In: Proceedings of the 9th International Scientific Conference MOBILITA, Bratislava, Slovenia, May 6–7.

Jasny B.R., Zahn L.M., Marshall E., 2009, Connections, Science, vol. 325, no. 5939, p. 405. - doi:10.1126/science.325_405

Jenelius E., Petersen T., Mattsson L., 2006, Importance and exposure in road network vulnerability analysis, Transportation Research Part A 40 , 537–560. - doi:10.1016/j.tra.2005.11.003

Kołowrocki K., Soszyńska-Budny J., 2011, Reliability and Safety of Complex Technical Systems and Processes: Modeling - Identification - Prediction - Optimization, London, Dordrecht, Heildeberg, New York, Springer. - doi:10.1007/978-0-85729-694-8

Kruskal J. B., 1956, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Am. Math. Soc., vol.7, pp.48–50. - doi:10.1090/S0002-9939-1956-0078686-7

Leeuwen, Van, J., 1986, Graph Algorithms Book. Handbook of Theoretical Computer Science, 1990, Pages 525, 527-631 - doi:10.1016/B978-0-444-88071-0.50015-1

Ming‐Hua, L., Jung‐Fa, T., Chian‐Son Y., 2012, A Review of Deterministic Optimization Methods in Engineering and Management, Mathematical Problems in Engineering, Volume 2012. - doi:10.1155/2012/756023

Neumann T., 2016, The Shortest Path Problem with Uncertain Information in Transport Networks. In Challenge of Transport Telematics J. Mikulski, Ed. Springer International Publishing. - doi:10.1007/978-3-319-49646-7_40

Neumann, T. Comparative Analysis of Long-Distance Transportation with the Example of Sea and Rail Transport. Energies 2021, 14, 1689. - doi:10.3390/en14061689

Newell G.F., 1980, Traffic flow on transportation networks. MIT Press Series in transportation studies, Monograph 5.

Piña-Barcenas, J., Cedillo-Campos, M.G., Moreno-Quintero, E. et al. Graph Theory to Achieve the Digital Transformation in Managing Freight Transportation Corridors. Mobile Netw Appl (2023). - doi:10.1007/s11036-023-02283-8

Proag V., 2014, The Concept of Vulnerability and Resilience, Procedia Economics and Finance, vol. 18, pp. 369–376, ISSN 2212-5671, - doi:10.1016/S2212-5671(14)00952-6

Rausand M., Høyland A., 2004, System Reliability Theory; Models, Statistical Methods and Applications, Second Edt., Wiley Series in Probability and Statistics.

Reggiani A., Nijkamp P., Lanzi D., 2015, Transport resilience and vulnerability: The role of connectivity, Transportation Research Part A: Policy and Practice, vol. 81, pp. 4–15. - doi:10.1016/j.tra.2014.12.012

Rodrigue J.P., Comtois C., Slack B., 2017, The geography of transport systems (4th Edition), Routledge, Taylor & Francis Group, New York. - doi:10.4324/9781315618159

Sarewitz D., Pielke R. Jr., Keykhah M., 2003, Vulnerability and risk: some thoughts from a political and policy perspective. Risk Analysis 23 (4), 805–810. - doi:10.1111/1539-6924.00357

Solé R.V., Valverde S., 2004, Information theory of complex networks: on evolution and architectural constraints, Complex networks. Springer, Berlin, Heidelberg, pp. 189–207. - doi:10.1007/978-3-540-44485-5_9

Taylor M.A.P., 1999a, Dense network traffic models, travel time reliability and traffic management. I: General introduction. Journal of Advanced Transportation, vol. 33, no. 2, 218–233. - doi:10.1002/atr.5670330209

Taylor M.A.P., 1999b, Dense network traffic models, travel time reliability and traffic management. II: application to network reliability. Journal of Advanced Transportation, vol. 33, no. 2, 235–251. - doi:10.1002/atr.5670330210

Taylor M.A.P., D’Este G.M., 2004, Critical infrastructure and transport network vulnerability: developing a method for diagnosis and assessment. In: Nicholson, A., Dantas, A. (Eds.), Proceedings of the Second International Symposium on Transportation Network Reliability (INSTR). Christchurch, New Zealand, pp. 96–102.

Thakkar D. K., Jamvecha N.P., 2018, Edge-Vertex Domination in Graphs, Int. J. Math. And Appl., 6(1–C), pp. 549–555.

Tinós R., 2015, Analysis of the dynamic traveling salesman problem with weight changes, 2015 Latin America Congress on Computational Intelligence (LA-CCI), Curitiba, pp. 1–6, doi: 10.1109/LA-CCI.2015.7435936 - doi:10.1109/LA-CCI.2015.7435936

Walikar H.B., Acharya B.D., Sampathkumar E., 1979, Recent developments in the theory of domination in graphs. Allahabad, 1.

Watts D. J., Strogatz S.H., 1998, Collective dynamics of ’small-world’ networks,” Nature, vol. 393, no. 6684, pp. 440–442. - doi:10.1038/30918

Willie R.R., 1978. Computer-Aided Fault Tree Analysis, ORC 78-14, Operations Research Center, University of California, Berkeley. - doi:10.21236/ADA066567

Yamuna M., Karthika K., 2013, Minimal Spanning Tree From a Minimum Dominating Set, WSEAS TRANSACTIONS on MATHEMATICS, Issue 11, vol. 12, pp. 1055– 1064.

Yang M., Li C., Kang L., 2006, A new approach to solving dynamic traveling salesman problems, in Simulated Evolution and Learning, vol. 4247 of Lecture Notes in Computer Science, pp. 236–243, Springer, Berlin, Germany. - doi:10.1007/11903697_31

Ziemska-Osuch, M.; Guze, S. Analysis of the Impact of Road Traffic Generated by Port Areas on the Urban Transport Network—Case Study of the Port of Gdynia. Appl. Sci. 2023, 13, 200. - doi:10.3390/app13010200

Ziemska-Osuch M., Osuch D.: Analysis of the Capacity of Intersections with Fixed-time Signalling Depending on the Duration of the Green Phase for Pedestrians. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 18, No. 2, doi:10.12716/1001.18.02.08, pp. 323-327, 2024

Citation note:

Strzelczyk A., Guze S.: An Approach to the Analysis of Critical Elements of Transport and Logistics Networks Using Graph Theory. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 18, No. 3, doi:10.12716/1001.18.03.07, pp. 535-544, 2024

BibTeX EndNote

Authors in other databases:

Adriana Strzelczyk:

Sambor Guze: ORCID iD icon

orcid.org/0000-0003-1635-1924 Scopus icon