Box Allocation Optimization in Meal Kit Delivery
Thi Minh Thu Nguyen, Loïc Genest, Alain Zemkoho · 2025
Read Box Allocation Optimization in Meal Kit Delivery by Thi Minh Thu Nguyen, Loïc Genest, Alain Zemkoho (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06157.txt.
Introduction
Which factory should pack which meal kit order? Thi Minh Thu Nguyen and two co-authors formalize that daily puzzle as the Box Allocation Problem in a 2025 paper, set in the United Kingdom's large meal kit market. Assigning orders across plants should minimize day-to-day recipe variation while respecting capacity and eligibility limits over a fifteen-day horizon.
Cast as a mixed-integer linear program, the problem is attacked with the CBC branch-and-cut solver and with heuristics including tabu search and targeted pairwise swaps. On instances up to one hundred thousand orders, CBC consistently finds optimal solutions in under two minutes, even as capacities and orders fluctuate. Steadier recipes improve ingredient forecasting and cut food waste, and the authors offer the first full framework for this allocation problem.
Catalog record
| CREATOR | Thi Minh Thu Nguyen, Loïc Genest, Alain Zemkoho |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06157
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Box Allocation Optimization in Meal Kit Delivery Thi Minh Thu Nguyen, Loïc Genest, Alain Zemkoho Abstract This study introduces the Box Allocation Problem (BAP), a novel optimization challenge in the $1.4 billion UK meal kit delivery market. BAP involves assigning orders across multiple production facilities to minimize daily recipe variations while adhering to capacity and eligibility constraints over a 15-day planning horizon. We formulate BAP as a mixed-integer linear programming (MILP) problem and systematically compare the performance of the COIN-OR Branch and Cut (CBC) solver with heuristic methods, including Tabu Search and Iterative Targeted Pairwise Swap. Scalability experiment on instances with up to 100,000 orders show that CBC consistently achieves optimal solutions in under two minutes, maintaining optimality even under dynamic conditions with fluctuating factory capacities and changing customer orders. By reducing day-to-day recipe discrepancies, this approach supports more accurate ingredient forecasting, decreases food waste, and improves operational efficiency across multi-factory network. These results provide the first comprehensive solution framework for temporal allocation problems in meal kit delivery operations. Keywords: recipe box allocation, meal kit delivery, CBC solver, heuristics, production planning, sustainability, supply chain management Abbreviations: B&B, Branch and Bound; BAP, Box Allocation Problem; BPP, Bin Packing Problem; CBC, COIN-OR Branch and Cut; CVRP, Capacitated Vehicle Routing Problem; ITPS, Iterative Targeted Pairwise Swap; LD, Lead Day; MILP, Mixed-Integer Linear Programming; TS, Tabu Search; WMAPE, Weighted Mean Absolute Percentage Error. 1 Introduction The UK meal kit delivery market has experienced rapid expansion, driven by consumer demand for convenient, nutritious, and personalized meal solutions. Reaching $1.4 billion in revenue by 2024, this sector presents a highly competitive environment where both established food companies and technology-driven startups compete for market share [ 24 ] . Operational excellence in this segment depends heavily on sophisticated supply chain networks capable of coordinating fresh ingredient procurement, inventory management, and time-sensitive distribution across multiple production facilities. The inherent complexity stems from managing perishable goods with short shelf lives, unpredictable demand patterns, and stringent quality requirements – challenges that transform supply chain optimization from a cost consideration into a strategic imperative for survival [ 13 , 4 ] . Companies that fail to achieve operational agility in response to demand volatility and supply disruptions face immediate risks to customer satisfaction, food waste costs, and ultimately, business viability [ 23 ] . Figure 1 : Recipe box [ 27 ] Within this operational landscape emerges the Box Allocation Problem (BAP), a critical optimization challenge that involves strategically distributing recipe boxes (Figure 1 ) across production facilities to minimize day-to-day variations in recipe allocations. BAP seeks to minimize the Weighted Mean Absolute Percentage Error (WMAPE) of daily recipe distributions while satisfying factory capacity constraint and recipe eligibility restriction [ 16 ] . This objective delivers dual operational benefits that directly impact both sustainability and profitability. First, consistent recipe allocations across facilities enable accurate ingredient demand forecasting, reducing over-procurement and food spoilage – a critical advantage given that food waste accounts for approximately 10% of global greenhouse gas emissions [ 26 ] . Second, stabilized allocation patterns ensure reliable ingredient availability across all production sites, minimizing stockouts that can disrupt customer orders and damage brand reputation in this highly competitive market. Despite BAP’s fundamental importance to operational efficiency and environmental sustainability in meal kit delivery, it has received minimal attention in the supply chain optimization literature, representing a significant research gap in network-based production planning. This study addresses the identified research gap by developing a comprehensive mixed-integer linear programming (MILP) formulation of BAP that captures the interplay between facility capacity constraints and recipe eligibility requirements. We systematically benchmark the COIN-OR Branch and Cut (CBC) solver – an exact optimization method – against two established heuristic approaches: Iterative Targeted Pairwise Swap (ITPS) and Tabu Search (TS). These heuristics were selected based on their proven effectiveness in structurally similar combinatorial optimization problems, particularly the Bin Packing Problem (BPP) and Capacitated Vehicle Routing Problem (CVRP), which share BAP’s fundamental characteristics of resource allocation under capacity constraints [ 14 , 15 , 8 ] . TS demonstrates particular strength in escaping local optima through its adaptive memory structure and strategic exploration of large solution spaces [ 19 , 17 ] , while CBC guarantees global optimality through systematic branch-and-bound enumeration combined with sophisticated cut generation and primal heuristics [ 18 , 3 ] . Our experimental design encompasses diverse operational scenarios, ranging from 10,000 to 100,000 orders across static and dynamic conditions, including fluctuating factory capacities and evolving customer demand patterns. This comprehensive evaluation framework enables rigorous assessment of each method’s computational efficiency, solution quality, and adaptability to real-world complexities. Our findings highlight the superior performance of the CBC solver in attaining optimal solutions, even under challenging dynamic conditions. By integrating both theoretical foundations and practical applications of BAP, this study makes a substantial contribution to the supply chain optimization literature while offering actionable insights for meal kit delivery enterprises. It bridges a critical knowledge gap by proposing scalable solutions that enhance operational efficiency and promote environmental sustainability in this rapidly growing segment. The remainder of this paper is structured as follows: Section 2 introduces the characteristics of BAP and presents its mathematical formulation, situating it in relation to two classic optimization problems. Section 3 outlines the optimization methods employed, covering both exact and heuristic approaches. Section 4 reports the results of numerical experiments, comparing the performance of all methods. Finally, Section 5 discusses the implications of the findings, acknowledges limitations, and identifies promising avenues for future research. 2 Problem Statement 2.1 Problem background BAP in meal kit delivery involves assigning recipe boxes, structured as in Figure 2(a) , to multiple factories (Figure 2(b) ). The objective is to minimize daily variations in recipe allocations. For example, if Factory 1 (F1) produced 100 units of Recipe 1 yesterday, the optimal solution would allocate approximately 100 units today. (a) Box structure [ 16 ] (b) Allocation process [ 16 ] Figure 2 : Recipe box allocation The problem includes two key constraints. First, each factory (except the final simulated factory m ) has a fixed daily production capacity, limiting the number of boxes it can process. To optimize resource use, solutions must fully meet this capacity (Figure 3(a) ). Second, not all factories can produce every recipe, so allocation must follow the eligibility constraint in Figure 3(b) , ensuring recipes are assigned only to capable facilities. (a) Capacity constraint [ 16 ] (b) Eligibility constraint [ 16 ] Figure 3 : Main constraints A key feature of BAP is its temporal dimension, requiring daily allocation of both actual and simulated orders (Figure 4 ). This study uses a 15-day planning horizon from lead day 18 (LD18) to lead day 3 (LD3). The process begins with total demand forecasting, followed by continuous monitoring of actual orders. When real orders fall short of projections, simulated orders are generated to represent expected demand. Initially, both real and simulated orders are distributed across factories ( soft allocation ). As the planning horizon progresses, actual orders replace simulated ones. By LD3, the allocation consists solely of real orders, transitioning to hard allocation , which can no longer be changed. The company then has three days to produce and deliver the boxes.