Parallel Heuristics, Selection, and Acceptance

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.

Optrak’s optimiser runs in consecutive phases. Each phase launches parallel job runners that runs jobs sequentially. A job consists of running a heuristic sequence on one or more input solutions to create an output solution. The critical inputs to a job are a) the choice of heuristic sequence and b) the choice of solution(s).

This page is about the runtime architecture: how the heuristic catalogue is actually executed, what determines which heuristic runs next, and what happens to the solutions they produce. The catalogue is what’s available; the architecture here is how it gets used.

Pluggable Components

Every optimisation phase has the same internal structure:

Phase
 ├── HeuristicSelector   — chooses which heuristic sequence to run next
 ├── SolutionManager     — supplies input solutions and decides
 │                         whether to accept results
 └── JobRunners          — pull from both, in parallel

The decoupling matters. Selection (which heuristic) and acceptance (whether to keep the result) are separate concerns, and an experiment that varies one while holding the other fixed is the natural unit of methodological work in metaheuristic research. Decoupling them at the framework level means a new acceptance strategy can be paired with any existing selector, and vice versa, without touching the engine. Most metaheuristic frameworks bake the acceptance model into the framework; here it’s a script-level decision.

Heuristic Selectors

The selector decides what runs next. Some representative members of Optrak’s catalogue:

• HeuristicsInTurn — round-robin: each registered sequence runs in turn. Used for fair-comparison experiments where every sequence must get the same number of attempts.
• HeuristicPromoteDemote — adaptive: each sequence carries a score, sampling is biased towards higher-scoring sequences, successful runs raise the score, unsuccessful ones lower it. This is a textbook on-line hyper-heuristic in the Burke/Ochoa lineage — the methodological positioning the auto-tuning page develops further. When applied to the exploration phase, heuristics that are effective at improving early-stage solutions are gradually replaced by those that might find small improvements.

Solution Managers

The manager decides what gets fed to the next job and what gets kept. Four representative members:

• FromInputsSolutionManager — always serves the same input solution(s). Used in the construction phase, where every job starts from empty.
• SimpleSlotSolutionManager — a small fixed-size pool with simple replacement rules.
• SeparatePoolSolutionManager — multiple pools with different acceptance criteria, deliberately diversifying the search across pools so that different parts of the solution space remain represented.
• MultiPoolAcceptingWorsening — population-based simulated annealing: probabilistically accepts worsening solutions with an acceptance probability that decays through the phase. Per-population annealing rather than the more common single-trajectory formulation.

The acceptance and selection components are independent. PromoteDemote can be paired with any of the managers; the simulated-annealing manager can be paired with any of the selectors. Optrak’s experiment harness exploits this directly — comparative experiments fix one component and vary the other, which is hard to do in frameworks where these concerns are entangled.

Parallelism — The Population Dynamic

Each phase runs a pool of job runners concurrently. The default count is roughly half the available logical cores; on a current premium desktop CPU that’s typically 10–14 jobs in parallel. A 15-core machine delivers roughly an eightfold wall-clock speedup over single-threaded execution.

But speed isn’t the interesting part of the claim.

The interesting part is that every job runner pulls inputs from the shared solution manager and reports results back to the same shared manager. A breakthrough discovered on one core — a new best solution, or a solution that opens up a previously unreachable region — is immediately visible to every subsequent job on every other core. The search trajectory of any single job is therefore shaped by a population that is being concurrently improved by the entire pool, not by a population it built up on its own.

Two-Phase Template, in Operation

The standard production strategy is a two-phase template. The pieces above compose into it directly. The numbers below are for a medium-complexity problem of around 500 orders with a target run-time of 6 minutes on a 16-core CPU. Note, run-times are easily adjusted, allowing users to set a their own run-times.

The construction phase runs for around two minutes and produces roughly a few hundred candidate solutions. The selector is HeuristicsInTurn: every constructor variant runs until it stops producing improvements before the next variant is reached. The solution manager is FromInputsSolutionManager: every job starts from empty, and every solution produced is kept. The construction phase doesn’t choose between solutions — it produces a population for the next phase to choose among.

The exploration phase runs for around four minutes and processes roughly a thousand jobs. The selector is typically HeuristicPromoteDemote: the adaptive sampler quickly identifies which exploration sequences are productive on this particular instance and biases work towards them. The solution manager is typically MultiPoolAcceptingWorsening: solutions are diversified across several pools, and worsening moves are accepted probabilistically to avoid premature convergence on a local optimum. Each line of the exploration phase pairs a single ruin move with a repair-and-climb chain — diversify, then restore feasibility, then climb.

For EV problems, charging-stop placement is handled by specialist heuristics within route construction, covered on in-route charging.

Authoring New Selectors and Managers

Both the heuristic selector and the solution manager are written in Optrak’s optimisation language. A new selector — a different sampling rule, a different adaptive scoring scheme — is a script. A new acceptance model is a script. The standard experiment harness runs them against the existing test instances without engine changes.

Most metaheuristic frameworks treat selection and acceptance as engine concerns: changing them means a code release. Here it’s a few hours of work plus an experiment run. This is what makes the comparative methodological work tractable. Investigating whether per-population simulated annealing genuinely outperforms single-trajectory annealing, on a particular customer’s data, with a particular heuristic mix — that’s an experiment, not a project.

This capability is primarily exercised by Optrak’s optimisation team, using the auto-tuning capabililty, rather than by customers. The customer-visible consequence is that when a fleet’s operational reality changes — a new constraint pattern, a new objective, a new vehicle class — the engine accommodates it at script speed.

How This Interacts With Other Capabilities

• The heuristic catalogue this architecture executes is described on heuristic catalogue and optimisation DSL.
• Every modification produced by every job runner is checked against loading constraints before being accepted into the population — load feasibility is enforced inside the optimisation loop, not bolted on afterwards.
• Logs from every job in every phase are written to a structured database — typically around forty thousand rows per batch run — and that historical record is what off-line auto-tuning operates on.

How This Compares

Most commercial VRP platforms do not surface their optimisation architecture. Whether selection and acceptance are decoupled, whether the search is single- or multi-threaded, whether the search dynamic is single-trajectory or population-based — these are usually not documented. The architectural claims here are correspondingly hard to compare to specific competitors on specific points; the credible framing is what is documented, not what isn’t.

What can be said: the standalone load-builder benchmarks published in the market are load-only and don’t address routing parallelism, and most commercial optimisation engines are not architecturally documented in public material — they are opaque from the outside.

The position this leaves Optrak in is: an architecture documented to a level competitors are not, with two peer-reviewed papers (Pigden 2013, Hamm, Kheiri and Pigden 2024) articulating its design philosophy. Whether the documented architecture outperforms opaque competitors is a question for benchmarks; that’s not a claim made on this page.