Tramp ship routing and scheduling with voyage separation requirements

Jesper Larsen, Richard Martin Lusby, Charlotte Vilhelmsen

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review


    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.
    Original languageEnglish
    Publication date2017
    Publication statusPublished - 2017
    EventIFORS 2017: 21st Conference of the International Federation of Operations and Research - Québec City Convention Centre, Québec City, Canada
    Duration: 17 Jul 201721 Jul 2017


    ConferenceIFORS 2017
    Location Québec City Convention Centre
    City Québec City
    Internet address


    Dive into the research topics of 'Tramp ship routing and scheduling with voyage separation requirements'. Together they form a unique fingerprint.

    Cite this