{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T03:22:11Z","timestamp":1776828131667,"version":"3.51.2"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,7,17]],"date-time":"2021-07-17T00:00:00Z","timestamp":1626480000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,17]],"date-time":"2021-07-17T00:00:00Z","timestamp":1626480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Field of Excellence \u201cCOLIBRI\u201d"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["OR Spectrum"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a packing problem that arises in a direct-shipping system in the food and beverage industry: Trucks are the containers, and products to be distributed are the items. The packing is constrained by two independent quantities, weight (e.g., measured in kg) and volume (number of pallets). Additionally, the products are grouped into the three categories: standard, cooled, and frozen (the latter two require refrigerated trucks). Products of different categories can be transported in one truck using separated zones, but the cost of a truck depends on the transported product categories. Moreover, splitting orders of a product should be avoided so that (un-)loading is simplified. As a result, we seek for a feasible packing optimizing the following objective functions in a strictly lexicographic sense: minimize the (1)\u00a0total number of trucks; (2)\u00a0number of refrigerated trucks; (3)\u00a0number of refrigerated trucks which contain frozen products; (4)\u00a0number of refrigerated trucks which also transport standard products; (5)\u00a0and minimize splitting. This is a real-world application of a bin-packing problem with cardinality constraints a.k.a. the two-dimensional vector packing problem with additional constraints. We provide a heuristic and an exact solution approach. The heuristic meta-scheme considers the multi-compartment and item fragmentation features of the problem and applies various problem-specific heuristics. The exact solution algorithm covering all five stages is based on branch-and-price using stabilization techniques exploiting dual-optimal inequalities. Computational results on real-world and difficult self-generated instances prove the applicability of our approach.<\/jats:p>","DOI":"10.1007\/s00291-021-00628-x","type":"journal-article","created":{"date-parts":[[2021,7,17]],"date-time":"2021-07-17T01:02:16Z","timestamp":1626483736000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Bin packing with lexicographic objectives for loading weight- and volume-constrained trucks in a direct-shipping system"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1334-1117","authenticated-orcid":false,"given":"Katrin","family":"He\u00dfler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9383-4546","authenticated-orcid":false,"given":"Stefan","family":"Irnich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Kreiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8881-1497","authenticated-orcid":false,"given":"Ulrich","family":"Pferschy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,17]]},"reference":[{"issue":"3","key":"628_CR1","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10732-017-9326-0","volume":"24","author":"R Aringhieri","year":"2018","unstructured":"Aringhieri R, Duma D, Grosso A, Hosteins P (2018) Simple but effective heuristics for the 2-constraint bin packing problem. J Heuristics 24(3):345\u2013357","journal-title":"J Heuristics"},{"key":"628_CR2","doi-asserted-by":"crossref","unstructured":"Bansal N, Eli\u00ed\u0161 M, Khan A (2016) Improved approximation for vector bin packing. In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, vol 3. SIAM, pp 1561\u20131579","DOI":"10.1137\/1.9781611974331.ch106"},{"issue":"3","key":"628_CR3","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1287\/opre.1060.0278","volume":"54","author":"H Ben Amor","year":"2006","unstructured":"Ben Amor H, Desrosiers J, Val\u00e9rio de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper Res 54(3):454\u2013463","journal-title":"Oper Res"},{"key":"628_CR4","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.dam.2018.08.023","volume":"261","author":"L Bertazzi","year":"2019","unstructured":"Bertazzi L, Golden B, Wang X (2019) The bin packing problem with item fragmentation: a worst-case analysis. Discrete Appl Math 261:63\u201377","journal-title":"Discrete Appl Math"},{"key":"628_CR5","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.cor.2015.11.009","volume":"69","author":"F Brand\u00e3o","year":"2016","unstructured":"Brand\u00e3o F, Pedroso JP (2016) Bin packing and related problems: general arc-flow formulation with graph compression. Comput Oper Res 69:56\u201367","journal-title":"Comput Oper Res"},{"issue":"1\u20133","key":"628_CR6","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0166-218X(98)00046-8","volume":"87","author":"A Caprara","year":"1998","unstructured":"Caprara A (1998) Properties of some ILP formulations of a class of partitioning problems. Discrete Appl Math 87(1\u20133):11\u201323","journal-title":"Discrete Appl Math"},{"issue":"3","key":"628_CR7","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0166-218X(00)00267-5","volume":"111","author":"A Caprara","year":"2001","unstructured":"Caprara A, Toth P (2001) Lower bounds and algorithms for the 2-dimensional vector packing problem. Discrete Appl Math 111(3):231\u2013262","journal-title":"Discrete Appl Math"},{"issue":"1","key":"628_CR8","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1002\/nav.10058","volume":"50","author":"A Caprara","year":"2003","unstructured":"Caprara A, Kellerer H, Pferschy U (2003) Approximation schemes for ordered vector packing problems. Naval Res Logist 50(1):58\u201369","journal-title":"Naval Res Logist"},{"issue":"2","key":"628_CR9","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/s11590-018-1327-x","volume":"13","author":"M Casazza","year":"2019","unstructured":"Casazza M (2019) New formulations for variable cost and size bin packing problems with item fragmentation. Optim Lett 13(2):379\u2013398","journal-title":"Optim Lett"},{"key":"628_CR10","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/j.cor.2016.06.007","volume":"75","author":"M Casazza","year":"2016","unstructured":"Casazza M, Ceselli A (2016) Exactly solving packing problems with fragmentation. Comput Oper Res 75:202\u2013213","journal-title":"Comput Oper Res"},{"key":"628_CR11","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen HI, Khan A, Pokutta S, Tetali P (2017) Approximation and online algorithms for multidimensional bin packing: a survey. Comput Sci Rev 24:63\u201379","journal-title":"Comput Sci Rev"},{"key":"628_CR12","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-1-4419-7997-1_35","volume-title":"Handbook of combinatorial optimization","author":"EG Coffman Jr","year":"2013","unstructured":"Coffman EG Jr, Csirik J, Galambos G, Martello S, Vigo D (2013) Bin packing approximation algorithms: survey and classification. In: Pardalos P, Du DZ, Graham R (eds) Handbook of combinatorial optimization. Springer, New York, pp 455\u2013531"},{"issue":"4","key":"628_CR13","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1287\/ijoc.2018.0806","volume":"30","author":"J-F C\u00f4t\u00e9","year":"2018","unstructured":"C\u00f4t\u00e9 J-F, Iori M (2018) The meet-in-the-middle principle for cutting and packing problems. INFORMS J Comput 30(4):646\u2013661","journal-title":"INFORMS J Comput"},{"issue":"1","key":"628_CR14","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1287\/ijoc.2018.0880","volume":"32","author":"M Delorme","year":"2020","unstructured":"Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J Comput 32(1):101\u2013119","journal-title":"INFORMS J Comput"},{"issue":"1","key":"628_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2016.04.030","volume":"255","author":"M Delorme","year":"2016","unstructured":"Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur J Oper Res 255(1):1\u201320","journal-title":"Eur J Oper Res"},{"key":"628_CR16","volume-title":"Column generation","year":"2005","unstructured":"Desaulniers G, Desrosiers J, Solomon M (eds) (2005) Column generation. Springer, New York, NY"},{"key":"628_CR17","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"P Gilmore","year":"1961","unstructured":"Gilmore P, Gomory R (1961) A linear programming approach to the cutting-stock problem. Oper Res 9:849\u2013859","journal-title":"Oper Res"},{"issue":"1","key":"628_CR18","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1287\/ijoc.2015.0670","volume":"28","author":"T Gschwind","year":"2016","unstructured":"Gschwind T, Irnich S (2016) Dual inequalities for stabilized column generation revisited. INFORMS J Comput 28(1):175\u2013194","journal-title":"INFORMS J Comput"},{"key":"628_CR19","unstructured":"Henke T (2018) Multi-compartment vehicle routing problems in the context of glass waste collection. Ph.D. thesis, Otto-von-Guericke University Magdeburg, Magdeburg, Germany"},{"issue":"2","key":"628_CR20","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/j.ejor.2018.04.047","volume":"271","author":"K He\u00dfler","year":"2018","unstructured":"He\u00dfler K, Gschwind T, Irnich S (2018) Stabilized branch-and-price algorithms for vector packing problems. Eur J Oper Res 271(2):401\u2013419","journal-title":"Eur J Oper Res"},{"key":"628_CR21","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/0-387-25486-2_2","volume-title":"Column generation, chapter 2","author":"S Irnich","year":"2005","unstructured":"Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon M (eds) Column generation, chapter 2. Springer, Berlin, pp 33\u201365"},{"key":"628_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin"},{"key":"628_CR23","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.tcs.2015.08.005","volume":"602","author":"B LeCun","year":"2015","unstructured":"LeCun B, Mautor T, Quessette F, Weisser M-A (2015) Bin packing with fragmentable items: presentation and approximations. Theor Comput Sci 602:50\u201359","journal-title":"Theor Comput Sci"},{"issue":"1\u20133","key":"628_CR24","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/S0166-218X(01)00347-X","volume":"123","author":"A Lodi","year":"2002","unstructured":"Lodi A, Martello S, Vigo D (2002) Recent advances on two-dimensional bin packing problems. Discrete Appl Math 123(1\u20133):379\u2013396","journal-title":"Discrete Appl Math"},{"issue":"6","key":"628_CR25","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1287\/opre.1050.0234","volume":"53","author":"M L\u00fcbbecke","year":"2005","unstructured":"L\u00fcbbecke M, Desrosiers J (2005) Selected topics in column generation. Oper Res 53(6):1007\u20131023","journal-title":"Oper Res"},{"issue":"3","key":"628_CR26","doi-asserted-by":"publisher","first-page":"874","DOI":"10.1016\/j.ejor.2018.09.020","volume":"273","author":"E Malaguti","year":"2019","unstructured":"Malaguti E, Monaci M, Paronuzzi P, Pferschy U (2019) Integer optimization with penalized fractional values: the Knapsack case. Eur J Oper Res 273(3):874\u2013888","journal-title":"Eur J Oper Res"},{"issue":"11","key":"628_CR27","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0898-1221(98)00087-X","volume":"35","author":"CA Mandal","year":"1998","unstructured":"Mandal CA, Chakrabarti PP, Ghose S (1998) Complexity of fragmentable object bin packing and an application. Comput Math Appl 35(11):91\u201397","journal-title":"Comput Math Appl"},{"key":"628_CR28","unstructured":"Martello S, Toth P (1990) Bin-packing problem. In: Knapsack problems: algorithms and computer implementations, Wiley series in discrete mathematics and optimization. Wiley, pp 221\u2013245"},{"issue":"5","key":"628_CR29","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1287\/opre.51.5.826.16757","volume":"51","author":"S Martello","year":"2003","unstructured":"Martello S, Toth P (2003) An exact algorithm for the two-constraint 0\u20131 knapsack problem. Oper Res 51(5):826\u2013835","journal-title":"Oper Res"},{"issue":"2","key":"628_CR30","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00291-014-0386-3","volume":"37","author":"H Pollaris","year":"2014","unstructured":"Pollaris H, Braekers K, Caris A, Janssens GK, Limbourg S (2014) Vehicle routing problems with loading constraints: state-of-the-art and future directions. OR Spectrum 37(2):297\u2013330","journal-title":"OR Spectrum"},{"issue":"1","key":"628_CR31","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0305-0548(94)90059-0","volume":"21","author":"FC Spieksma","year":"1994","unstructured":"Spieksma FC (1994) A branch-and-bound algorithm for the two-dimensional vector packing problem. Comput Oper Res 21(1):19\u201325","journal-title":"Comput Oper Res"},{"key":"628_CR32","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1023\/A:1018952112615","volume":"86","author":"JM Val\u00e9rio de Carvalho","year":"1999","unstructured":"Val\u00e9rio de Carvalho JM (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Ann Oper Res 86:629\u2013659","journal-title":"Ann Oper Res"},{"issue":"2","key":"628_CR33","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1287\/ijoc.1030.0060","volume":"17","author":"JM Val\u00e9rio de Carvalho","year":"2005","unstructured":"Val\u00e9rio de Carvalho JM (2005) Using extra dual cuts to accelerate column generation. INFORMS J Comput 17(2):175\u2013182","journal-title":"INFORMS J Comput"},{"issue":"3","key":"628_CR34","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s101070050105","volume":"86","author":"F Vanderbeck","year":"1999","unstructured":"Vanderbeck F (1999) Computational study of a column generation algorithm for bin packing and cutting stock problems. Math Program 86(3):565\u2013594","journal-title":"Math Program"},{"issue":"1","key":"628_CR35","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.ejor.2019.08.024","volume":"281","author":"L Wei","year":"2020","unstructured":"Wei L, Lai M, Lim A, Hu Q (2020a) A branch-and-price algorithm for the two-dimensional vector packing problem. Eur J Oper Res 281(1):25\u201335","journal-title":"Eur J Oper Res"},{"issue":"2","key":"628_CR36","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1287\/ijoc.2018.0867","volume":"32","author":"L Wei","year":"2020","unstructured":"Wei L, Luo Z, Baldacci R, Lim A (2020b) A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS J Comput 32(2):428\u2013443","journal-title":"INFORMS J Comput"}],"container-title":["OR Spectrum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-021-00628-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00291-021-00628-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-021-00628-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T08:21:21Z","timestamp":1653294081000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00291-021-00628-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,17]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["628"],"URL":"https:\/\/doi.org\/10.1007\/s00291-021-00628-x","relation":{},"ISSN":["0171-6468","1436-6304"],"issn-type":[{"value":"0171-6468","type":"print"},{"value":"1436-6304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,17]]},"assertion":[{"value":"14 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}