Modeling and Solving the Liner Shipping Service Selection Problem

Christian Vad Karsten, Anant Balakrishnan

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    Abstract

    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

    Conference

    ConferenceLOT - Logistics, Optimization and Transportation
    LocationMolde University College
    CountryNorway
    CityMolde
    Period01/09/201402/09/2014

    Bibliographical note

    Oral presentation

    Keywords

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

    Cite this

    Karsten, C. V., & Balakrishnan, A. (2014). Modeling and Solving the Liner Shipping Service Selection Problem. Abstract from LOT - Logistics, Optimization and Transportation, Molde, Norway.