International Journal

on Marine Navigation

and Safety of Sea Transportation

Volume 1

Number 3

September 2007

273

Multiobjective Approach to Weather Routing

J. Szlapczynska

Gdynia Maritime University, Gdynia, Poland

ABSTRACT: The paper presents a weather routing solution for sail-assisted ships. Since the route finding

optimisation process is a multiobjective one, the emphasis is put on possible application of multiobjective

optimisation methods. The paper focuses on two such methods, namely evolutionary algorithms and ranking

methods represented by Fuzzy TOPSIS. In addition, a proposed set of optimization criteria is presented.

Descriptions of assumed ship and sail models as well as exemplary speed characteristic are also provided.

Finally, a proposal of application to a weather routing tool is presented

1 INTRODUCTION

A problem of finding the most suitable vessel route

taking into account changeable weather conditions

and navigational constraints is referred to as a

weather routing optimisation problem. Such a

problem is mostly considered for ocean going ships

where adverse weather conditions may impact both,

often contradictory, economic and security aspects of

voyage.

One of the first approaches to the problem was a

minimum time route planning based on a weather

forecast called an isochrone method. The method

was based on geometrically determined and

recursively defined time fronts, so called isochrones.

Originally proposed by R.W. James (James 1957),

isochrone method was in wide use through decades.

In late seventies based on the original isochrone

method the first computer-aided weather routing

tools were developed. However, along with

computer implementation some problems arose, i.e.

with so called “isochrone loops”. Numerous

improvements to the method were proposed since

early eighties, with (Hagiwara 1989, Spaans 1986,

Wisniewski 1991) among others. Since then several

different approaches to the optimisation problem

was in use, with dynamic programming or genetic

and evolutionary algorithms among others.

Most of recent scientific researches in weather

routing focus on shortening the passage time,

reducing fuel consumption and avoiding severe

weather i.e. tropical cyclones. Nowadays,

evolutionary or genetic algorithms are common

solutions for weather routing services. However, due

to multiobjective nature of weather routing it is

recommended to introduce some state-of-the-art

multiobjective methods to the process of route

finding. It may facilitate the process of reaching a

trade-off between often conflicting economic and

safety criteria sets. Thus, it is proposed to introduce

multiobjective evolutionary algorithms as well as

multiobjective ranking methods to the route finding

process.

The remainder of the paper is organized as

follows: section 2 introduces the basic idea of a

single-objected evolutionary algorithm. Section 3

provides detailed description of multiobjective methods

applicable to weather routing. The description includes

multiobjective evolutionary algorithms (MOEAs) and

multiobjective ranking methods represented by Fuzzy

TOPSIS. Section 4 presents proposed application of

the methods to weather routing. Finally, section 5

summarizes the material presented.

274

2 THE IDEA OF SINGLE-OBJECTED

EVOLUTIONARY ALGORITHMS

Evolutionary algorithms are natural successors of

genetic algorithms. The key difference between them

is in the chromosome structure. Genetic algorithms

assume binary and fixed-length chromosome strings,

whereas the evolutionary ones allow more

complicated chromosome structures. It implies that

original genetic binary operators, namely mutation

and crossover, are substituted by evolutionary

operators specialized to fit given chromosome

structure and the optimisation task. However, the

general idea of both genetic and evolutionary

algorithms remains the same. At first initial

population of individuals is being generated and

evaluated. After modifications by operators designed

to improve algorithm’s convergence some

individuals are selected and a new population is

generated. The process of evaluation, modification

and selection lasts until a termination condition is

met.

Single-objected goal function is utilized to

evaluate the individuals by means of so called fitness

function. The goal function is either equal to the

fitness function or at least is an element of the latter.

In general: the better the individual in terms of goal

function the higher evaluation score it gets. By the

evaluation process future modifications and

selection is executed mainly for a group of “best

fitted” individuals. This way the algorithm

converges to a final set being sufficiently close to the

optimal solution.

Apart from the goal function, constraints are

another important issue in single-objected

optimisation process. In the evolutionary framework

the constraints are met due to specialized operators

assuring that any modified individual remains in the

feasible solution space.

3 MULTIOBJECTIVE METHODS APPLICABLE

TO WEATHER ROUTING

3.1 MultiObjective Evolutionary Algorithms

(MOEAs)

MultiObjective Evolutionary Algorithms (MOEAs)

have been growing in popularity since its inception

in mid-1980s. In general, MOEAs extend the

functionality of regular single-objected evolutionary

algorithms providing a method of dealing with

multiple and often conflicting objectives.

When multiobjective problems are being

considered one of the important issues is the

problem of ranking the criteria in terms of their

importance and impact on final result. It is often

designated that a decision maker is a person who

makes such a choice. There are three distinctive

subgroups of MOEA solutions, differentiated by the

way of involving the decision maker:

− “a priori” preference, where the decision maker

combines all the objectives into a single scalar

function;

− progressive preference, where the decision

making and optimization processes alternate;

− “a posteriori” preference, where the resulting set

of Pareto-optimal solutions is presented to the

decision maker who selects the final solution

from the set provided.

This paper is focused entirely on Pareto-based

MOEA solutions with “a posteriori” preference. It is

caused by the fact that decision-making in the

proposal described in the next section is transferred

to the multiobjective ranking method.

One should be aware that “MOEA” term refers

to some algorithmic framework rather than a

specific ready-to-use and universal solution. Thus,

already known MOEA techniques should be applied

prior to building a problem-oriented multiobjective

evolutionary application. Thus, the following

subsections describe core set of basic MOEA

techniques.

3.1.1 Secondary population

Secondary population is an additional population

maintained throughout MOEA execution time,

collecting all Pareto-optimal solutions found so far

during the search process. Its main goal is to

preserve all desirable solutions throughout the

generation process. In accordance with Pareto

notation the secondary population is termed

)(tP

known

where t denotes current generation number.

Similarly, a current set of Pareto-optimal solutions

determined at the end of each generation with

respect to the current MOEA generational

population is termed

)(tP

current

. It is assumed, though,

that

)0(

known

is an empty set and

known

without t

annotation stands for the final set of Pareto optimal

solutions collected before MOEA termination.

Several strategies of secondary population storage

exist. The most obvious and commonly used is the

strategy of adding

)(tP

current

)(tP

known

in the end

of each generation t:

)1()()( −= tPtPtP

knowncurrentknown



(1)

The set of

)(tP

known

must be periodically checked

against obsolete Pareto solutions as Pareto

optimality should always be evaluated within current

Ω set. The simplest policy does not assume explicit

copying

)(tP

known

solutions back into the next

population. However, other strategies exist where

275

the secondary population participates in a

tournament selecting next generations or is directly

inserted into the next mating population.

3.1.2 Multiobjective ranking

Multiobjective evolutionary approach enforces

that some transformation of the performance vector

into a scalar fitness value is necessary. This

transformation is achieved by means of a

multiobjective ranking, often also referred to as

Pareto ranking. In general, there are several ranking

methods. All these methods are based on an

assumption that preferred Pareto optimal solutions

are ranked the same value whereas other solutions

are assigned some less desirable rank value.

3.1.3 Niching and fitness sharing

The term niching refers to the process of

clustering in either solution space or criterion space.

In this process clusters consist of groups formed by

some individuals selected from the entire population.

Niching is primarily aimed at finding and

maintaining multiple optima. In result, this technique

should assure a good spread of discovered solutions

and prevent MOEA algorithm from being swamped

by solutions with identical fitness. Fitness sharing is

the most popular realization of the niching

technique. It is based on an assumption that

individuals in a particular niche share available

resources. Thus, the more individuals are located in

the vicinity of a certain individual, the more its

fitness value is deteriorated. The vicinity is most

often determined by a distance measure d(i,j) and

specified by niche radius σ

. The distance

function d(i,j) operates either in solution space or

criterion space, resulting in appropriate type of

fitness sharing.

3.1.4 Mating restrictions

The idea behind restricted mating is to prevent or

minimize offsprings, so called lethals, created by

recombination of chromosomes from different

niches. Such individuals can lead to degradation of

MOEA performance. To remedy the problem some

restrictions to mating might be introduced providing

a distance metric and a maximum distance value

mate

for which mating is still permitted. The most

popular solution for mating restriction is to introduce

the fitness sharing niche radius σ

into the

problem and setting σ

mate

=σ

. However, it is

questioned (Van Veldhuizen 2000) whether such

restriction policy is indeed a compulsory MOEA

component, especially when there is no quantitative

evidence of its benefits.

3.2 Fuzzy TOPSIS as a multobjective ranking

method

Ranking methods belong to a group of

multiobjective optimisation methods where

preferences of the decision maker are utilized to

build a ranking of alternatives. The ranking is a list

of all possible solutions ordered from the least to the

most desirable one. Given order is achieved by

casting all the objectives into a single-objective goal

function. Preferences are reflected by weight values

assigned to the original objectives in the aggregated

goal function.

Technique for Order Preference by Similarity to

an Ideal Solution (TOPSIS) is a multiobjective

ranking method proposed by Hwang & Yoon

(Hwang et al. 1982). The method is based on a

concept that the best alternative among the available

alternative set is the closest to the best possible

solution and the farthest from the worst possible

solution simultaneously. The best possible solution,

referred to as an ideal one, is defined as a set of the

best attribute values, whereas the worst possible one,

referred to as a negative-ideal solution, is a set of the

worst attribute values. In order to compare the

alternatives and build the output ranking, the

Euclidean distances between each alternative and

both the ideal and the negative-ideal solutions are

calculated. Then the closeness coefficient is

determined to measure the two distances

simultaneously. Sorting in descending order the

coefficient values assigned to the alternatives creates

the final TOPSIS ranking. The alternative with the

highest ranking value is considered as the most

desirable.

Based on the original TOPSIS method, an

extension has been proposed by Chu & Lin (Chu et

al. 2003) providing support for fuzzy criteria and

fuzzy weights both described by triangular fuzzy

values. The new method has already been applied to

navigational problems in (Szlapczynska 2005).

Detailed Fuzzy TOPSIS algorithm differs from

standard TOPSIS one in the following:

− each criterion can be either crisp or fuzzy, the

latter means that the criterion is described by a

linguistic variable with triangle fuzzy values;

− weight vector is described by a set of triangle

fuzzy values assigned from another linguistic

variable;

− decision matrix is converted to a fuzzy decision

matrix;

− scaled V matrix is a result of multiplication of

fuzzy weight vector and fuzzy decision matrix;

− in order to determine ideal and negative-ideal

solutions first the scaled V matrix is defuzzified,

276

then the standard TOPSIS computations are

continued.

As a result, similarly to original TOPSIS, final

Fuzzy TOPSIS ranking consists of crisp values. The

alternative with the highest ranking value is

considered as the most desirable.

4 WEATHER ROUTING FOR SAIL-ASSISTED

SHIPS AS A MULTIOBJECTIVE

OPTIMISATION PROBLEM

4.1 Model assumed

For a sail-assisted ship separate ship and sail models

are assumed. Ship model is based on a B-470 bulk

carrier. Its basic parameters are shown in Table 1.

Table 1. Basic parameters of the ship model

Parameter name

Value

Length

172 m

Width

22.8 m

Draught

9.5 m

Height

14.3 m

Service speed

15 kn

Displacement

30,288 t

Sail model presented in Figure 1 is based on

textile winds from “Oceania” ship. There are six

sails forming a palisade. Each sail has 522m

sail

surface area.

For given ship and sail models, the speed

characteristic is determined based on algorithm by

Oleksiewicz (Oleksiewicz in prep.). An exemplary

speed characteristic for starboard tack is presented in

Figure 2.

Fig. 1. Sail model

Fig. 2. Exemplary speed characteristic for given ship and sail

model - starboard tack

4.2 Problem definition

Prior to a problem definition a model of ship

movements is assumed as kinematical one with

elements of ship’s dynamics according to possibility

of manoeuvre execution.

The values to be found by the optimisation

process of route finding are route’s waypoints

defined by their geographical coordinates and ship

speed between two consecutive waypoints. The

optimisation criteria are split into two groups,

namely:

− economic criteria, such as passage time and fuel

consumption;

− safety criteria, represented by traffic intensity and

constraint violation factors.

Thus, the goal function is defined as presented by

equations 2 - 4:

minrifvtfrivtf

traffsafetyfcreconomytrafffcr

→= )},(),,({),,,(

(2)

)}(),({),(

__ fcnconsumptiofuelrtimepassagefcreconomy

vftfvtf =

(3)

)}(),({),(

int_int_

rfifrif

violationconstratraffensitytraffictraffsafety

(4)

where:

– passage time [h],

– total fuel consumption [t],

traff

– traffic intensity factor [/],

277

r – penalty function for constraint violation [/].

All limitations to the problem domain in weather

routing are purely navigational. Landmasses that

cannot be crossed constitute the prime constraint.

Even a small violation of the constraint results in a

route unacceptable from navigational standpoint.

Along with an assumption that land shore does not

change its shape during a route execution this

constraint is assumed static. However, other

navigational constraints exist that do not fall into

category of static ones, namely ice phenomenon and

tropical cyclones. Available information about ice

and cyclones is mostly derived from forecasted, that

is probabilistic, data. Moreover, both ice concentra-

tion as well as a centre of a tropical depression

changes with time. Thus these constraints are

assumed fuzzy dynamic. Last but not least constraint

is determined by the assumed ship’s draught. Given

ship model is able to navigate only through waters

sufficiently deep for assumed draught value.

4.3 Proposed solution for the problem

The solution proposed is based on the optimisation

criteria defined in the previous subsection. It utilizes

two basic multiobjective mechanisms, namely

multiobjective evolutionary algorithm (MOEA) and

multiobjective ranking method - Fuzzy TOPSIS. In

general, the main algorithm is presented in Figure 3.

In the proposed solution the evolutionary framework

is responsible for iterative process of population

development. MOEA-specific techniques, namely

multiobjective ranking, secondary population and

niching extend the framework to achieve a

Pareto-optimal set of routes according to given

criteria set. Mating restriction, as a MOEA technique

of questionable profits, is not utilized in the

proposal.

Initial population of routes will be generated

based on an orthodrome and a route determined by

the adopted isochrone method (Szlapczynska et al. in

prep.). The population should consist of avg. 50

individuals, each being a random mutation of the

basic routes. Also pure orthodrome and isochrone

route should belong to the initial population. In

addition to that, it is worth considering whether

some other routes optimising one of the other criteria

(fuel consumption, vessel traffic intensity, degree of

constraints violation) should be included in the

initial population.

Fig. 3. Main algorithm of the proposed multiobjective weather

routing

The process of fitness assignment will include

multiobjective ranking and niching, necessary

for assumed multiobjective goal function. In the end

of each generation an increase of fitness function

will be determined. The evolutionary process will

be terminated whenever the increase will be

satisfactorily small (smaller than some ε value).

Then, the ranking Fuzzy TOPSIS method will

prepare the output ranking facilitating the final

decision which route to choose.

If the termination condition is not met the

iterative process of population development must

continue. First, dominance between individuals

should be determined. Based on this information the

secondary population will be updated. A new

population will be created by means of selection and

modification processes. Again all individuals in

the population will be assigned their fitness values

and the evolutionary iterations will proceed until the

termination condition is finally met.

5 SUMMARY

The paper describes a possible multiobjective

approach to weather routing. Two families of

multiobjective decision-making methods are

presented, namely multiobjective evolutionary

algorithms and ranking methods. The author

278

describes model assumed and defines problem of

route finding in weather routing. Then a solution to

given model and problem is presented. The proposal

includes an algorithm determining a route satisfying

given optimisation criteria and navigational

constraints. Further details on the proposed

algorithm will be provided as soon as the weather

routing algorithm in finally implemented.

REFERENCES

Chu, T.C. & Lin Y.C. 2003. A Fuzzy TOPSIS Method for

Robot Selection, The International Journal Of Advanced

Manufacturing Technology: pp. 284-290.

Hagiwara, H. 1989. Weather routing of (sail-assisted) motor

vessels, PhD Thesis, Delft: Technical University of Delft.

Hwang, C.L. & Yoon K. 1982. Multiple Attribute Decision

Making - A State-of-the-Art Survey, The Journal of the

Operational Research Society, Vol. 33, No. 3: pp. 289-300.

James, R.W. 1957. Application of wave forecast to marine

navigation, Washington: US Navy Hydrographic Office.

Oleksiewicz, B. (in preparation). Motor-sailer – A hybrid

Propulsion for Commercial Vessels. The case study.

Spaans, J.A. 1986. Windship routeing, Delft: Technical

University of Delft.

Szlapczynska, J. 2005. Fuzzy TOPSIS as a multicriteria

decision making method in navigational applications (in

Polish), Works of the Faculty of Navigation, pp. 180-192.

Szlapczynska, J. & Smierzchalski R. (in preparation). Adopted

isochrone method improving ship safety in weather routing

with evolutionary approach.

Wisniewski, B. 1991. Methods of route selection for a sea

going vessel (in Polish), Gdansk: Wydawnictwo Morskie.

Van Veldhuizen, D.A. & Lamont, G.B. 2000. Multiobjective

Evolutionary Algorithms: Analyzing the State-of-the-Art,

Evolutionary Computation, pp.125-147.