brooom — VRP solver in Rust (alternative to Vroom)
==================================================

Status symbols:
  [x] done    [~] partial    [ ] not started

------------------------------------------------------------
CORE — DATA MODEL AND PROBLEM TYPES
------------------------------------------------------------
[x] Problem structure (jobs, shipments, vehicles, matrices)
[x] Job with location, service time, time windows, amount, skills, priority
[x] Shipment (pickup + delivery pair, same route)
[x] Vehicle with start/end, capacity, skills, time window, cost, speed
[x] Multidimensional capacity (vectors)
[x] Time windows (multiple per job)
[x] Service and setup time
[x] Open trips (vehicle does not return to depot — omit `end`)
[x] Skills / requirements (job must match the vehicle's skills)
[x] Priority (ordering at insertion time)
[x] Max travel time / distance / tasks per route
[x] Speed factor per vehicle
[x] Fixed cost and per-hour cost

------------------------------------------------------------
DISTANCE / DURATION MATRIX
------------------------------------------------------------
[x] Matrix trait (durations + distances)  -> trait MatrixSource
[x] Haversine fallback (no external service)
[x] OSRM table-API client (HTTP)
[ ] Valhalla matrix client
[ ] OpenRouteService matrix client
[x] User-supplied custom matrix (in input under "matrices")
[ ] Caching matrices to disk
[x] Profile selection (vehicle.profile -> OSRM /table profile)
[ ] Geometry/polyline fetch per route (extra call)

------------------------------------------------------------
SOLUTION ALGORITHMS
------------------------------------------------------------
[x] Solution representation (routes + unassigned)
[x] Greedy cheapest insertion (Solomon-style sequential)
[~] Parallel insertion — only the greedy variant so far
[ ] Regret-k insertion (k=2,3) — IMPORTANT for closing the cost gap to Vroom
[ ] Multiple starting solutions with varied parameters
[x] Local-search framework (per-task best-improvement with don't-look bits)
[x] Operator: Relocate (Or-opt 1-3 nodes, intra and inter)
[x] Operator: 2-opt intra-route (segment reversal)
[x] Operator: Exchange inter-route (swap two single nodes)
[ ] Operator: Cross-exchange (swap segments between routes)
[ ] Operator: Reverse 2-opt
[ ] Operator: Mixed exchange
[ ] Operator: Tour split / merge
[ ] Operator: Priority replace (swap a low-priority node for a high-priority one)
[x] Forward time slack + cumulative load precompute (eval.rs)
[x] O(1) probe for insertion feasibility + Δ-cost
[x] Flat-layout load arrays (positions × dim) — memory/cache
[x] Don't-look bits in local search — customers that yielded no improvement are skipped
[x] Granular neighborhoods (Toth–Vigo, K=20) — skip everything outside the top-K
[x] i32 in Matrix (was i64) — half the memory footprint
[x] Bounded top-K probe storage (BinaryHeap) — caps insertion-time memory
[x] Streaming JSON parser + drop matrices from the problem after build
[x] Reusable load buffer (thread_local) in the evaluator — zero alloc per candidate
[ ] Multi-thread: parallel starting solutions with rayon
[ ] Time budget (--exploration-level / --threads)
[ ] Warm start from a predefined plan

------------------------------------------------------------
CONSTRAINT EVALUATION
------------------------------------------------------------
[~] Forward time slack — TW check is done linearly, not with precompute
[~] Capacity precomputation per route
[x] Skill-mask check
[x] Max-distance / max-load / max-tasks
[x] Pickup-precedence check for shipments

------------------------------------------------------------
INPUT/OUTPUT (Vroom-compatible JSON)
------------------------------------------------------------
[x] Read Vroom JSON input (jobs, shipments, vehicles, matrices)
[x] Write Vroom JSON output (routes, summary, unassigned)
[x] Step per route (start, job, pickup, delivery, end)
[x] Cost and duration summary
[ ] Geometry in output (optional)
[ ] Plan mode (no optimisation, evaluate a given plan)
[x] Pretty-print and compact output

------------------------------------------------------------
CLI
------------------------------------------------------------
[x] `brooom` CLI built on clap
[x] -i input.json, -o output.json
[~] -p max-passes (no real threads/exploration yet)
[x] -r routing (haversine|osrm)
[x] --osrm-host / --osrm-profile
[ ] -g include geometry
[ ] -l time-limit
[x] Stdin/stdout mode

------------------------------------------------------------
SERVER MODE (like vroom-express)
------------------------------------------------------------
[ ] HTTP server with axum/actix
[ ] POST /  -> solve problem
[ ] /health endpoint
[ ] CORS config

------------------------------------------------------------
BENCHMARK AGAINST VROOM 1.15 (synthetic R1 instances, Euclidean matrix)
------------------------------------------------------------
Speed (seconds, smaller is better):
  N=50    Vroom 0.09s   brooom 0.025s   = 3.8×
  N=100   Vroom 0.36s   brooom 0.035s   = 10.5×
  N=250   Vroom 2.28s   brooom 0.091s   = 25.0×
  N=500   Vroom 11.80s  brooom 0.462s   = 25.5×
  N=1000  Vroom 59.64s  brooom 3.227s   = 18.5×

Memory (peak RSS, smaller is better):
  N=50    Vroom 5.4 MB    brooom 1.8 MB     = 3.0× smaller
  N=100   Vroom 11.1 MB   brooom 2.4 MB     = 4.6× smaller
  N=250   Vroom 39.2 MB   brooom 3.9 MB     = 10.1× smaller
  N=500   Vroom 104.0 MB  brooom 8.8 MB     = 11.8× smaller
  N=1000  Vroom 320.5 MB  brooom 28.7 MB    = 11.2× smaller

Cost (lower is better):
  N=50    Vroom 1554   brooom 1692   (+9%)
  N=100   Vroom 2466   brooom 2750   (+12%)
  N=250   Vroom 4472   brooom 5841   (+31%)
  N=500   Vroom 7132   brooom 8654   (+21%)
  N=1000  Vroom 11748  brooom 15174  (+29%)

Status: 5-50× speed AND 3-12× less memory at every size. A 9-31 % cost
gap remains — next round to close it:
  1) Regret-2 insertion → better starting solution
  2) Cross-exchange operator in local search
  3) Multi-threaded parallel multi-start

------------------------------------------------------------
QUALITY / OPERATIONS
------------------------------------------------------------
[x] Structured error handling (thiserror)
[~] Logging — only eprintln on `-v` so far (tracing is imported)
[x] Unit tests for matrix/haversine
[x] Integration test: CVRP, capacity, TW, skills, shipment, LS validity
[x] Compiles on stable Rust
[~] cargo fmt — done; clippy not run
[x] Sample dataset under examples/oslo_5jobs.json
