Abstract The multi-commodity network flow problem (MCNF) consists in routing a set of commodities through a capacitated network at minimum cost and is relevant for routing containers in liner shipping networks. As commodity transit times are often a critical factor, the literature has introduced hard limits on commodity transit times. In practical contexts, however, these hard limits may fail to provide sufficient flexibility since routes with even tiny delays would be discarded. Motivated by a major liner shipping operator, we study an MCNF generalization where transit time restrictions are modeled as soft constraints, in which delays are discouraged using penalty functions of transit time. Similarly, early commodity arrivals can receive a discount in cost. We derive properties that distinguish this model from other MCNF variants and adapt a column generation procedure to efficiently solve it. Extensive numerical experiments conducted on realistic liner shipping instances reveal that the explicit consideration of penalty functions can lead to significant cost reductions compared to hard transit time deadlines. Moreover, the penalties can be used to steer the flow towards slower or faster configurations, resulting in a potential increase in operational costs, which generates a trade-off that we quantify under varying penalty functions.

    Highlights We study a generalization of the multi-commodity network flow problem. Longer commodity routes are discouraged using a penalty function of transit time. We propose a path formulation that is solved using a column generation method. Numerical experiments are conducted using realistic liner shipping instances. We discuss economic implications on costs and delays at varying penalty functions.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    The multi-commodity network flow problem with soft transit time constraints: Application to liner shipping


    Contributors:


    Publication date :

    2021-04-17




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    The time constrained multi-commodity network flow problem and its application to liner shipping network design

    Karsten, Christian Vad / Pisinger, David / Ropke, Stefan et al. | Elsevier | 2015



    A Matheuristic for the Liner Shipping Network Design Problem with Transit Time Restrictions

    Brouer, Berit Dangaard / Desaulniers, Guy / Karsten, Christian Vad et al. | British Library Conference Proceedings | 2015


    The liner shipping berth scheduling problem with transit times

    Reinhardt, Line Blander / Plum, Christian E.M. / Pisinger, David et al. | Elsevier | 2015