Self-tuning metaheuristic search for hard optimization

The search engine behind Surge

Hard combinatorial optimization (VRP, scheduling, packing) doesn't yield to exact solvers at real-world scale. You need metaheuristics — and the quality of your metaheuristic framework determines the quality of your solutions. Most ALNS implementations are bespoke, tightly coupled to a single problem, and impossible to test independently.

Arbor separates the search strategy (operator selection, acceptance, adaptation) from the problem domain (VRP, scheduling, etc.). Surge registers 18 operators. Arbor manages which ones run, how often, and when to accept worse solutions. This separation means Arbor is tested independently (66 tests) and Surge operators are tested independently (340 tests).

How ALNS works

  ar_alns_solve(ctx, initial_solution, best_out)
         │
         ▼
  ┌──────────────────────────────────────────────────────────┐
  │                    ALNS Main Loop                        │
  │                                                          │
  │  ┌────────────┐    ┌────────────┐    ┌────────────────┐  │
  │  │  Roulette   │───▶│  Destroy   │───▶│    Repair      │  │
  │  │  Selection  │    │  Operator  │    │    Operator    │  │
  │  │  (weighted) │    │  (remove q │    │    (reinsert)  │  │
  │  └────────────┘    │   elements)│    └───────┬────────┘  │
  │                    └────────────┘            │           │
  │                                              ▼           │
  │  ┌────────────┐    ┌────────────┐    ┌────────────────┐  │
  │  │  Weight     │◀───│  Segment   │◀───│   Accept /     │  │
  │  │  Update     │    │  Boundary  │    │   Reject       │  │
  │  │  (adaptive) │    │  (every N) │    │   (SA/RRT/GD)  │  │
  │  └────────────┘    └────────────┘    └────────────────┘  │
  │                                                          │
  │  Stop: max_iters │ time_limit │ stagnation │ target_cost │
  └──────────────────────────────────────────────────────────┘
         │
         ▼
  ARALNSStats { iterations, improvements, best_cost, ... }

Acceptance criteria

Adaptive weight learning

Every segment_size iterations (default 100), Arbor updates operator weights based on their performance during that segment:

// Reward for each operator usage during segment
if (new_global_best)   reward = 8.0;   // Best solution found
else if (improved)     reward = 4.0;   // Improving accepted
else if (accepted)     reward = 2.0;   // Non-improving accepted
else                   reward = 0.5;   // Rejected

// Weight update at segment boundary
avg_reward = segment_score / segment_uses;
new_weight = (1 - reaction) * old_weight + reaction * avg_reward;
// reaction = 0.1: 10% new data, 90% history

This means operators that consistently find improvements get selected more often. Operators that waste CPU get downweighted. The reaction_factor (default 0.1) controls learning speed — low values keep weights stable, high values react quickly to recent performance.

SA temperature calibration

ar_alns_calibrate_sa() auto-tunes the initial temperature and cooling rate from the problem cost and iteration budget:

• T₀ = 0.05 × |cost| / ln(2) — a 5%-worse solution is accepted with ~50% probability initially
• Cooling rate = exp(-6.9 / max_iterations) — temperature drops to 0.1% of T₀ by the end
• Example: cost=1000, 1000 iters → T₀ ≈ 72, cooling ≈ 0.993, final T ≈ 0.07

Built-in removal strategies + pluggable anything

Standard removal helpers

Arbor provides three parameterized removal strategies in ar_operators.h. These are building blocks — your domain operators call them with problem-specific callbacks for element access, cost, and relatedness.

Surge's 18 operators (real-world example)

Adaptive destruction size

When enabled, the number of elements removed (q) adapts to search progress. During improvement phases, q stays small (exploitation). During stagnation, q grows up to 3× the initial maximum (exploration). Resets to initial when improvements resume.

Register, solve, read stats — three steps

#include "ar_alns.h"

// 1. Configure
ARALNSParams params;
ar_alns_params_default(&params);
params.max_iterations = 5000;
params.accept_type = AR_ACCEPT_SA;
ar_alns_calibrate_sa(&params, initial_cost, 5000);

// Solution callbacks: copy, free, cost, size, validate, is_better
ARSolutionOps ops = {
    .copy = my_copy, .free = my_free,
    .cost = my_cost, .size = my_size,
    .is_better = my_compare
};

// 2. Create context and register operators
ARALNSContext *ctx = ar_alns_create(&params, &ops, solver_data);
ar_alns_set_seed(ctx, 42);

ar_alns_add_destroy(ctx, "random",    destroy_random,  NULL, 1.0);
ar_alns_add_destroy(ctx, "worst",     destroy_worst,   NULL, 1.0);
ar_alns_add_destroy(ctx, "shaw",      destroy_shaw,    NULL, 1.0);
ar_alns_add_repair(ctx,  "regret-3",  repair_regret3,  NULL, 1.0);
ar_alns_add_repair(ctx,  "greedy",    repair_greedy,   NULL, 1.0);

// 3. Solve
void *best = NULL;
ar_alns_solve(ctx, initial_solution, &best);

// 4. Read results
ARALNSStats stats;
ar_alns_get_stats(ctx, &stats);
// stats.best_cost, stats.iterations, stats.improvements

// Per-operator performance
for (int i = 0; i < ar_alns_destroy_count(ctx); i++) {
    ARALNSOperatorStats os;
    ar_alns_get_destroy_stats(ctx, i, &os);
    // os.name, os.weight, os.selected, os.improvements
}

ar_alns_free(ctx);

Solution interface

Arbor is problem-agnostic. You provide six callbacks that define your problem:

Progress callback

// Called at each segment boundary (~100 iterations)
int on_progress(const ARALNSStats *stats, void *user_data) {
    printf("iter=%lld cost=%.1f improved=%lld\n",
           stats->iterations, stats->best_cost, stats->improvements);
    return should_cancel ? 1 : 0;  // return 1 to stop
}

ar_alns_set_progress_callback(ctx, on_progress, my_data);

Design decisions

Restart mechanism

When stagnation exceeds restart_threshold, Arbor resets to the best known solution and reheats the SA temperature to initial_temp × restart_temp_ratio. This escapes local optima without losing the global best. Statistics track restart count.

Memory model

Operator arrays grow dynamically (default capacity 8, doubles as needed). The best solution is cached in context. One SHRng (Xoshiro256**) instance per context. No global state — multiple ALNS contexts run concurrently without interference.

Stop conditions

Codebase

Get started in minutes

1. Build from source

# Clone and build
git clone https://github.com/ottofleet/otto.git
cd otto && make arbor

# Run tests
make test-arbor

2. Minimal example

// Define your solution type
typedef struct { int *assignment; int n; double cost; } MySolution;

// Implement 6 callbacks: copy, free, cost, size, validate, is_better
// Write at least 1 destroy + 1 repair operator

// Create, register, solve
ARALNSParams p;
ar_alns_params_default(&p);
p.max_iterations = 1000;

ARALNSContext *ctx = ar_alns_create(&p, &ops, NULL);
ar_alns_add_destroy(ctx, "random", my_destroy, NULL, 1.0);
ar_alns_add_repair(ctx, "greedy", my_repair, NULL, 1.0);

void *best = NULL;
ar_alns_solve(ctx, initial, &best);
ar_alns_free(ctx);

Common questions

Why separate Arbor from Surge?

Testability and reuse. Arbor's 66 tests validate the ALNS framework independently of any problem domain. If we build a scheduling module tomorrow, it registers its own operators and gets adaptive weight learning, SA acceptance, restarts, and per-operator statistics for free. Surge focuses purely on VRP domain logic.

Which acceptance criterion should I use?

Start with Simulated Annealing and use ar_alns_calibrate_sa() to auto-tune. SA is the most versatile criterion — it explores aggressively early (high temperature) and converges late (low temperature). Use RRT for quick diversification with a known quality threshold. Use Great Deluge for slow, steady convergence. Use improving-only for final polishing after SA has explored.

How many operators should I register?

More is better, up to a point. Surge uses 18 operators. The adaptive weights handle operator selection — poor operators get weight ≈0.01 and rarely fire. Minimum: 1 destroy + 1 repair. For competitive results on VRP: 6–12 destroy + 3–6 repair operators covering random, worst, related, and structural removal.

What about genetic algorithms or tabu search?

ALNS is the state-of-the-art metaheuristic for vehicle routing and scheduling problems. Ropke & Pisinger (2006) showed it consistently outperforms tabu search and GA on VRPTW. Surge also implements SREX crossover (population-based) alongside Arbor's ALNS — the two approaches complement each other.

What license?

AGPLv3 with a Trucking Exception. Same terms as all OTTO modules.