A Model and Solution Algorithm for Optimal Routing of a Time-Chartered Containership

We formulate a mathematical programming model for optimally routing a chartered container ship. Our model helps in evaluating whether a container ship should be chartered or not. The model calculates the optimal sequence of port calls, the number of containers transported between port pairs, and the number of trips the ship makes in the chartered period. A specialized algorithm is developed to solve the integer network subprograms which determine the sequence of port calls. Our algorithm, which solves an integer program optimally, is quite efficient. Comparison of computational results with a Lagrangean Relaxation method and an embedded dynamic program are also presented.