Article
citation information:
Chládek, P., Smetanová,
D., Krile, S. On some aspects of graph theory for optimal transport among marine ports.
Scientific Journal of Silesian University
of Technology. Series Transport. 2018, 101,
3745. ISSN: 02093324. DOI: https://doi.org/10.20858/sjsutst.2018.101.4.
Petr CHLÁDEK[1],
Dana SMETANOVÁ[2],
Srećko KRILE[3]
ON SOME ASPECTS OF
GRAPH THEORY FOR OPTIMAL TRANSPORT AMONG MARINE PORTS
Summary. 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.
Keywords: Travelling Salesman Problem; graph
theory; minimum spanning tree;
marine ports
1. INTRODUCTION
The Travelling Salesman Problem (TSP) is
formulated as a task with a given set of cities and the paths between them. The
task is to find the shortest (most economical) path passing through all the
cities and returning to the starting point. The TSP is usually formulated using
concepts based on graph theory. Graph vertices represent cities, while graph
edges refer to individual paths between cities. In the traditional view, the
solution to the problem lies in finding a closed path (a circle) on a rated
(usually nonoriented) graph, cf. [1, 8]. Contrary to the classical case, our
method recognizes that distances
between individual cities are different when travelling in the opposite
direction. Such a situation is described by means of a closed path in an
oriented graph. The TSP remains a viable topic for study, cf. [2, 7, 1920].
The Czechoslovak
Ocean Shipping (COS) company was founded in 1959. During its existence, the
company was using 28 home ports in various countries. This paper is devoted to
the Black Sea region. In this area, the business interests of the company were
realized through seven marine ports (Braila, Galati, Reni, Izmail, Constanza, Varna, Burgas) in three
countries (Bulgaria, Romania, Ukraine). There are currently other transport
companies operating in the Czech Republic that engage in ocean shipping. These
include DSV Air & Sea s.r.o., Cargo IHL  International Shipping Company,
Multitrans CZ s.r.o. and Logex Logistics, s.r.o. These companies are represented
in most of the major world ports, including former home ports of COS. For the
history of Czechoslovak maritime shipping, see, e.g., [10, 15].
In line with the TSP principles, we search for
and also compare the shortest and longest paths from Prague, through all seven
ports and back to Prague. We assume that the trip from Prague to the Black Sea
area takes place by air, the journey then continues through the individual
ports and ends after a final return flight back to Prague. Given that, among
the cities in question, only Varna and Burgas had operational international
airports at the time COS existed,
these two locations necessarily become the second and the penultimate vertices on
our graph.
2. DATA AND METHODS
For calculating and finding the shortest
path, we are going to use the road distances between the ports listed in Table
1 and the air distances from Prague to the Black Sea. The air distance from
Prague to Varna (or from Varna to Prague) is 1,279 km and the air distance from
Prague to Burgas (or from Burgas to Prague) is 1,304 km.
Table
1
Shortest distances
(in km) [7]
Varna 
Burgas 
Constanza 
Izmail 
Reni 
Galati 
Braila 

Varna 
 
 
160 
438 
372 
349 
332 
Burgas 
 
 
290 
502 
436 
414 
393 
Constanza 
158 
288 
 
283 
217 
194 
178 
Izmail 
435 
503 
283 
 
66 
89 
111 
Reni 
369 
437 
217 
66 
 
23.3 
44.4 
Galati 
346 
414 
194 
89 
23.3 
 
21.5 
Braila 
330 
392 
177 
110 
44.6 
21.7 
 
We emphasize that, in most
theoretical tasks of this type, it is assumed that the distances between two
vertices A and B are the same in both directions: AB, BA. However, in the
case of real road traffic, these distances may be different (see Table 1). The
difference may be caused, for example, by oneway roads, highway connections
and city bypasses.
The transport problem is modelled
using a graph. All graphs represented in this article are finite, connected,
weighted and closed with oriented edges. The system of traffic routes can be
transformed into a graph in which vertices represent seaports, edges represent
transport routes and weights of edges represent the energy consumed while using
the means of transport (ship, car, airplane, train or something else) between
the respective two ports. To model this situation, we create a connected graph G=(V,E), where V is the set of n
vertices and E is the set of edges as
usual. The edges are weighted.
A Hamiltonian path is a path that
visits each vertex of the graph exactly once. A Hamiltonian cycle is a closed
path that visits each vertex exactly once (except for the vertex that is both
the start and the end, which is visited twice). A graph containing a
Hamiltonian cycle is called a Hamiltonian graph. In the language of graph
theory, the TSP requires finding a Hamiltonian cycle with the smallest sum of
the weights of the edges.
Using the mathematical software
“Maple”, the length of all circular paths (Hamiltonian cycles) was
computed. All discovered circular paths were divided into two groups. The first
group included paths beginning with PragueBurgas nodes and ending with
VarnaPrague nodes. The second group included paths beginning with PragueVarna
nodes and ending with BurgasPrague nodes. The paths in each group were
examined individually and arranged in terms of length from the shortest to the
longest. From each group, the five longest and five shortest paths were
selected. It has been examined whether the five shortest paths in Group 1
correspond exactly to the five shortest paths in Group 2, except for the fact
that they run in opposite directions. The same methodology was used for the
five longest trips of each group. The conclusions are presented in Table 25
with a subsequent analysis of the findings.
For comparison with Hamilton cycles,
we present a minimum spanning tree (MST) and its length. Although the MST does
not solve the problem of circular paths, it has significant use in logistic
processes. A typical application of such an MST algorithm would be in searching
for the most effective way for road or train lane construction, electricity
distribution, water distribution and especially engineering networks.
The spanning tree of a connected
graph G is a subgraph G´, which connects all vertices
but does not contain any cycles [9, 14]. For the MST, we denote _{}, where _{} and E´
represents the set of n 1 edges of
the MST, such that that _{}. The sum of the weights _{} of the edges of the MST is minimal. Thus,
for subgraph G´= (V´,E´) of the graph G, we propose _{} and the spanning tree G´ of the graph G is minimal if,
for each spanning tree G´´
of the graph G, it holds that _{}.
There are several generally known
algorithms that use different ways to search for the MST, e.g., Kruskal’s
algorithm [16], Prim’s algorithm or Borůvka’s algorithm.
3. RESULTS
This chapter summarizes and interprets the
results that have been obtained from input data by mathematical methods.
For the purposes of summary, in Tables 25,
we use the following markings for individual ports: Bu  Burgas, V  Varna, C 
Constanza, I  Izmail, R  Reni, G  Galati, Br  Braila, P  Prague.
Two paths can be considered as mutually
equivalent if these paths pass through the ports in reverse order, e.g., the
first path in Table 2 (PBuBrIRGCVP) and the fourth path in Table
3 (PVCGRIBrBuP). The following tables present two sets of the
five shortest and longest paths in the direction PragueBurgas and
PragueVarna, including the paths equivalent to them.
Table
2
The shortest paths
in the direction PragueBurgas
PATH 
DISTANCE 
EQUIVALENT PATH 
DISTANCE 
PBuBrIRGCVP 
3,527.3 
PVCGRIBrBuP 
3,529.3 
PBuBrRIGCVP 
3,527.6 
PVCGIRBrBuP 
3,528.4 
PBuBrGIRCVP 
3,527.7 
PVCRIGBrBuP 
3,528.5 
PBuBrGRICVP 
3,528.0 
PVCIRGBrBuP 
3,528.8 
PBuRIGBrCVP 
3,530.5 
PVCBrGIRBuP 
3,534.7 
In the left half of Table 2, we see the
shortest paths in the direction of PragueBurgas, while the right half shows
the equivalent paths. A similar layout for the PragueVarna paths is found in
Table 3.
Table
3
The
shortest paths in the direction PragueVarna
PATH 
DISTANCE 
EQUIVALENT PATH 
DISTANCE 
PVCGIRBrBuP 
3,528.4 
PBuBrRIGCVP 
3,527.6 
PVCRIGBrBuP 
3,528.5 
PBuBrGIRCVP 
3,527.7 
PVCIRGBrBuP 
3,528.8 
PBuBrGRICVP 
3,528.0 
PVCGRIBrBuP 
3,529.3 
PBuBrIRGCVP 
3,527.3 
PVCBrIRGBuP 
3,534.3 
PBuGRIBrCVP 
3,532.3 
For the five longest paths in each direction,
Tables 45 are compiled in an analogous manner to the Tables 23. Table 4
concerns the PragueBurgas routes.
Table
4
The
longest paths in the direction PragueBurgas
PATH 
DISTANCE 
EQUIVALENT PATH 
DISTANCE 
PBuGCIBrRVP 
3,998.6 
PVRBrICGBuP 
4,000.4 
PBuGBrRCIVP 
3,998.1 
PVICRBrGBuP 
4,001.1 
PBuRCIBrGVP 
3,997.7 
PVGBrICRBuP 
4,000.5 
PBuIBrGCRVP 
3,997.7 
PVRCGBrIBuP 
4,000.5 
PBuIBrRCGVP 
3,997.6 
PVGCRBrIBuP 
4,000.4 
Table 5 contains the longest paths
in the direction PragueVarna. It can be noticed that the table contains a
larger number of items (paths) than the previous ones, due to the existence of
four paths of identical length in kilometres (4,001.1) in fifth place.
Table
5
The longest paths in the direction PragueVarna
PATH 
DISTANCE 
EQUIVALENT PATH 
DISTANCE 
PVRCIBrGBuP 
4,001.7 
PBuGBrICRVP 
3,997.5 
PVIBrGCRBuP 
4,001.7 
PBuRCGBrIVP 
3,996.5 
PVGCIBrRBuP 
4,001.6 
PBuRBrICGVP 
3,996.4 
PVIBrRCGBuP 
4,001.6 
PBuGCRBrIVP 
3,997.4 
PVGBrRCIBuP 
4,001.1 
PBuICRBrGVP 
3,997.1 
PVRBrGCIBuP 
4,001.1 
PBuICGBrRVP 
3,997.1 
PVICGBrRBuP 
4,001.1 
PBuRBrGCIVP 
3,997.1 
PVICRBrGBuP 
4,001.1 
PBuGBrRCIVP 
3,998.1 
From these tables, various observations can be made, which are discussed in the next chapter. Next, Figure 1 shows the MST of the examined graph. The length of the MST is 2,012.8 km.
Fig. 1. MST
4. DISCUSSION
In Tables 25, one can see that the paths in which Varna is the second vertex are longer than the paths starting with the PragueBurgas step.
A. PragueBurgas direction: In this direction, the shortest path found has a length of 3,527.3 km. The cities were passed in the following order: PragueBurgasBrailaIzmailReniGalatiConstanzaVarnaPrague (Figure 2). Due to asymmetries in Table 1, the length of this path in the opposite direction is 3,529.3 km (Table 2).
B. PragueVarna direction: In this direction, the shortest path has a length of 3,528.4 km. The cities were passed in the following order: PragueVarnaConstanzaGalatiIzmailReniBrailaBurgasPrague. The length of this path in the opposite direction is 3,527.6 km.
From Tables 23, it becomes apparent that, if we compare the five shortest paths in both directions, the following applies:
1) Of the five shortest paths in each direction, only four are mutually equivalent.
2) When arranging paths in terms of distance, the mutually equivalent paths do not appear in the same position in the order.
3) The path from Table 2, which does not have an equivalent counterpart in Table 3, and the path from Table 3, which does not have an equivalent counterpart in Table 2, both appear in fifth position in their respective tables.
4) In the direction PragueBurgas, the distance difference between the first and the fifth path is only 3.2 km, while, in the direction PragueVarna, it is 5.9 km. Corresponding to this fact, the distance differences in the columns displaying equivalent paths are greater in the direction PragueVarna than in the direction PragueBurgas.
Fig. 2. The shortest and the longest Hamiltonian cycles
In a similar way, we can classify the five longest paths in both directions, as described in Tables 45:
1) For the direction PragueVarna, the table contains a greater number of paths than five, because, in Table 5, there are four paths of equal length in kilometres.
2) Among the longest paths listed in both directions, there are only two equivalent ones (one in each table). Furthermore, these two paths do not appear in the same position in the order.
3) In the direction PragueBurgas, the difference between the first and the fifth path is 1 km, while, in the direction PragueVarna, the difference in length between the paths is only 0.6 km. Corresponding to this fact, the distance differences in the columns displaying equivalent paths are smaller in the direction PragueVarna than in the direction PragueBurgas.
4) The longest path of all has a length of 4,001.7 km and can be achieved in two different ways (one of them is described in Figure 2).
The overall comparison of all tables shows that the distance differences between the shortest paths are in the order of kilometres, while the differences between the longest paths are in the order of hundreds of meters.
In line with
the formulation of the problem, the BurgasVarna edge is excluded from this
graph. This fact had to be taken into account in all calculations and also
while constructing Figures 12. It might appear to be more advantageous to use
the spanning tree for comparing the length of the MST and Hamiltonian cycles.
However, according to the formulation of the problem (Chapter 1), the path must
end again at the starting vertex. Therefore, when using the MST, it is
necessary to pass each edge twice (see Figure 1). Thus, the length of the path
is disproportionately increased, so it is much more advantageous to use
Hamiltonian cycles for solving this task.
5. CONCLUSION
In this paper, the discussed TSP has
an additional property, namely, that paths in opposite directions can have a
different length. The differences between the five shortest and the five
longest paths between Black Sea ports are studied and the paths are compared
with an MST. The shortest and the longest paths are found in both possible
directions. Differences between equivalent paths are discussed.
In the field of transport studies,
many different methods are being used to solve optimization problems, be it the
optimization of transport itself [2, 4, 67, 1112], the placement
of logistics centres [5, 13] or the construction of transport networks
[3]. Other practical applications of a theoretical approach to freight
transport or combined transport issues are studied in [1718, 21].
We may expect that the further study
of transport optimization will continue to take into account everincreasing
traffic density, the increasing volume of freight transported, improvements in
technologies and rising standards of living.
Acknowledgements
This article was supported by Project Grant No.
IGS06C2 from the Faculty of Economics, University of South Bohemia, Czech
Republic.
References
1.
Applegate David L.
et al. 2006. The Traveling Salesman
Problem. Princeton: Princeton University Press. ISBN: 9780691129938.
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):
895902. 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):
300304.
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): 9196. 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, 57 October 2016. Book
Series: Transport Means  Proceedings of
the International Conference: 107111.
6.
Čejka
Jiří. 2016. “Transport Planning
Realized Through the Optimization Methods”. World Multidisciplinary Civil EngineeringArchitectureUrban Planning
Symposium 2016, WMCAUS 2016. Book Series: Procedia Engineering 161: 11871196.
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: 9780691163529.
9.
Cormen Thomas H.,
Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. 2001. Introduction to Algorithms, Second Edition.
MIT Press and McGrawHill. ISBN:0262033844 9780262033848.
10.
Herman Jan. 2015. “Czechoslovak Shipping in the Interwar Period: The
Maritime Transport Operations of the Baťa Shoe Company, 19321935”. The International Journal of Maritime
History 27(1): 79103. ISSN: 08438714. DOI: 10.1177/0843871414566579.
11.
Jelínek
Jiří. 2014. “Municipal Public
Transport Line Modelling”. Komunikacie
16 (2): 48. 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): 115119. ISSN: 04696255.
13.
Kampf Rudolf, Petr
Průša, Christopher Savage. 2011. “Systematic Location of the Public Logistic Centres
in Czech Republic”. Transport
26(4): 425432. ISSN: 16484142. DOI: 10.3846/16484142.2011.635424.
14.
Kleinberg Jon M.,
Eva Tardos. 2006. Algorithm Design. New York: Pearson Education Inc. ISBN:
9780321295354.
15.
Krátká
Lenka. 2016. “Czechoslovak Seafarers
Before 1989: Living on the Edge of Freedom”. The International Journal of Maritime History 28(2): 376387. ISSN:
08438714. DOI: 10.1177/0843871416630687.
16.
Kruskal Joseph B. 1956.
“On the Shortest Spanning
Subtree of a Graph and the Traveling Salesman Problem”. Proceedings of the American Mathematical
Society 7: 4850.
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: 10831087.
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). 2425
November 2016, Beograd, Serbia: 382387.
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): 436457.
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: 114.
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): 283286. ISSN:
04696255.
Received 15.08.2018; accepted in revised form 21.10.2018
Scientific
Journal of Silesian University of Technology. Series Transport is licensed
under a Creative Commons Attribution 4.0 International License
[1] Faculty of Economics, University of
South Bohemia, Studentská 13 Street, 370 05 České
Budějovice, Czech Republic. Email: chladek@jcu.cz.
[2] Faculty of Technology, The
Institute of Technology and Business, Okružní 10 Street, 370 01
České Budějovice, Czech Republic. Email:
smetanova@mail.vstecb.cz.
[3] University of Dubrovnik, Dubrovnik,
Ćira Carića 4 Street, 20000 Dubrovnik, Croatia. Email:
srecko.krile@unidu.hr.