Tramp ship routing and scheduling with voyage separation requirements

Activity: Talks and presentationsConference presentations

View graph of relations

Jesper Larsen - Guest lecturer

Charlotte Vilhelmsen - Other

Richard Martin Lusby - Other

This presentation addresses a tramp routing and scheduling problem. Tramp ships operate like taxies by following the available demand, as opposed to liner ships that operate like busses on a fixed route network according to a published timetable. Tramp operators determine some of the demand in advance by ensuring long-term contracts. The rest of the demand comes from optional voyages found in the spot market. Routing and scheduling a tramp feet to best utilize feet capacity according to the current demand is therefore an ongoing and complicated problem. We add further complexity by incorporating voyage separation requirements that enforce a minimum time spread between some voyages. We developed a new and exact Branch-and-Price procedure for this problem. A dynamic programming algorithm generates columns, while a novel time window branching scheme is used to enforce the voyage separation requirements. Computational results show that the algorithm finds optimal solutions very quickly for the vast majority of test instances. We compare the results with two earlier published methods and show that our Branch-and-Price approach outperforms both an a priori path generation method and an Adaptive Large Neighbourhood Search heuristic.
17 Jul 2017

Event (Conference)

TitleIFORS 2017
Location Québec City Convention Centre
City Québec City
Degree of recognitionInternational event


  • Applications, Maritime Logistics Programming, Integer
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 139445882