On some aspects of graph theory for optimal transport among marine ports

• Autorzy: Chládek P. , Smetanová D. , Krile S.

Identyfikatory

DOI

10.20858/sjsutst.2018.101.4

• Języki publikacji: EN

Abstrakty

EN

This paper is devoted to the Travelling Salesman Problem as applied to Czechoslovak ocean shipping companies and their marine ports on the Black Sea. The shortest circular path around these ports is found and discussed. Formulation of the problem accounts for the fact that distances between the individual cities are not the same in both directions. The consequences that arise from this situation are studied. The used algorithms are based on graph theory and standard logistic methods. In addition, the results are compared with the results obtained by using a minimum spanning tree algorithm.

Słowa kluczowe

EN

graph theory; minimum spanning tree; seaport; Travelling Salesman Problem

PL

teoria grafów; minimalne drzewo spinające; port morski

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Transport / Politechnika Śląska
• Rocznik: 2018
• Tom: z. 101
• Strony: 37--45
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Chládek P.

• Faculty of Economics, University of South Bohemia, Studentská 13 Street, 370 05 České Budějovice, Czech Republic

autor

Smetanová D.

• Faculty of Technology, The Institute of Technology and Business, Okružní 10 Street, 370 01 České Budějovice, Czech Republic

autor

Krile S.

• University of Dubrovnik, Dubrovnik, Ćira Carića 4 Street, 20000 Dubrovnik, Croatia

Bibliografia

• 1. Applegate David L. et al. 2006. The Traveling Salesman Problem. Princeton: Princeton University Press. ISBN: 978-0-691-12993-8.
• 2. Bartoněk Dalibor, Jiří Bureš, Jindřich Petrucha. 2017. “Fast Herustic Algorithm Searching Hamiltonian Patrh in Graph”. 17th International Multidisciplinary Scientific Geoconference (SGEM 2017) Conference Proceedings - Informatics, Geoinformatics and Remote Sensing 17(21): 895-902. Sofia: STEF92 Technology Ltd.
• 3. Bartuška Ladislav, Vladislav Biba, Rudolf Kampf. 2016. “Modeling of Daily Traffic Volumes on Urban Roads”. Proceedings of the Third International Conference on Traffic and Transport Engineering (ICTTE): 300-304.
• 4. Bartuška Ladislav, Jiří Čejka, Zdeněk Caha. 2015. “The Application of Mathematical Methods to the Determination of Transport Flows”. Naše More 62(3): 91-96. ISSN: 04696255. DOI:10.17818/NM/2015/SI1.
• 5. Bartuška Ladislav, Ondrej Stopka, Mária Chovancová et al. 2016. “Proposal of Optimizing the Transportation Flows of Consignments in the Distribution Center”. 20th International Scientific Conference on Transport Means. Juodkrante, Lithuania, 5-7 October 2016. Book Series: Transport Means - Proceedings of the International Conference: 107-111.
• 6. Čejka Jiří. 2016. “Transport Planning Realized Through the Optimization Methods”. World Multidisciplinary Civil Engineering-Architecture-Urban Planning Symposium 2016, WMCAUS 2016. Book Series: Procedia Engineering 161: 1187-1196.
• 7. Chládek Petr, Dana Smetanová. 2018. “Travelling Salesman Problem Applied to Black Sea Ports Used by Czech Ocean Shipping Companies”. Naše More. (In press.)
• 8. Cook William J. 2012. In Pursuit of the Traveling Salesman. Princeton: Princeton University Press. ISBN: 978-0-691-16352-9.
• 9. Cormen Thomas H., Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. 2001. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. ISBN:0262033844 9780262033848.
• 10. Herman Jan. 2015. “Czechoslovak Shipping in the Inter-war Period: The Maritime Transport Operations of the Baťa Shoe Company, 1932-1935”. The International Journal of Maritime History 27(1): 79-103. ISSN: 08438714. DOI: 10.1177/0843871414566579.
• 11. Jelínek Jiří. 2014. “Municipal Public Transport Line Modelling”. Komunikacie 16 (2): 4-8. ISSN: 13354205.
• 12. Jeřábek Karel, Peter Majerčák, Tomáš Klieštik, Katarína Valášková. 2016. “Application of Clark and Wright’s Savings Algorithm Model to Solve Routing Problem in Supply Logistics”. Naše More 63(3): 115-119. ISSN: 04696255.
• 13. Kampf Rudolf, Petr Průša, Christopher Savage. 2011. “Systematic Location of the Public Logistic Centres in Czech Republic”. Transport 26(4): 425-432. ISSN: 16484142. DOI: 10.3846/16484142.2011.635424.
• 14. Kleinberg Jon M., Eva Tardos. 2006. Algorithm Design. New York: Pearson Education Inc. ISBN: 978-0321295354.
• 15. Krátká Lenka. 2016. “Czechoslovak Seafarers Before 1989: Living on the Edge of Freedom”. The International Journal of Maritime History 28(2): 376-387. ISSN: 08438714. DOI: 10.1177/0843871416630687.
• 16. Kruskal Joseph B. 1956. “On the Shortest Spanning Sub-tree of a Graph and the Traveling Salesman Problem”. Proceedings of the American Mathematical Society 7: 48-50.
• 17. Ližbetin Ján, Rudolf Kampf, Karel Jeřábek et al. 2016. “Practical Application of the Comparative Analysis of Direct Road Freight Transport and Combined Transport”. Proceedings of the 20th International Scientific Conference Transport Means 2016. Book Series: Transport Means - Proceedings of the International Conference: 1083-1087.
• 18. Ližbetin Ján, Ondrej Stopka. 2016. “Practical Application of the Methodology for Determining the Performance of a Combined Transport Terminal”. Third International Conference on Traffic and Transport Engineering (ICTTE). 24-25 November 2016, Beograd, Serbia: 382-387.
• 19. Mnich Matthias, Tobias Mömke. 2018. “Improved Integrality Gap Upper Bounds for Traveling Salesperson Problems with Distances One and Two”. European Journal of Operational Research 266(2): 436-457.
• 20. Pereira Armando H., Sebastián Urrutia. 2018. “Formulations and Algorithms for the Pickup and Delivery Traveling Salesman Problem with Multiple Stacks”. Computers & Operations Research 93: 1-14.
• 21. Stopka Ondrej, Jozef Gašparík, Ivana Šimková. 2015. “The Methodology of the Customers’ Operation from the Seaport Applying the ‘Simple Shuttle Problem’”. Naše More 62(4): 283-286. ISSN: 04696255.