Modeling and Solving the Liner Shipping Service Selection Problem

Christian Vad Karsten, Anant Balakrishnan

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review


    We address a tactical planning problem, the Liner Shipping Service Selection Problem (LSSSP), facing container shipping companies. Given estimated demand between various ports, the LSSSP entails selecting the best subset of non-simple cyclic sailing routes from a given pool of candidate routes, and transporting as much demand as possible over the chosen routes. Since most containers are sent directly or transshipped at most twice in current liner shipping networks, we impose limits on the number of transshipments for each container. The objective is to maximize the net revenue, i.e., revenue from demand served less shipping costs. We propose a new hop-constrained multi-commodity arc flow model for the LSSSP that is based on an augmented network containing, for each candidate route, an arc (representing a sub-path) between every pair of ports that the route visits. This sub-path construct permits us to accurately model transshipment costs and incorporate routing policies such as maximum transit time, maritime cabotage rules, and operational alliances. Our hop-indexed arc flow model is smaller and easier to solve than path flow models. We outline a preprocessing procedure that exploits both the routing requirements and the hop limits to reduce problem size, and describe techniques to accelerate the solution procedure. We present computational results for realistic problem instances from the benchmark suite LINER-LIB.
    Original languageEnglish
    Publication date2014
    Publication statusPublished - 2014
    EventLOT - Logistics, Optimization and Transportation: A special EU/MEeting in memory of late Professor Arne Løkketangen - Molde University College, Molde, Norway
    Duration: 1 Sep 20142 Sep 2014


    ConferenceLOT - Logistics, Optimization and Transportation
    LocationMolde University College

    Bibliographical note

    Oral presentation


    • Liner Shipping
    • Service Selection
    • Transit Time
    • Cabotage Rules

    Fingerprint Dive into the research topics of 'Modeling and Solving the Liner Shipping Service Selection Problem'. Together they form a unique fingerprint.

    Cite this