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:

m

k

j

i

h

g

f

e

d

c

b

a

200020

)4(00000

000000

010010

0)3(0000

010100

000220

000110

003030

001010

000044

000066

F

B

−+

−+

+−

+−

−+

−+

+−

−+

+−

=

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