We consider the Tramp Ship Routing and Scheduling Problem (TSRSP) in which we plan routes for a 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 routes of a vessel, while the master problem keeps track of the binding constraints. The pricing problem is solved efficiently using a time–space graph and several dominance rules. Real-life instances with up to 40 vessels, 35 geographic regions, and four months planning horizon can be solved to optimality in less than half an hour. The optimized routes increase earnings by 7% compared to historical schedules. Furthermore, policy-makers can use the model as a simulation of a rational agent behavior.
We consider the Tramp Ship Routing and Scheduling Problem (TSRSP) in which we plan routes for a 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 routes of a vessel, while the master problem keeps track of the binding constraints. The pricing problem is solved efficiently using a time–space graph and several dominance rules. Real-life instances with up to 40 vessels, 35 geographic regions, and four months planning horizon can be solved to optimality in less than half an hour. The optimized routes increase earnings by 7% compared to historical schedules. Furthermore, policy-makers can use the model as a simulation of a rational agent behavior.
In transportation of goods in large container ships, shipping industries need to minimize the time spent at ports to load/unload containers. An optimal stowage of containers on board minimizes unnecessary unloading/reloading movements, while satisfying many operational constraints. We address the basic container stowage planning problem (CSPP). Different heuristics and formulations have been proposed for the CSPP, but finding an optimal stowage plan remains an open problem even for small-sized instances. We introduce a novel formulation that decomposes CSPPs into two sets of decision variables: the first defining how single container stacks evolve over time and the second modeling port-dependent constraints. Its linear relaxation is solved through stabilized column generation and with different heuristic and exact pricing algorithms. The lower bound achieved is then used to find an optimal stowage plan by solving a mixed-integer programming model. The proposed solution method outperforms the methods from the literature and can solve to optimality instances with up to 10 ports and 5,000 containers in a few minutes of computing time.