Purpose: Answer the question a dispatcher actually has at 6am — I have 40 deliveries, five trucks, a load limit and a delivery window on every drop, and drivers who go home at 4pm. Which truck does what, in what order?
Domain: Last-mile logistics and field service. The problem is the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW): depot, stops with demand and a [readyTime, dueTime] window, per-vehicle capacity, a shift horizon, and an objective of total distance plus a fixed cost per vehicle used.
Dataset: Three deterministic delivery scenarios generated from a fixed-seed LCG over the real 2,530-node Redlands OpenStreetMap road network. Stops sit on actual road-network nodes, so snapping is exact and every stop is genuinely reachable.
Architecture: The client posts only the scenario — depot, stops, fleet parameters, about 2 KB. The server fetches the graph, builds the road-distance matrix, solves, and expands every solved leg back into a street-following polyline. The existing Route Planner page downloads a 425 KB graph and re-uploads it on every request; this page deliberately does not.
Statelessness: No database and no persistence. Scenarios are generated in code, the graph is a compile-time constant, and the solver is a pure function of its inputs, so every run is reproducible.
Algorithm
Distance matrix: The depot and every stop snap to the nearest road node, then a single (n+1)² road-distance matrix is built by Graph_ComputeDistanceMatrix, which constructs the adjacency structure once and runs n+1 Dijkstras over it. Doing this as n+1 separate shortest-path calls would rebuild 6,374 adjacency entries every time.
Distance to time, outside the search: Travel minutes are km ÷ 40 × 60, computed after the graph search, never inside it. A*'s haversine heuristic is admissible only because edge costs are along-road kilometres; put minutes on the edges and A* silently starts returning suboptimal paths.
Phase 1 — Clarke-Wright parallel savings: Start with one route per stop, score every pair by s(i,j) = d(0,i) + d(0,j) − d(i,j), sort descending, and merge route ends while capacity and every window still hold. Only end-to-end joins are considered: reversing a leg is free in a symmetric distance problem but not once time windows are involved.
Phase 2 — local search:2-opt within each route reverses a segment to remove a crossing. Or-opt relocates a run of one to three consecutive stops into any position of any route, including another vehicle's. Both accept a move only if it lowers the objective and leaves every affected route feasible.
First improvement, not best improvement: The search takes the first improving move it finds rather than scanning for the best one. It converges in far fewer distance evaluations, and at 40–120 stops the solution-quality difference is small. At larger sizes, or with a stronger neighbourhood, best-improvement starts to earn its cost.
Feasibility walk:t += travel; t = max(t, readyTime); if (t > dueTime) infeasible; t += serviceTime, then check the return leg against the shift end. Early arrival waits; late arrival fails. This asymmetry is the part that is easy to get wrong.
Objective:Σ route distance + vehicleFixedCost × routes used. Without the fixed cost the solver happily spreads work across every truck available; the fixed cost is what makes it choose four over five.
Fleet truncation happens last: If construction produces more routes than there are trucks, the surplus is dropped after local search, not before. Or-opt consolidates routes, so truncating early strands stops the search was about to absorb — in the tight-windows preset that was the difference between two unserved stops and none.
API Layer
Endpoints:GET /api/v1/fleet/scenario?preset=fullday and POST /api/v1/fleet/optimize.
Versioning:Asp.Versioning with the version in the route template, matching every other API in the portfolio.
Payload guards:[RequestSizeLimit(4_000_000)] on the POST and [EnableRateLimiting("expensive")] on the controller — a solve is an NP-hard search plus a few dozen A* expansions.
Caching: Scenarios are deterministic, so GET /scenario carries [ResponseCache(Duration = 3600)]. VaryByQueryKeys is deliberately absent — it throws a 409 unless the response-caching middleware is registered, which this app does not do; caches key on the full URL and the preset lives in the query string anyway.
Infeasibility is an answer, not an error: A stop no vehicle can reach inside its window comes back in UnservedStopIds with Feasible = false in a normal 200. Only malformed input — a demand above capacity, a shift that ends before it starts — is a 400.
Honest instrumentation: The response carries MatrixBuildMs, SolveMs and PathExpandMs separately. At demo sizes the matrix build and the polyline expansion each cost more than the solve, which is worth knowing before optimising the wrong thing.
Error contract: Only ArgumentException is caught, returning 400 with { "error": "..." }. The service's validation messages are therefore the public API contract and are written as user-facing text.
Services and Native Boundary
Kernel:vrp_solver_kernel, a C++20 shared library exposing a single export, Vrp_SolveCvrptw, through a stable C ABI with #pragma pack(push, 8) structs and status-code returns.
Where the boundary sits: The kernel receives two flat matrices and a stop array and returns route membership as zero-based stop indices in the flat-buffer idiom — one contiguous index buffer plus per-route lengths. Arrival times, per-route distances, unserved stops and the road-following geometry are all derived in C#, where they stay readable and unit-testable.
Marshalling: Blittable [StructLayout(Sequential, Pack = 8)] structs with preallocated managed output arrays and explicit [In]/[Out] direction attributes. Native code never allocates across the boundary.
Managed fallback:VrpSolverNativeBridge.IsAvailable gates the native path. The managed solver mirrors the kernel move for move — same savings ordering, same tiebreaks, same acceptance epsilon — so both paths return the identical solution. The fallback is production behaviour, not a test convenience: the deployed container does not build the native libraries.
Measured speedup: Native is about 2.3× faster than the managed fallback, with bit-identical solutions. Best of five warm runs on the same machine, solve time only (matrix construction and polyline expansion excluded):
Native versus managed benchmark results for the vehicle routing solver kernel, by workload.
Workload
Native
Managed
Speedup
60 stops, 5 local-search passes
0.64 ms
1.66 ms
2.59×
90 stops, 31 local-search passes
4.89 ms
11.41 ms
2.33×
120 stops, 26 local-search passes
7.33 ms
16.78 ms
2.29×
Final objective, initial objective, total distance and the ordered stop sequence all match exactly across both paths on all three shipped presets and four synthetic workloads — the two implementations make identical accept/reject decisions, not merely similar ones.
Where the speedup came from — and where it did not: The first working kernel was 1.7× slower than managed C#, because the move operators allocated a fresh std::vector for every candidate route and the .NET nursery allocator beats malloc at that game. Hoisting three scratch buffers out of the hot loops and reusing their capacity via assign turned a 1.7× loss into a 2.3× win. There is no SIMD and no threading in this kernel; the entire gain is allocation discipline plus a tighter inner loop over raw double* rather than bounds-checked arrays.
Compiled with /fp:precise, deliberately: Every other kernel in this portfolio uses /fp:fast. This one cannot: the solver's accept/reject test is a floating-point comparison against an epsilon, and a reassociated sum can flip a decision and send the search down a different branch. Determinism across the native and managed paths was worth more than the last few percent.
Known wart:IsNativeInvocationException includes InvalidOperationException, which is exactly what the negative-status check throws. A genuine native error therefore logs one warning and silently degrades to managed rather than surfacing. This is consistent across every kernel here and is a deliberate availability-over-visibility trade, but it means native failures are invisible in production metrics.
Engineering Decisions and Tradeoffs
Scenario in, routes out: The client never sees the road graph. Sending the scenario instead of the network cut the request from roughly 425 KB to about 2 KB and moved snapping, matrix construction and leg expansion to the server where they belong. It also means the client cannot desynchronise from the network the server actually routed on.
Stateless kernel, no graph handle: The kernel takes matrices, not a graph. A reusable Graph_Create/Graph_Destroy handle would let the adjacency structure survive across calls and is the single highest-leverage future change, but it breaks the stateless-kernel convention every other library here follows, so it stays a conversation rather than a commit.
Presets tuned from measured behaviour, not round numbers: The three scenarios were calibrated by running them. Morning uses 2 of 3 vans and improves 1.0% — with loose windows Clarke-Wright is already close to optimal. Full day uses 4 of 5 trucks and improves 14.8%. Tight windows needs all 6 trucks for the same 40 drops and improves 14.1%. That contrast is the whole demonstration: narrow windows cost trucks, not kilometres.
Local search never regresses: Every recorded objective is monotonically non-increasing by construction — a move is applied only when it strictly lowers the objective. That is a real limitation, not just a safety property: pure descent cannot escape a local optimum.
Waiting is free, lateness is fatal: Arriving early parks the driver until the window opens and costs nothing in this model. That matches parcel delivery; it does not match paid driver hours, where waiting is real money and belongs in the objective.
Leaflet, not hand-built SVG: The other compute demos here draw their own SVG to avoid a tile dependency. Routes that trace real streets only mean something on a real basemap, so this page takes the dependency — but the convergence chart and the schedule timeline are still hand-built SVG using CSS custom properties, so both follow the light/dark theme.
The schedule is the proof: The timeline is the view a dispatcher actually reads, and it is also the artifact that proves the time windows are respected — each solid block has to land inside its pale band. ArrivalMinutes is emitted parallel to StopIds precisely so this is checkable rather than asserted.
Interview Discussion Points
CVRPTW is NP-hard. What does that actually mean for a dispatcher who needs an answer in 30 seconds, and how do you decide when to stop searching?
Clarke-Wright is a construction heuristic and 2-opt/Or-opt is local search. Why do you need both, and what happens if you skip the construction phase?
The solver uses first-improvement rather than best-improvement. What is the tradeoff, and when would you switch?
Local search gets stuck in local optima. How would you escape — simulated annealing, tabu search, large neighbourhood search, or a genetic algorithm? What does each cost in implementation complexity?
Distance comes from the real road network, but travel time is distance ÷ 40 km/h. What breaks when you introduce time-of-day traffic, and why can't you just put minutes on the graph edges?
The distance matrix is (n+1)² Dijkstras. At what stop count does matrix construction dominate solve time, and what would you do about it?
The first version of this kernel was slower than the C# it replaced. How would you have caught that before shipping, and what does it say about when to reach for native code at all?
How would you handle a driver going sick at 10am with half a route completed?
What changes if stops can be served by any of three depots instead of one?
Waiting for a window to open is free in this objective. What breaks when you price driver hours, and how would you model a lunch break?