Optimality properties of speed optimization for a vessel operating with time window constraint

We consider speed optimization for a vessel that has to arrive at every port along its voyage within a time window at each port. The objective of the problem is to minimize the vessel’s bunker fuel cost given that fuel consumption rate is a convex function of speed. The intent of this paper is to establish the optimality properties for this problem and show that a solution with such properties (which we refer to as a good solution) is unique and optimal. The optimality properties established in this paper facilitate the proof of exactness for existing and future algorithms, as one needs only to show that the solution provided by an algorithm satisfies the definition of a good solution. As an illustration, we show how we can apply our results to prove the exactness of an existing algorithm in literature. Our work contributes to the understanding of the problem’s optimality structure, which will provide intuition for development of algorithms for this problem.