Simulated annealing for optimal ship routing

In this article we present a simulated annealing based algorithm for the determination of optimal ship routes through the minimization of a cost function defined as a weighted sum of the time of voyage and the voyage comfort (safety is taken into account too). This cost function is dependent on the wind speed and its direction as well as on the wave height and its direction. The constructed algorithm at the beginning discretizes an initial route and then optimizes it by considering small deviations, which are accepted or rejected by utilizing the simulated annealing technique. Using calculus of variations, we prove a key theorem which tremendously accelerates the convergence of the proposed algorithm. For an illustration of the advantages of the constructed method, both computational and real experiments have been carried out which are presented and discussed. (C) 2011 Elsevier Ltd. All rights reserved.