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 single‐criterion
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
time‐optimal or fuel‐optimal 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 hybrid‐propulsion or motor‐driven 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 Pareto‐optimal
(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 Pareto‐optimal 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
Pareto‐set a single route that isthe most suitable for
the decision‐maker. It is provided by considering
decision‐maker’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 hybrid‐propulsion or a motor‐driven 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 Pareto‐optimality 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
(j‐1)‐th and j‐th waypoints and given ship model;
valuesofthecoefficientranges[0;1],where1depicts
completelysafesectionofrouteand0–unacceptably
dangerous section. Definition of the coefficient for a
hybrid‐propulsion ship was presented
in
(Szlapczynska, 2007) and for a motor‐driven 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 Pareto‐optimal set of solutions.
Themulticriteriarankingmethod(e.g.FuzzyTOPSIS
or Zero Unitarization Method) is responsible for
sorting the resulting Pareto‐optimal solutions
according to the given preferences of the
decision
maker.
An individual in the evolutionary approach
representsasingleroute.Therouteincludesanarray
ofwaypointsconstitutingship’stra ck, wherethefirst
oneisequaltothepositionoftheoriginportandthe
lastone–tothedestinationport.Asingleentryofthe
waypoint
array includes also some additional
parameterscharacterizingtheshiptrackbetweenthe
(n‐1)‐thandn‐thwaypoints.
The initial population is a set of pre‐defined and
randomly generated routes. Modified isochrone
routes (Spaans, 1986 & Hagiwara, 1989) – a time‐
optimalandafuel‐optimal–mayalso
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
Pareto‐optimalset
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
Pareto‐set is constructed can be found further in the
paper,inSection3.1.
The final step is to sort the Pareto‐set of routes
accordingtothedecision‐ma
ker’s(e.g.captainsofthe
ship) preferences. The decision‐maker 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
firstrouteisthePareto‐optimalonewhichisthemost
suitable for given preferences. Usually this route
becomes a route recommendation. Unlike the SPEA
processing,thesortingprocedureisabletoreturnit
s
resultsimmediately,thus,incasethedecision‐makers
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
Pareto‐optimality,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 Pareto‐optimalsetofroutes
In order to define Pareto‐opt
imality (optimality in
pure multicriteria sense) first the notion of Pareto‐
dominance must be introduced. Let us consider two
routesA&B.RouteAPareto‐dominatesBifandonly
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
Pareto‐optimal 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 Pareto‐dominance
betweeneverypairofroutesinthisset.
Now, let us consider an exemplary set of routes
presentedinTable1forwhichPareto‐optimalitywill
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.ExemplarysetofroutesforwhichPareto‐optimality
willbechecked.
_______________________________________________
Time[h] Fuel[t] Safety
_______________________________________________
Route#1200200good
Route#2210180good
Route#3190175moderate
Route#4250190good
Route#5205205onlysatisfactory
_______________________________________________
TheresultsofParetodominancecheckonthi
sset
ispresentedinTable2.
The Pareto‐optimal set of routes is constructed
basedontheoriginalset(Table1)takingintoaccount
Pareto dominance check results (Table 2). In Table 3
the final Pareto‐optimal 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#4Don’thavetocheck,#4is
dominated&removedfromtheset
Allchecksfor#5Don’thavetocheck,#5is
dominated&removedfromtheset
_______________________________________________
Table3. Pareto‐optimal set of routes for the considered
example.
_______________________________________________
Time[h] Fuel[t] Safety
_______________________________________________
Route#1200200good
Route#2210180good
Route#3190175moderate
_______________________________________________
Thefinalsetincludesonlythreefirstroutes,while
routes#4havebeenremovedasdominatedones
(route #4 is dominated by route #2 and route #5 is
dominatedbyroute#1).TheresultingPareto‐optimal
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,muchbiggerPareto‐optimalroutesets,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
userofthePareto‐settopickthemostsuitableroute.
InMEWRAtheprocessofselectionthemostsuitable
route out of the Pareto‐set 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 trade‐offs between criteria and
customizable fuzziness support. However, in a
practical implementation of MEWRA (described
brieflyinthenextsection)themethodexposesseveral
important drawbacks. The most
important one is its
property of 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,
whichmaybecomesignificantlytime‐consuming 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 non‐compensatory 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).
_______________________________________________
FuzzyTOPSISZUM
_______________________________________________
Typeofmethod compensatory non‐compensatory
Fuzzinesssupport yesno
Linguisticvaluesyesyes(withadditional
supportextensionbythe
author)
Computationssophisticated straight‐forward
Configuration complexeasy(orabitmore
complexwith
additionalextension
forlinguisticvalues
bytheauthor)
_______________________________________________
65
4 COMMERCIALMEWRAAPPLICATION
SoonaftertheNavSimPolandcompanyhaddecided
to include MEWRA into their weather forecast and
analysis software – NaviWeather, a team of Gdynia
Maritime University researchers started to build a
software prototype of multicriteria weather routing
tool onto the NaviWeather platform. It has been
decided
that MEWRA will be implemented as
separate NaviWeather plugin (a dll library). The
prototype weather routing plugin is planned to be
fully implemented by the time of this paper
publication. A summary of MEWRA
commercialisationprocesshasalreadybeenpresented
in(Szlapczynska,2012).
The MEWRA implementation for NaviWeather
followsits
originalalgorithm’sflow(depictedearlier
in the paper in Figure 1). It also includes the Zero
Unitarization Method as justified in Section3.2. The
key features of the MEWRA plugin, presented in
Figure2,areasfollows:
gathering origin and destination points from the
map,
uploading current weather forecast
for given
departuredate,
finding Pareto‐optimal set of routes by the
multicriteriaevolutionaryalgorithm(SPEA),
configuring decision‐maker’s preferences towards
theoptimizationcriteria,
sorting the resulting Pareto‐optimal set by the
ZUMrankingmethod–thefirstrouteinthesorted
set is the most suitable
one according to the
previouslyconfiguredpreferences.
Figure2.MEWRAprototypeasaNaviWeatherplugin–the
finalrankingofPareto‐optimalroutes(Szlapczynska,2012)
5 SUMMARY
The Multicriteria Evolutionary Weather Routing
Algorithm (MEWRA) is a unique weather routing
solution utilizing multicriteria, constrained Pareto‐
basedoptimizationandprovidinguserswithsupport
to select a single, the most suitable to their needs,
routeoutofPareto‐optimalset.Thispaper,unlikethe
previous technical MEWRA papers, focuses
on
practicalaspectsrelatedtoMEWRA.Itexplains,ina
practicalfashion,thewayofconstructingthePareto‐
optimal set of routes. It also presents a short
discussion on selecting the most suitable ranking
method applicable to MEWRA. As stated in
Section3.2theZeroUnitarizationMethod(ZUM)has
been
selected by the author as such. Finally, it
outlines the commercial MEWRA application as a
partofNaviWeathersoftwarebyNavSim.
REFERENCES
Chu T.C. & Lin Y.C. 2003. A Fuzzy TOPSIS Method for
RobotSe‐lection,TheInternationalJournalOfAdvanced
ManufacturingTechnology.pp.284‐290.Springer.UK.
HagiwaraH.1989.Weatherroutingof(sail‐assisted)motor
vessels. PhD Thesis. Technical University of Delft. The
Netherlands.
HinnenthalJ.2007.RobustPareto–Optimum
Routingof
Ships Utilizing Deterministic and Ensemble Weather
Forecasts. PhD Thesis. Technical University Berlin.
Germany.
Kim B.K. & Jo J.B. & Kim J.R. & Gen M.. 2009. Optimal
Route Search in Car Navigation Systems by Multi‐
objective Genetic Algorithms. International Journal of
Information Systems for Logistics and Management.
Vol. 4,
No. 2 (2009) 9‐18. lnderscience Enterprises Ltd.
Switzerland.
Krata P. & Szlapczynska J. 2012. Weather Hazard
AvoidanceinModelingSafetyofMotor‐DrivenShipfor
MulticriteriaWeatherRouting.TransNav‐International
Journal on Marine Navigation and Safety of Sea
Transportation.Vol.6.No.1.pp.71‐78.Poland.
KukulaK.2000.
ZeroUnitarizationMethod.Wydawnictwa
NaukowePWN.Poland.
Warszawa2000.
James R.W. 1957. Application of wave forecast to marine
navigation.Washington:USNavyHydrographicOffice.
MarieS. &CourteilleE.2009.Multi‐ObjectiveOptimization
ofMotorVesselRoute.TransNav‐InternationalJournal
onMarineNavigationandSafetyofSeaTransportation.
Vol.3.
No.2.pp.133‐141.Poland.
Spaans J.A. 1986. Windship routeing. Technical University
ofDelft.
Szlapczynska J. 2007. Multiobjective Approach to Weather
Routing. TransNav‐International Journal on Marine
NavigationandSafetyofSeaTransportation.Vol.1.No.
3.pp.273‐278.Poland.
Szlapczynska J. & Smierzchalski R. 2009. Multicriteria
Optimisation in
Weather Routing. TransNav‐
International Journal on Marine Navigation and Safety
ofSeaTransportation.Vol.3.No.4.pp.393‐400.Poland.
Szlapczynska J. 2012. Multicriteria Evolutionary Weather
Routing Algorithm (MEWRA) Applied to Marine
WeatherForecastandAnalysis Tool – NaviWeather by
NavSim.ProceedingsofENC’2012.PolishNavigational
Forum.Gdynia.
Poland.
Wisniewski B. 1991. Methods of route selection for a sea
going vessel (in Polish), Gdansk: Wydawnictwo
Morskie.
Zitzler E. & Thiele L. 1999. Multiobjective Evolutionary
Algorithms: A Comparative Case Study and the
Strength Pareto Approach. IEEE Transactions on
Evolutionary Computation, No. 3, Vol. 4, pp. 257‐271.
IEEEComputationalIntelligence
Society.USA.
