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

Project Development

Next ►
►

You have a validated specification; now you have to turn it into code without dying in the attempt. The classic self-taught trap is to start with the "interesting" part (the sophisticated algorithm) and leave the glue for last: data loading, evaluation, comparison. The usual result: 25 hours in, there are four brilliant pieces that don't fit together and not a single number to show. In this lesson we will do the opposite, following the tracer bullet technique: first a complete end-to-end pipeline with the dumbest possible solution, then improvements in layers, measuring after each one. We will see it with real code on the Rutalia reference project specified in 07-01; if your project is a different one, the structure, the milestones and the measurement discipline carry over as they are.

Contents

  1. Structuring the Python project
  2. The tracer bullet: milestone 0, the baseline that already works
  3. Improving in layers: milestones 1 to 3 with intermediate measurement
  4. Reproducible experiments: seeds, configuration and results
  5. Serious measurement: predict the cost, then verify it
  6. Minimal tests that earn their keep
  7. When to stop optimizing

Structuring the Python project

Before the first function, create this structure. Separate what changes at different rates: the data is generated once, the algorithms evolve in layers, the evaluation must never be touched (it is the referee), and the experiments are scripts that combine the rest.

rutalia-planner/
├── README.md               # completed in 07-03
├── requirements.txt        # numpy, scipy, matplotlib
├── config.py               # parameters and seeds, NO logic
├── data/
│   ├── generator.py        # creates synthetic history and instances
│   └── instances/          # generated .npz files (never edited by hand)
├── algorithms/
│   ├── regression.py       # time model (05-03)
│   ├── clustering.py       # k-means (05-05)
│   ├── assignment.py       # Hungarian (03-06)
│   └── routes.py           # nearest neighbor + 2-opt (06-01)
├── evaluation/
│   └── metrics.py          # actual cost of a plan; the single referee
├── experiments/
│   ├── exp_baseline.py     # milestone 0
│   ├── exp_layers.py       # compares variants across several seeds
│   └── results/            # .csv with parameters + results
└── tests/
    └── test_basics.py

Rules that spare you pain later:

  • evaluation/ only evaluates with the true times from the generator, never with the times predicted by your model. If the plan is scored with the same predictions that built it, a bad model congratulates itself — that is the leakage from 06-04 dressed up as optimization.
  • config.py gathers all the magic numbers (number of orders, k, seeds, 2-opt iterations). It must be possible to change an experiment without editing any algorithm.
  • Every module can be tested on its own: routes.py receives a time matrix and returns an ordering; it has no idea where the matrix came from.

Milestone 0: the tracer bullet

The first working day ends with the whole system running badly. Data generator, naive plan, evaluation and final number: everything connected.

# data/generator.py
import numpy as np

def generate_history(n=3000, seed=42):
    """Historical trips: [x1,y1,x2,y2,hour] -> actual minutes."""
    rng = np.random.default_rng(seed)
    X = rng.uniform(0, 10, size=(n, 4))          # coords in km
    hour = rng.integers(7, 22, size=n)
    dist = np.hypot(X[:, 2] - X[:, 0], X[:, 3] - X[:, 1])
    peak = np.isin(hour, [8, 9, 18, 19]) * 1.6   # rush-hour penalty
    y = dist / 0.35 * (1 + peak * 0.4) + rng.normal(0, 2.0, n)
    return np.column_stack([X, hour]), np.maximum(y, 1.0)

def generate_day(n_orders=80, n_couriers=5, seed=0):
    rng = np.random.default_rng(seed)
    orders = rng.uniform(0, 10, size=(n_orders, 2))
    depot = np.array([5.0, 5.0])
    return orders, depot, n_couriers
# experiments/exp_baseline.py
from data.generator import generate_day
from evaluation.metrics import plan_cost   # uses the TRUE times

def baseline_plan(orders, n_couriers):
    """Consecutive blocks in arrival order, route left unsorted."""
    size = len(orders) // n_couriers
    return [list(range(i * size, (i + 1) * size)) for i in range(n_couriers)]

orders, depot, n_couriers = generate_day(seed=0)
plan = baseline_plan(orders, n_couriers)
print(f"Total baseline cost: {plan_cost(plan, orders, depot):.0f} min")

Example output: Total baseline cost: 612 min. It is a horrible number and that is exactly what we wanted: the yardstick now exists, along with the plan format (a list of routes, each route a list of order indices) and the referee. Everything you do from here on either gets below 612 or is superfluous.

flowchart LR
    G[data generator] --> P[plan: baseline]
    P --> E[evaluation with true times]
    E --> R[final number]
    P -. "milestones 1-3: replace<br/>with better layers" .-> P

Milestones 1 to 3: improving in layers

Each milestone replaces one piece of the pipeline with its algorithmic version, gets measured against the running table, and the result is saved. Never two layers at once: if the number gets worse, you want to know which layer did it.

Milestone 1: travel-time regression (05-03)

We train the linear regression with gradient descent on the history (features: distance, rush-hour indicator) and build the time matrix between all the points of the day. With it, each courier orders their block with nearest neighbor — the assignment is still the naive one.

# algorithms/regression.py (integration skeleton)
import numpy as np

def features(X):
    dist = np.hypot(X[:, 2] - X[:, 0], X[:, 3] - X[:, 1])
    peak = np.isin(X[:, 4], [8, 9, 18, 19]).astype(float)
    return np.column_stack([np.ones(len(X)), dist, dist * peak])

def train(X, y, lr=0.01, epochs=500):
    A = features(X)
    w = np.zeros(A.shape[1])
    for _ in range(epochs):
        w -= lr * A.T @ (A @ w - y) / len(y)   # MSE gradient
    return w

def time_matrix(points, w, hour=9):
    n = len(points)
    pairs = np.array([[*points[i], *points[j], hour]
                      for i in range(n) for j in range(n)])
    return (features(pairs) @ w).reshape(n, n)

We measure two things: the quality of the model (MAE on the 20% test split: 3.1 min, within the specification's < 4 target) and the effect on the plan.

Milestone 2: clustering + assignment (05-05, 03-06)

k-means groups the 80 orders into 5 compact zones; the Hungarian algorithm assigns each group to the courier whose cost of covering it (predicted depot → centroid time, as an approximation) is lowest. In our version all couriers start from the depot, so the Hungarian barely changes the cost here — we keep it because it generalizes to couriers with different starting points, and we note that honestly in the results.

# fragment of experiments/exp_layers.py
from scipy.optimize import linear_sum_assignment
from algorithms.clustering import kmeans            # 05-05, our own
groups, centroids = kmeans(orders, k=n_couriers, seed=0)
cost = courier_group_cost_matrix(centroids, depot, w)
rows, cols = linear_sum_assignment(cost)             # Hungarian (03-06)
plan = [groups[c] for c in cols]

Milestone 3: 2-opt (06-01)

On each route, nearest neighbor gives the initial order and 2-opt refines it by reversing segments as long as there is improvement, just like in the operational day of 06-01 — but now over the matrix of predicted times, not distances.

Intermediate results table for the example (instance seed=0, always evaluated with true times):

Milestone Variant Total cost (min) Improvement vs. baseline Compute time
M0 Blocks + arrival order 612 — < 0.01 s
M1 Blocks + NN on predicted times 471 −23% 0.4 s
M2 k-means + Hungarian + NN 388 −37% 0.6 s
M3 k-means + Hungarian + NN + 2-opt 342 −44% 2.1 s

With a single instance this is an anecdote; the specification's ≥30% target is only declared met after the next section.

Reproducible experiments

Three rules turn "I got 342" into an experiment:

  1. Explicit, separate seeds. One seed for the data, another for the stochastic algorithms (k-means). Both in config.py, never np.random.seed scattered across modules.
  2. Configuration outside the code. Changing N_ORDERS or K must not touch any algorithm.
  3. Every run saves parameters + result together. A CSV that gets one row appended per run; without this, by milestone 4 you will not remember which configuration produced which number.
# experiments/exp_layers.py (main loop)
import csv, time
from config import DATA_SEEDS, ALGO_SEEDS, VARIANTS

with open("experiments/results/layers.csv", "a", newline="") as f:
    w = csv.writer(f)
    for d_seed in DATA_SEEDS:              # 10 day instances
        for a_seed in ALGO_SEEDS:          # 5 algorithm seeds
            for name, planner in VARIANTS.items():
                t0 = time.perf_counter()
                plan = planner(d_seed, a_seed)
                w.writerow([name, d_seed, a_seed,
                            plan_cost_from(plan, d_seed),
                            time.perf_counter() - t0])

Aggregating the example's 10 instances × 5 seeds: mean improvement of M3 over the baseline of −41% (minimum −33%, maximum −47%). Now, yes: target met, with known variability instead of a lone number.

Serious measurement: predict the cost, then measure it

Module 1 gave you a superpower that most projects waste: knowing how much something will cost before running it. Use it as a cross-check on your own implementation:

Piece Theoretical cost (01-01/01-02) Prediction for n=80, k=5 Measured consistent?
Time matrix O(n²) model evaluations 6,400 vectorized rows: ms Yes (~0.3 s including pair construction)
k-means O(iter · n · k) trivial Yes
Hungarian O(k³) 125 operations: nothing Yes
2-opt per route O(passes · m²), m≈16 ~256 checks/pass Yes (~1.5 s total)

If the measured time deviates by orders of magnitude from the predicted one, you have almost always found a bug (an accidental O(n³) loop, a matrix rebuilt inside a loop). Also verify empirical scalability: double n and check that the matrix time multiplies by ~4, as O(n²) dictates — the same doubling technique you used in 01-02.

Minimal tests

You don't need an industrial-grade suite; you need to not fool yourself. Two kinds of test are enough:

Small cases verifiable by hand. A day of 4 orders and 2 couriers where the optimum can be worked out with pencil and paper; your pipeline must find it or come very close.

Invariant properties that must hold for any input:

# tests/test_basics.py
def test_valid_plan():
    plan = plan_m3(data_seed=0, algo_seed=0)
    visited = [o for route in plan for o in route]
    assert sorted(visited) == list(range(80))   # every order, exactly once
    assert len(plan) == 5                        # one route per courier

def test_two_opt_never_worsens():
    route, M = example_route()
    assert route_cost(two_opt(route, M), M) <= route_cost(route, M) + 1e-9

def test_time_matrix_positive_with_zero_diagonal():
    M = time_matrix(example_orders(), trained_w)
    assert (M[~np.eye(len(M), dtype=bool)] > 0).all()

Adapt the properties to your domain: in a flow project, "flow is conserved at every node"; in a timetabling one, "no resource is in two places at once"; in an external sorting one, "the output is sorted and is a permutation of the input".

When to stop optimizing

The stop signal is not "I've run out of ideas", but any of these three:

  • Specification target met with measured variability. Ours was ≥30%; we are at −41% mean with a worst case of −33%. Met.
  • Diminishing returns. M1 contributed 23 points, M2 another 14, M3 another 7. A hypothetical M4 layer (3-opt, or or-opt) would cost hours to scrape 2-3 points: it gets written down as future work, not implemented.
  • Hour budget exhausted according to the milestone plan. The 07-01 plan reserved 6 hours for milestone 4 (experiments and report); stealing them for a micro-improvement is a bad trade, because measurement and communication are worth more marks than the extra 2%.

Final rule of thumb: every additional improvement must justify in advance which metric it will move and by how much it expects to move it. If you cannot answer, don't start it.

Common Mistakes and Tips

  • Mistake: evaluating with the predicted times. The most dangerous one in the whole project: the plan optimizes predictions and is scored with them, so improving the model "improves" the result even if the real routes get worse. The referee always uses the true data from the generator (or a separate evaluation set).
  • Mistake: two layers at once. If you integrate regression and clustering in the same session and the cost goes up, you don't know whom to blame. One layer, one measurement, one commit.
  • Mistake: results on screen and moving on. A number that is not saved with its parameters does not exist. The results CSV is as much a part of the project as the code.
  • Mistake: optimizing the code before the algorithm. Vectorizing an O(n³) baseline is polishing the Titanic's cabin; first the asymptotic improvement (01-02), then the constants, and only if compute time is actually a problem.
  • Tip: one commit per milestone with the number in the message. git commit -m "M2: kmeans+hungarian, 388 min (-37%) seed 0" gives you a history that in 07-03 almost writes the results section by itself.
  • Tip: a decision log. A DECISIONS.md with one line per choice ("2-opt and not 3-opt because O(m²) vs O(m³) and m=16") — in the next lesson it will be gold for the method-justification table.

Exercises

As in 07-01, these are guided milestones of your own project.

Exercise 1: tracer bullet

Implement your complete milestone 0: seeded data generator, dumb baseline, evaluator, and a final number printed. Implementing any "good" algorithm at this stage is forbidden.

Exercise 2: layers with a table

Develop your intermediate milestones one at a time and build your running results table (variant, metric, improvement vs. baseline, compute time), measuring each layer separately.

Exercise 3: reproducibility and tests

Run your final comparison with at least 5 instances × 3 seeds, saving a CSV, and write a minimum of 3 tests: one small hand-checked case and two invariant properties of your domain.

Solutions

Exercise 1 — self-assessment criteria. Definitive test: delete everything except the repository, clone it and run python experiments/exp_baseline.py; it must print the same number (fixed seed). Also: the evaluator lives in its own module and imports nothing from algorithms/; the "plan/solution" format is already the final one. If your baseline took more than an afternoon, your 07-01 specification made the baseline too ambitious: simplify it and write that down.

Exercise 2 — reference solution. A healthy table shows decreasing improvements per layer (like 23/14/7 in Rutalia) and compute times that grow consistently with the theoretical analysis. Two legitimate situations you must not hide: a layer that does not improve (like our Hungarian with a single depot — the why gets documented) and a layer that improves the metric but blows up the time (a trade-off decision: record both columns). Warning sign: increasing improvements per layer usually mean the baseline was artificially bad or there is leakage in the evaluation.

Exercise 3 — self-assessment criteria. The CSV must allow you to reconstruct any number in your table with a groupby (variant → mean, minimum, maximum); if you need to "remember" anything that is not in the file, parameter columns are missing. On the tests: the small-case test must have the expected result computed by hand in a comment, and the properties must fail if you introduce a deliberate bug (try it: break 2-opt by reversing the indices wrong and verify that the test catches it). A test that cannot fail protects nothing.

Conclusion

The project now exists: a clean structure with data, algorithms, evaluation and experiments kept apart; a baseline that ran end to end from day one; three algorithmic layers integrated one by one — travel-time regression (05-03), clustering and assignment (05-05, 03-06), nearest neighbor with 2-opt (06-01) — each with its own measurement; multi-seed experiments that turn a lone number into a result with variability (−41% mean, worst case −33%); tests that prevent self-deception and a clear stopping criterion. But a project that only you understand is half finished: in the last lesson of the course (07-03) we will write the final report, prepare the repository so anyone can reproduce it, evaluate the work with an honest rubric — and close the journey that began, seven modules ago, with asymptotic notation and a delivery company called Rutalia.

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