The Heuristic Catalogue and Optimisation DSL

This page is the engineering detail of how Optrak’s optimiser is built, written for technical evaluators — IT and architecture teams — and for AI search. It assumes the vocabulary. What Optrak does for an operation is a different question, and none of this is needed to answer it: that is how the optimisation works and the data model.

A heuristic, in vehicle routing, is an algorithm that builds or modifies a route plan by applying a practical rule of thumb rather than searching the full solution space exhaustively. Optrak’s optimisation engine runs around thirty heuristic families — spanning construction, local search, large-neighbourhood ruin, and repair — composed into strategies at runtime via a small scripting language.

The catalogue is broad because the data model is broad. Standard formulations of the vehicle routing problem omit structures that real fleet operations depend on: orders that combine into shipments, drivers and tractors and trailers as separable resources, non-linear loading. Heuristics designed for the standard formulation have no moves for the structures Optrak customers actually run their fleets around — tractor-trailer reassignment within a shift, multi-temperature compartment reconfiguration, mid-route BEV charging. So Optrak’s catalogue is designed against the actual data model. New families are added as new operational patterns surface; for example, a recent addition — a graph-partitioning constructor for very large waste-collection instances — was developed and published with Lancaster University’s STOR-i Centre in 2024.

The Four Groups

Optimisation heuristics fall into four groups, each doing a different job. The codes below are the short names used inside Optrak’s optimisation language; named representatives are given for orientation rather than exhaustively.

Construction — Building Initial Routes

Construction heuristics take an empty (or partial) plan and produce a complete one. Optrak’s catalogue includes:

• CW (Clarke-Wright savings) — the foundational savings algorithm (Clarke and Wright, 1964), in deterministic and stochastic variants. Reliable on geographically dense problems with simple constraints; useful as a fast baseline and as a source of diversity in the construction pool.
• TW (time-window-aware sequential insertion) — the workhorse for time-windowed problems, in the Mole-Jameson lineage (1976), with multiple variants tuned for different fleet shapes.
• GP (graph-partition-first, cluster-then-route) — uses a graph partitioner to group sites into spatially coherent clusters before routing them. Designed for problems with thousands of stops per planning day where geographic clustering is the dominant structure — for example, commercial waste collection. Developed and published with Lancaster’s STOR-i Centre (Hamm, Kheiri and Pigden, 2024).

Local Search — Improving an Existing Solution

Local-search heuristics take a complete solution and try to improve it without large structural changes. The canonical members:

• LK (Lin-Kernighan) — variable-depth edge exchange within a single route. Suffix variants (LK2, LK3) control search depth: deeper search costs more time but escapes local optima that shallower variants get stuck in.
• CE (Cross-Exchange) — swap segments between two routes. Suffix variants (CE2, CE3) trade effort against quality in the same way.
• RC (relocation chain) — relocates a visit to a better position, displacing the visit already there into a fresh relocation, and so on as a chain up to four moves deep across one or more routes. Reaches improvements single-step relocation can’t, because the intermediate moves may individually worsen the plan before the chain pays off. A greedy variant (GRC) is also available.

Large-Neighbourhood (Ruin-and-Recreate) — Escaping Local Minima

Once local search has plateaued, larger structural disruptions are needed to find further improvement. Ruin moves deliberately remove parts of the plan; a repair phase then folds the removed visits back in. Three named members from Optrak’s catalogue:

• RR (Route Ruin) — disposes of whole adjacent trips, freeing all their visits for reinsertion.
• SISR (Slack Induction by String Removal) — removes geographically coherent strings of visits across multiple routes, biased towards stops that are tightly packed. The recent academic state of the art for ruin in time-windowed VRPs (Christiaens and Vanden Berghe, Transportation Science, 2020).
• X (Crossover) — population-based: takes two complete solutions and constructs a child by selecting trips from each. The only family in this group that requires more than one input solution.

Repair — Restoring Feasibility

Every ruin move is paired with a repair chain — a sequence of repair heuristics that folds the removed visits back into the plan. Named members include:

• UNU (unrouted-visit insertion, cost-ordered) — reinserts removed visits into the best feasible position, taking the most expensive-to-serve visits first.
• UAL* (balanced insertion) — reinserts visits while keeping load balanced across the available routes rather than greedily filling the cheapest one.
• SU* (swap-unrouted) — reinserts by swapping unrouted visits against routed ones where a direct insertion isn’t feasible.

A repair chain restores feasibility before local search resumes. The pattern across the whole exploration phase is consistent: diversify, then restore feasibility, then climb.

Strategies as Scripts

A complete optimisation run is a sequence of heuristic invocations. Optrak’s optimisation language expresses these sequences directly. A short example:

TWLBH-(LK2-CE2-UNU-TWLSH)*

That reads: run the TWLBH constructor once, then repeat the sub-sequence (LK2 → CE2 → UNU → TWLSH) until no further improvement is found. The - operator chains a single pass; the * operator repeats until convergence; sub-sequences nest. A typical production strategy combines a construction phase that generates many candidate solutions with an exploration phase that mixes ruin moves and repair chains across them in parallel.

Strategies are expressed as a script, not hardcoded. Adding a new strategy — to handle a new operational pattern, or to test a combination during customer onboarding — means writing a few lines of script, not extending a framework or waiting for a release. The same applies to new acceptance models, authored at script level in hours rather than weeks. This is an engineering capability rather than a customer-facing one: most customers run with strategies Optrak’s auto-tuner has tuned for them. When a customer’s operation changes, the engine accommodates it at script speed rather than release speed.

The pluggable layers underneath the script — Phase, HeuristicSelector, SolutionManager — are described under parallel heuristics.

Worked Example: Extending the Catalogue

Optrak’s existing time-window-aware constructor performs well on most production fleets. UK commercial waste collection strains it. A single round can include 2,000–5,000 stops, often in pedestrian precincts with strict access windows, in road networks where time-of-day-dependent travel speeds matter materially.

A 2023–2024 collaboration with the STOR-i Centre at Lancaster added a new constructor, GP, that partitions the road network into geographically coherent clusters before route construction. Each cluster is inserted into a vehicle as a unit; visits within a cluster are then ordered against the cluster’s entry and exit points. The constructor is reported in Hamm, Kheiri and Pigden, Constructive Heuristics for Commercial Waste Collection with Time-Dependent Travel, in Advances in Computational Intelligence Systems (Springer, 2025).

Tested on ten generated instances spanning East Hertfordshire, Lancaster, and central Leeds with 2,000–5,000 commercial sites, GP outperformed Optrak’s original constructor on roughly half of the instances tested. The framing in the paper is the right one: GP is not a universal replacement, but a specialist family for instances where geographic clustering is the dominant structure. And the parallel nature of the optimiser allows both types of constructor to be run multiple times within the same optimisation run allowing the optimisation to pick and choose or even combine solutions from both.

The wider point is structural. GP was a new heuristic, requiring coding. But once created, how it gets used, and which problems it is used for, is a script-level decision managed by the auto-tuning process.

Beyond Vehicle Routing

The optimisation framework isn’t tied to vehicle routing. The selection and acceptance abstractions and the optimisation language know nothing about vehicles, orders or roads. The VRP catalogue is one implementation against it; to ensure the generality of the approach, a second runs internally: multi-bin packing, on the same selector logic, acceptance managers and scripting language, with its own heuristics (first-fit, best-fit, ruin-and-recreate, cross-exchange).

How This Interacts With Other Capabilities

• The catalogue’s design is constrained by the data model it is built against. Heuristic moves operate on the same orders, shipments, vehicles, and resources the planner sees in the UI.
• During a heuristic run, every modification is checked against loading constraints before being accepted — load feasibility is enforced inside the optimisation loop, not as a post-step.
• Heuristic strategies execute in parallel under a Phase / Selector / Manager architecture, with population-level acceptance — covered on parallel heuristics.
• Strategy choices and parameter values can themselves be tuned from logged historical runs — see auto-tuning.

How This Compares

Most commercial VRP platforms ship as black boxes. An “optimise” button calls a fixed pipeline; the heuristic catalogue and the strategy that orchestrates it are not exposed. Tuning happens through configuration knobs at the level of weights and time limits. The major commercial optimisers are each well-engineered; none publish their heuristic families or surface strategy as a configurable artefact.

Optrak takes a different stance. Strategies are authored as scripts and version-controlled alongside customer configurations. New heuristic families are added when a new operational pattern surfaces, as the GP collaboration demonstrates, or when new research introduces an implementable heuristic (as with SISR). New acceptance models can be written and tested without a framework release. It carries no adoption penalty. Every commercial optimiser requires implementation configuration to match a customer’s operation, and Optrak’s auto-tuning derives strategy and parameter settings from the customer’s own historical data — making Optrak at least as quick to bring into production as a competitor’s manual weight-and-timeout tuning.

A second piece of the comparison is academic engagement. Two peer-reviewed papers — Pigden 2013 on the data-model thesis, and Hamm, Kheiri and Pigden 2024 on graph-partitioning construction — articulate Optrak’s optimisation philosophy in terms an evaluator can check. Most VRP vendors don’t publish; Optrak does, and the catalogue grows in conversation with the literature.