Multi-Objective Ship Route Optimisation Using Estimation of Distribution Algorithm

Abstract

The paper proposes an innovative adaptation of the estimation of distribution algorithm (EDA), intended for multi-objective optimisation of a ship’s route in a non-stationary environment (tidal waters). The key elements of the proposed approach—the adaptive Markov chain-based path generator and the dynamic programming-based local search algorithm—are presented in detail. The experimental results presented indicate the high effectiveness of the proposed algorithm in finding very good quality approximations of optimal solutions in the Pareto sense. Critical for this was the proposed local search algorithm, whose application improved the final result significantly (the Pareto set size increased from five up to nine times, and the Pareto front quality just about doubled). The proposed algorithm can also be applied to other domains (e.g., mobile robot path planning). It can be considered a framework for (simulation-based) multi-objective optimal path planning in non-stationary environments.

Keywords

• multi-objective optimisation
• estimation of distribution algorithm
• EDA
• probabilistic model-building genetic algorithm
• Markov chain
• ship weather routing