Routing through dynamic ocean currents: General heuristics and empirical results in the gulf stream region

Anticipating the availability of good quality ocean current data in the near future, we formulate the problem of routing an ocean vessel through currents to minimize fuel consumption, propose methods to increase the efficiency of the solution techniques, and simulate voyages to investigate the performance of our approach. We formulate the problem as a dynamic program (DP) with two variables: Heading and Power (H&P). We then develop two heuristics, Headingthen-Power (H/P) and Heading-Alone (HA), that reduce the complexity of the formulation by decomposing the heading optimization from the power-setting optimization. To improve computational efficiency, we propose three approaches based on ship and ocean current dynamics to limit the spatial and temporal ranges that must be investigated to solve our DP formulations. In our simulation study, these approaches reduced the spatial ranges by over one third and the temporal ranges by over 70%. The study simulated minimum fuel current routing of 96 voyages in the Gulf Stream region, leading to average fuel savings of 7.4% and 4.5% for eastbound and westbound voyages, respectively. Moreover, the simplest HA heuristic, which emphasizes heading over power optimization, provided solutions as good as those provided by the most complete H&P formulation while reducing the computational time by a factor of 40. This indicates that the shipping industry's practice of emphasizing heading considerations seems appropriate in the current routing case and that current routing implementations and algorithmic developments might be able to reduce problem complexity by concentrating on spatial variables at the expense of temporal variables.