Routing

Answer-first: Combinatorial fleet routing at scale requires decoupling road-network distance calculation from vehicle assignment. By pairing an in-memory OSRM table engine with an Adaptive Large Neighborhood Search (ALNS) solver written in Go 1.24, engineering teams can solve Capacitated Vehicle Routing with Time Windows (VRPTW) for 500+ stops in under 800ms while eliminating 99% of third-party map API costs. Key Architectural Takeaways NP-Hard Complexity Separation: Point-to-point routing (A*, Dijkstra, Contraction Hierarchies) solves the shortest path between 2 physical nodes in O(E + V log V) time. Combinatorial vehicle routing (CVRP/VRPTW) optimizes the permutation of N stops across K heterogeneous vehicles in O(K * N!) search space. Combining them into a single monolithic loop causes catastrophic CPU bottlenecks. ALNS as the Industry Gold Standard: Exact solvers (Branch-and-Cut, Mixed Integer Linear Programming) fail when N > 40. Adaptive Large Neighborhood Search (ALNS) dynamically orchestrates coupled Destroy (Shaw, Worst, Random) and Repair (Regret-k, Greedy) heuristics with Simulated Annealing cooling, converging to within 1% to 3% of the theoretical global optimum. Zero-Allocation Memory Topology: High-frequency solver loops incur severe Garbage Collection (GC) pauses when using nested slices ([][]float64). Laying out N x N cost matrices into single contiguous 1D arrays ([from * N + to]) and recycling candidate states via sync.Pool maximizes CPU L1/L2 cache line hits (64 bytes) and sustains sub-millisecond execution. FinOps ROI: Self-hosting an in-memory OSRM Table cluster paired with a Go ALNS microservice reduces fleet mileage by 15% to 25% and saves tens of thousands of dollars monthly compared to quadratic O(N^2) billing on Google Routes Matrix APIs. 1. Problem Taxonomy: From TSP to Multi-Depot VRPTW Before writing a single line of optimization code, systems architects must classify the operational constraints of their logistics domain. Real-world delivery networks rarely resemble the idealized Traveling Salesperson Problem (TSP). ...

Series Index | Next Chapter: Part 1: Core Algorithms (A*, Dijkstra) Visualized → Answer-first: High-concurrency routing architectures decouple fast graph-traversal engines (OSRM, GraphHopper) from spatial indexing pipelines (Uber H3) using a Go 1.25 API gateway and Redis semantic caching. This architecture resolves $100 \times 100$ distance matrices in under 22ms while reducing graph calculation load by 92% compared to un-cached routing engines, maintaining sub-30ms P99 latency at 50,000 QPS. 1. The Engineering Challenge: The $O(N^2)$ Distance Matrix Bottleneck in Logistics In high-velocity on-demand logistics platforms (food delivery, ride-hailing networks, rapid e-commerce fulfillment), algorithmic efficiency centers entirely on solving the Vehicle Routing Problem (VRP). Unlike consumer navigation applications where a single user requests a single turn-by-turn route from point A to point B, dispatching algorithms must compute pairwise travel distances and travel times across dynamic fleets and orders simultaneously. ...

Series Index | ← Previous Chapter: Executive Summary | Next Chapter: Part 2: Zero to Hero Environment Setup → Answer-first: For large-scale Distance Matrix computations $O(N^2)$, single-source Dijkstra combined with Contraction Hierarchies (CH) substantially outperforms A* by generating an entire shortest-path tree in a single pass. Edge-based graph transformations accurately enforce turn prohibitions, while Customizable Contraction Hierarchies (CCH) enable sub-3s dynamic traffic weight updates with sub-millisecond query latencies. 1. The Logistics Reality: Why A* Fails at Distance Matrices In introductory computer science curricula and standard textbook algorithms, software engineers are routinely introduced to a widely accepted rule of thumb: “A* is strictly superior to Dijkstra because its directional heuristic guides the search toward the destination, pruning irrelevant graph exploration.” ...

Answer-first: MCP Gateway architecture solves N×M connectivity fragmentation by decoupling AI agent clients from distributed tool providers through persistent SSE connection multiplexing, Redis Token Bucket rate limiting, and dynamic tool schema routing. In production, a Go-based gateway delivers sub-4ms P99 proxy latency while protecting downstream backends with distributed circuit breakers and centralized OAuth 2.1 token introspection. ← Part 3: Identity & AuthN | Next Chapter: Part 5: Production Security & OWASP MCP Top 10 → ...

← Previous Chapter: Part 6: Building an Allocation Engine in Go | Series Hub | Next Chapter: Part 8: Intelligent Order Release → Prerequisite: Foundations in graph theory (Dijkstra, A* search, Contraction Hierarchies), geographic information systems (GIS, coordinate projections), and distributed caching topologies. Answer-first: Accurate order allocation relies on sub-millisecond road distance and transit time calculations rather than inaccurate straight-line Haversine spherical approximations. Deploying localized Open Source Routing Machine table engines paired with Uber H3 spatial indexing resolution-7 partitions and Redis geospatial semantic caches allows logistics platforms to resolve 100-by-100 origin-destination distance matrices in under 8 milliseconds without external API dependencies. ...

Answer-first: Production-grade geospatial routing architectures require decoupling graph-traversal engines (OSRM, GraphHopper) from spatial partitioning indexes (Uber H3, Google S2) via high-concurrency Go 1.25 API gateways. This 9-part masterclass details the complete engineering blueprint for building an in-memory routing cluster with sub-5ms point-to-point queries, 50,000 QPS distance matrices, Redis semantic caching, and zero-downtime map rollouts on Kubernetes, reducing cloud map spend by 99.7%. 1. Production Reality: The Economics and Latency Wall of Commercial Mapping APIs In on-demand delivery platforms, ride-hailing networks (Grab, Uber, GoTo), and rapid-fulfillment e-commerce fleets (ShopeeXpress, Amazon Logistics), software survival hinges on solving one continuous question: “What is the exact travel duration, road distance, and route geometry between thousands of moving vehicles and pending pickup orders?” ...

Self-Hosting GraphHopper on Kubernetes with OSM Data Answer-first: Self-hosting GraphHopper routing engines on Kubernetes uses initContainers for S3 graph cache hydration, JVM heap tuning, and HPA auto-scaling to process heavy routing traffic. Sizing pods with 4GB off-heap memory and 1GB JVM heap for country-level OpenStreetMap data achieves sub-50ms routing queries while cutting commercial map API costs by over 95%. GraphHopper is arguably the most capable open-source routing engine available — it supports Contraction Hierarchies (CH) for sub-millisecond route queries, custom vehicle profiles, turn restrictions, and the full OpenStreetMap road network. The problem most teams encounter is not the algorithm; it is the operational challenge of running it in Kubernetes: loading a large OSM PBF file, sizing JVM memory correctly, handling the long CH pre-processing startup time, and updating map data without downtime. ...

OSRM Shared Memory on Kubernetes: Live Traffic Updates with Zero-Downtime Answer-first: Operating OSRM on Kubernetes with live traffic updates uses POSIX shared memory (/dev/shm), atomic memory pointer swapping via osrm-datastore, and Multi-Level Dijkstra (MLD) cell customization without restarting routing pods. Sharing a single 15GB graph across 10+ worker pods cuts node RAM usage by 85%+ while delivering sub-2ms P99 matrix latencies and zero-downtime speed updates. The Challenge of Operating Large-Scale OSRM on Kubernetes Normally, the osrm-routed process loads the entire binary map file directly into its Heap Memory. For massive files weighing tens of gigabytes, a single Kubernetes Pod can take anywhere from 5 to 10 minutes to finish loading before it becomes healthy and ready to serve traffic. This creates two fatal operational issues: ...