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

Description

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 con-
straints studied, hence we present the first unified model that can han-
dle 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 efficiently 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 algorith-
mic performance but also answering operational and tactical questions
for the tramp shipping company and the tramp shipping sector.

Period	1 Jul 2024
Event title	EURO-2024 Copenhagen: 33rd European Conference on Operational Research
Event type	Conference
Conference number	33
Location	Copenhagen, DenmarkShow on map
Degree of Recognition	International