IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v150y2021ics1366554521001137.html
   My bibliography  Save this article

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

Author

Listed:
  • Trivella, Alessio
  • Corman, Francesco
  • Koza, David F.
  • Pisinger, David

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.

Suggested Citation

  • Trivella, Alessio & Corman, Francesco & Koza, David F. & Pisinger, David, 2021. "The multi-commodity network flow problem with soft transit time constraints: Application to liner shipping," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 150(C).
  • Handle: RePEc:eee:transe:v:150:y:2021:i:c:s1366554521001137
    DOI: 10.1016/j.tre.2021.102342
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554521001137
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.tre.2021.102342?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Liu, Zhiyuan & Meng, Qiang & Wang, Shuaian & Sun, Zhuo, 2014. "Global intermodal liner shipping network design," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 28-39.
    2. Richa Agarwal & Özlem Ergun, 2008. "Ship Scheduling and Network Design for Cargo Routing in Liner Shipping," Transportation Science, INFORMS, vol. 42(2), pages 175-196, May.
    3. Kaj Holmberg & Di Yuan, 2003. "A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 42-57, February.
    4. Wang, Shuaian & Meng, Qiang & Liu, Zhiyuan, 2013. "Containership scheduling with transit-time-sensitive container shipment demand," Transportation Research Part B: Methodological, Elsevier, vol. 54(C), pages 68-83.
    5. Luigi Di Puglia Pugliese & Francesca Guerriero, 2013. "A Reference Point Approach for the Resource Constrained Shortest Path Problems," Transportation Science, INFORMS, vol. 47(2), pages 247-265, May.
    6. Melchiori, Anna & Sgalambro, Antonino, 2020. "A branch and price algorithm to solve the Quickest Multicommodity k-splittable Flow Problem," European Journal of Operational Research, Elsevier, vol. 282(3), pages 846-857.
    7. Wang, Shuaian & Meng, Qiang, 2012. "Robust schedule design for liner shipping services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(6), pages 1093-1106.
    8. Meng, Qiang & Lee, Chung-Yee, 2016. "Liner container assignment model with transit-time-sensitive container shipment demand and its applicationsAuthor-Name: Wang, Shuaian," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 135-155.
    9. Jun Xia & Kevin X. Li & Hong Ma & Zhou Xu, 2015. "Joint Planning of Fleet Deployment, Speed Optimization, and Cargo Allocation for Liner Shipping," Transportation Science, INFORMS, vol. 49(4), pages 922-938, November.
    10. Cynthia Barnhart & Christopher A. Hane & Pamela H. Vance, 2000. "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems," Operations Research, INFORMS, vol. 48(2), pages 318-326, April.
    11. Guericke, Stefan & Tierney, Kevin, 2015. "Liner shipping cargo allocation with service levels and speed optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 84(C), pages 40-60.
    12. Koza, David Franz, 2019. "Liner shipping service scheduling and cargo allocation," European Journal of Operational Research, Elsevier, vol. 275(3), pages 897-915.
    13. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    14. Karsten, Christian Vad & Pisinger, David & Ropke, Stefan & Brouer, Berit Dangaard, 2015. "The time constrained multi-commodity network flow problem and its application to liner shipping network design," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 76(C), pages 122-138.
    15. Abbas Azadi Moghaddam Arani & Fariborz Jolai & Mohammad Mahdi Nasiri, 2019. "A multi-commodity network flow model for railway capacity optimization in case of line blockage," International Journal of Rail Transportation, Taylor & Francis Journals, vol. 7(4), pages 297-320, October.
    16. Brouer, Berit D. & Dirksen, Jakob & Pisinger, David & Plum, Christian E.M. & Vaaben, Bo, 2013. "The Vessel Schedule Recovery Problem (VSRP) – A MIP model for handling disruptions in liner shipping," European Journal of Operational Research, Elsevier, vol. 224(2), pages 362-374.
    17. Sedeño-noda, Antonio & Colebrook, Marcos, 2019. "A biobjective Dijkstra algorithm," European Journal of Operational Research, Elsevier, vol. 276(1), pages 106-118.
    18. Enzi, Miriam & Parragh, Sophie N. & Pisinger, David & Prandtstetter, Matthias, 2021. "Modeling and solving the multimodal car- and ride-sharing problem," European Journal of Operational Research, Elsevier, vol. 293(1), pages 290-303.
    19. Theo E Notteboom, 2006. "The Time Factor in Liner Shipping Services," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 8(1), pages 19-39, March.
    20. Reinhardt, Line Blander & Pisinger, David & Sigurd, Mikkel M. & Ahmt, Jonas, 2020. "Speed optimizations for liner networks with business constraints," European Journal of Operational Research, Elsevier, vol. 285(3), pages 1127-1140.
    21. Duque, Daniel & Lozano, Leonardo & Medaglia, Andrés L., 2015. "An exact method for the biobjective shortest path problem for large-scale road networks," European Journal of Operational Research, Elsevier, vol. 242(3), pages 788-797.
    22. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    23. Gelareh, Shahin & Nickel, Stefan & Pisinger, David, 2010. "Liner shipping hub network design in a competitive environment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(6), pages 991-1004, November.
    24. David F. Koza & Guy Desaulniers & Stefan Ropke, 2020. "Integrated Liner Shipping Network Design and Scheduling," Transportation Science, INFORMS, vol. 54(2), pages 512-533, March.
    25. Wang, Shuaian & Meng, Qiang & Sun, Zhuo, 2013. "Container routing in liner shipping," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 49(1), pages 1-7.
    26. Refael Hassin, 1992. "Approximation Schemes for the Restricted Shortest Path Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 36-42, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gam Thi Hong Nguyen & Daria Ruzaeva & Julio Cesar Góez & Mario Guajardo, 2022. "Insights on the introduction of autonomous vessels to liner shipping networks," Journal of Shipping and Trade, Springer, vol. 7(1), pages 1-27, December.
    2. Ding, Xiaoshu & Qi, Qi & Jian, Sisi & Yang, Hai, 2023. "Mechanism design for Mobility-as-a-Service platform considering travelers’ strategic behavior and multidimensional requirements," Transportation Research Part B: Methodological, Elsevier, vol. 173(C), pages 1-30.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Karsten, Christian Vad & Pisinger, David & Ropke, Stefan & Brouer, Berit Dangaard, 2015. "The time constrained multi-commodity network flow problem and its application to liner shipping network design," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 76(C), pages 122-138.
    2. Akyüz, M. Hakan & Lee, Chung-Yee, 2016. "Service type assignment and container routing with transit time constraints and empty container repositioning for liner shipping service networks," Transportation Research Part B: Methodological, Elsevier, vol. 88(C), pages 46-71.
    3. Wetzel, Daniel & Tierney, Kevin, 2024. "Rethinking cyclic structures in liner shipping networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 556-568.
    4. David F. Koza & Guy Desaulniers & Stefan Ropke, 2020. "Integrated Liner Shipping Network Design and Scheduling," Transportation Science, INFORMS, vol. 54(2), pages 512-533, March.
    5. Christiansen, Marielle & Hellsten, Erik & Pisinger, David & Sacramento, David & Vilhelmsen, Charlotte, 2020. "Liner shipping network design," European Journal of Operational Research, Elsevier, vol. 286(1), pages 1-20.
    6. Lee, Chung-Yee & Song, Dong-Ping, 2017. "Ocean container transport in global supply chains: Overview and research opportunities," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 442-474.
    7. Liu, Zhiyuan & Meng, Qiang & Wang, Shuaian & Sun, Zhuo, 2014. "Global intermodal liner shipping network design," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 28-39.
    8. Guericke, Stefan & Tierney, Kevin, 2015. "Liner shipping cargo allocation with service levels and speed optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 84(C), pages 40-60.
    9. Qiang Meng & Shuaian Wang & Henrik Andersson & Kristian Thun, 2014. "Containership Routing and Scheduling in Liner Shipping: Overview and Future Research Directions," Transportation Science, INFORMS, vol. 48(2), pages 265-280, May.
    10. Wang, Shuaian, 2014. "A novel hybrid-link-based container routing model," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 165-175.
    11. Koza, David Franz, 2019. "Liner shipping service scheduling and cargo allocation," European Journal of Operational Research, Elsevier, vol. 275(3), pages 897-915.
    12. Meng, Qiang & Lee, Chung-Yee, 2016. "Liner container assignment model with transit-time-sensitive container shipment demand and its applicationsAuthor-Name: Wang, Shuaian," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 135-155.
    13. Reinhardt, Line Blander & Pisinger, David & Sigurd, Mikkel M. & Ahmt, Jonas, 2020. "Speed optimizations for liner networks with business constraints," European Journal of Operational Research, Elsevier, vol. 285(3), pages 1127-1140.
    14. Yadong Wang & Qiang Meng & Haibo Kuang, 2019. "Intercontinental Liner Shipping Service Design," Transportation Science, INFORMS, vol. 53(2), pages 344-364, March.
    15. Karsten, Christian Vad & Brouer, Berit Dangaard & Desaulniers, Guy & Pisinger, David, 2017. "Time constrained liner shipping network design," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 152-162.
    16. Balakrishnan, Anantaram & Karsten, Christian Vad, 2017. "Container shipping service selection and cargo routing with transshipment limits," European Journal of Operational Research, Elsevier, vol. 263(2), pages 652-663.
    17. Asghari, Mohammad & Jaber, Mohamad Y. & Mirzapour Al-e-hashem, S.M.J., 2023. "Coordinating vessel recovery actions: Analysis of disruption management in a liner shipping service," European Journal of Operational Research, Elsevier, vol. 307(2), pages 627-644.
    18. Mulder, J. & Dekker, R., 2016. "Optimization in container liner shipping," Econometric Institute Research Papers EI2016-05, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    19. Zhen, Lu & Wu, Yiwei & Wang, Shuaian & Laporte, Gilbert, 2020. "Green technology adoption for fleet deployment in a shipping network," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 388-410.
    20. Aydin, N. & Lee, H. & Mansouri, S.A., 2017. "Speed optimization and bunkering in liner shipping in the presence of uncertain service times and time windows at ports," European Journal of Operational Research, Elsevier, vol. 259(1), pages 143-154.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:150:y:2021:i:c:s1366554521001137. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.