International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 3
Number 1
March 2009
55
Applying Graph Theory Terms to Description
of VTS
K. Jackowski
Gdynia Maritime University, Gdynia, Poland
1 INTRODUCTION
Nowadays - as VTSes are growing in number and
their area is still expanding - it may be advisable to
take into account description of marine traffic sys-
tems in terms of graph theory, with the purpose of
finding its advantages or disadvantages. A model of
a VTS, assumed to illustrate an application of graph
theory formalism, need not be very complex (though
it is the formalism invented for depicting and analys-
ing various traffic systems of great complexity).
2 EXAMPLE OF DESCRIPTION
Let system in consideration comprises two fairways
leading to pilot station, two anchorages and one
fairway from pilot station to port entrance. Its graph
representation is shown in Fig.1
Graph arcs can also have a numerical notation,
for instance: a → (1,2), b → (2,1), c → (2,4),
d → (4,2), e → (3,2), f → (2,3), g → (3,5),
i → (5,2), j → (4,6), m → (6,2).
Figure 1. VTS graph:
vertex 1 - port entrance
vertex 2 - pilot station
vertex 3 - western reporting point
vertex 4 - northern reporting point
vertex 5 - western anchorage
vertex 6 - north-eastern anchorage
arcs (directed branches) a,b,c,d,e,f,g,i,j,m
- stand for traffic lanes
loops h,k - for denoting anchored vessels
Incidence matrix J of the graph and its binary ma-
trix of adjacency A are as follows:
ABSTRACT: The paper presents an example of applying graph theory notation to description of a VTS;
it also contains some remarks on applicability of such notation for marine traffic systems
56
−+
+−
−+
+−
−+
+−
−+
+−
+−
−+
=
100010
200000
101000
010010
020000
010100
000110
000110
001010
001010
000011
000011
J
(In incidence matrix: +1 denotes arc directed to-
wards the vertex, 2 symbolizes the loop).
=
101010
010110
100010
010010
111101
000
010
A
The graph has no edges, which means that along
each traffic lane vessels may proceed in one direc-
tion only.
With the allowance for the established direction of
traffic flow, the adjacency matrix A transforms into
matrix B:
=
100010
010010
100010
010010
001101
000010
B
At any moment a traffic in the system can generally
be characterized by flow matrix F determining the
number of vessels which have departed from a point
(matrix F
O
of outcoming traffic, with graph vertices
as its sources) or vessels making for a point (matrix
F
I
of incoming traffic, vertices as outlets).
Let an example traffic distribution (for the system
in consideration) be given by flow matrix F in one
of the following forms:
=
)4(00020
0)3(0010
)0(00030
010010
001204
000060
F
O
or
=
)4(0)0(000
0)3(0100
000010
000020
213106
000040
F
I
where numerals in brackets (3),(4) denote vessels
awaiting at anchor and symbol (0) indicates that
there is no traffic in the lane.
(It is easy to notice, that F
O
T
= F
I
, that is each
matrix is transposition of the other.)
Instead of matrices F
O
, F
I
(related to vertices)
there can be used matrix F
B
for all graph branches:
where algebraic signs mark the direction of an
arc (minus, if directed from a vertex, plus − if to-
wards it); the numbers of vessels at anchor in brack-
ets (as above).
The traffic network defined by matrices F
O
, F
I
or
F
B
is illustrated in Fig.2, (next page), where:
vertices − 1,2,3,4,5,6;
arcs (traffic lanes) − a,b,c,d,e,f,g,i,m;
(in brackets the number of ships underway);
arc (lane) − j (with no traffic);
loops − h & k (in brackets the number of vessels
at anchor).
Matrices F
O
, F
I
or F
B
and its graph representation
constitute a very general description, however. To
57
give more detailed information, each arc of the
graph (i.e. each traffic lane in the system) should
have its ascribed vector of state which, at any given
moment, characterizes the traffic flow in the lane.
(And similarly, each vertex can be described by its
state vector as well.)
For instance, state vectors describing port ap-
proach fairway at a chosen moment could be as fol-
lows:
a (lane 1,2):
[ 0
H
15
M
, 0
H
40
M
, 0
H
55
M
, 1
H
25
M
, 1
H
55
M
, 2
H
10
M
],
b (lane 2,1):
[ 0
H
20
M
, 0
H
45
M
, 1
H
10
M
, 2
H
15
M
],
where vector a (1,2), for 6 vessels proceeding to
pilot station, gives remaining time to go for each of
them and vector b (2,1), for 4 vessels approaching
port entrance − remaining time to enter the harbour.
Exemplary state vectors for anchorages,
h (5,5):
[ 3
H
15
M
, 6
H
30
M
, 10
H
00
M
]
and k (6,6):
[ 0
H
30
M
, 2
H
45
M
, 8
H
00
M
, 12
H
00
M
],
define time to wait at anchor, for each vessel. (
For vertices, which are junction nodes of the traffic
system, the notion “state” may mean whether the
node is accessible and passable, or not.)
Of course, the examples given are the simplest
ones. The vectors of state, if necessary, may include
many more particulars, such as next destination
point or allotted berthing place, kind and amount of
cargo, some ship’s data, existing restrictions and
constrains etc. (And for such “vertex”, as p o r t , the
state of the “point” may depend, in very complex
and sophisticated way, on internal port traffic, cargo
handling operations and other technical and econom-
ical factors.)
Figure 2. Graph of traffic
Vectors of state of every traffic lane and waiting
area (a, b, c, d, e, f, g, h, i, j, k, m) together with
state vectors of vertices (v
1
, v
2
, v
3
, ..., v
6
) and flow
matrix F define the state of the whole system.
Transformation of state may be determined by
two sets of functions:
{v
x
(t)} for vertices and {w
u
(t)} for arcs,
where t denotes time;
(in considered example of traffic system, index x:
1,2,3,4,5,6 and u: a,b,c.d,e,f,g,h,i,j,k,m);
these functions also implicate transformation of
flow matrix: F(t) = F({v
x
(t)}, {w
u
(t)}).
In general, transformation functions are determin-
istic, but they may include statistical parameters and
random variables as well, or be stochastically modi-
fied. It would be useful to reckon and apply such
transformation operators W, V, T, that:
w
u
(t) = W(t, t
o
) w
u
(t
o
),
v
x
(t) = V(t, t
o
) w
u
(t
o
),
F(t) = T(t, t
o
) F(t
o
) or F(t) = T(t) B
Finding affine forms
W, V, T,
however, is not an easy task, as usually the prob-
lem is non-linear, or the attempts to solve it may en-
tail the necessity of inversion of a singular matrix.
3 FINAL REMARKS
Graph description of traffic systems is inseparably
associated with matrix algebra formalism. A major
practical difficulty with application of this descrip-
tion, as it seems now, is the problem of finding line-
ar (matrix) operators for transformation of state of
the depicted system. Searching for a solution may be
done in the way of decomposing the transformation
into a few stages, doing indispensable simplifica-
tions and finally introducing such variables and pa-
rameters (resulting from the intermediate stages of
transformation), which – albeit somewhat artificial –
make possible to express transformation of state by
required matrix operators. It is clear, that such de-
composition can not be excessive (too many stages
of transformation may turn one complex problem in-
to another) and also that undue simplifications may
affect negatively the result of transformation.
All of these may hinder the application of graph
description to marine traffic systems.
On the other hand, however, its expected ad-
vantages are obvious. Matrix notation is especially
suitable for real-time automatic data processing and
58
ensure obtaining requested information quickly and
easily.
As to problems with creation of dynamic graph
models of traffic systems, which may arise in case of
very complex and extensive systems – they can be
overcome gradually: by proceeding from simplest
version of the description towards more sophisticat-
ed ones.
The existing possibilities of simulation experi-
ments and examining the effects of theoretical inves-
tigations by simulator tests shall make it managea-
ble.
REFERENCE LIST
[1] Chen W.K.: Applied Graph Theory, North-Holland, Am-
sterdam 1976
[2] Kubale M.: Introduction to Computational Complexity and
Algorithmic Graph Coloring, Gdańsk Scientific Society,
Gdańsk 1998
[3] Leszczyński J.: Modelowanie systemów i procesów trans-
portowych, Oficyna Wydawnicza Politechniki Warszaw-
skiej, Warszawa 1999
[4] Piszczek W.: Modele miar systemu
inżynierii ruchu mor-
skiego, Studia nr 14, Szczecin 1990
[5] Wilson R.J.: Introduction to Graph Theory, Oliver and
Boyd, Edinburg 1972