An Improved Formulation for Bulk Cargo Ship Scheduling with a Single Loading Port

Abstract

This paper presents an improved, significantly more efficient formulation of an existing model for bulk cargo or semi-bulk cargo ship scheduling problems with a single loading port. The original model, published by Ronen in 1986, was formulated as a non-linear, mixed integer program. In this work, the authors were able to re-formulate it into a linear one, by eliminating all the non-linearities of the original model. In addition, this model has far fewer integer variables than the original one. A numerical example has been given to illustrate the elimination of non-linearities and how 40 integer variables, in the original model, are reduced to just eight. This example also shows that this model is better at finding exact optimal solutions than the original one. It is also worth observing that the resulting model is a generalization of the 'capacitated facility location problem'.