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

A matheuristic for the liner shipping network design problem

Author

Listed:
  • Brouer, Berit Dangaard
  • Desaulniers, Guy
  • Pisinger, David

Abstract

We present an integer programming based heuristic, a matheuristic, for the liner shipping network design problem. This problem consists of finding a set of container shipping routes defining a capacitated network for cargo transport. The objective is to maximize the revenue of cargo transport, while minimizing the cost of operating the network. Liner shipping companies publish a set of routes with a time schedule, and it is an industry standard to have a weekly departure at each port call on a route. A weekly frequency is achieved by deploying several vessels to a single route, respecting the available fleet of container vessels. The matheuristic is composed of four main algorithmic components: a construction heuristic, an improvement heuristic, a reinsertion heuristic, and a perturbation heuristic. The improvement heuristic uses an integer program to select a set of improving port insertions and removals on each service. Computational results are reported for the benchmark suite LINER-LIB 2012 following the industry standard of weekly departures on every schedule. The heuristic shows overall good performance and is able to find high quality solutions within competitive execution times. The matheuristic can also be applied as a decision support tool to improve an existing network by optimizing on a designated subset of the routes. A case study is presented for this approach with very promising results.

Suggested Citation

  • Brouer, Berit Dangaard & Desaulniers, Guy & Pisinger, David, 2014. "A matheuristic for the liner shipping network design problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 42-59.
  • Handle: RePEc:eee:transe:v:72:y:2014:i:c:p:42-59
    DOI: 10.1016/j.tre.2014.09.012
    as

    Download full text from publisher

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

    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. Krishan Rana & R. G. Vickson, 1991. "Routing Container Ships Using Lagrangean Relaxation and Decomposition," Transportation Science, INFORMS, vol. 25(3), pages 201-214, August.
    3. 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.
    4. 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.
    5. Gulczynski, Damon & Golden, Bruce & Wasil, Edward, 2011. "The period vehicle routing problem: New heuristics and real-world variants," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(5), pages 648-668, September.
    6. 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.
    7. Gulczynski, Damon & Golden, Bruce & Wasil, Edward, 2010. "The split delivery vehicle routing problem with minimum delivery amounts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(5), pages 612-626, September.
    8. Kjetil Fagerholt *, 2004. "Designing optimal routes in a liner shipping problem," Maritime Policy & Management, Taylor & Francis Journals, vol. 31(4), pages 259-268, October.
    9. Karlaftis, Matthew G. & Kepaptsoglou, Konstantinos & Sambracos, Evangelos, 2009. "Containership routing with time deadlines and simultaneous deliveries and pick-ups," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(1), pages 210-221, January.
    10. Marielle Christiansen & Kjetil Fagerholt & David Ronen, 2004. "Ship Routing and Scheduling: Status and Perspectives," Transportation Science, INFORMS, vol. 38(1), pages 1-18, February.
    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. Plum, Christian E.M. & Pisinger, David & Sigurd, Mikkel M., 2014. "A service flow model for the liner shipping network design problem," European Journal of Operational Research, Elsevier, vol. 235(2), pages 378-386.
    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.
    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. repec:eee:transe:v:104:y:2017:i:c:p:189-210 is not listed on IDEAS
    2. repec:eee:ejores:v:263:y:2017:i:2:p:652-663 is not listed on IDEAS
    3. 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.
    4. 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.
    5. repec:eee:transb:v:106:y:2017:i:c:p:321-344 is not listed on IDEAS
    6. repec:eee:transe:v:105:y:2017:i:c:p:152-162 is not listed on IDEAS
    7. Mulder, J. & Dekker, R., 2016. "Will liner ships make fewer port calls per route?," Econometric Institute Research Papers EI2016-04, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    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. Bello, Omar & Phillips, Willard & Indar, Delena, 2016. "Towards a demand model for maritime passenger transportation in the Caribbean: a regional study of passenger ferry services," Studies and Perspectives – ECLAC Subregional Headquarters for The Caribbean 44, Naciones Unidas Comisión Económica para América Latina y el Caribe (CEPAL).
    10. Zhen, Lu & Shen, Tao & Wang, Shuaian & Yu, Shucheng, 2016. "Models on ship scheduling in transshipment hubs with considering bunker cost," International Journal of Production Economics, Elsevier, vol. 173(C), pages 111-121.
    11. 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.

    More about this item

    Keywords

    Liner shipping; Network design; Matheuristic;

    Statistics

    Access and download statistics

    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:72:y:2014:i:c:p:42-59. See general information about how to correct material in RePEc.

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

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.