A rich model for the tramp ship routing and scheduling problem — solved through column generation

We consider the Tramp Ship Routing and Scheduling Problem (TSRSP) in which we plan routes for a homogeneous fleet of tramp shipping vessels operating on a combined contract and spot market. Earlier research has been fragmented due to variations in the side constraints studied, hence we present the first unified model that can handle speed optimization, chartering costs, bunker planning, and hull cleaning. The model is solved by column generation, where the columns represent the possible routing of a vessel while the master problem keeps track of the binding constraints. The pricing problem is solved e ciently using a time-space graph, making it possible to solve relatively large instances of the TSRSP in a very short time. Detailed computational results are reported giving insight into both the algorithmic performance but also answering operational and tactical questions for the tramp shipping company and the tramp shipping sector.