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

Abstract

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.

Keywords:

• bunker fuel
• speed optimization
• optimality properties

Acknowledgements

The authors wish to thank two anonymous referees and the associate editor for their insightful comments, which have helped in making significant improvements in the article. This research is partially supported by the NOL Fellowship (NOLF) programme, an initiative by Neptune Orient Lines Ltd and the National University of Singapore.