61
1 INTRODUCTION
Along with rapid development of multicriteria
methods and algorithms in the last 15 years,
popularity of multiobjective optimization in route
finding has been constantly increasing. In such
multicriteria approach the task is to find the most
suitable route, taking into account two or more
criteria(suchaspassageti
meand fuel consumption)
simultaneously. The majority of generic multicriteria
optimization algorithms utilize genetic or
evolutionary computations (GC/EC), thus this
approach has become a foundation for the most of
multiobjectiveroutefindingapplications.
The search space in evolutionary route finding
processmaybeeitherdiscreetorcontinuous.Thefirst
case is usually ut
ilized for vehicle optimal route
finding. Kim et al. (2009), among other researchers,
proposedadiscreetspacemulticriteriarouteplanning
forvehiclesbasedontheGC/ECapproach.However,
in case of ship route finding process the continuous
search space is considered in most cases. Possible
locations of consecutive route waypoints are limit
ed
bytheoptimizationcriteriaandconstraintsonlyand
hardlycanbeconsideredtoformafixedgrid.Thatis
thekeyreasonbehindselectingthecontinuoussearch
spaceforshiproutefindings.
Whenatransoceanicvoyageofavesselisplanned
the weather conditions as well as some navigational
obstacles (e.g. narrow passages) must be ta
ken into
account.Thisprocess,called“weatherrouting”,may
be supported by software applications usually
following the implementation of a singlecriterion
isochrone method (James, 1957). Numerous
improvementstotheoriginalisochronemethodwere
proposed since early eighties, with Hagiwara (1989),
Spaans (1986) and Wisniewski (1991) am
ong others.
The modified isochrone methods are able to find a
timeoptimal or fueloptimal route, yet are not
suitabletohandle multicriteria optimization. Thus, a
multicriteria approach towards weather routing has
been proposed so far by Hinnenthal (2007), Marie &
Multicriteria Evolutionary Weather Routing
Algorithm in Practice
J
.Szlapczynska
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT: The Mult
icriteria Evolutionary Weather Routing Algorithm (MEWRA) has already been
introducedbytheauthoronearlierTransNav2009and2011conferenceswithafocusontheoreticalapplication
to a hybridpropulsion or motordriven ship. This paper addresses the topic of possible practical weather
routingapplicationsofMEWRA.Inthepapersomepra
cticaladvantagesofutilizingParetofrontasaresultof
multicriteria optimization in case of route finding are described. The paper describes the notion of Pareto
optimality of routes along with a simplified, easy to follow, example. It also discusses a choice of the most
suitablerankingmethodforMEWRA(acomparisonbetweenFuzzyTOPSISandZeroUnit
arizationMethodis
presented).InadditiontothatthepaperbrieflyoutlinesacommercialapplicationofMEWRA.
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.07
62
Courteille (2009) and by the author of this paper
(Szlapczynska, 2007). All the proposed methods
utilizesome multicriteria GC/EC algorithmto search
continuous search space to find Paretooptimal
(optimal in multiobjective sense) set of routes. Both
the solutions by Hinnenthal and Marie et al. utilize
MultiObjectiveGeneticAlgorithm
MOGA,however
are restricted to provide the Paretooptimal set of
routes as their final result. The multicriteria weather
routingmethodproposedbytheauthor,Multicriteria
Evolutionary Weather Routing Algorithm (MEWRA)
utilizesthemorerobustGC/EC algorithm Strength
Pareto Evolutionary Algorithm‐SPEA (Zitzler &
Thiele, 1999). But what
is even more important,
MEWRAincludes amechanismofselectingoutofthe
Paretoset a single route that isthe most suitable for
the decisionmaker. It is provided by considering
decisionmaker’s preferences towards the criteria by
theadditionalmulticriteriarankingmethod.Lastbut
not least, difference between MEWRA
and the other
solutions is that MEWRA evolves only the feasible
routes(ie.routesthatdonotcrossthelandobstacles),
which makes the MEWRA’s results acceptable from
the navigational standpoint regardless of the
computationaltime(numberofgenerations).
MEWRAhasalreadybeenpresentedbytheauthor
on previous TransNavʹ
2009 and TransNav’2011
conferenceswithafocusontheoreticalapplicationto
a hybridpropulsion or a motordriven ship. The
objective of this paper is to present some aspects of
practicalMEWRAapplications.Therestofthepaper
is organized as follows. Section2 recalls the basic
foundationsofMEWRAalgorithm.
Section3presents
selected aspects of practical MEWRA application. It
describes the notion of Paretooptimality of routes
along with a simplified, easy to follow, example.
Section 3 presents also a comparison between two
multicriteria ranking methods: Fuzzy TOPSIS and
Zero Unitarization Method and points the one more
suitablefor
MEWRA.Thenextsectionbrieflyoutlines
thecommercializationprocessofMEWRAasapartof
NaviWeather tool by NavSim. Section 5 summarizes
thepresentedmaterial.
2 MULTICRITERIAEVOLUTIONARYWEATHER
ROUTINGALGORITHM(MEWRA)
Themulticriteriaset of goal functions intheweather
routing optimization process proposed by
(Szlapczynska & Smierzchalski, 2009) is
given by
equations1‐4:

_
min
passage time r r
ftt (1)

_
min
fuel consumption fc fc
fqq
(2)

_
min
voyage risks risk risk
fii (3)
2
1
jsafety
k
risk
i
i
k
(4)
where:
t
r=[h]passagetimeforgivenrouteandshipmodel,
q
fc =[g]totalfuelconsumptionforgivenrouteand
shipmodel,
i
risk= [dimensionless] risk coefficient for given route
andtheshipmodel,
k=[dimensionless]numberofroute’ssegmentswithi
j
safety<1,
i
jsafety = [dimensionless] fractional safety coefficient for
(j1)th and jth waypoints and given ship model;
valuesofthecoefficientranges[0;1],where1depicts
completelysafesectionofrouteand0unacceptably
dangerous section. Definition of the coefficient for a
hybridpropulsion ship was presented
in
(Szlapczynska, 2007) and for a motordriven ship in
(Krata&Szlapczynska,2012).
The weather routing optimization process is
defined as a constrained one. The key optimization
constraint set includes landmasses and predefined
minimum acceptable level of fractional safety
coefficienti
jsafetyforgivenroute.
The abovementioned optimization model has
become a foundation for MEWRA‐Multicriteria
Evolutionary Weather Routing Algorithm. MEWRA,
as presented in Figure 1, utilizes two basic
multicriteria mechanisms, namely multicriteria
evolutionary algorithm Strength Pareto
Evolutionary Algorithm, SPEA (Zitzler & Thiele,
1999) and a multicriteria ranking method. The SPEA
framework in the proposed algorithm is responsible
for iterative process of population development. The
result of SPEA is a Paretooptimal set of solutions.
Themulticriteriarankingmethod(e.g.FuzzyTOPSIS
or Zero Unitarization Method) is responsible for
sortingthe resultingParetooptimal solutions
according to the given preferences of the
decision
maker.
An individual in the evolutionary approach
representsasingleroute.Therouteincludesanarray
ofwaypointsconstitutingship’stra ck, wherethefirst
oneisequaltothepositionoftheoriginportandthe
lastonetothedestinationport.Asingleentryofthe
waypoint
array includes also some additional
parameterscharacterizingtheshiptrackbetweenthe
(n1)thandnthwaypoints.
The initial population is a set of predefined and
randomly generated routes. Modified isochrone
routes (Spaans, 1986 & Hagiwara, 1989) a time
optimalandafueloptimalmayalso
beincludedin
theinitialset.ThesetbecomesaninputforSPEA‐the
evolutionary multicriteria optimization algorithm.
Theevolutionaryprocesstransformsthesetbymeans
of mutation, crossover & specialized operators to
browse through the whole (or at least the most of)
searchspace. TheSPEAresultisa
Paretooptimalset
ofroutes.
63
Figure1.MEWRA’salgorithmflow
The resulting set may include a variety of
diversified,yetoptimalinmulticriteriasense,routes:
some having short passage time, some other having
low fuel consumption and possibly other assuring
high safety though the voyage. Details on how the
Paretoset is constructed can be found further in the
paper,inSection3.1.
The final step is to sort the Paretoset of routes
accordingtothedecisionma
ker’s(e.g.captainsofthe
ship) preferences. The decisionmaker can assign a
value (by a number e.g. 0.7 or linguistic value e.g.
“good”)toeachofthethreeoptimizationcriteria,thus
reflecting their preferences to each crit
erion. Then a
ranking method is able to sort the set. This way the
firstrouteistheParetooptimalonewhichisthemost
suitable for given preferences. Usually this route
becomes a route recommendation. Unlike the SPEA
processing,thesortingprocedureisabletoreturnit
s
resultsimmediately,thus,incasethedecisionmakers
changetheirmindaboutthepreferences,thelaststep
canberepeatedmultipletimes.Further discussionon
the most suitable MEWRA ranking method can be
foundinSection3.2.
3 MULTICRITERIAOPTIMISATIONOFSHIP
ROUTESINPRACTICE
The author’s earlier papers on MEWRA were met
with quest
ion concerning the notion of multicriteria
Paretooptimality,especiallyinrelationtoshiproutes.
Therefore the first subsection introduces a practical
definitionofroutePareto optimalityaccompaniedby
aneasytofollowexample.
The previous MEWRA papers (Szlapczynska,
2007, Szlapczynska & Smierzchalski, 2009, Krata &
Szlapczynska, 2012) int
roduced Fuzzy TOPSIS as a
multicriteriarankingmethod.Inpractice itappeared
that the Fuzzy TOPSIS method has several
disadvantages and another method has been
proposedinstead,namelyZeroUnitarizationMethod
(Kukula,2000).Thesecondsubsectionprovides brief
definitions of both methods, compares their
propertiesandjustifiesthefinalselectionbetweenthe
tworankingmethods.
3.1 Paretooptimalsetofroutes
In order to define Paretoopt
imality (optimality in
pure multicriteria sense) first the notion of Pareto
dominance must be introduced. Let us consider two
routesA&B.RouteAParetodominatesBifandonly
if A has at least one pa
rameter (a value for
optimizationcriterion)betterthanBandalltheother
parameters of A are no worse than B. Then, a set of
Paretooptimal individuals is built by routes that
cannot be Pareto dominated by any other route. To
conclude the definition, the notion of Pareto
opt
imality always refers to a set of routes and its
checking is performed via testing Paretodominance
betweeneverypairofroutesinthisset.
Now, let us consider an exemplary set of routes
presentedinTable1forwhichParetooptimalitywill
bechecked.Itisassumedthattherearethreestandard
op
timization criteria, namely passage time (given in
hours),fuelconsumption(givenintons)andsafetyof
passage (dimensionless). The last criterion, to keep
the example simple, is specified by linguistic values:
“good”,“moderate”and“onlysatisfactory”.Thetime
& fuel criteria should be minimized, but the safety
crit
erion should be maximized (i.e. “good” safety is
betterthan“moderate”one).
Table1.ExemplarysetofroutesforwhichParetooptimality
willbechecked.
_______________________________________________
Time[h]  Fuel[t] Safety
_______________________________________________
Route#1200200good
Route#2210180good
Route#3190175moderate
Route#4250190good
Route#5205205onlysatisfactory
_______________________________________________
TheresultsofParetodominancecheckonthi
sset
ispresentedinTable2.
The Paretooptimal set of routes is constructed
basedontheoriginalset(Table1)takingintoaccount
Pareto dominance check results (Table 2). In Table 3
the final Paretooptimal set for the considered
exampleispresented.
64
Table2. Results of Pareto dominance check on the
exemplaryrouteset.
_______________________________________________
Dominancecheck Checkresult
betweenapairofroutes
_______________________________________________
Does#1dominate#2? No
Does#1dominate#3? No
Does#1dominate#4? No
Does#1dominate#5? Yes(allparametersofroute#1are
betterthanthoseofroute#5),thus
removeroute#5asdominated
Does#2dominate#1? No
Does#2dominate#3? No
Does#2
dominate#4? Yes (betterintime&fuel),thus
removeroute#4asdominated
Does#2dominate#5? Don’thavetocheck,#5is
dominated&removedfromtheset
Does#3dominate#1? No
Does#3dominate#2? No
Does#3dominate#4? Don’thavetocheck,#4
is
dominated&removedfromtheset
Does#3dominate#5? Don’thavetocheck,#5is
dominated&removedfromtheset
Allchecksfor#4Don’thavetocheck,#4is
dominated&removedfromtheset
Allchecksfor#5Don’thavetocheck,#5is
dominated&removedfromtheset
_______________________________________________
Table3. Paretooptimal set of routes for the considered
example.
_______________________________________________
Time[h]  Fuel[t] Safety
_______________________________________________
Route#1200200good
Route#2210180good
Route#3190175moderate
_______________________________________________
Thefinalsetincludesonlythreefirstroutes,while
routes#4&#5havebeenremovedasdominatedones
(route #4 is dominated by route #2 and route #5 is
dominatedbyroute#1).TheresultingParetooptimal
routesobviouslydifferinvaluesoftheirparameters.
One can choose the shortest
and cheapest route (#3)
forthecostofloweredsafetylevel.Alternatively,one
cangoforhighersafetylevelandpicktheroutewith
possiblelowestfuelconsumptionwith“good”safety
(#2)ortheonewithmoderatetime&fuelvalues(#1).
Itis common thatroutes insuchsets
differ. Even
inreal,muchbiggerParetooptimalroutesets,thereis
alwaysaroutewithshortestpassage,possiblythereis
another (in the example it is the same one) having
lowest fuel consumption, some other with highest
safetylevelandfinallyasetofrouteswithparameter
values in between
the extremes. It is then up to the
useroftheParetosettopickthemostsuitableroute.
InMEWRAtheprocessofselectionthemostsuitable
route out of the Paretoset is facilitated by the
multicriteriarankingmethod.
3.2 Comparisonofrankingmethodinrouteselection
Fuzzy
TOPSISisa multicriteria ranking methodthat
has been originally proposed as part of MEWRA
(Szlapczynska, 2007, Szlapczynska & Smierzchalski,
2009).Themethod,proposedbyChu&Lin(2003),is
based on a technique of ranking building called
Technique for Order Preference by Similarity to an
Ideal Solution (TOPSIS). The technique
utilizes an
approach towards ranking building that the best
alternative among the available alternative set is the
closest to the best possible solution and the farthest
fromtheworstpossiblesolutionsimultaneously.The
Fuzzy TOPSIS implementation by Chu & Lin (2003)
introduces additional support for linguistic values,
fuzzy criteria and
fuzzy weights (described by
triangularfuzzyvalues).
Fuzzy TOPSIS is a commonly used multicriteria
ranking method, valued mostly for allowing easily
obtainable tradeoffs between criteria and
customizable fuzziness support. However, in a
practical implementation of MEWRA (described
brieflyinthenextsection)themethodexposesseveral
important drawbacks. The most
important one is its
propertyof compensation.The compensatory
methods, such as Fuzzy TOPSIS, allow for situation
whereapoorresultinonecriterionmaybeconcealed
by a good result in another criterion. In case of
searching for ship routes such property is not
welcomed, since for example poor
safety level of a
routeshouldnotbecompensatedbyitsshortpassage
time. Another important issue is that the method
require complex configuration, which may be not
enough user friendly. Last but not least, the method
assumesquitesophisticatedcalculustoreturnresults,
whichmaybecomesignificantlytimeconsuming for
a
vastsetofroutes.
To overcome the abovementioned problems
another multicriteria ranking method has been
applied to the practical MEWRA implementation,
namely Zero Unitarization Method‐ZUM (Kukula,
2000). The ZUM is a noncompensatory muticriteria
ranking method allowing normalization of the
diagnosticvariablesbythegapbetweenthevariable’s
valueandthemostortheleastsuitablevariablevalue
(depending on the optimization direction). Its
configuration is straightforward and computations
arelimitedtobasicmultiplicationanddivisionofreal
values. The author proposes also some obvious
extensionstothemethod:
introducing normalized weights assigned to the
criteria,
introducing
linguisticvaluestoZUMbyassigning
fixedvaluestoeachlinguisticvalue.
All these makes ZUM the more suitable ranking
method for MEWRA purposes comparing to Fuzzy
TOPSIS.Table4presentsadirectcomparisonbetween
thetwomethods.
Table4. Comparison of Fuzzy TOPSIS and Zero
UnitarizationMethod(ZUM).
_______________________________________________
FuzzyTOPSISZUM
_______________________________________________
Typeofmethod compensatory noncompensatory
Fuzzinesssupport yesno
Linguisticvaluesyesyes(withadditional
supportextensionbythe
author)
Computationssophisticated straightforward
Configuration complexeasy(orabitmore
complexwith
additionalextension
forlinguisticvalues
bytheauthor)
_______________________________________________