{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:00:00Z","timestamp":1740182400086,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,10,21]],"date-time":"2020-10-21T00:00:00Z","timestamp":1603238400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,21]],"date-time":"2020-10-21T00:00:00Z","timestamp":1603238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN Oper. Res. Forum"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Maritime transportation is the backbone of the global economy and one of its most important segments is liner shipping. To design a liner shipping network is notoriously difficult but also very important since an efficient network can be the difference between prosperity and bankruptcy. In this paper, we propose a branch-and-price algorithm for the liner shipping network design problem, which is the problem of designing a set of cyclic services and to deploy a specific class of vessels to each service so that all demand can flow through the network at minimal cost. The proposed model can create services with a complex structure and correctly calculate the transshipment cost. The formulation of the master problem strengthens a known formulation with valid inequalities. Because of multiple dependencies between ports that are not necessarily adjacent and no defining state at any of the ports, the subproblem is formulated and solved as a mixed integer linear program. Strategies to improve the solution time of the subproblem are proposed. The computational study shows that the algorithm provides significantly tighter lower bounds in the root node than existing methods on a set of small instances.<\/jats:p>","DOI":"10.1007\/s43069-020-00027-y","type":"journal-article","created":{"date-parts":[[2020,10,21]],"date-time":"2020-10-21T02:03:07Z","timestamp":1603245787000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Branch-and-Price Algorithm for the Liner Shipping Network Design Problem"],"prefix":"10.1007","volume":"1","author":[{"given":"Kristian","family":"Thun","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0312-8072","authenticated-orcid":false,"given":"Henrik","family":"Andersson","sequence":"additional","affiliation":[]},{"given":"Magnus","family":"St\u00e5lhane","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,21]]},"reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1287\/trsc.1070.0205","volume":"42","author":"R Agarwal","year":"2008","unstructured":"Agarwal R, Ergun \u00d8 (2008) Ship scheduling and network design for cargo routing in liner shipping. Transp Sci 42:175\u2013196","journal-title":"Transp Sci"},{"key":"27_CR2","doi-asserted-by":"publisher","unstructured":"Ameln M, Fuglum JS, Thun K, Andersson H, St\u00e5lhane M A new formulation for the liner shipping network design problem. Int Trans Oper Res 2019. https:\/\/doi.org\/10.1111\/itor.12659","DOI":"10.1111\/itor.12659"},{"issue":"3","key":"27_CR3","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1287\/opre.46.3.316","volume":"46","author":"C Barnhart","year":"1998","unstructured":"Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MPW, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46(3):316\u201329","journal-title":"Oper Res"},{"issue":"2","key":"27_CR4","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1287\/trsc.2013.0471","volume":"48","author":"BD Brouer","year":"2014","unstructured":"Brouer BD, Alvarez JF, Plum CEM, Pisinger D, Sigurd MM (2014) A base integer programming model and benchmark suite for liner-shipping network design. Transp Sci 48(2):281\u2013312","journal-title":"Transp Sci"},{"issue":"3","key":"27_CR5","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1016\/j.ejor.2012.12.002","volume":"228","author":"M Christiansen","year":"2012","unstructured":"Christiansen M, Fagerholt K, Nygreen B, Ronen D (2012) Ship routing and scheduling in the new millennium. Eur J Oper Res 228(3):467\u2013483","journal-title":"Eur J Oper Res"},{"issue":"1","key":"27_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2019.09.057","volume":"286","author":"M Christiansen","year":"2020","unstructured":"Christiansen M, Hellsten E, Pisinger D, Sacramento D, Vilhelmsen C (2020) Liner shipping network design. European J Oper Res 286 (1):1\u201320. https:\/\/doi.org\/10.1016\/j.ejor.2019.09.057","journal-title":"European J Oper Res"},{"issue":"1","key":"27_CR7","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1287\/opre.1090.0713","volume":"58","author":"G Desaulniers","year":"2010","unstructured":"Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper Res 58(1):179\u2013192","journal-title":"Oper Res"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Desrosiers J, L\u00fcbbecke ME (2005) A primer in column generation. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation. Springer, New York, pp 1\u201332","DOI":"10.1007\/0-387-25486-2_1"},{"key":"27_CR9","volume-title":"International sea transport: the years ahead","author":"SA Lawrence","year":"1972","unstructured":"Lawrence SA (1972) International sea transport: the years ahead. Lexington Books, Lexington"},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1016\/j.trb.2016.05.001","volume":"95","author":"C-Y Lee","year":"2017","unstructured":"Lee C-Y, Song D-P (2017) Ocean container transport in global supply chains: overview and research opportunities. Transport Res Part B Meth 95:442\u2013474","journal-title":"Transport Res Part B Meth"},{"issue":"2","key":"27_CR11","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1287\/trsc.2013.0461","volume":"48","author":"Q Meng","year":"2014","unstructured":"Meng Q, Wang S, Andersson H, Thun K (2014) Containership routing and scheduling in liner shipping: overview and future research directions. Transp Sci 48(2):265\u2013280","journal-title":"Transp Sci"},{"issue":"2","key":"27_CR12","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/j.ejor.2013.10.057","volume":"235","author":"CEM Plum","year":"2014","unstructured":"Plum CEM, Pisinger D, Sigurd MM (2014) A service flow model for the liner shipping network design problem. European J Oper Res 235(2):378\u2013386","journal-title":"European J Oper Res"},{"issue":"3","key":"27_CR13","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s10696-011-9105-4","volume":"24","author":"LB Reinhardt","year":"2011","unstructured":"Reinhardt LB, Pisinger D (2011) A branch and cut algorithm for the container shipping network design problem. Flex Serv Manuf J 24(3):349\u2013374","journal-title":"Flex Serv Manuf J"},{"issue":"2","key":"27_CR14","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1016\/j.ejor.2017.06.063","volume":"264","author":"A Santini","year":"2018","unstructured":"Santini A, Plum CEM, Stefan Ropke A (2018) Branch-and-price approach to the feeder network design problem. European J Oper Res 264(2):607\u2013622","journal-title":"European J Oper Res"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"3361","DOI":"10.1016\/j.cor.2012.04.021","volume":"39","author":"M St\u00e5lhane","year":"2012","unstructured":"St\u00e5lhane M, Andersson H, Christiansen M, Cordeau JF, Desaulniers G (2012) A branch-price-and-cut method for a ship routing and scheduling problem with split loads. Comput Oper Res 39:3361\u20133375","journal-title":"Comput Oper Res"},{"issue":"3","key":"27_CR16","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s10696-016-9262-6","volume":"29","author":"K Thun","year":"2017","unstructured":"Thun K, Andersson H, Christiansen M (2017) Analyzing complex service structures in liner shipping network design. Flex Serv Manuf J 29 (3):535\u2013552","journal-title":"Flex Serv Manuf J"},{"issue":"2-3","key":"27_CR17","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s10696-013-9179-2","volume":"27","author":"NK Tran","year":"2015","unstructured":"Tran NK, Haasis HD (2015) Literature survey of network optimization in container liner shipping. Flex Serv Manuf J 27(2-3):139\u2013179","journal-title":"Flex Serv Manuf J"},{"key":"27_CR18","unstructured":"UNCTAD Review of maritime transport 2019. Technical report, United Nations"}],"container-title":["SN Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-020-00027-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-020-00027-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-020-00027-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T00:14:43Z","timestamp":1634775283000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-020-00027-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,21]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["27"],"URL":"https:\/\/doi.org\/10.1007\/s43069-020-00027-y","relation":{},"ISSN":["2662-2556"],"issn-type":[{"type":"electronic","value":"2662-2556"}],"subject":[],"published":{"date-parts":[[2020,10,21]]},"assertion":[{"value":"20 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of interest"}}],"article-number":"28"}}