Design a service that, for a fleet of vehicles and a set of stops, computes optimized multi-stop routes (a vehicle-routing problem with time windows and capacity) as an asynchronous batch job. Clients submit a job and later collect per-vehicle routes.

Operating context. Logistics customers submit optimization jobs both in nightly bulk and intraday. A job carries stops (each with a time window and demand) and vehicles (each with a capacity and shift). Jobs are large and compute-heavy; the biggest reach thousands of stops and hundreds of vehicles, and a run can take minutes. The client does not block: it gets a job id and polls or subscribes for the result. A travel-time matrix between stops must be computed before the solver runs.

Out of scope. The exact optimization algorithm inside the solver, the road-distance engine that answers point-to-point travel times (assume a matrix/distance service exists), the driver dispatch app, and real-time in-trip re-routing. Assume those are separate systems.

What to produce. A high-level architecture covering: job submission, queueing, and the async result contract; how the O(n²) travel-time matrix is computed, cached, and sharded for a large job; the solver worker pool, how a very large job is split and how long-running solves are checkpointed; autoscaling workers to the queue; durable storage of inputs, intermediate matrices, and results with retention; and idempotency, cancellation, and retry semantics. Sketch the components and the lifecycle of one job from submit to result; we will probe specifics in checkpoints.