IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v88y2016icp46-71.html
   My bibliography  Save this article

Service type assignment and container routing with transit time constraints and empty container repositioning for liner shipping service networks

Author

Listed:
  • Akyüz, M. Hakan
  • Lee, Chung-Yee

Abstract

A decision tool is developed for a liner shipping company to deploy its fleet considering vessel speeds and to find routes for cargos with repositioning of empty containers and transit time constraints. This problem is referred as the simultaneous Service type Assignment and container Routing Problem (SARP) in the sequel. A path-flow based mixed-integer linear programming formulation is suggested for the SARP. A Branch and Bound (BB) algorithm is used to solve the SARP exactly. A Column Generation (CG) procedure, embedded within the BB framework, is devised to solve the linear programming relaxation of the SARP. The CG subproblems arises as Shortest Path Problems (SPP). Yet incorporating transit time requirements yields constrained SPP which is NP-hard and solved by a label correcting algorithm. Computational experiments are performed on randomly generated test instances mimicking real life. The BB algorithm yields promising solutions for the SARP. The SARP with and without transit time constraints is compared with each other. Our results suggest a potential to increase profit margins of liner shipping companies by considering transit time requirements of cargos.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transb:v:88:y:2016:i:c:p:46-71
    DOI: 10.1016/j.trb.2016.02.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261515302137
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2016.02.007?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. Wang, Shuaian & Meng, Qiang, 2012. "Liner ship fleet deployment with container transshipment operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(2), pages 470-484.
    2. 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.
    3. Imai, Akio & Shintani, Koichi & Papadimitriou, Stratos, 2009. "Multi-port vs. Hub-and-Spoke port calls by containerships," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(5), pages 740-757, September.
    4. Theo Notteboom & Jean-Paul Rodrigue, 2008. "Containerisation, Box Logistics and Global Supply Chains: The Integration of Ports and Liner Shipping Networks," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 10(1-2), pages 152-174, March.
    5. Krishan Rana & R. G. Vickson, 1991. "Routing Container Ships Using Lagrangean Relaxation and Decomposition," Transportation Science, INFORMS, vol. 25(3), pages 201-214, August.
    6. 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.
    7. Kjetil Fagerholt & Trond A. V. Johnsen & Haakon Lindstad, 2009. "Fleet deployment in liner shipping: a case study," Maritime Policy & Management, Taylor & Francis Journals, vol. 36(5), pages 397-409, October.
    8. Marielle Christiansen & Kjetil Fagerholt & David Ronen, 2004. "Ship Routing and Scheduling: Status and Perspectives," Transportation Science, INFORMS, vol. 38(1), pages 1-18, February.
    9. Wang, Shuaian & Meng, Qiang, 2012. "Liner ship route schedule design with sea contingency time and port time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 615-633.
    10. Song, Dong-Ping & Dong, Jing-Xin, 2012. "Cargo routing and empty container repositioning in multiple shipping service routes," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1556-1575.
    11. Mulder, Judith & Dekker, Rommert, 2014. "Methods for strategic liner shipping network design," European Journal of Operational Research, Elsevier, vol. 235(2), pages 367-377.
    12. Christiansen, Marielle & Fagerholt, Kjetil & Nygreen, Bjørn & Ronen, David, 2013. "Ship routing and scheduling in the new millennium," European Journal of Operational Research, Elsevier, vol. 228(3), pages 467-483.
    13. Berit D. Brouer & J. Fernando Alvarez & Christian E. M. Plum & David Pisinger & Mikkel M. Sigurd, 2014. "A Base Integer Programming Model and Benchmark Suite for Liner-Shipping Network Design," Transportation Science, INFORMS, vol. 48(2), pages 281-312, May.
    14. Xinxin Liu & Heng-Qing Ye & Xue-Ming Yuan, 2011. "Tactical planning models for managing container flow and ship deployment," Maritime Policy & Management, Taylor & Francis Journals, vol. 38(5), pages 487-508, September.
    15. 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.
    16. Wang, Shuaian & Meng, Qiang, 2012. "Sailing speed optimization for container ships in a liner shipping network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 701-714.
    17. Desrochers, Martin & Soumis, Francois, 1988. "A reoptimization algorithm for the shortest path problem with time windows," European Journal of Operational Research, Elsevier, vol. 35(2), pages 242-254, May.
    18. 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.
    19. Meng, Qiang & Wang, Shuaian, 2011. "Liner shipping service network design with empty container repositioning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(5), pages 695-708, September.
    20. 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.
    21. 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.
    22. Bell, Michael G.H. & Liu, Xin & Angeloudis, Panagiotis & Fonzone, Achille & Hosseinloo, Solmaz Haji, 2011. "A frequency-based maritime container assignment model," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1152-1161, September.
    23. Qi, Xiangtong & Song, Dong-Ping, 2012. "Minimizing fuel emissions by optimizing vessel schedules in liner shipping with uncertain port times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(4), pages 863-880.
    24. 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.
    25. 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.
    26. Petering, Matthew E.H., 2011. "Decision support for yard capacity, fleet composition, truck substitutability, and scalability issues at seaport container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(1), pages 85-103, January.
    27. 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.
    28. Gelareh, Shahin & Pisinger, David, 2011. "Fleet deployment, network design and hub location of liner shipping companies," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(6), pages 947-964.
    29. Meng, Qiang & Wang, Shuaian, 2012. "Liner ship fleet deployment with week-dependent container shipment demand," European Journal of Operational Research, Elsevier, vol. 222(2), pages 241-252.
    30. Feremans, Corinne & Labbe, Martine & Laporte, Gilbert, 2003. "Generalized network design problems," European Journal of Operational Research, Elsevier, vol. 148(1), pages 1-13, July.
    31. Notteboom, Theo E. & Vernimmen, Bert, 2009. "The effect of high fuel costs on liner service configuration in container shipping," Journal of Transport Geography, Elsevier, vol. 17(5), pages 325-337.
    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. Kuzmicz, Katarzyna Anna & Pesch, Erwin, 2019. "Approaches to empty container repositioning problems in the context of Eurasian intermodal transportation," Omega, Elsevier, vol. 85(C), pages 194-213.
    2. 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.
    3. Zhang, Ruiyou & Zhao, Haishu & Moon, Ilkyeong, 2018. "Range-based truck-state transition modeling method for foldable container drayage services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 225-239.
    4. Chen, Jingxu & Jia, Shuai & Wang, Shuaian & Liu, Zhiyuan, 2018. "Subloop-based reversal of port rotation directions for container liner shipping network alteration," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 336-361.
    5. Tan, Zhijia & Zeng, Xianyang & Shao, Shuai & Chen, Jihong & Wang, Hua, 2022. "Scrubber installation and green fuel for inland river ships with non-identical streamflow," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 161(C).
    6. Alaa Abdelshafie & May Salah & Tomaž Kramberger & Dejan Dragan, 2022. "Repositioning and Optimal Re-Allocation of Empty Containers: A Review of Methods, Models, and Applications," Sustainability, MDPI, vol. 14(11), pages 1-23, May.
    7. 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.
    8. Sun, Qinghe & Li, Wei & Meng, Qiang, 2024. "Single-leg shipping revenue management for expedited services with ambiguous elasticity in transit-time-sensitive demand," Transportation Research Part B: Methodological, Elsevier, vol. 180(C).
    9. 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.

    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. 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.
    2. 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.
    3. Wang, Hua & Wang, Shuaian & Meng, Qiang, 2014. "Simultaneous optimization of schedule coordination and cargo allocation for liner container shipping networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 261-273.
    4. 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.
    5. Nguyen Khoi Tran & Hans-Dietrich Haasis & Tobias Buer, 2017. "Container shipping route design incorporating the costs of shipping, inland/feeder transport, inventory and CO2 emission," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 19(4), pages 667-694, December.
    6. Zheng, Jianfeng & Qi, Jingwen & Sun, Zhuo & Li, Feng, 2018. "Community structure based global hub location problem in liner shipping," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 1-19.
    7. Manuel Herrera & Per J. Agrell & Casiano Manrique-de-Lara-Peñate & Lourdes Trujillo, 2017. "Vessel capacity restrictions in the fleet deployment problem: an application to the Panama Canal," Annals of Operations Research, Springer, vol. 253(2), pages 845-869, June.
    8. 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.
    9. 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.
    10. 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.
    11. Wang, Shuaian & Liu, Zhiyuan & Bell, Michael G.H., 2015. "Profit-based maritime container assignment models for liner shipping networks," Transportation Research Part B: Methodological, Elsevier, vol. 72(C), pages 59-76.
    12. Wang, Shuaian, 2013. "Essential elements in tactical planning models for container liner shipping," Transportation Research Part B: Methodological, Elsevier, vol. 54(C), pages 84-99.
    13. 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.
    14. Dongping Song, 2021. "A Literature Review, Container Shipping Supply Chain: Planning Problems and Research Opportunities," Logistics, MDPI, vol. 5(2), pages 1-26, June.
    15. Berit Dangaard Brouer & Christian Vad Karsten & David Pisinger, 2018. "Optimization in liner shipping," Annals of Operations Research, Springer, vol. 271(1), pages 205-236, December.
    16. Zheng, Jianfeng & Sun, Zhuo & Zhang, Fangjun, 2016. "Measuring the perceived container leasing prices in liner shipping network design with empty container repositioning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 123-140.
    17. Wang, Shuaian & Meng, Qiang, 2013. "Reversing port rotation directions in a container liner shipping network," Transportation Research Part B: Methodological, Elsevier, vol. 50(C), pages 61-73.
    18. 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.
    19. Chen, Kang & Chen, Dongxu & Sun, Xueshan & Yang, Zhongzhen, 2016. "Container Ocean-transportation System Design with the factors of demand fluctuation and choice inertia of shippers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 267-281.
    20. Zheng, Jianfeng & Meng, Qiang & Sun, Zhuo, 2015. "Liner hub-and-spoke shipping network design," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 75(C), pages 32-48.

    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:transb:v:88:y:2016:i:c:p:46-71. 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/548/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.