1. INTRODUCTION
Nowadays the most popular commercial approach to planning a ship voyage while taking weather conditions into account (known as “weather routing”) is the one based on isochrones. The isochrone method was proposed by James (Reference James1957) for manual use and is based on geometrically determined and recursively defined time fronts, so called isochrones. The method allows single-objective optimisation only: time-optimal or fuel-optimal paths for the same voyage must be sought by different methods. Moreover, its support for optimisation constraints is limited – the isochrone method handles only static (time-independent) constraints such as land obstacles or other areas to be avoided. Despite these limitations the method became extremely popular as a simple, reliable and fast tool for finding usually a time-optimal route. In the late 1970s the first computer aided weather routing tools were developed based on the original isochrone method. Along with computer implementation some additional problems with isochrones arose, i.e. with so-called “isochrone loops”. Numerous improvements to the method eliminating these problems have been proposed since the early 1980s by Spaans (Reference Spaans1986), Hagiwara and Spaans (Reference Hagiwara and Spaans1987), Hagiwara (Reference Hagiwara1989) and Wiśniewski (Reference Wiśniewski1991) among others. Today, several commercial weather routing services utilise highly modified isochrone methods.
Apart from the isochrone method there are also some other approaches to this problem. Basic utilisation of dynamic programming for a grid of points has been proposed by de Wit (Reference de Wit1990) and Motte and Calvert (Reference Motte and Calvert1990). Moreover, a new European commercial weather routing service utilising a three-dimensional (3D) dynamic programming has been just announced in Chen (Reference Chen2013). As presented in Bijlsma (Reference Bijlsma2008), solving a specified optimal control problem allows for finding a time-optimal path, particularly when voyage fuel consumption is restricted to a specific value. Another approach to weather routing assumes using the Dijkstra algorithm as presented in Mannarini et al. (Reference Mannarini, Coppini, Oddo and Pinardi2013).
All the abovementioned weather routing methods utilise single-objective optimisation, i.e. only one criterion (e.g. passage time) can be optimised by a single run of the method. A possibility to widen the optimisation towards a multi-objective approach, where more criteria can be taken into account simultaneously, came together with the introduction of evolutionary computation. However, some of the proposed approaches to multi-objective optimisation, though interesting, are largely simplified. In Wiśniewski et al. (Reference Wiśniewski, Medyna and Chomski2006) the multi-objective goal function is a product of the single goals, while in Tsou (Reference Tsou2010) the aim is a weighted linear sum of the goals. In both cases multiple criteria have been aggregated to a single one, with the impact of all criteria (criteria weights) set arbitrarily before the optimisation process. This results in losing a lot of detailed information on various possible routes, including the best routes for each criterion. The approach proposed in this paper is a strict multi-objective optimisation.
A purely mathematical approach to optimisation with multiple goal functions requires finding a set of solutions optimal in a multi-objective sense, a so-called Pareto-optimal set. Utilising Pareto-based optimisation in weather routing makes it possible to find in a single run a set of routes satisfying all given criteria, however with different levels of satisfaction for a single goal. In a Pareto set, apart from routes with balanced impact of the criteria, there are also all the criteria's best routes. Such a multi-objective Pareto-based approach towards weather routing has been proposed so far by Hinnenthal (Reference Hinnenthal2007), Marie and Courteille (Reference Marie and Courteille2009) and by the author of this paper (Szlapczynska, Reference Szlapczynska2007). All the proposed methods utilise a genetic or evolutionary algorithm with multiple goal functions to search discrete or continuous search space to find a Pareto-optimal set of routes. The method introduced by Hinnenthal (Reference Hinnenthal2007) as well as the one by Marie and Courteille (Reference Marie and Courteille2009) both utilise a Multi Objective Genetic Algorithm – MOGA, but their functionality is restricted to provide the Pareto-optimal set of routes as their final result. In comparison, the multi-objective weather routing method proposed by the author, namely Multi-objective Evolutionary Weather Routing Algorithm (MEWRA), has the following advantages:
• utilises more robust evolutionary algorithm – Strength Pareto-Evolutionary Algorithm – SPEA (Zitzler and Thiele, Reference Zitzler and Thiele1999),
• includes a mechanism of selecting from the Pareto-set a single route, which is the most suitable for the decision-maker (it is provided by considering the decision-maker's preferences towards the criteria by the additional multi-criteria ranking method),
• supports customisable optimisation constraints: static (time-independent) or dynamic (time-dependant) ones.
MEWRA's first draft has already been presented by the author in Szlapczynska (Reference Szlapczynska2007). This paper presented an overview of the method designed initially for a ship model with hybrid propulsion (motor engine with additional sails), without providing any experimental results. In Szlapczynska and Smierzchalski (Reference Szlapczynska and Smierzchalski2009) MEWRA was described in detail together with simulation results for the hybrid ship passing North Atlantic routes. At that stage MEWRA supported only a predefined set of criteria and constraints. The Fuzzy Technique for Order of Preference by Similarity to Ideal Solution (Fuzzy TOPSIS) method was presented there as the selected multicriteria ranking method. Together with an idea of MEWRA adaptation to support motor ships, a necessity arose to rebuild the ship model. In Krata and Szlapczynska (Reference Krata and Szlapczynska2012) an approach towards safety calculus for an engine-driven ship model was documented. A new engine-based MEWRA has been presented in Szlapczynska (Reference Szlapczynska2013). This paper introduced an amendment in the ranking method: Fuzzy TOPSIS has been replaced by the Zero Unitarization Method, widely known as the additive weighted values method. MEWRA has been presented there also as a plugin for NaviWeather software.
Unlike the previous papers, this one aims at presenting a mature, complete MEWRA version. It underlines newly introduced support for customisable sets of criteria and constraints including appropriate experimental results. The rest of the paper is organised as follows. Section 2 introduces the basic theory required to grasp the idea of multi-objective optimisation. In Section 3 the MEWRA algorithm is presented with a focus on the evolutionary mechanisms the optimisation utilises. Examples of MEWRA's usage are presented in Section 4. Section 5 summarises the presented material.
2. NOTES ON THE THEORY OF MULTI-OBJECTIVE OPTIMISATION
In general, finding a solution to a multi-objective optimisation problem is a complex task based on finding a trade-off between often incompatible and competing objectives. This trade-off means that progress according to one criterion is often a step back according to another. Thus, it is unlikely that a solution to a multi-objective problem would be a single optimal individual (in this case – single optimal route); it is rather a set of equal individuals (solutions). The set is the previously mentioned Pareto-optimal set.
An underlying definition for Pareto-optimal sets is the notion of Pareto-dominance. A classic definition of dominance states that an individual x is said to dominate an individual y if the former performs better than the latter for at least one objective and performs no worse than the latter for all other objectives. Mathematically the concept of Pareto-optimality is defined as follows. Let us consider a multi-objective optimisation problem with m decision variables and n objectives. Without loss of generality the optimisation problem can be expressed as follows:
$$u = F(x) = \{ f_1 (x),f_2 (x),f_3 (x), \ldots, f_n (x)\} \to min $$where x={x 1, x 2,…,x m} is a vector of decision variables and u={u 1, u 2 ,…, u n} is a performance vector associated with the x vector. A particular individual x with associated performance vector u is said to dominate another individual y with performance vector v (x≺y) if the performance vectors u and v meet the following:
$$x \prec y \Leftrightarrow u \prec v$$
$$u \prec v\ {\rm iff} [\forall {\rm i} \in \{ 1, \ldots, n\}, u_i \leqslant v_i ] \wedge [\exists i \in \{ 1, \ldots, n\} :u_i \lt v_i ]$$An individual x∈Ω is Pareto-optimal with respect to Ω if and only if it is non-dominated, i.e. there is no such x′∈Ω, for which a conjunction of v≺u, Equations (4) and (5) holds:
$$u = F(x) = \{ f_1 (x),f_2 (x),f_3 (x), \ldots, f_n (x)\} $$
$$v = F(x') = \{ f_1 (x'),f_2 (x'),f_3 (x'), \ldots, f_n (x')\} $$It must be emphasised, though, that the Pareto-optimality is always considered with respect to the Ω set that is assumed to be equal to the entire decision variable space, unless otherwise specified. A Pareto-front is a set of points in the problem's criterion space corresponding to the Pareto-optimal set. Formal definitions of the Pareto-optimal set P* and Pareto-optimal front PF* are provided by the following:
$$P^*: = \left\{ {x \in \Omega \left\vert \neg \right.\exists x' \in \Omega :F(x') \prec F(x)} \right\}$$
$$PF^*: = \left\{ {u = F(x) = \{ f_1 (x), \ldots, f_n (x)\} \left\vert {x \in P^*} \right.} \right\}$$Since the weather routing optimisation problem belongs to a class of constrained problems, it is necessary to extend the classic Pareto-dominance to the constraint dominance (Deb, Reference Deb2000). The constrained dominance takes into account feasibility of the individual. A feasible individual is one that complies with all given constraints. An infeasible one violates at least one of the constraints. The constraint-dominance (also known as c-dominance) is then determined based on a three-step procedure, exemplified below for two individuals. An individual i constraint dominates another individual j if and only if one of the following holds:
• i is feasible and j is not,
• both i and j are infeasible, but i has lower constraint violation level,
• both i and j are feasible and i dominates j (as in the classic Pareto-dominance approach).
3. WEATHER ROUTING UTILISING MULTI-OBJECTIVE OPTIMISATION WITH CONSTRAINTS
Based on the abovementioned Pareto-optimality a concept of Multi-objective Evolutionary Weather Routing Algorithm (MEWRA) has been proposed in Szlapczynska (Reference Szlapczynska2007). The algorithm utilises multi-objective optimisation in continuous space with constraints via the Strength Pareto-Evolutionary Algorithm (SPEA). MEWRA first finds the Pareto-optimal set of routes by means of the evolutionary SPEA algorithm and then selects a route recommendation out of this set by means of a multi-criteria ranking method. The recommendation is based on preferences towards optimisation criteria expressed by the decision maker (e.g. the captain of the ship). The decision maker is also able to re-enter his preferences among the criteria and redo the selection of recommended route immediately, without re-running the evolutionary optimisation, which is the most time-consuming phase of the process.
Insights of MEWRA's construction are given in the following subsections describing ship model, optimisation criteria and constraints, the individual's structure and the algorithm's flow.
3.1. Ship model
MEWRA was originally designed for a theoretical hybrid-propulsion ship model (based on a bulk carrier) with a motor engine supported by additional textile sails, as presented in Szlapczynska (Reference Szlapczynska2007) and Szlapczynska and Smierzchalski (Reference Szlapczynska and Smierzchalski2009). The model assumed that for favourable wind conditions engine power can be reduced or even turned off if an “engine start and stop” option is enabled. Recently, a new model for MEWRA (motor engine ships only) has been constructed and substituted for the hybrid-propulsion one. The new model is based on the data gathered from a set of ships belonging to a sea carrier company. It does not allow for turning the engine off en route. The model includes the following elements:
• ship speed estimation – for given propulsion settings and weather conditions (including wind and wave forecasts) the speed (in knots) is estimated,
• fuel consumption estimation – total fuel consumption is calculated over the entire route length (separately for route segments between consecutive control points),
• safety of voyage estimation – safety is modelled by a dimensionless index with values in the range [0·0;1·0], where 0·0 depicts absolutely unsafe route and 1·0 an ideal safe one. Fractional safety index values are computed separately for each segment between control points of a route and are averaged to compute the final index for the route. Safety calculations are based on forecasted wind and wave conditions as described in Krata and Szlapczynska (Reference Krata and Szlapczynska2012). In general, the safety index non-linearly decreases with an increase of unfavourable weather conditions, e.g. strong waves astern of the ship.
Following recent research in weather routing, e.g. by Bijlsma (Reference Bijlsma2010) and Chang et al. (Reference Chang, Tseng, Chen, Chu and Shen2013), the author plans to extend MEWRA by taking into account the following factors when estimating elements of the ship model:
• ocean currents,
• tides,
• visibility,
• ship traffic volume.
3.2. Customisable optimisation criterion and constraint sets
Both the constraints and criteria sets in the current MEWRA version can be customised: extended or reduced by the user. This customisation has been implemented by means of:
• supporting ENABLED/DISABLED functionality, separately for criteria and constraints, along the whole optimisation path,
• introducing a pointer to the evaluation function for each criterion,
• introducing two function pointers: one for checking if a given route violates a constraint and a second identifying control points of the route that violate the constraint.
In the current version it is possible to define as many optimisation criteria as needed. To build a new criterion only two elements are necessary: optimisation direction (minimisation or maximisation) and an evaluation function. The criteria set should be free of unnecessary elements as each new criterion results in a new dimension in the search space and increases the execution time. The set presented in Section 4 includes three criteria: passage time, fuel consumption and safety of voyage.
Analogically, the MEWRA user is able to define multiple constraints in the optimisation process. Two types of constraints are handled, namely the static (not changing with time, e.g. areas to be avoided in routing) and dynamic ones (changing with time, e.g. all weather-related restrictions). MEWRA's advantage lays in the stochastic nature of the evolutionary algorithm that forms its optimisation base. The set of constraints presented in Section 4 includes the following:
• landmasses and shallow waters (static),
• customisable “piracy threat” area to be avoided (static),
• regions of wind speed exceeding 30 knots (kn) (dynamic).
3.3. Evolutionary individual's structure
In the method each route is represented by an evolutionary individual. It includes an array of control points constituting the ship's track. The first point is equal to the position of the origin port and the last one to the destination port. A single entry in this array includes:
• geographical coordinates (longitude, latitude) of the control point,
• motor engine relative settings between the previous and the current control point, ranging [0;1],
• time of reaching the current control point,
• forecasted weather conditions for the current control point,
• performance values of the ship in the control point (assumed to be constant between the previous and the current control point) such as speed, fuel consumption or safety index, calculated by the ship model based on, among other factors, the weather conditions.
Only the first two elements of the waypoint entry remain under direct control of the evolutionary mechanisms: the coordinates and motor settings. All the other values are calculated as functions of the former and stored in the evolutionary individual's structure in order to improve on the efficiency of the algorithm.
3.4. Weather routing algorithm (MEWRA) – the flow
Elements of the Multi-objective Evolutionary Weather Routing Algorithm are presented in Figure 1. The algorithm includes four key steps:
• generation of the initial set of routes,
• evolutionary multi-objective optimisation of routes (SPEA),
• defining decision maker's preferences towards optimisation criteria,
• multi-criteria ranking method.
All the abovementioned elements are described in detail in the following subsections.
Figure 1. Weather Routing algorithm (MEWRA) with multi-objective optimisation with constraints and its key element – SPEA algorithm.
3.4.1. Generation of the initial set of routes
The first step of MEWRA is generation of a set of initial feasible routes (i.e. not violating any of the defined optimisation constraints). The generation process is random, however, it is driven by a set of pre-defined routes, such as:
– a loxodrome between given origin and destination points,
– a Great Circle between given origin and destination points,
– a reflected Great Circle (along the loxodrome),
– direct routes connecting origin and destination points without any land crossing, generated by the method of isochrones and A* algorithm.
3.4.2. Evolutionary multi-objective optimisation of routes (SPEA)
The initial set from the previous step constitutes the initial population of routes in MEWRA's evolutionary engine. The general idea behind evolutionary optimisation is to amend the initial set during the evolution so as to find a sub-optimal solution (a set of Pareto-optimal solutions in case of optimisation with multiple goals). In MEWRA, the Strength Pareto-Evolutionary Algorithm (SPEA), proposed originally in Zitzler and Thiele (Reference Zitzler and Thiele1999), has been applied as the evolutionary route optimiser. SPEA is a multi-objective evolutionary algorithm able to find multiple Pareto-optimal solutions of the given optimisation problem. The general SPEA flow is presented in Figure 1 and reflects the generic evolutionary algorithm. Its key elements are:
• initial population creation (in case of MEWRA the previously found initial set is simply copied),
• fitness assignment,
• selection,
• applying problem-specific operators,
• checking for termination condition.
These elements are supplemented by additional steps concerning maintenance of a non-dominated set N. Here, unlike in a typical evolutionary approach, throughout the evolution process two populations are maintained, the basic population P and the secondary one N. The main purpose of the latter is to store all non-dominated routes during the generation process. Routes from the non-dominated set N also participate in fitness assignment, thus selection procedure is able to utilise a multi-set union of individuals from P+N.
The non-dominated set N is initialised as empty during the creation of initial population in P. Then, in each generation current non-dominated routes from P are added to the non-dominated set N. However, adding new routes to N may cause some of the old elements already in N to become dominated. Thus, checking and removal of the dominated individuals from non-dominated set N must be performed. In cases of exceeding the defined maximum size N, the non-dominated set is reduced. The process of dominance checking utilises the previously mentioned constraint-dominance rules (Deb, Reference Deb2000).
Fitness assignment in SPEA is organised as follows. First, for each route from the population N a fitness value, so-called “strength”, is calculated. The strength of a given individual from N is proportional to the number of individuals from basic population P that are covered (dominated or equal to) by this individual. In the second step each individual from population P is assigned a fitness value that is a sum of strengths of elements from N that cover given individual from P.
The evolution is terminated if one of the following happens:
– a maximum number of generations has been reached,
– the non-dominated set (population N) has not been modified since last r generations (where r is configured by the user).
When evolution is completed the non-dominated set (population N) is returned as the Pareto-optimal set of routes.
Typically for all meta-heuristic methods of a stochastic nature, SPEA does not guarantee that the resulting set of solutions would be identical each time it is run for the same set of input parameters. However, the resulting set of routes would always be almost identical when routes' parameters (e.g. passage time or fuel consumption, etc.) are taken into account, even though the geographical location of some control points may slightly vary.
3.4.3. Defining decision maker's preferences towards optimisation criteria
The size of the resulting Pareto-optimal set is not a constant value, i.e. the maximum size of the set is determined by the user and usually is equal to the population size. It is possible though, that the set would consist of only a single route. That would happen in the case of MEWRA running for a single-criterion optimisation or, in a rare case, when optimisation constraints would severely limit generation of feasible routes. However, in the most typical case the Pareto-optimal set of routes will be numerous. In order to facilitate the user to browse through the set in search of “the best” (subjectively) route, MEWRA sorts the set based on user's preferences towards optimisation criteria. A user decides how important each criterion is and specifies that via linguistic values such as “very important”, “quite important” or “unimportant”. These linguistic values have in turn numerical crisp values from [0·0;1·0] range assigned to them (e.g. 0·5 for “quite important”), which are input values for the last MEWRA step – the ranking method.
3.4.4. Multi-criteria ranking method
The ranking method is used to sort, via its multi-criteria decision making properties, the Pareto-optimal set of routes (returned previously by the SPEA algorithm) based on user's preferences. Originally MEWRA was designed to support fuzzy values assigned to the linguistic ones (Szlapczynska and Smierzchalski, Reference Szlapczynska and Smierzchalski2009), thus it used Fuzzy TOPSIS (Chu and Lin, Reference Chu and Lin2003) as a multi-criteria ranking method. However, in practice it turned out that the fuzzy approach has several disadvantages (e.g. a property of compensation) and another crisp-based method has been proposed instead – the additive weighted values method (Fishburn, Reference Fishburn1978). A comparison of usage of the two abovementioned ranking methods in MEWRA has been presented in Szlapczynska (Reference Szlapczynska2013).
The additive weighted values method sorts the Pareto-optimal routes based on crisp values assigned (via linguistic ones) to each criterion by the user. This way the first route in the sorted set is the one that fits the user's preferences best. Usually this route becomes a route recommendation. Unlike previously described SPEA processing, the ranking method is able to return its results immediately, thus, in case the user changes their mind about the preferences, the last step can be repeated multiple times.
4. EXAMPLES OF USAGE
In this section two examples of MEWRA's usage are presented. The first one is focused on multi-objective optimisation with no additional optimisation constraints (except land obstacles and shallow waters, obviously). It provides detailed Pareto front analysis for the voyage. The latter example concentrates on introducing additional optimisation constraints of static (“piracy threat” areas to be avoided) and dynamic type (wind speed above a threshold of 30 kn). The test bed environment has been build by incorporating MEWRA into the NaviWeather marine weather forecast and analysis software tool by NavSim Ltd. (as a weather routing plug-in). GRid In Binary (GRIB) files from the Global Forecast System (GFS) model have been utilised as a source of weather forecasts in this environment. The data in the GRIB files are organised as follows. There is a set of gridded points (by default 0·5° × 0·5°) for a specified time, for each of the points a single forecast is given. The sets of gridded points for each three hour time interval are provided in the same GRIB file. MEWRA utilises the data in such a way that whenever a forecast for a point in time is required, then the data from GRIB file is 3D interpolated (the three dimensions are: longitude, latitude and time). The forecasted data in a single GRIB file covers +180 h. If a forecasted ship's passage time is longer than 180 h then it is assumed that the weather conditions remain the same as for the last GRIB entry (the 180th h) for the excess time.
In both examples the following MERWA settings have been applied:
– population size and non-dominated set size of 100 routes each,
– mutation probability 0·4, crossover probability 0·6,
– 100 generations.
4.1. Example 1- Rotterdam – Miami voyage, departure 2013·09·27 00:00 am
In this example the criteria optimisation set includes only two criteria, namely passage time and safety of voyage (represented by a safety index). Fuel consumption has been here excluded from the criteria set so as to simplify the Pareto front analysis. For the same reason the optimisation constraints are limited to land obstacles and shallow waters only, as a must-be constraint. MEWRA total execution time for this example was 1 min 22 sec. on a standard PC machine.
A set of final 72 Pareto-optimal routes for the Rotterdam – Miami voyage found by MEWRA is presented in Figure 2.
Figure 2. Pareto-optimal set of routes for Rotterdam-Miami voyage, departure 2013·09·27 00:00 am, along with the ranked list of routes.
The resulting routes in the set are geographically similar to two local single-criterion extremes, the north-westerly going ones for shortest time and the south-easterly going ones for the highest voyage safety. When browsing through the Pareto-optimal set of routes (with assistance of MEWRA's ranking method) one can distinguish a route with the shortest passage time (presented in Figure 3, passage time 329·7 h and safety index 0·845) and a route assuring highest safety (Figure 4, passage time 353·2 h and safety index 0·938). The best-time route is quite close to the Rotterdam-Miami Great Circle, the differences being caused by impact of the weather conditions on ship's speed characteristics. The best-safety route is longer than the best-time one by 23·5 h (over 7%), but achieves a significant increase of the voyage safety (over 11%) by southerly bypassing unfavourable weather (mostly wind) conditions.
Figure 3. Best time route for Rotterdam-Miami voyage, departure 2013·09·27 00:00 am.
Figure 4. Best safety route for Rotterdam-Miami voyage, departure 2013·09·27 00:00 am.
A balanced route for the voyage, with preferences towards the criteria expressed as follows: “quite important” (0·5) for passage time and “quite important” (0·5) for safety of voyage, is presented in Figure 5. The balanced route (passage time 337·4 h and safety index 0·902) is close to the Great Circle through most of the voyage, but takes short southern bypasses, in the beginning and then a bit longer at the end of voyage, to avoid unfavourable weather conditions.
Figure 5. Route selected for balanced user's preferences for Rotterdam-Miami voyage, departure 2013·09·27 00:00 am.
Figure 6 presents a Pareto front plotted by using the Pareto-optimal routes data for the Rotterdam-Miami voyage. It is a very close approximation of a typical Pareto front curve for two contradictory criteria, when progress according to one criterion is a step back according to the other one. This is the case here: shortening passage time is achieved by utilising stronger favourable (from ship's speed characteristics) winds and waves (to a reasonable extent, obviously), which in turns lowers the safety index. On the other hand, bypassing unfavourable weather conditions (from the safety of voyage perspective) increases passage time. Additionally, in Figure 6 the selected best-time, best-safety and balanced routes are depicted. As expected, the best-time route can be located as the left-most Pareto front point, best-safety as the right-most point, while the balanced route is near the middle of the front.
Figure 6. Pareto front for the Rotterdam-Miami voyage, departure 2013·09·27 00:00 am.
4.2. Example 2- Plymouth – Havana, departure 2013·09·24 12:00 am
In this example the criteria set includes all three criteria: passage time, fuel consumption and safety index. Moreover, the optimisation constraint set includes:
• land obstacles and shallow waters,
• customisable areas excluded from search – the “piracy threat” areas to be avoided (a static constraint); based on a piracy report (RIANovosti, 2010) for this example a single area with location near Cuba has been chosen; on the resulting MEWRA screenshots (Figures 9–12)
• the area of “piracy threat” is presented as an orange box,
• regions where forecasted wind speed is above 30 kn (a dynamic constraint).
The NaviWeather tool has been used to process GRIB data and visualise regions of forecasted wind speed above the threshold of 30 kn during the voyage. Selected results of the wind speed data processing, presenting regions excluded from search (in red), are provided by Figures 7 and 8 respectively. Wind speed exceeding the assumed threshold has not been forecasted for the considered area for periods: 2013·09·24 12·00 am – 2013·09·27 03·00 am and 2013·09·30 03·00 pm – 2013·10·04 03·00 am. That is why these periods are not included in data visualisation (Figures 7 and 8). In this example MEWRA total execution time was 5 min 41 sec. on a standard PC machine.
Figure 7. Regions of forecasted wind speed above 30 kn for 2013·09·24 12:00 am – 2013·09·29 3:00 am (in the 09·24–09·26 period no winds above threshold in the area have been forecasted).
Figure 8. Regions of forecasted wind speed above 30 kn for 2013·09·29 3:00 pm – 2013·10·04 3:00 pm (in the 10·01–10·03 period no winds above threshold in the area have been forecasted).
A set of final 18 Pareto-optimal routes for the Plymouth – Havana voyage found by MEWRA (by its SPEA element) is presented in Figure 9. Obviously the set has been seriously limited by the optimisation constraints. All the Pareto-optimal routes bypass, which is clearly visible in the Figure 9, the static area of “piracy threat”. The constraint of regions with wind speed value exceeding 30 kn is a dynamic one and requires an animation to verify if it is not violated by a resulting route. However, when comparing the resulting Pareto-optimal routes and (Figure 9) with selected screenshots of winds above threshold during the voyage (Figures 7 and 8) one can discover that a key region limiting the optimal routes was the one that formed 500 Nm east from Newfoundland around 2013·09·28 01:00 am and diminished around 2013·09·30 06:00 pm. The region made all routes near to the Great Circle unfeasible (i.e. violating the constraint), thus all the Pareto-optimal routes bypass it by converging to a nearly loxodromic route around 45W longitude.
Figure 9. Pareto-optimal set of routes for Plymouth-Havana voyage, departure 2013·09·24 12:00 am, along with the ranked list of routes.
Again, as in the previous example, with assistance of MEWRA's ranking method, one can distinguish between the Pareto-optimal routes and the shortest one, having also the smallest fuel consumption (Figure 10, passage time 327·23 h, fuel consumption 206·16 t and safety index 0·832), a route assuring highest safety (Figure 11, passage time 335·39 h, fuel consumption 211·30 t and safety index 0·876) and a balanced one (Figure 12, passage time 328·62 h, fuel consumption 207·04 t and safety index 0·866). In this example the balanced route was selected based on the following preferences:
• passage time “quite important” (0·5),
• fuel consumption “almost unimportant” (0·15),
• safety of voyage “less important” (0·35).
Figure 10. Best time (and also best fuel) route for Plymouth-Havana voyage, departure 2013·09·24 12:00 am.
Figure 11. Best safety route for Plymouth-Havana voyage, departure 2013·09·24 12:00 am.
Figure 12. Route selected for balanced user's preferences for Plymouth-Havana voyage, departure 2013·09·24 12:00 am.
The best time and best fuel route (Figure 10) is the most similar, with regard to the constraints severely limiting the search space, to the Great Circle route among the Pareto set. The fact that the same route is the shortest and has the lowest fuel consumption indicates that the criteria are related (and, of course, are not contradictory). The best safety route (Figure 11) increases the safety index by 5·2% by taking a southern passage in its first half. The cost of the increase is an extra 8·16 h of passage time (2·5% of the best-time passage) and extra 5·14 t of fuel (also 2·5% of the best fuel consumption). The balanced route is close to the best time one in its performance values, as directed by the user preferences (the highest ranking weight among the criteria), however it has more loxodromic shape through the most of the voyage.
4.3. Conclusions from the examples
Both presented examples prove that MEWRA allows the finding of Pareto-optimal routes, taking into account forecasted weather conditions, in reasonable time. The execution time was less than 2 min for two criteria and basic constraint of landmasses and less than 6 min for three criteria and extended sets of constraints, including one static (“piracy threat” area) and one dynamic (regions of wind speed exceeding 30 kn). The most time consuming elements in the second example were precisely the additional constraints. They also severely limited the Pareto-optimal set of routes, which was evident in the number of obtained routes and their diversity. It is worth mentioning that the maximum capacity of the Pareto-optimal set is limited by the non-dominated set size, set by the user before starting MEWRA. In both examples the capacity was set to 100 routes. However, in practice the Pareto-optimal pool is rarely full: in both example cases the resulting Pareto-optimal set was smaller: 72 routes in the first one and only 18 in the second. The maximum Pareto-optimal pool size is only used in case of the method running for a large number of generations.
5. SUMMARY
In the paper the author presented the Multi-objective Evolutionary Weather Routing Algorithm (MEWRA), its base assumptions, structure and finally the examples of usage. MEWRA proves to be a valuable weather routing tool: it provides support in finding the Pareto-optimal set of routes for a given voyage (by its SPEA component) and facilitates browsing the set by the multi-criteria ranking method. The presented approach also offers fully customisable support to multiple criteria and constraints (both static and dynamic ones). The resulting Pareto-optimal set of routes enables users to choose a trade-off between optimisation goals via expressing their preferences towards the criteria. Last but not least, MEWRA returns its results in a reasonable time. All the above should make it a useful tool for users interested in optimising ship routes according to their preferences.
FINANCIAL SUPPORT
This research has been financially supported by NavSim Ltd. Poland, based on agreement between NavSim and Gdynia Maritime University, signed 26 January 2011.
