Greedy routing, a 34% gap, and twelve days left
A Year 13 student is building a route-planning tool for a produce co-op. Each weekday the co-op fills 380 orders across 26 suburbs using four vans with a 220 kg payload. The prototype assigns orders by nearest neighbour and produces routes within 1.8 seconds, but the total distance is 34% longer than the co-op's experienced dispatcher achieves by hand. The teacher has supplied last season's 400 order records and the co-op's actual routes for 20 days. The student wants to spend the remaining 12 days implementing simulated annealing. No test cases, no error handling and no logging exist yet. The assessment asks for a program that is ‘fit for purpose’ and ‘robust’.
1. Evaluate whether the plan to implement simulated annealing is justified. What evidence would you want before any optimisation work?
Read the worked answer
The proposal attacks a problem that has not been established.
Check the comparison first. Is the 34% figure measured on the same orders? If the dispatcher's routes come from the 20 supplied days and the prototype's 1.8-second run is on today's 380 orders, the two numbers describe different problems and the headline gap may be meaningless. Re-run the prototype on the 20 benchmark days before believing any gap exists.
Check correctness next. Does the prototype actually enforce the 220 kg payload? If capacity is not enforced, a longer route may be the visible symptom of an infeasible one, and optimisation would be tuning the wrong thing.
Check the requirement. At 1.8 seconds, runtime is not the constraint. Any practical user will wait that long. Optimising speed or even distance is not where the risk lies; the risk lies in a program with no error handling, no logging and no tests, which is what ‘robust’ in the assessment asks about.
Evidence I would gather: constraint violations per run, total kilometres and time against the dispatcher on the 20 supplied days, and behaviour on deliberately malformed input. Then decide, on that evidence rather than on interest, whether a heuristic upgrade earns its twelve days.
2. Design a test plan that would let the student claim the program is robust. Include specific edge cases and the expected result for each.
Read the worked answer
Robustness is about behaviour under invalid input and boundary conditions, so the plan needs layers.
Unit level. Distance function: symmetric, zero for identical points, correct for two known addresses. Capacity accumulator: exactly 220 kg passes, 220.1 kg fails. Suburb lookup: known suburb returns coordinates, unknown returns a defined outcome.
Edge cases with expected results.
- Zero orders → empty route set, no crash.
- One order heavier than 220 kg → reported as unassignable, not silently dropped.
- Duplicate order IDs → rejected with a message identifying the row.
- Address not in the suburb list → logged and handled by a stated rule (excluded with a report, or routed), because an accidental rule is a bug.
- All 380 orders in one suburb across four vans → capacity split correct, four non-empty routes.
- Exactly 220 kg on one van → accepted.
- Malformed CSV: missing column, text in the weight field, blank line → clear error, non-zero exit, no partial output that looks complete.
Integration and acceptance. Run the 20 supplied days; compare kilometres and elapsed time against the dispatcher's actual routes; count constraint violations across all runs.
The definition to test against: a robust program fails safely and visibly - a message, a log entry, and no plausible-looking wrong answer - rather than succeeding on average.
3. Recommend a plan for the twelve days, and state what you would cut if time runs short.
Read the worked answer
Order the work by risk, not by interest.
Days 1–2: make it trustworthy. Input validation, logging, capacity enforcement, and a re-run of the baseline on the 20 supplied days. You cannot improve what you cannot measure, and you cannot submit a program that crashes on a bad file.
Days 3–5: fix the obvious structural weakness. A 34% gap with a nearest-neighbour heuristic usually means the routes ignore geography in practice - for example, orders are loaded by capacity order before proximity is considered, or each van is filled before the next is started. Change the construction order, re-measure on the benchmark, and write the tests for it.
Days 6–7: build the evidence. A benchmark harness that produces the comparison table (prototype versus dispatcher on 20 days) as evidence for the report, not just for the student.
Days 8–10: only now, if the gap survives and tests are green, add a simple time-capped improvement - 2-opt local search on the greedy solution is far quicker to implement and validate than annealing, and can be capped so runtime stays predictable. Keep it only if it wins on the benchmark.
Days 11–12: documentation, evidence, final run.
What to cut: the annealing, and any optimisation, if the tests are not green. A tested 20% improvement is worth more than an untested 30% one.