Optimization of Packaging Box Design Using Linear and Genetic Algorithms

Background: The “Aurora Blue” packaging box has become a brand identifier for the DeWu app, but early box dimensions were manually designed, leading to mismatches with product sizes, causing waste, higher shipping costs, and potential damage.

Problem analysis: SKU data from the past year, box size constraints (lower and upper bounds), limit on number of box types (≤15), and coverage requirement (order coverage ≥99%). Exhaustive search over millions of box combinations is infeasible.

Problem simplification: Box count limited to 8‑15, treat the objective as maximizing packing rate (total SKU volume / total box volume). Other constraints are handled outside the model.

Modeling: Define integer variables for box dimensions (length > width > height) and enforce integer sizes. Sample constraints and objective are expressed in Python code:

constraint_ueq = (
    lambda x: x[1] - x[0],
    lambda x: x[2] - x[1],
    lambda x: x[4] - x[3],
    lambda x: x[5] - x[4],
    ...
)

def cal_avg_r_cached(p):
    '''The objective function.'''
    total_r = 0
    for row in npd:
        r = [-1] * box_num
        for i in range(box_num):
            if (row[0] <= p[3*i]) and (row[1] <= p[3*i+1]) and (row[2] <= p[3*i+2]):
                r[i] = row[4] / (p[3*i] * p[3*i+1] * p[3*i+2])
        total_r += max(r) * row[3]
    return -total_r / sum_cnt

Solution methods: Exact methods (linear programming, nonlinear programming, integer programming with branch‑and‑bound) and meta‑heuristics (genetic algorithm). The genetic algorithm workflow includes initialization, fitness evaluation, selection (e.g., 95% probability of choosing top individuals), crossover, mutation, and replication.

if random.random() < 0.95:
    poly_a = random.choice(polygons[:1])
    poly_b = random.choice(polygons[1:5])
else:
    poly_a = random.choice(polygons)
    poly_b = random.choice(polygons)

Results: Several versions were tested; the selected “1203” solution improved packing rate by 5.49%, reduced average paper usage by 7.6%, and lowered average shipping cost by 0.06 CNY.