# Multi-Objective Ship Route Optimisation Using Estimation of Distribution Algorithm
## 1 Introduction  
The importance of maritime cargo transport is on the rise. It is estimated that approximately 80% of goods are transported by sea, and this amount is constantly increasing. At the same time, there is a greater need to reduce carbon emissions--in 2018, the International Maritime Organization set the goal of reducing emissions by 40% (compared to 2008) per transport unit by 2030 [1]. As a result, fuel consumption reduction and optimal navigation have become more important than ever [2; 3; 4; 5].  
A significant number of real-life maritime transport optimisation problems are very complex [6], mainly because they are at the same time _multi-objective_ (the route should be optimal at least in terms of passage time and fuel consumption), _non-stationary_ (due to tidal streams and changing weather conditions), and _variational_ (the search space consists of trajectories). The only solution methods that can be effective for such cases are simulation based, which naturally leads to the use of meta-heuristic algorithms [7].  
Meta-heuristics typically require special mechanisms to maintain the population diversity to avoid getting stuck in local optima--this stops the search process and is particularly unfavourable when looking for the Pareto front. Unfortunately, diversity control mechanisms can result in a loss of exploitability, and this is why we often use local search algorithms simultaneously. The local search component becomes particularly important in the context of variational problems since, in most cases, the probability of missing a non-dominated solution (i.e., an element of the Pareto set) is significantly higher than in non-variational optimisation problems. This stems mainly from an assumed (non-obvious) distance representation in the search space and the corresponding implementation of a local perturbation, which should mimic trajectory variation.  
Considering all the above-mentioned properties, to the best of our knowledge, there are no methods that effectively meet all these requirements, especially as far as the real-lifeapplications are considered (a detailed review of the related research can be found in Section 2). Therefore, in this paper, we address this issue.  
The main contributions of this paper are as follows:  
1. A _3D-graph_-based design space and the computational topology it generates for dynamic programming (DP)-based local search (Section 4.1);
2. An (inspired by the estimation of distribution algorithm) adaptive Markov chain-based path generator directing the global search process (Section 4.2);
3. The DP-based local search algorithm, significantly boosting--thanks to its exploitation capabilities--the global search process (Section 4.3);
4. The meta-heuristic algorithm combining the above elements to create an effective framework for (simulation based) multi-objective optimal path planning in non-stationary environments (Section 4.4);
5. Experimental results showing the high effectiveness of the proposed algorithm in finding very good quality and diversified approximations of the set of Pareto optimal solutions (Section 5).  
The remainder of this paper is organised as follows. Section 2 presents related research. Following that, in Section 3, the optimisation problem under consideration is defined, and the proposed algorithm is described in Section 4. Thereafter, experimental results are presented and discussed in Section 5. Finally, Section 6 contains the conclusion of the study.