53
1 INTRODUCTION
A new weather ship routing service is being
developed in the framework of European research
projectIONIO
5
andItalianindustrialresearchproject
TESSA
6
. The service will assist the shipmaster in
taking decisions for a safe and efficient navigation.
TheinitialDecisionSupportSystem(DSS)outlinedin
this paper will make use of meteomarine and
oceanographic operational information data for all
relevant environmental field variables (wind, waves
and currents) at high spatial and ti
me resolution.
Furthermore, the DSS will provide webbased real
timeinformation.
Academic research in the field of ship routing
developedseveraldifferentapproaches, andsomeof
themarebrieflyreviewedinthefollowing.
Takashima et.al. (2009) propose a method for
optimizing fuel consumption. It is based on a
5
http://www.ionioproject.eu/
6
http://tessa.linksmt.it/
Dijkstra’salgorithmforcomputingtheoptimalroute.
Thegridisbuiltstartingfromthestandardshiproute
and adding vertexes on lines perpendicular to the
standard route. The authors apply the method to
routesalongJapan’scoastusingmodelenvironmental
forcing with at least 6 miles resolution, and the
voyagedurationsareoftheorderofoneday.
In Wei & Zhou (2012) a dynamic progra
mming
method is used in which both ship speed and ship
course are control variables. They show that
accounting for voluntary ship speed modification
leads to extra fuel savings with respect to the
optimization with respect to ship course only. Their
grid is ma
de up of stages ofnodes perpendicular to
thegreatcircle.Thecasestudyisarouteclosetothe
Equatorwithvoyagelengthoftheorderof10days.
Szłapczynska & Smierzchalski (2009) perform a
multicriteria weather routing optimization with
respecttovoyageti
me,fuelconsumption,andvoyage
risk. Their method is based on an evolutionary
algorithm. The authors also develope a method of
ranking of routes based on the decisionmaker’s
preferences.TheyapplyittoanAtlanticroute.
A Prototype of Ship Routing Decision Support System
for an Operational Oceanographic Service
G.Mannarini&G.Coppini
CentroEuroMediterraneosuiCambiamentiClimatici,Lecce,Italy
P.Oddo
IstitutoNazionalediGeofisicaeVulcanologia,Bologna,Italy
N.Pinardi
UniversitàdegliStudidiBologna,Bologna,Italy
ABSTRACT: A prototype for an operational ship routing Decision Support System using ti
medependent
meteooceanographic fields is presented. The control variable is ship course, which is modified using a
directional resolution of less than 27 degrees. The shortest path is recovered using a modified Dijkstra’s
algorithm.Safetyrestrictions foravoidingsurfridingandpa
rametricrollingaccordingtotheguidelinesofthe
International Maritime Organization (IMO) are implemented. Numerical experiments tailored on a medium
sizevesselarepresentedandperspectivesofdevelopmentofthesystemareoutlined.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 7
Number 1
March 2013
DOI:10.12716/1001.07.01.06
54
Montes (2005) provides a detailed documentation
of Optimum Track Ship Routing (OTSR), an
automation of the weather ship routing service
providedbytheUSnavy.Therouteisretrievedbya
binary heap version of Dijkstra’s algorithm. The
system employs model fields with ½ degree spatial
resolution for both wind
and waves in the Western
Pacific Ocean. The safety is taken into account by
restricting navigation to grid points where
windspeedand wave height are within ship’s
predefinedlimits.
FortheDSS under developmentthefocus will be
on the Mediterranean Sea, where an operational
distribution of oceanographic fields
is already
running
7
(Pinardi & Coppini 2010) and subregional
models with high spatial temporal resolution are
under development in the framework ofIONIO and
TESSA projects. This willprovide a special focus on
Southern Italian seas, and in particular on their
coastalzone.TheprototypeDSSillustratedheretakes
into account the safety
restrictions from the most
recent technical guidelines for avoiding dangerous
situations on the ship. The prototype uses time
dependent environmental information for
computationoftheoptimalroutewithrespecttototal
navigation time. Route optimization with respect to
fuel consumption and other parameters is at the
planningstage.
The present paper
is organized into 4 sections,
which besides Introduction include a description of
thestructureoftheprototype(Sect.2),theapplication
oftheprototypetoseveralidealizedand yet realistic
situations(Sect.3),theconclusionsandabriefoutlook
offuturedevelopments(Sect.4).
2 PROTOTYPESTRUCTURE
In this section, the main features
of the prototype
systemapplicationaredescribed:thegridresolution,
the input fields, the ship response parametrization,
the constraints for navigational safety, and the
minimizationalgorithm.
2.1 Grid
The prototype DSS is based on a shortest path
algorithmonagraph.
Graphsaregridsforwhicheachgridpoint(“node”
or“vertex”)
isconnectedtoasubsetoftheremaining
nodes.Toeachconnection(“edge”or“link”)aweight
isassigned.Ifsuchweightdependsontheorientation
of the edge, the graph is said to be “directed”. The
objective of a shortest path algorithm is to find a
sequenceofedges
betweengivenstartandendnodes,
which lead to a minimum sum of the weights. If
chosenedgeweightisthetimeneededfornavigating
between edge nodes, then upon termination the
shortestpathalgorithmdeliverstheminimumvoyage
time.

7
http://gnoo.bo.ingv.it/myocean/
Model grid (i.e. the grid on which the meteo
oceanographic information is available) and graph
gridareingeneraldifferent.Sinceforthemomentwe
usesyntheticdataonly,wefindconvenienttoidentify
modelandgraphgrid.
A regular squared grid is constructed, with N
y
rows and N
x columns of nodes (see Table 1 for the
numericalvaluesoftheseandotherparameters).
In the work of Montes (2005), 8 edges and 8
directions per node are used, corresponding for the
northeasternquadrant oforiginnodeOto thenodes
marked with A and C in Figure 1.
This implies an
angularresolutionof45°.
Inourprototypeinstead,eachnodeisconnectedto
atotalof24edges,allowingfor16distinctdirections.
In Figure 1, points marked by A’, B’, C’, and D’
corresponds to the 4 possible directions in the
northeastern quadrant of origin node O.
Such an
organizationoftheedgesenablesreachinganangular
resolution
12givenby
o
6.26)2/1arctan(
12
(1)
Wedeemthatinanincreaseinangularresolution
iscomputationallymoreeffectivethananincreasein
grid resolution obtained by reduction of the
intermodal distance. Indeed, doubling the angular
resolution (
12 ~ 45°/2) increases the computational
cost by a factor of 3 (=24/8). Doubling the spatial
resolution instead would introduce a factor of 4
(=2^2).
Table1. Parameters of the spatial graph discretization and
inputfieldtimeresolutionemployedintheprototype.
_______________________________________________
Symbol NameValue Units
_______________________________________________
Nx=Ny Linearnumberofnodes 30‐
inthespatialgrid
D
x=Dy Spacingofthespatialgrid 4 Nautical
Miles(NM)
D
tTimeresolutionofinputfields 1 Hours
_______________________________________________
Figure1. Sample of the plot of graph edges (safegram). At
eachnode,theedgesaredisplayedasarrowspointingtothe
connected nodes. For clarity, the arrows do not reach the
nodetowhichtheypoint.Instead,theedgescorresponding
to all possible directions in the NorthEastern quadrant of
the central node O are drawn as solid lines spanning the
whole internodal distance. Note that in the vicinity of the
graphborder,therearelessthan24edgespernode.
55
Coastline, islands and other types of obstructions
can be represented on the grid as polygonal chains,
termed “barriers” in the following. Edges containing
at least one node laying within or on a barrier are
removedfromthegraph.
2.2 Inputfields
Sea state fields taken into consideration are wave
height,
wave direction, and wave period. At the
presentstageof developmentof theprototype, these
fields are not yet model output but rather synthetic
fields, designed for an idealized testing of the
prototype.
WaveheightandwaveperiodfieldsareGaussian
shaped. Allowing peak position of these fields to
change
with a prescribed velocity generates time
dependentwaveheightandwaveperiodfields.Time
resolution D
t (Table 1) corresponds to the resolution
ofmeteomarinemodelfieldstobeusedinthefuture.
The field of wave direction instead is taken to be
homogeneousinspaceandconstantintime.
2.3 Shipresponseparametrization
The edge weight used is time dt required for
navigating between edge
nodes, given the
involuntary ship speed reduction due to meteo
oceanographicconditions.Thatis:
})({Mv
dx
dt
(2)
where dx is the edge length (Euclidean distance
betweennodes)andv({M})istheinvoluntaryreduced
ship speed due to a set {M} of meteooceanographic
inputfields.
For the moment, the effect of wave height and
wave direction only is taken into account. Also,
voluntary speed reduction is
not yet implemented.
Themotorboatresponseisparameterizedas
2
0
)(),(})({ HfvHvMv
(3)
where H is the significant wave height and
is the
shipwaverelativedirection.Equation3isafitofdata
displayedin Fig.3703 of Bowditch (2002).Thevalues
ofcoefficientfarereportedinTable2.
Table2.ValuesofcoefficientfinEquation3.
_______________________________________________
Configurationnamef[kn/ft
2
]
_______________________________________________
45°Followingseas.0083
45°<<135°Beamseas.0165
135°180° Headseas.0248
_______________________________________________
Bytakingintoaccounttheaddedresistancedueto
the environmental conditions and the ship response
operator,amorerealisticmodelization of shipspeed
is possible, see e.g. Padhy (2008) and Lloyd (1998).
However, such a detail is beyond the purpose of
presentpaper.
We note that, according to Equation 3,
edge ship
velocityand,consequently,edgeweightdependsnot
only on position on the graph but also on direction.
Thus,wehaveadirectedgraph.
2.4 Safetyrestrictions
The prototype takes into account some safety
restrictionscorrespondingtotherecommendationsof
the International Maritime Organization (IMO) for
avoiding dangerous situations
in adverse weather
and sea conditions (IMO circular no. 1228). Angle
being the shiptowave relative direction (=180
o
for
followingseas),withintheprototypeitischeckedfor:
Surfriding and broachingto (shortly termed
“surfriding” in this paper). It occurs when both
conditionsarefulfilled:
135
o
225
o
(4.1)
1.8
cos(180 - )
ship
ship
o
L
v
(4.2)
Parametricrollingmotions.Itoccurswhenoneof
thefollowingconditionsisfulfilled:
|-|
E
RR
TT T
(5.1)
|2 - |
E
RR
TT T
(5.2)
where the encountered wave frequency 1/TE is
Doppler shifted with respect to wave frequency
1/Tw,as
)cos(3
3
2
shw
w
E
vT
T
T
(6)
and
is the relative tolerance in frequency
matching.
Equation6holdswhenwaveperiodsT
EandTware
expressedinsecondsandspeedv
shinknots.
In the case that navigation along a given edge
leads to a potentially unsafe situation, that edge is
removed from the graph. For this reason, we call
“safegram” every plot like the one displayed in
Figure1.
2.5 Algorithm
Once the grid and the input fields are correctly
prepared, the barrier configuration set up, the ship
response provided, and the safety restrictions taken
into account, a shortest path algorithm is run to
compute the optimal route. A Matlab®
implementation of Dijkstra’s algorithm by Joseph
Kirk
8
is used. The edge weight is computed using

8
http://www.mathworks.com/matlabcentral/fileexchange/12850
dijkstrasshortestpathalgorithm