{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:14:25Z","timestamp":1771485265225,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NTNU Norwegian University of Science and Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper considers a generalized version of the planar storage location problem arising in the stowage planning for Roll-on\/Roll-off ships. A ship is set to sail along a predefined voyage where given cargoes are to be transported between different port pairs along the voyage. We aim at determining the optimal stowage plan for the vehicles stored on a deck of the ship so that the time spent moving vehicles to enable loading or unloading of other vehicles (shifting), is minimized. We propose a novel mixed integer programming model for the problem, considering both the stowage and shifting aspect of the problem. An adaptive large neighborhood search (ALNS) heuristic with several new destroy and repair operators is developed. We further show how the shifting cost can be effectively evaluated using Dijkstra\u2019s algorithm by transforming the stowage plan into a network graph. The computational results show that the ALNS heuristic provides high quality solutions to realistic test instances.<\/jats:p>","DOI":"10.1007\/s10732-020-09451-z","type":"journal-article","created":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T20:03:10Z","timestamp":1597435390000},"page":"885-912","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["An adaptive large neighborhood search heuristic for the planar storage location assignment problem: application to stowage planning for Roll-on Roll-off ships"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9576-983X","authenticated-orcid":false,"given":"Jone R.","family":"Hansen","sequence":"first","affiliation":[]},{"given":"Kjetil","family":"Fagerholt","sequence":"additional","affiliation":[]},{"given":"Magnus","family":"St\u00e5lhane","sequence":"additional","affiliation":[]},{"given":"J\u00f8rgen G.","family":"Rakke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,14]]},"reference":[{"key":"9451_CR1","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/j.ejor.2018.08.004","volume":"273","author":"C Bayliss","year":"2019","unstructured":"Bayliss, C., Currie, C.S., Bennell, J.A., Martinez-Sykora, A.: Dynamic pricing for vehicle ferries: using packing and simulation to optimize revenues. Eur. J. Oper. Res. 273, 288\u2013304 (2019)","journal-title":"Eur. J. Oper. Res."},{"key":"9451_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-28356-0","volume-title":"Search Methodologies","author":"EK Burke","year":"2005","unstructured":"Burke, E.K., Kendall, G., et al.: Search Methodologies. Springer, Berlin (2005)"},{"key":"9451_CR3","unstructured":"Chen, P., Fu, Z., Lim, A., Rodrigues, B.: Two-dimensional packing for irregular shaped objects. In: Proceedings of the 36th Annual Hawaii International Conference on System Sciences, 2003. IEEE (2003)"},{"key":"9451_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.ejor.2011.06.008","volume":"215","author":"JF Cordeau","year":"2011","unstructured":"Cordeau, J.F., Laporte, G., Moccia, L., Sorrentino, G.: Optimizing yard assignment in an automotive transshipment terminal. Eur. J. Oper. Res. 215, 149\u2013160 (2011)","journal-title":"Eur. J. Oper. Res."},{"key":"9451_CR5","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/j.ejor.2015.03.044","volume":"246","author":"D Ding","year":"2015","unstructured":"Ding, D., Chou, M.C.: Stowage planning for container ships: a heuristic algorithm to reduce the number of shifts. Eur. J. Oper. Res. 246, 242\u2013249 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"9451_CR6","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0167-6377(89)90002-3","volume":"8","author":"TA Feo","year":"1989","unstructured":"Feo, T.A., Resende, M.G.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67\u201371 (1989)","journal-title":"Oper. Res. Lett."},{"key":"9451_CR7","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"TA Feo","year":"1995","unstructured":"Feo, T.A., Resende, M.G.: Greedy randomized adaptive search procedures. J. Global Optim. 6, 109\u2013133 (1995)","journal-title":"J. Global Optim."},{"key":"9451_CR8","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1287\/trsc.2014.0533","volume":"49","author":"AH Gharehgozli","year":"2014","unstructured":"Gharehgozli, A.H., Laporte, G., Yu, Y., de Koster, R.: Scheduling twin yard cranes in a container block. Transp. Sci. 49, 686\u2013705 (2014)","journal-title":"Transp. Sci."},{"key":"9451_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2006.02.025","volume":"177","author":"J Gu","year":"2007","unstructured":"Gu, J., Goetschalckx, M., McGinnis, L.F.: Research on warehouse operation: a comprehensive review. Eur. J. Oper. Res. 177, 1\u201321 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"9451_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1109\/TSSC.1970.300290","volume":"6","author":"MJ Haims","year":"1970","unstructured":"Haims, M.J., Freeman, H.: A multistage solution of the template-layout problem. IEEE Trans. Syst. Sci. Cybern. 6, 145\u2013151 (1970)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"9451_CR11","doi-asserted-by":"crossref","unstructured":"Hansen, J.R., Fagerholt, K., St\u00e5lhane, M.: A shortest path heuristic for evaluating the quality of stowage plans in roll-on roll-off liner shipping. In: Lecture Notes in Computer Science, vol. 10572, pp. 351\u2013365 (2017)","DOI":"10.1007\/978-3-319-68496-3_24"},{"key":"9451_CR12","doi-asserted-by":"crossref","unstructured":"Hansen, J.R., Hukkelberg, I., Fagerholt, K., St\u00e5lhane, M., Rakke, J.G.: 2d-packing with an application to stowage in roll-on roll-off liner shipping. In: Lecture Notes in Computer Science, vol. 9855, pp. 35\u201349 (2016)","DOI":"10.1007\/978-3-319-44896-1_3"},{"key":"9451_CR13","doi-asserted-by":"publisher","first-page":"3215","DOI":"10.1016\/j.cor.2012.04.007","volume":"39","author":"VC Hemmelmayr","year":"2012","unstructured":"Hemmelmayr, V.C., Cordeau, J.F., Crainic, T.G.: An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Comput. Oper. Res. 39, 3215\u20133228 (2012)","journal-title":"Comput. Oper. Res."},{"key":"9451_CR14","doi-asserted-by":"crossref","unstructured":"Iris, C., Pacino, D.: A survey on the ship loading problem. In: Lecture Notes in Computer Science, vol. 9335, pp. 238\u2013251 (2015)","DOI":"10.1007\/978-3-319-24264-4_17"},{"key":"9451_CR15","unstructured":"Iris, C., Pacino, D., Ropke, S.: Improved formulations and an Adaptive Large Neighborhood Search heuristic for the integrated berth allocation and quay crane assignment problem. Transp. Res. Part E Logist. Transp. Rev. 105, 123\u2013147 (2017)"},{"key":"9451_CR16","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.trb.2018.03.009","volume":"111","author":"C Iris","year":"2018","unstructured":"Iris, C., Christensen, J., Pacino, D., Ropke, S.: Flexible ship loading problem with transfer vehicle assignment and scheduling. Transp. Res. Part B 111, 39\u201356 (2018)","journal-title":"Transp. Res. Part B"},{"key":"9451_CR17","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/s00291-006-0051-6","volume":"28","author":"DC Mattfeld","year":"2006","unstructured":"Mattfeld, D.C., Orth, H.: The allocation of storage space for transshipment in vehicle distribution. OR Spectrum 28, 681\u2013703 (2006)","journal-title":"OR Spectrum"},{"key":"9451_CR18","unstructured":"Mauri, G.R., Ribeiro, G.M., Lorena, L.A.N., Laporte, G.: An adaptive large neighborhood search for the discrete and continuous Berth allocation problem. Comput. Oper. Res. 70, 140\u2013154 (2016)"},{"key":"9451_CR19","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/j.ejor.2014.05.030","volume":"239","author":"MF Monaco","year":"2014","unstructured":"Monaco, M.F., Sammarra, M., Sorrentino, G.: The terminal-oriented ship stowage planning problem. Eur. J. Oper. Res. 239, 256\u2013265 (2014)","journal-title":"Eur. J. Oper. Res."},{"key":"9451_CR20","doi-asserted-by":"publisher","first-page":"1425","DOI":"10.1016\/j.cor.2011.01.004","volume":"38","author":"BO \u00d8vsteb\u00f8","year":"2011","unstructured":"\u00d8vsteb\u00f8, B.O., Hvattum, L.M., Fagerholt, K.: Optimization of stowage plans for roro ships. Comput. Oper. Res. 38, 1425\u20131434 (2011a)","journal-title":"Comput. Oper. Res."},{"key":"9451_CR21","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1016\/j.trc.2011.02.001","volume":"19","author":"BO \u00d8vsteb\u00f8","year":"2011","unstructured":"\u00d8vsteb\u00f8, B.O., Hvattum, L.M., Fagerholt, K.: Routing and scheduling of roro ships with stowage constraints. Transp. Res. Part C Emerg. Technol. 19, 1225\u20131242 (2011b)","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"9451_CR22","doi-asserted-by":"publisher","first-page":"1062","DOI":"10.1016\/j.cie.2009.04.010","volume":"57","author":"C Park","year":"2009","unstructured":"Park, C., Seo, J.: Mathematical modeling and solving procedure of the planar storage location assignment problem. Comput. Ind. Eng. 57, 1062\u20131071 (2009)","journal-title":"Comput. Ind. Eng."},{"key":"9451_CR23","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.tre.2009.07.004","volume":"46","author":"C Park","year":"2010","unstructured":"Park, C., Seo, J.: Comparing heuristic algorithms of the planar storage location assignment problem. Transp. Res. Part E Logist. Transp. Rev. 46, 171\u2013185 (2010)","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"9451_CR24","first-page":"1","volume":"9","author":"M Prais","year":"2000","unstructured":"Prais, M., Ribeiro, C.C.: Parameter variation in grasp procedures. Investig. Oper. 9, 1\u201320 (2000)","journal-title":"Investig. Oper."},{"key":"9451_CR25","doi-asserted-by":"publisher","DOI":"10.1080\/20464177.2018.1516942","author":"R Puisa","year":"2018","unstructured":"Puisa, R.: Optimal stowage on ro-ro decks for efficiency and safety. J. Mar. Eng. Technol. (2018). https:\/\/doi.org\/10.1080\/20464177.2018.1516942","journal-title":"J. Mar. Eng. Technol."},{"key":"9451_CR26","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-1-4614-6940-7_11","volume-title":"Search Methodologies","author":"MG Resende","year":"2014","unstructured":"Resende, M.G., Ribeiro, C.C.: Grasp: greedy randomized adaptive search procedures. In: Burke, E., Kendall, G. (eds.) Search Methodologies, pp. 287\u2013312. Springer, Boston (2014)"},{"key":"9451_CR27","first-page":"199","volume":"10","author":"J Reyes","year":"2019","unstructured":"Reyes, J., Solano-Charris, E., Montoya-Torres, J.: The storage location assignment problem: a literature review. Int. J. Ind. Eng. Comput. 10, 199\u2013224 (2019)","journal-title":"Int. J. Ind. Eng. Comput."},{"key":"9451_CR28","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1016\/j.cor.2011.05.005","volume":"39","author":"GM Ribeiro","year":"2012","unstructured":"Ribeiro, G.M., Laporte, G.: An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 39, 728\u2013735 (2012)","journal-title":"Comput. Oper. Res."},{"key":"9451_CR29","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1287\/trsc.1050.0135","volume":"40","author":"S Ropke","year":"2006","unstructured":"Ropke, S., Pisinger, D.: An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40, 455\u2013472 (2006)","journal-title":"Transp. Sci."},{"key":"9451_CR30","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1057\/jors.2015.62","volume":"67","author":"MP Seixas","year":"2016","unstructured":"Seixas, M.P., Mendes, A.B., Pereira Barretto, M.R., Da Cunha, C.B., Brinati, M.A., Cruz, R.E., Wu, Y., Wilson, P.A.: A heuristic approach to stowing general cargo into platform supply vessels. J. Oper. Res. Soc. 67, 148\u2013158 (2016)","journal-title":"J. Oper. Res. Soc."},{"key":"9451_CR31","doi-asserted-by":"publisher","first-page":"4289","DOI":"10.1080\/00207543.2013.774477","volume":"51","author":"N Tao","year":"2013","unstructured":"Tao, N., Jiang, Z., Qu, S.: Assembly block location and sequencing for flat transporters in a planar storage yard of shipyards. Int. J. Prod. Res. 51, 4289\u20134301 (2013)","journal-title":"Int. J. Prod. Res."},{"key":"9451_CR32","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.dam.2014.01.005","volume":"169","author":"K Tierney","year":"2014","unstructured":"Tierney, K., Pacino, D., Jensen, R.M.: On the complexity of container stowage planning problems. Discrete Appl. Math. 169, 225\u2013230 (2014)","journal-title":"Discrete Appl. Math."},{"key":"9451_CR33","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1287\/opre.31.3.573","volume":"31","author":"P Wang","year":"1983","unstructured":"Wang, P.: Two algorithms for constrained two-dimensional cutting stock problems. Oper. Res. 31, 573\u2013586 (1983)","journal-title":"Oper. Res."},{"key":"9451_CR34","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/s11804-005-0018-z","volume":"4","author":"Z Wei-Ying","year":"2005","unstructured":"Wei-Ying, Z., Yan, L., Zhuo-Shang, J.: Model and algorithm for container ship stowage planning based on bin-packing problem. J. Mar. Sci. Appl. 4, 30\u201336 (2005)","journal-title":"J. Mar. Sci. Appl."},{"key":"9451_CR35","doi-asserted-by":"publisher","first-page":"1321","DOI":"10.1080\/00207540802555736","volume":"48","author":"J Xiao","year":"2010","unstructured":"Xiao, J., Zheng, L.: A correlated storage location assignment problem in a single-block-multi-aisles warehouse considering bom information. Int. J. Prod. Res. 48, 1321\u20131338 (2010)","journal-title":"Int. J. Prod. Res."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-020-09451-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-020-09451-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-020-09451-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:35:40Z","timestamp":1667781340000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-020-09451-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,14]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["9451"],"URL":"https:\/\/doi.org\/10.1007\/s10732-020-09451-z","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,14]]},"assertion":[{"value":"26 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}