Family 8 · OR Problem Family
Integrated Structural
Problems whose formulation structurally requires the simultaneous modeling of two or more problem families — solving sub-problems independently does not yield optimal solutions.
Problem Collection
Three integrated optimization problems combining location, routing, inventory, and scheduling
Inventory-Routing Problem
The Inventory-Routing Problem jointly optimizes inventory replenishment decisions (when and how much to deliver) and vehicle routing decisions (which customers to visit on each route) over a multi-period planning horizon. A depot with unlimited supply serves n customers, each with deterministic per-period demand, holding cost, and storage capacity. K homogeneous vehicles with capacity Q deliver goods across T discrete periods. The objective minimizes total routing cost plus holding cost. NP-hard because it generalizes both the VRP and multi-period lot-sizing.
s.t.
(1) Iit = Ii,t−1 + qit − di inventory balance
(2) 0 ≤ Iit ≤ Ui no stockout + storage capacity
(3) qit ≤ Ui · ∑k yikt deliver only if visited
(4) ∑i qit · yikt ≤ Q vehicle capacity
(5) ∑k yikt ≤ 1 at most one visit per period
(6) flow conservation + subtour elimination
| Algorithm | Type | Complexity | Details |
|---|---|---|---|
| Greedy IRP | Heuristic | O(T · n²) | Period-by-period urgency-based insertion. Visits customers closest to stockout first, builds routes via nearest-neighbor |
| Greedy Fill-Up | Heuristic | O(T · n²) | Baseline heuristic: visit all customers every period and fill to storage capacity. Simple but provides feasibility guarantee |
| Simulated Annealing | O(iter · T · n) | Reassign/swap/2-opt neighborhoods across periods. Warm-started with greedy IRP. Geometric cooling with Boltzmann acceptance |
Location-Routing Problem
The Location-Routing Problem jointly optimizes facility (depot) location decisions and vehicle routing decisions. Given m candidate depot locations with fixed opening costs and capacities, n customers with demands, and a fleet of capacitated vehicles, the goal is to select which depots to open, assign customers to open depots, and design vehicle routes from each depot to serve its assigned customers. Solving location and routing sequentially does not guarantee global optimality, making the integrated approach essential. NP-hard because it generalizes both the Uncapacitated Facility Location Problem and the Capacitated Vehicle Routing Problem.
s.t.
(1) ∑j∈J zij = 1 each customer assigned once
(2) zij ≤ yj assign only to open depots
(3) ∑i∈I di · zij ≤ Uj depot capacity
(4) route demand ≤ Q vehicle capacity
(5) flow conservation + subtour elimination
(6) yj, zij, xijk ∈ {0, 1}
| Algorithm | Type | Complexity | Details |
|---|---|---|---|
| Sequential Greedy | Heuristic | O(m·n + n²) | Three-phase decomposition: (1) greedy depot opening by efficiency score, (2) nearest-neighbor routing per depot, (3) border customer reassignment for cost reduction |
| Simulated Annealing | O(iter · n) | Four neighborhoods: toggle depot, reassign customer, swap customers between depots, 2-opt intra-route. Warm-started with greedy. Geometric cooling |
Assembly Line Balancing
Assembly Line Balancing is classified as an integrated structural problem because it combines task-to-station assignment (Family 4) with precedence-constrained scheduling (Family 1) under cycle time constraints. SALBP-1 minimizes the number of stations given a fixed cycle time C; SALBP-2 minimizes the cycle time for a given number of stations. Each task has a processing time and a set of predecessors that must be completed before it can start. The primary implementation resides in the scheduling family where it shares infrastructure with other scheduling problems.
s.t.
(1) ∑s xis = 1 ∀ i each task assigned to exactly one station
(2) ∑i ti · xis ≤ C ∀ s cycle time constraint
(3) ∑s s · xis ≤ ∑s s · xjs ∀ (i,j) ∈ Prec precedence constraints
(4) xis ∈ {0, 1}
| Algorithm | Type | Complexity | Details |
|---|---|---|---|
| Ranked Positional Weight (RPW) | Heuristic | O(n²) | Helgeson & Birnie (1961). Assign tasks by decreasing sum of own + successor processing times. Greedy station-filling respects precedence and cycle time |
Primary implementation resides in
Family 1 — Scheduling
(1_scheduling/assembly_line_balancing/)