The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Optimization in Industry

Next ►
►

At the end of module 5 we said we were done sharpening tools and ready to head out into the world. This lesson is the first outing: we are going to see where optimization lives in real industry — logistics, manufacturing, energy, workforce planning — and, above all, we are going to solve "a day in Rutalia's operations" end to end by chaining together pieces you already built: the clustering from 05-05, the Hungarian algorithm from 03-06 and the TSP from module 2, to which we will add one new, lightweight technique (the 2-opt improvement). The goal is no longer to understand an algorithm, but something harder and more valuable: modeling — translating a business problem into the right algorithms, choosing between alternatives, and measuring the improvement at every step.

Contents

  1. The map of industrial optimization
  2. The central case: a day in Rutalia's operations
  3. Step 1 — Grouping orders into delivery zones (clustering)
  4. Step 2 — Assigning couriers to zones (Hungarian algorithm)
  5. Step 3 — Sequencing the stops within each zone (TSP + 2-opt)
  6. Measuring the improvement: the full pipeline with metrics
  7. Beyond the case: shifts as LP, and the VRP as the real-world generalization
  8. The engineering lesson: "good enough today"

The map of industrial optimization

Industrial optimization is not an algorithm: it is a modeling discipline. In every sector the business problem sounds different, but underneath there is almost always a canonical problem you already know from this course:

Domain Business problem Canonical problem Algorithm from the course
Logistics In what order do I visit my stops? TSP / VRP DP and B&B (02-02, 02-03), genetic algorithms (02-04), ant colony (02-05)
Logistics How do I fill vans without wasting space? Bin packing FFD and greedy methods (02-02)
Manufacturing What product mix do I make with limited resources? Linear programming Simplex with scipy.linprog (02-01)
Manufacturing In what order do jobs go through the machines? Scheduling (job shop) Greedy, backtracking, B&B (02-02, 02-03)
Energy Which plants do I switch on each hour? Unit commitment (ILP) Integer LP (02-01) + heuristics (02-04)
Energy / telecom What minimal network connects all the nodes? Minimum spanning tree Kruskal/Prim (03-04)
Workforce How many people per shift and who covers each task? Coverage / assignment LP/ILP (02-01), Hungarian (03-06)
Transport How much flow can my network carry and where is the bottleneck? Max flow / min cut Edmonds-Karp (03-05)

Notice the pattern: the hard column is not the last one (you already have the algorithms), but the third. Recognizing the canonical problem inside the business problem is 80% of the job. An optimization specialist spends more time asking "which constraints are truly hard and which are negotiable?" than programming.

flowchart LR
    A[Business problem] --> B[Modeling:<br>variables, constraints, objective]
    B --> C[Canonical problem<br>recognized]
    C --> D[Exact algorithm<br>if the size allows it]
    C --> E[Heuristic / metaheuristic<br>if not]
    D --> F[Measure against the<br>current situation]
    E --> F
    F -->|no improvement or breaks constraints| B

That loop back (measure → remodel) is what separates real optimization from textbook exercises: the first model almost never captures all the constraints the business took for granted.

The central case: a day in Rutalia's operations

The situation: it is 7:00 a.m. and Rutalia has 60 orders pending for today, scattered across the city, and 4 couriers available, each with different knowledge of each part of the city. The current operation — the one we want to beat — is artisanal: a coordinator hands out orders "by eye" in order of arrival and each courier improvises their route.

The algorithmic plan chains three decisions, each with its own algorithm:

  1. Which orders go together? → k-means clustering (05-05) with k = 4 zones.
  2. Which courier takes each zone? → optimal assignment with the Hungarian algorithm (03-06).
  3. In what order does each courier visit their stops? → heuristic TSP: nearest neighbor (02-02) + 2-opt improvement (new in this lesson).

Each step reduces total cost, and we will measure it. First, the fictional data (coordinates in km on the city grid we have used since 01-03):

import random
import math

random.seed(42)

# 60 orders: id and coordinates (km) in a 10x10 city.
# We generate them around 4 demand hotspots, like the zone
# profiles we discovered with clustering in 05-05.
hotspots = [(2, 2), (8, 3), (3, 8), (7.5, 7.5)]
orders = []
for i in range(60):
    fx, fy = hotspots[i % 4]
    orders.append({
        "id": f"P-{i+1:03d}",
        "x": fx + random.gauss(0, 1.0),
        "y": fy + random.gauss(0, 1.0),
    })

DEPOT = (5.0, 5.0)   # central warehouse, playing the role of DEP in the 02-02 TSP

def dist(a, b):
    return math.hypot(a[0] - b[0], a[1] - b[1])

The business metric will be total kilometers driven (all couriers: leaving the depot, all their stops, and back). Fewer kilometers = less fuel, fewer hours and more deliveries per day.

The baseline. To know whether we improved, we need an honest point of comparison: we simulate the "by eye" operation by splitting the orders into 4 blocks in order of arrival (no geographic criterion) and visiting them in that same order.

def route_cost(stops):
    """Km of a route DEPOT -> stops in order -> DEPOT."""
    if not stops:
        return 0.0
    points = [DEPOT] + [(p["x"], p["y"]) for p in stops] + [DEPOT]
    return sum(dist(points[i], points[i + 1]) for i in range(len(points) - 1))

# Baseline: 4 blocks of 15 orders in order of arrival
blocks = [orders[i::4] for i in range(4)]
baseline = sum(route_cost(b) for b in blocks)
print(f"Baseline (by-eye dispatch): {baseline:.1f} km")

With the fixed seed, the baseline comes out around 330 km. Everything we do from here on is compared against that number.

Step 1 — Grouping orders into delivery zones (clustering)

In 05-05 you implemented k-means and k-means++ from scratch; here we use it as a building block, without re-explaining its mechanics. The modeling decision is a different one: why clustering and not, say, an even split of 15 orders per head?

  • Because the dominant cost of delivery is the travel between orders: nearby orders should go together.
  • Because k-means minimizes exactly that: within-group dispersion.
  • The price: the groups can come out unbalanced (18 orders in one zone, 11 in another). At Rutalia we accept that today; if it were unacceptable, we would need a model with a capacity constraint (we come back to this when we discuss the VRP).
def kmeans(points, k, iters=100):
    """Classic k-means (seen in 05-05), compact version."""
    centroids = random.sample(points, k)
    for _ in range(iters):
        groups = [[] for _ in range(k)]
        for p in points:
            j = min(range(k), key=lambda c: dist(p, centroids[c]))
            groups[j].append(p)
        updated = [
            (sum(p[0] for p in g) / len(g), sum(p[1] for p in g) / len(g))
            if g else centroids[j]
            for j, g in enumerate(groups)
        ]
        if updated == centroids:
            break
        centroids = updated
    return centroids

coords = [(p["x"], p["y"]) for p in orders]
centroids = kmeans(coords, k=4)

# Rebuild the zones as lists of orders
zones = [[] for _ in range(4)]
for p in orders:
    j = min(range(4), key=lambda c: dist((p["x"], p["y"]), centroids[c]))
    zones[j].append(p)

step1 = sum(route_cost(z) for z in zones)
print(f"After clustering (routes still unordered): {step1:.1f} km")
for j, z in enumerate(zones):
    print(f"  Zone {j}: {len(z)} orders, centroid ({centroids[j][0]:.1f}, {centroids[j][1]:.1f})")

Just by grouping well — without having ordered a single route yet — the total typically drops to about 210 km: no courier crosses the entire city anymore. First modeling lesson: the higher-level decision (what goes with what) usually moves the needle more than the fine-grained optimization that follows.

Step 2 — Assigning couriers to zones (Hungarian algorithm)

We have 4 zones and 4 couriers, but they are not interchangeable: each courier knows some parts of the city better (less time wasted, fewer incidents). We model that knowledge as a courier × zone cost matrix (estimated extra minutes per day) and solve the optimal assignment with the Hungarian method you already used via scipy in 03-06.

import numpy as np
from scipy.optimize import linear_sum_assignment

couriers = ["R-01", "R-02", "R-03", "R-04"]
# cost[i][j]: estimated extra minutes if courier i works zone j.
# Fictional data: in practice they would come from the delivery
# history per zone, using the regression models from 05-03.
cost = np.array([
    [12, 35, 28, 40],
    [30, 10, 33, 25],
    [27, 32, 11, 30],
    [38, 24, 29,  9],
])

rows, cols = linear_sum_assignment(cost)
total = cost[rows, cols].sum()
worst = sum(cost[i].max() for i in range(4))  # worst possible assignment, for reference
for i, j in zip(rows, cols):
    print(f"{couriers[i]} -> Zone {j} ({cost[i][j]} min extra)")
print(f"Cost of the optimal assignment: {total} min (worst possible: {worst} min)")

Here the matrix is friendly and the optimum (42 min) can be spotted at a glance, but that is precisely the point: with 4×4 you can eyeball it; with 40 couriers and 40 zones you cannot, and the Hungarian algorithm still hands you the exact optimum in O(n³). Also notice where the numbers in the matrix come from: estimates over the history — the optimization in this module consumes the predictions of module 5. The modules were never watertight compartments: they were layers.

Step 3 — Sequencing the stops within each zone (TSP + 2-opt)

Each zone has ~15 stops plus the depot. In 02-02 you saw that the exact DP solution to the TSP (Held-Karp) is O(2ⁿ·n²): with 15 stops it is still feasible but slow, and with 25 it is impossible. The standard industrial recipe for medium sizes is humbler and very effective: build a quick route with nearest neighbor (the greedy method from 02-02, counterexample included) and improve it with 2-opt.

2-opt, the new technique of this lesson. The idea fits in one sentence: if the route crosses over itself, uncrossing it always shortens it. Formally: take two edges of the route, (a→b) and (c→d), remove them and reconnect as (a→c) and (b→d), reversing the segment between b and c. If the sum of the two new edges is smaller than that of the old ones, the route improves. Repeat until no swap improves anything (a local optimum).

flowchart LR
    subgraph Before[Before: the route crosses itself]
        A1((a)) --> B1((b))
        B1 -. segment .-> C1((c))
        C1 --> D1((d))
    end
    subgraph After[After the 2-opt swap]
        A2((a)) --> C2((c))
        C2 -. reversed segment .-> B2((b))
        B2 --> D2((d))
    end
    Before --> After
def nearest_neighbor(stops, origin=DEPOT):
    """Greedy construction: always go to the closest stop (02-02)."""
    remaining = stops[:]
    route, current = [], origin
    while remaining:
        nearest = min(remaining, key=lambda p: dist(current, (p["x"], p["y"])))
        remaining.remove(nearest)
        route.append(nearest)
        current = (nearest["x"], nearest["y"])
    return route

def two_opt(route):
    """Uncross the route until reaching a 2-opt local optimum."""
    def pts(r):
        return [DEPOT] + [(p["x"], p["y"]) for p in r] + [DEPOT]
    improved = True
    while improved:
        improved = False
        P = pts(route)
        for i in range(len(route) - 1):
            for j in range(i + 1, len(route)):
                # current edges: P[i]->P[i+1] and P[j+1]->P[j+2]
                before = dist(P[i], P[i + 1]) + dist(P[j + 1], P[j + 2])
                after = dist(P[i], P[j + 1]) + dist(P[i + 1], P[j + 2])
                if after < before - 1e-9:
                    route[i:j + 1] = reversed(route[i:j + 1])  # reverse the segment
                    P = pts(route)
                    improved = True
    return route

total_nn, total_2opt = 0.0, 0.0
for j, zone in enumerate(zones):
    route = nearest_neighbor(zone)
    km_nn = route_cost(route)
    route = two_opt(route)
    km_2opt = route_cost(route)
    total_nn += km_nn
    total_2opt += km_2opt
    print(f"Zone {j}: nearest neighbor {km_nn:.1f} km -> 2-opt {km_2opt:.1f} km")
print(f"Total NN: {total_nn:.1f} km | Total after 2-opt: {total_2opt:.1f} km")

Details that matter when reading the code:

  • The condition after < before - 1e-9 prevents infinite loops caused by floating-point rounding errors: we only accept strict improvements.
  • Each pass evaluates O(n²) swaps; with 15 stops it is instantaneous. With hundreds of stops, 2-opt still works but it pays to speed it up (near-neighbor lists) or scale up to metaheuristics: genetic algorithms (02-04) and ant colony optimization (02-05) are exactly the natural evolution when 2-opt gets stuck in a poor local optimum or the instance grows.
  • 2-opt yields a local optimum, not a global one — the same limitation you saw in k-means (05-05) and in gradient descent (05-03). It is a recurring theme of the course: almost all practical optimization is "local improvement + knowing when to settle".

Measuring the improvement: the full pipeline with metrics

Let us recap Rutalia's day in numbers (yours will vary somewhat with a different seed; the order of magnitude is what stays stable):

Stage Algorithm Lesson Total km Cumulative improvement
"By eye" baseline — — ~330 —
Coherent zones k-means 05-05 ~210 ~36%
Routes built Nearest neighbor 02-02 ~105 ~68%
Routes polished 2-opt 06-01 ~92 ~72%
Courier ↔ zone Hungarian 03-06 42 min extra (vs 141 in the worst case) (metric in minutes)

Three engineering observations:

  • Each layer is measured on its own. If tomorrow the business asks "what happens if I drop 2-opt to simplify?", the answer is a number (~13 km/day), not an opinion.
  • The marginal gain shrinks. Clustering saved ~120 km; 2-opt, ~13. That curve tells you where to invest the next unit of effort.
  • An honest baseline is sacred. Comparing against an artificially bad baseline inflates the improvement and destroys the project's credibility. It is the operational equivalent of the accuracy trap from 05-02.

Beyond the case: shifts as LP, and the VRP as the real-world generalization

Shift planning. The other great industrial classic is modeled with the linear programming of 02-01. Minimal example: Rutalia needs to cover a demand for couriers per slot (morning 6, midday 10, afternoon 8, night 3) with 8-hour shifts that cover two consecutive slots (the night shift wraps around into the morning). Variables: how many people start in each slot; objective: minimize headcount; constraints: every slot covered.

from scipy.optimize import linprog

# x[i] = people starting their shift in slot i (they cover slots i and i+1)
demand = [6, 10, 8, 3]
# Coverage of slot f: x[f-1] + x[f] >= demand[f]
# linprog minimizes with A_ub @ x <= b_ub, so we negate both sides.
A_ub = [
    [-1,  0,  0, -1],   # slot 0: covered by x0 and x3 (the wrap-around night shift)
    [-1, -1,  0,  0],   # slot 1: x0 and x1
    [ 0, -1, -1,  0],   # slot 2: x1 and x2
    [ 0,  0, -1, -1],   # slot 3: x2 and x3
]
b_ub = [-d for d in demand]
res = linprog(c=[1, 1, 1, 1], A_ub=A_ub, b_ub=b_ub,
              bounds=[(0, None)] * 4, integrality=[1, 1, 1, 1])
print("Starts per slot:", res.x, "| minimum headcount:", res.fun)

The integrality parameter asks for integer solutions (you cannot hire 2.5 couriers): this is the integer LP that in 02-01 we saw blows up the theoretical complexity, yet modern solvers handle it without breaking a sweat at these sizes.

The VRP. Our pipeline (clustering + TSP per zone) is in fact a classic heuristic — cluster first, route second — for the Vehicle Routing Problem, the industrial generalization of the TSP. The VRP adds what the TSP ignores: capacity of each vehicle (weight, volume), delivery time windows ("between 9:00 and 11:00"), heterogeneous fleets, multiple passes through the depot. It is NP-hard with aggravating factors, and in practice almost nobody solves it from scratch: specialized solvers like Google OR-Tools (free and ubiquitous in logistics) are used, which internally combine greedy construction, 2-opt/3-opt-style local search and metaheuristics — exactly the families you have learned. Knowing what is inside the box is what lets you configure it well and spot when its answer does not make sense.

The engineering lesson: "good enough today"

In 02-02 we computed the exact optimum of the 9-stop TSP (35.22 km) because the size allowed it. Today, with 60 orders and the vans leaving at 8:00, the right question is not "what is the optimum?" but "how much improvement can I fit in before 8:00?". The golden rule of industrial optimization:

A solution 5% worse than the optimum, available on time, is worth infinitely more than the optimum that arrives late. The optimum is the measuring stick, not always the goal.

And a warning that is not rhetorical: the outputs of these models are recommendations. Before applying them to a real operation (routes, shifts, assignments of people) they must be validated by those who know the ground and the business's obligations — labor regulations, traffic restrictions, customer commitments — because the model only optimizes what was put into the objective function, and reality always has constraints that nobody wrote down. The final decision is human.

Common Mistakes and Tips

  • Optimizing without a baseline. If you do not measure the current situation with the same metric, you cannot claim you improved anything. It is the number-one mistake in real projects.
  • Confusing the model's optimum with the business's optimum. The model minimizes kilometers; the business may care more about punctuality. Ask what is really being optimized before writing the objective function.
  • Applying 2-opt without a numerical tolerance. Accepting "improvements" of size 1e-15 causes infinite loops due to rounding. Always use after < before - epsilon.
  • Chaining stages without checking the coupling. Cluster first, route second is a heuristic: an optimal clustering can induce mediocre routes. If the overall result disappoints, try varying k or moving border orders between zones and re-routing.
  • Reinventing the VRP. For problems with capacities and time windows, evaluate OR-Tools or another solver before writing your own: your value lies in the modeling and the validation, not in reimplementing mature local search.
  • Tip: fix the random seeds (random.seed) in your experiments. Without reproducibility there is no fair comparison between variants.

Exercises

  1. Sensitivity to the number of zones. Run the full pipeline with k = 3, 4, 5 and 6 zones (with the matching number of couriers) and build the table k → total km after 2-opt. Does the total keep dropping as k grows? What hidden cost of increasing k do the kilometers not reflect?
  2. The fooled greedy, revisited. Build a zone of 12 stops where nearest neighbor produces a route at least 15% worse than the one obtained after applying 2-opt (hint: remember the greedy counterexample from 02-02 — stops almost in a line with a trap near the origin). Verify it with route_cost.
  3. Shifts with a cap. Extend the shift model to 6 slots of 4 hours with demand [4, 6, 10, 9, 7, 3], shifts covering two consecutive slots (the slot-5 shift wraps around into slot 0), and the extra constraint that no slot may have more than 12 people active. Solve it with linprog and integrality.

Solutions

  1. With the hotspots from the example, k=4 matches the real structure of the demand and gives the best balance; k=5 and k=6 barely reduce kilometers (sometimes they even increase them, because more zones mean more depot↔zone trips) and add the hidden cost of one more courier and one more vehicle per zone. The km-vs-k curve has an elbow shape — exactly the elbow method you used to choose k in 05-05: the same statistical criterion turns out to be a business criterion.
  2. A pattern that works: depot at (0,0), a "bait" stop at (0.5, 0.1) and the rest almost collinear at x = 1..10 (y≈0), with a final stop at (10, 3). Nearest neighbor takes the bait, walks the line, and the return crosses the whole city; it also tends to zigzag between nearly equidistant stops. 2-opt uncrosses those returns. Measuring with route_cost, the improvement comfortably exceeds 15%. The moral from 02-02 holds: greedy is a good builder, not a good finisher.
  3. With circular coverage, the demand constraint for slot f is x[(f-1) % 6] + x[f] >= demand[f] (rows with -1 in those two positions and b_ub = -demand[f]), and the cap constraint is the same pair with positive sign and b_ub = 12. That is 12 rows in total. With the given demand, the minimum feasible integer solution comes out around 20 people; check in the solution that the slot with demand 10 is covered almost exactly and that no slot exceeds 12 — when a cap constraint and a demand constraint squeeze at the same time, the solver "pushes" shift starts toward valley slots.

Conclusion

You have seen the catalog of industrial optimization and solved a full day at Rutalia by chaining three algorithms from three different modules: clustering (05-05) to decide what goes together, the Hungarian algorithm (03-06) to decide who does what, and nearest neighbor + 2-opt (02-02 and this lesson) to decide in what order — with a metric measuring every link and a total improvement of close to 70% over the artisanal operation. The ideas to take with you: recognizing the canonical problem is 80% of the job, high-level decisions move the needle more than fine polishing, and "good enough on time" beats the late optimum. In the next lesson we change domain but not method: social networks as graphs, where the BFS, the components and the clustering you already master become community detection, influence measurement — with PageRank as the star case — and friend recommendation.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved