Vehicle routing & tour optimisation

Dispatchers at couriers, wholesalers, waste collectors and home-care services still build daily tours by hand or with fixed-route habits. Vehicle routing solvers combined with ML-predicted travel and service times assign stops to vehicles and sequence them under time windows, capacity and driver-hour rules, and re-plan during the day. Typical result: fewer kilometres and vehicles for the same service level, plus lower emissions and more reliable ETAs.

Problem & value

• Today: planners use spreadsheets, map tools or the experience of senior drivers. Plans are static, ignore real service times, and break when a rush order, traffic jam or breakdown hits.
• Why it is hard: the Vehicle Routing Problem (VRP) and its variants (time windows, pickup & delivery, heterogeneous fleet, multi-depot) are NP-hard; good heuristics matter at 100–10,000 stops.
• AI value: (1) metaheuristic/MIP/CP solvers find high-quality plans in seconds to minutes; (2) ML replaces guessed inputs (travel time by hour, service time per customer, no-show risk); (3) learned or hybrid solvers speed up large instances; (4) LLM copilots let planners state rules in plain language (see OPT-018).
• Benefit evidence: route optimisation is one of the best-documented operations-research successes (e.g. UPS ORION, described in INFORMS Franz Edelman work) [6]. Savings depend heavily on baseline quality; treat vendor percentage claims as pilot hypotheses and measure them on your own historical days.

Variants

• Last-mile parcel & food/grocery delivery: many stops, narrow time slots, customer-chosen windows.
• Distribution / wholesale / field sales: fewer, larger stops, capacity and loading constraints (OPT-012).
• Waste collection, winter service, municipal rounds: arc routing, often public sector.
• Service and care tours (home care, technicians): skills and appointments, see OPT-019.
• Pickup & delivery / FTL-LTL: paired stops, precedence; trucks subject to EU driving-time rules.
• Electric fleets: range and charging stops, see OPT-021.
• Dial-a-ride / demand-responsive: see OPT-028.
• School bus and public tendering: fixed-schedule variants, see OPT-013.
• Private use: errand and trip chaining in map apps (small multi-stop planners); trivial scale.

How it works

1. orders + fleet + depots
2. geocoding & address cleaning
3. travel-time matrix (road network, traffic profiles; ML-corrected)
4. constraint model (time windows, capacity, skills, breaks, driver-time law, cost function)
5. solver (construction heuristic
6. local search / HGS / LNS; or MIP/CP for small cases)
7. planner review (what-if, manual locks, overrides)
8. dispatch to driver app / telematics
9. live tracking
10. re-optimisation on events (new order, delay, breakdown)
11. feedback of actuals into ML

• Core is classical optimisation: hybrid genetic search (HGS), adaptive large neighbourhood search, constraint programming and GPU-parallel heuristics. ML does not replace the solver in most products; it supplies better inputs and sometimes warm starts.
• ML components: travel-time and service-time regression from telematics (gradient boosting), ETA models (PRED-018), demand forecasts for pre-planning, and neural/RL construction heuristics as research-grade accelerators.
• Human-in-the-loop: planners approve plans, lock customers to drivers, and handle exceptions; drivers can reject or re-sequence stops with logged reasons that become training data.

Data preparation

Routing needs clean master and order data: customer addresses, time windows, service times, vehicle and driver data. These typically live in the ERP or TMS, in dispatcher Excel sheets and in telematics portals; some knowledge sits only in drivers' heads (access restrictions, ramp heights, key handling).

Typical gaps are unverified or duplicate addresses, missing geocodes, service times that are guesses, outdated vehicle capacities and driver rules kept on paper.

Preparation steps: - Export orders, fleet and customer data (see PREP-005) and consolidate duplicates. - Geocode and validate addresses with a geocoder or OSM-based tool; fix failures manually. - Derive real service and travel times from 3-6 months of GPS/telematics history instead of estimates. - Record local knowledge as structured stop attributes (time window, access notes) via dispatcher and driver interviews (PREP-016). - Define who owns master-data quality (PREP-004).

Rough share of effort: about 30-40 percent of the project. Data requirements are modest, but address and time quality decides plan quality. Run the data readiness check from GUIDE-003 first.

Implementation paths

Which path for whom

• SMB: Path A. Mature, EU-hostable tour-planning SaaS exists at per-vehicle prices and the routing problem is standard.
• Enterprise: Path B. Routing is a core cost lever, so a solver on own cloud with TMS/ERP integration avoids per-stop fees and lock-in.
• Developer: Path C. OR-Tools or PyVRP run on HW1 and give full control over constraints and costs.
• Public sector: Path C. Open-source solvers on sovereign infrastructure ease procurement and keep citizen addresses (waste, home care) in-house.

Path A — Buy (recommended for most SMBs and mid-market)

• Route planning & dispatch SaaS: Routific, Circuit, OptimoRoute, Onfleet, Locus, Track-POD, Descartes, Trimble, Omnitracs, Bringg; ERP/TMS modules from SAP TM and Oracle.
• EU vendors: PTV Group (PTV Route Optimiser, PTV Developer, DE), Quintiq/Dassault (planning, NL/FR), TourSolver / Mapotempo (FR), Timefold (BE) as solver platform; ORTEC (NL).
• Choose A when: under a few hundred vehicles, standard constraints, no unusual rules. Check: telematics integration, EU data hosting, driver app, driver-time law support, API access.

Path B — Build on cloud APIs

• Route-optimisation APIs: Google Maps Platform Route Optimization API, Microsoft/Azure Maps routing, HERE Tour Planning API (HERE is EU-headquartered), PTV Developer APIs, TomTom Routing and matrix APIs, Mapbox Optimization API (small VRPs).
• Cloud solver services: Gurobi, FICO Xpress or Hexaly (FR) hosted; NVIDIA cuOpt as service.
• Orchestration: n8n/Airflow job feeding orders, matrix call, solver, push to driver app; an LLM layer can translate planner requests into constraint changes (OPT-018).
• Choose B when: you need custom rules or embedding in your own product.

Path C — Self-host (open source)

• Solvers: Google OR-Tools (routing library, CP-SAT), PyVRP (HGS-based, strong benchmark results), VROOM (fast C++ engine), Timefold Solver (Java/Kotlin/Python), jsprit, LKH-3, NVIDIA cuOpt (open-sourced GPU solver), HiGHS for MIP parts.
• Routing/matrix engine: OSRM, Valhalla or GraphHopper on OpenStreetMap data (Geofabrik extracts).
• Hardware: HW1 (CPU server) suffices for most fleets; GPU (HW2) only for cuOpt-scale instances.
• Ops effort: map-data refresh, traffic profiles, monitoring of solve times; 1 engineer part-time.

Path D — Custom training

Worth it for very large, repetitive problems (national parcel networks) or special constraints. Train service-time and travel-time models on 6–12 months of telematics; research on neural combinatorial optimisation and RL-based construction (e.g. attention-model routing, learned HGS components) can cut solve time but must beat tuned classical solvers on your data to justify it.

State of the art (2026)

• Benchmarks: the DIMACS Vehicle Routing Challenge and the Solomon/Gehring-Homberger/X instances show HGS-type and LNS solvers (PyVRP, HGS-CVRP, FILO) remain hard to beat; learned solvers help mostly on speed and warm starts [3].
• GPU optimisation: NVIDIA open-sourced cuOpt, parallelising VRP heuristics for large instances [2].
• Dynamic and stochastic routing: re-optimisation within seconds on new events is standard in commercial tools; predictive stop-time models improve plan realism.
• LLM copilots: natural-language what-if and constraint authoring on top of solvers; LLMs should translate to solver models, not "solve" routes themselves (poor at combinatorial optimality).
• Limits and failure modes: bad geocodes, wrong service times, ignored tacit driver knowledge (access restrictions, parking), plan instability (small changes flip all routes), and over-optimisation that leaves no slack for delays.

Shared resources & combinations

• Same stack (optimization-solver + time-series): OPT-019 technician dispatch, OPT-028 ridepooling, OPT-003 workforce scheduling, OPT-005 replenishment (feeds delivery volumes).
• Upstream: PRED-018 ETA prediction, OPT-005 inventory, DOC-006 transport documents.
• Downstream/related: OPT-021 EV charging constraints, OPT-012 load planning, VIS-028 in-cabin monitoring (separate, high-sensitivity, see risks), ROBO-020 delivery robots.
• Travel-time matrices and map data are reusable across all routing use cases.

Effort, cost & KPIs

• Path A: days to weeks; per-vehicle or per-stop monthly pricing is typical.
• Path B: 1–3 months incl. integration with order management and driver app.
• Path C: 2–4 months; low hardware cost, main cost is engineering and map operations.
• KPIs: total km and drive hours, vehicles used, stops per route-hour, on-time/in-window rate, first-attempt delivery rate, plan-vs-actual deviation, CO2 per parcel, planner time per day, plan acceptance rate by drivers.

People & change

Involve management (budget, KPIs) and the dispatch lead from the start; dispatchers are the key users and should co-define rules. Bring in IT for TMS/ERP and telematics integration, data owners for address and customer master data, and the works council early.

Works council: depends. Tour planning alone is not monitoring, but driver GPS, ETAs and on-time rates make the system objectively suited to monitor behaviour or performance, so co-determination under §87(1) no. 6 BetrVG usually applies; §90(1) no. 3 requires timely information about AI-planned work processes. Public sector: staff council. Agree purposes (no individual performance ranking) in a works agreement (GUIDE-004).

Data protection: driver location data and private-customer addresses are personal data; involve the DPO, conclude an AVV with the vendor and check whether a DPIA is needed (GUIDE-005).

AI literacy: provide short training for dispatchers and drivers on what the solver optimises and where it errs, supporting AI literacy as Art. 4 AI Act requires (GUIDE-006).

Communication and pilot: start with one depot or tour group, compare plans against real tours, and address typical concerns (drivers fear tighter control, dispatchers fear being replaced). Dispatchers keep the final say and can override any tour; see GUIDE-008.

Risks, regulation & compliance

• EU AI Act: typically minimal risk. Watch for the line to Annex III point 4 (employment): if the system allocates tasks based on individual behaviour or personal traits and monitors or evaluates workers (e.g. driver scoring that drives task allocation), it may be high-risk [4]. Keep routing separate from performance evaluation. No Art. 5 issue for routing itself; AI literacy (Art. 4) applies.
• GDPR: customer addresses, delivery windows and driver GPS traces are personal data; works council co-determination in Germany (BetrVG §87) for driver tracking; purpose limitation, retention limits on GPS data, DPIA for continuous location tracking [5].
• Sector rules: EU driving-time and rest rules (Regulation (EC) 561/2006 and amendments) must be hard constraints in the model; city access restrictions and low-emission zones; Working Time rules.
• Risks and mitigations: unsafe or unrealistic plans (add slack, driver feedback loop), unfair workloads (fairness constraints), vendor lock-in (open data formats, export of constraints), map-data licence compliance (OSM ODbL attribution).

Getting started

1. Export 30–60 days of real orders, stop times and GPS traces; compute baseline km, hours and on-time rate.
2. List hard constraints (time windows, vehicle types, driver-time law) and soft ones (preferred driver).
3. Re-plan 5–10 historical days with two Path A tools or OR-Tools/PyVRP and compare with the actual tours.
4. Pilot on one depot with planners able to override; log overrides and driver feedback.
5. Replace guessed service/travel times with ML estimates from telematics, then add live re-optimisation.

Sources

1. Google OR-Tools — Vehicle Routing — https://developers.google.com/optimization/routing
2. NVIDIA cuOpt — https://github.com/NVIDIA/cuopt
3. PyVRP — https://github.com/PyVRP/PyVRP
4. Regulation (EU) 2024/1689 (AI Act), Annex III — https://eur-lex.europa.eu/eli/reg/2024/1689/oj
5. EDPB — Guidelines 01/2020 on connected vehicles and mobility applications — https://www.edpb.europa.eu/our-work-tools/our-documents/guidelines/guidelines-012020-processing-personal-data-context_en
6. INFORMS — UPS ORION, Franz Edelman Award — https://www.informs.org/Impact/O.R.-Analytics-Success-Stories/UPS-On-Road-Integrated-Optimization-and-Navigation-ORION-Project
7. VROOM project — https://github.com/VROOM-Project/vroom
8. Timefold Solver — https://github.com/TimefoldAI/timefold-solver
9. Regulation (EC) 561/2006 on driving times and rest periods — https://eur-lex.europa.eu/eli/reg/2006/561/oj