A Branch-and-Repair Method for Three-Dimensional Bin Selection and Packing in E-Commerce

References

• Allen S, Burke E, Mareček J (2012) A space-indexed formulation of packing boxes into a larger box. Oper. Res. Lett. 40(1):20–24.Crossref, Google Scholar
• Alonso M, Alvarez-Valdes R, Parreño F, Tamarit J (2016) Determining the best shipper sizes for sending products to customers. Internat. Trans. Oper. Res. 23(1–2):265–285.Crossref, Google Scholar
• Amazon (2022) Improving packaging. Accessed March 29, 2022, https://www.aboutamazon.com/planet/improving-packaging.Google Scholar
• Baena D, Castro J, Frangioni A (2020) Stabilized Benders methods for large-scale combinatorial optimization, with application to data privacy. Management Sci. 66(7):3051–3068.Link, Google Scholar
• Belov G, Rohling H (2013) LP bounds in an interval-graph algorithm for orthogonal-packing feasibility. Oper. Res. 61(2):483–497.Link, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Benjaafar S, Kim JS, Vishwanadham N (2004) On the effect of product variety in production-inventory systems. Ann. Oper. Res. 126(1):71–101.Crossref, Google Scholar
• Biggs K (2020) Sustainability in e-commerce: How can online retailers make their business greener? parcelLab Insights Blog (March 25), https://parcellab.com/e-commerce/sustainability-online-retail/.Google Scholar
• Birge JR, Louveaux FV (1988) A multicut algorithm for two-stage stochastic linear programs. Eur. J. Oper. Res. 34(3):384–392.Crossref, Google Scholar
• Box Dimensions (2019) Amazon box sizes. Accessed September 27, 2019, https://www.boxdimensions.com/.Google Scholar
• Brinker J, Gündüz HI (2016) Optimization of demand-related packaging sizes using a p-median approach. Internat. J. Adv. Manufacturing Tech. 87(5):2259–2268.Crossref, Google Scholar
• Castro PM, Oliveira JF (2011) Scheduling inspired models for two-dimensional packing problems. Eur. J. Oper. Res. 215(1):45–56.Crossref, Google Scholar
• Chen C, Lee S, Shen Q (1995) An analytical model for the container loading problem. Eur. J. Oper. Res. 80(1):68–76.Crossref, Google Scholar
• Codato G, Fischetti M (2006) Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54(4):756–766.Link, Google Scholar
• Crainic TG, Montreuil B (2016) Physical internet enabled hyperconnected city logistics. Transportation Res. Procedia 12:383–398.Crossref, Google Scholar
• Côté JF, Dell’Amico M, Iori M (2014) Combinatorial Benders’ cuts for the strip packing problem. Oper. Res. 62(3):643–661.Link, Google Scholar
• Côté JF, Haouari M, Iori M (2021) Combinatorial Benders decomposition for the two-dimensional bin packing problem. INFORMS J. Comput. 33(3):963–978.Link, Google Scholar
• 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–20.Crossref, Google Scholar
• Delorme M, Iori M, Martello S (2017) Logic based Benders’ decomposition for orthogonal stock cutting problems. Comput. Oper. Res. 78:290–298.Crossref, Google Scholar
• DHL (2022) Artificial intelligence saves costs and emissions by optimizing packaging of shipments for dhl supply chain customers. Press release, Deutsche Post DHL Group (April 13), https://www.dpdhl.com/en/media-relations/press-releases/2022/artificial-intelligence-optimizing-packaging-for-dhl-supply-chain-customers.html.Google Scholar
• Dowsland KA, Soubeiga E, Burke E (2007) A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation. Eur. J. Oper. Res. 179(3):759–774.Crossref, Google Scholar
• Emadikhiav M, Bergman D, Day R (2020) Consistent routing and scheduling with simultaneous pickups and deliveries. Production Oper. Management 29(8):1937–1955.Crossref, Google Scholar
• Esser K, Kurte J (2020) KEP-Studie 2019—Analyse des Marktes in Deutschland. Technical report, BIEK, Berlin.Google Scholar
• FedEx (2019) Service guide. Technical report, https://www.fedex.com/content/dam/fedex/us-united-states/services/Service_Guide_2019.pdf.Google Scholar
• Fekete SP, Schepers J (2004a) A combinatorial characterization of higher-dimensional orthogonal packing. Math. Oper. Res. 29(2):353–368.Link, Google Scholar
• Fekete SP, Schepers J (2004b) A general framework for bounds for higher-dimensional orthogonal packing problems. Math. Methods Oper. Res. 60(2):311–329.Crossref, Google Scholar
• Fekete SP, Schepers J, van der Veen JC (2007) An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. 55(3):569–587.Link, Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2017) Redesigning Benders decomposition for large-scale facility location. Management Sci. 63(7):2146–2162.Link, Google Scholar
• Freichel SL, Wollenburg J, Wörtge JK (2020) The role of packaging in omni-channel fashion retail supply chains–how can packaging contribute to logistics efficiency? Logist. Res. 13(1), https://doi.org/10.23773/2020_01.Google Scholar
• Hooker JN (2007) Planning and scheduling by logic-based Benders decomposition. Oper. Res. 55(3):588–602.Link, Google Scholar
• Hooker JN, Ottosson G (2003) Logic-based Benders decomposition. Math. Programming 96(1):33–60.Crossref, Google Scholar
• Hübner A, Holzapfel A, Kuhn H (2015) Operations management in multi-channel retailing: an exploratory study. Oper. Management Res. 8(3):84–100.Crossref, Google Scholar
• Iori M, de Lima VL, Martello S, Miyazawa FK, Monaci M (2021) Exact solution techniques for two-dimensional cutting and packing. Eur. J. Oper. Res. 289(2):399–415.Crossref, Google Scholar
• Living Packets (2020) THE BOX. https://www.livingpackets.com/.Google Scholar
• Martello S, Pisinger D, Vigo D (2000) The three-dimensional bin packing problem. Oper. Res. 48(2):256–267.Link, Google Scholar
• Mirchandani PB, Francis RL, eds. (1990) Discrete Location Theory (Wiley, New York).Google Scholar
• Montreuil B, Ballot E, Tremblay W (2014) Modular design of physical internet transport, handling and packaging containers. Proc. 13th Internat. Material Handling Res. Colloquium, https://digitalcommons.georgiasouthern.edu/pmhr_2014/1.Google Scholar
• Murawski C, Bossaerts P (2016) How humans solve complex problems: The case of the knapsack problem. Sci. Rep. 6(1):34851.Crossref, Google Scholar
• Olist (2019) Brazilian e-commerce public data set by Olist. Accessed October 2, 2019, https://www.kaggle.com/olistbr/brazilian-ecommerce.Google Scholar
• Paquay C, Limbourg S, Schyns M (2018) A tailored two-phase constructive heuristic for the three-dimensional multiple bin size bin packing problem with transportation constraints. Eur. J. Oper. Res. 267(1):52–64.Crossref, Google Scholar
• Paquay C, Schyns M, Limbourg S (2016) A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application. Internat. Trans. Oper. Res. 23(1-2):187–213.Crossref, Google Scholar
• Pitney Bowes (2019) Pitney Bowes parcel shipping index. https://www.pitneybowes.com/us/shipping-index.html.Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801–817.Crossref, Google Scholar
• Rahmaniani R, Ahmed S, Crainic TG, Gendreau M, Rei W (2020) The Benders dual decomposition method. Oper. Res. 68(3):878–895.Link, Google Scholar
• Thonemann UW, Brandeau ML (2000) Optimal commonality in component design. Oper. Res. 48(1):1–19.Link, Google Scholar
• Thorsteinsson E (2001) Branch-and-check: A hybrid framework integrating mixed integer programming and constraint logic programming. Walsh T, ed. Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin), 16–30.Google Scholar
• UPS (2021) Cube optimization. https://www.ups.com/media/en/CubeOptimizationSalesSheet.pdf.Google Scholar
• Vieira MVC, Ferreira F, Duque JCM, Almeida RMP (2021) On the packing process in a shoe manufacturer. J. Oper. Res. Soc. 72(4):853–864.Crossref, Google Scholar
• Walmart (2022) Walmart Sustainability Hub. https://www.walmartsustainabilityhub.com/.Google Scholar
• Wang K, Jacquillat A (2020) A stochastic integer programming approach to air traffic scheduling and operations. Oper. Res. 68(5):1375–1402.Link, Google Scholar
• Wäscher G, Haußner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183(3):1109–1130.Crossref, Google Scholar
• Westerheide C (2019) Amazon-Chef Kleber: Die letzte Meile schreit nach Innovation. Deutsche Verkehrs-Zeitung, https://www.dvz.de/rubriken/land/kep/detail/news/amazon-chef-kleber-die-letzte-meile-schreit-nach-innovation.html.Google Scholar
• Wu Y, Li W, Goh M, de Souza R (2010) Three-dimensional bin packing problem with variable bin height. Eur. J. Oper. Res. 202(2):347–355.Crossref, Google Scholar
• Zeighami V, Soumis F (2019) Combining Benders’ decomposition and column generation for integrated crew pairing and personalized crew assignment problems. Transportation Sci. 53(5):1479–1499.Link, Google Scholar
• Zhao X, Bennell JA, Bektaş T, Dowsland K (2016) A comparative review of 3D container loading algorithms. Internat. Trans. Oper. Res. 23(1–2):287–320.Crossref, Google Scholar