EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

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

Invited abstract in session MA-29: Combinatorial Optimization models and applications in Logistics and Transportation I, stream Combinatorial Optimization.

Monday, 8:30-10:00
Room: 157 (building: 208)

Authors (first author is the speaker)

1. Alberto Tamburini
Management Engineering, DTU
2. David Pisinger
Management, DTU
3. Nina Lange
Department of Mathematical Sciences, University of Copenhagen

Abstract

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 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 algorithmic performance but also answering operational and tactical questions for the tramp shipping company and the tramp shipping sector.

Keywords

Status: accepted

Back to the list of papers