Packaging Logistics

Resources

• Slides
• Exercise Questions (Solution)

Packaging

Packaging provides product functions (providing quantity), marketing functions (advertising and information), usage functions (additional purposes for the customer), and logistics functions (protection, transport, and storage, manipulation, information).

Tasks for packaging include design (volume, weight, bulkiness, fragility, legal conditions, material), the process (automated packaging) and closed-loop logistics (returnable packaging, disposal).

Packaging is divided into multiple levels:

• Good: The smallest unit. Loose goods, fluids, mass products
• Article: Sales unit. Packaged goods, bags, cans.
• Outer Packaging: Packaging unit. Delivery orders, pallets, boxes.
• Delivery: Transport unit. Pallets, parcels, containers.
• Load: Loading unit; freight.
• Transport: Transport unit. Truck, ship, wagon.

Stowage Planning

The process of optimally arranging cargo in a transport unit (e.g., container, truck, ship) to maximize space utilization, ensure safety, and facilitate efficient standardized loading and unloading. It involves considering weight distribution, fragility of goods, and accessibility for delivery.

Resource Allocation

Knapsack Problem

The knapsack problem is a combinatorial optimization problem where the goal is to maximize the total value of items placed in a bag without exceeding its weight capacity. $N$ items have a value $c_i$ and capacity requirement $a_i$, with a limited capacity of $W$. The boolean decision variable $x_i$ indicates whether item $i$ is included in the knapsack.

Knapsack Model

Decision variables:

• Selection state: $x_i=1$ if object $i$ is chosen, $0$ otherwise

Objective:

• Maximize total value: $\max {\sum }_{i=1}^N{c}_i\cdot x_i$

Constraints:

• Resource capacity: ${\sum }_{i=1}^N{a}_i\cdot x_i\le W$

Bounds:

• Binary restriction: $x_i\in \{0,1\}\forall i\in \{1,\dots ,N\}$

Greedy Approach

To solve the knapsack problem, simply determine a priority for each possible item ($\frac{c_i}{a_i}$) and select items in descending order of priority until the capacity limit is reached. This greedy approach works well for the fractional knapsack problem, where items can be divided, but may not yield an optimal solution for the 0-1 knapsack problem.

Packing

Cutting Stock Problem

The goal is to cut large stock materials (like rolls of paper, metal sheets, or fabric) into smaller pieces to meet specific demand sizes while minimizing waste. For example, from a 210cm roll, supply 200 45cm rolls and 3000 27cm rolls; with a maximum storage for overproduction of 160 cut rolls.

Data: Order data, specification of cutting patterns, storage capacity.
Decision: Cutting pattern and respective quantities.
Objective: Minimize waste or overproduction.
Constraint: Fulfill orders, compliant with technology, storage capacity.

Cutting Stock Model

Decision variables:

• Number of rolls $x_i$ cut according to pattern $i$
• Rest $y_1$ and $y_2$ of the two orders (overproduction)

Objectives:

• Minimize waste: $\min Z_1=21x_1+3x_2+12x_3+21x_4+3x_5$
• Minimize used rolls: $\min Z_2=x_1+x_2+x_3+x_4+x_5$

Constraints:

• Order fulfillment 1: $7x_1+6x_2+4x_3+2x_4+1x_5\ge 3000+y_1$
• Order fulfillment 2: $x_2+2x_3+3x_4+4x_5=200+y_2$
• Storage restriction: $y_1+y_2\le 160$

Bounds:

• Non-negativity: $x_1,x_2,x_3,x_4,x_5,y_1,y_2\ge 0$

Bin Packaging Problem

An optimization problem where the goal is to $N$ items into the least $M$ number of bins, respecting allocation and capacity constraints. Each item $j$ has a size $a_j$, and each bin has a capacity $K$. The boolean decision variable $x_{ij}$ indicates whether item $i$ is in bin $j$, and $y_j$ indicates whether bin $j$ is used.

Bin Packing Model

Decision variables:

• Bin usage: $y_i=1$ if bin $i$ is used, $0$ otherwise
• Item allocation: $x_{ij}=1$ if object $j$ is allocated to container $i$, $0$ otherwise

Objective:

• Minimize required bins: $\min {\sum }_{i=1}^M{y}_i$

Constraints:

• Bin capacity: ${\sum }_{j=1}^N{a}_j{x}_{ij}\le y_{i}K\forall i\in \{1,\dots ,M\}$
• Allocation of all objects: ${\sum }_{i=1}^M{x}_{ij}=1\forall j\in \{1,\dots ,N\}$

Bounds:

• Binary variables: $y_i,x_{ij}\in \{0,1\}\forall i\in \{1,\dots ,M\},j\in \{1,\dots ,N\}$

3D Bin Packing Problem

An extension of the bin packing problem where items and bins are three-dimensional. Each item $j$ has dimensions $(l_j,w_j,h_j)$, and each bin has dimensions $(L,W,H)$.

Priority Rules

Priority rules are simple heuristics that assign a priority to each item or task based on specific attributes, such as size, weight, or value. These rules help in making quick decisions for packing or scheduling problems without the need for complex optimization algorithms.

Presorting objects can drastically improve the performance of these heuristics.

• First Fit Heuristic: For bin packaging, assigns objects to the first bin that has sufficient capacity, or a new one if none are available.
• Best Fit Heuristic: Assigns objects to the bin that will have the least remaining capacity after placement, or a new one if none are available.

Block Heuristics: Layer Plans

A class of geometric algorithms used to design optimal two-dimensional layouts (layer plans) for placing identical items onto a standardized packing space, such as a Euro-pallet. It focuses on maximizing the number of items on a single layer by arranging them into orthogonal blocks with different orientations.

To find the optimal layer plan:

1. Define Block Orientations: Partition the layout area into a set of distinct blocks (often a 3-block division). Items within each individual block share the same orientation (either vertical or horizontal).
2. Generate Efficient Partitions: Determine mathematically feasible combinations of item counts along the length and width for each side of the pallet. A partition is considered efficient when the remaining space is too small to fit another item.
3. Combine and Validate Plans: Combine the side partitions to form all variations of complete layer plans. Ensure the layout is valid by verifying that adjacent blocks share matching boundary lengths at their intersection points.
4. Evaluate Efficiency: Calculate the total number of items ($n_1\cdot m_1+n_2\cdot m_2+n_3\cdot m_3$) for each permitted combination and select the layer plan that maximizes space utilization.