Route Optimization

Booking decides which day a customer is served and roughly when. Route optimization decides everything else: which technician goes, in what order, and at what time each truck pulls up. It's where a route-based business makes or loses its margin. A technician paid for eight hours who spends three of them driving does five hours of revenue work. The same technician, on a route with tight stops in one neighborhood, does six or seven. Nothing else in the platform moves unit economics that directly, and nothing else is as easy to get subtly wrong. A plan that looks good on a map can be undeliverable in practice: a route that ignores a lunch break, sends an unlicensed technician into a county, or was computed from yesterday's cancellations.

This chapter is about building the optimization problem correctly, protecting what the solver mustn't touch, and knowing when its answer is still valid. Dispatch & the Day of Service covers what people do with the plan once it exists.

The Problem Has a Name#

Assigning stops to vehicles and ordering them is the vehicle routing problem (VRP). It first appeared in 1959, when Dantzig and Ramser called it "the truck dispatching problem" and applied it to petrol deliveries. Field service almost always needs the variant with time windows (VRPTW): each stop can only be visited inside a window, such as a customer's morning arrival window or a business's opening hours.

Two facts about the VRP shape every system that solves it:

• It's NP-hard. The VRP generalizes the traveling salesman problem, so no known algorithm finds a guaranteed optimum quickly as the problem grows. Timefold's documentation makes the point concretely: 4 vehicles and 8 visits already give more than 19 million possible assignments. Real days have dozens of technicians and hundreds of stops.
• So solvers use heuristics, under a time limit. A practical solver builds a decent first solution (cheapest insertion, savings, sweep) and then improves it with local search until a limit is reached. OR-Tools lists guided local search as generally the most efficient metaheuristic for vehicle routing, and its search limits default to effectively unlimited. If you don't set a time limit, the search doesn't stop.

The consequence is that "optimal" isn't a property you'll ever verify. You get a good plan within a time budget, and the job of the platform is to make sure it's a good plan for the right problem.

Two Engines, Not One#

Route optimization needs two separate pieces of software, and they're often confused:

Piece	Answers	Examples
Routing engine	How long does it take to drive from A to B, and by what road?	OSRM, openrouteservice, Valhalla, GraphHopper, commercial map APIs
Solver	Given those travel times, which vehicle visits which stop in what order?	VROOM, Google OR-Tools, Timefold (formerly OptaPlanner), Google Route Optimization API

The routing engine turns a road network into a travel matrix: a duration and distance for every pair of locations in the problem. OSRM's table service, for example, returns durations in seconds and distances in meters, and its distances are along the fastest route, not straight lines. OSRM, openrouteservice and Valhalla all run on OpenStreetMap data and can be self-hosted. The solver never sees a road. It sees the matrix.

The split matters for three reasons:

• Cost scales with the matrix. A day with 400 stops and 40 technician start points needs a 440 by 440 matrix: about 194,000 cells. A per-element commercial matrix API priced for occasional lookups becomes expensive at that volume, every time you re-optimize. Self-hosting a routing engine over OpenStreetMap is a common answer for route-dense businesses.
• You can swap one without the other. VROOM, for example, will either query a routing engine for the matrix or accept custom matrices you compute yourself, keyed by vehicle profile.
• Errors look different. A wrong travel time is a routing-engine problem (bad map data, a closed road, an address snapped to the wrong street). A bad assignment is a solver or modeling problem. Log both inputs so you can tell them apart.

Buying versus building is a real choice here. Commercial route optimization APIs bundle the map data, traffic and solver, and handle much of the modeling for you; Google's Route Optimization API, for instance, takes shipments, vehicles, time windows, shifts and breaks, and offers a long-running variant for big solves. Self-hosting an open-source solver over OpenStreetMap costs engineering time and gives you control over cost, constraints and data. Either way, the hard part is the next section, and it's yours regardless.

Building the Problem#

Every solver input is a promise about the real world. Most bad routes come from inputs that were wrong, not from a weak solver.

Vehicles Are Technician Shifts

In delivery, the vehicle is the unit. In field service, the unit is a technician on a shift: one vehicle in the problem per person working that day, with that person's hours as the vehicle's time window. Two technicians riding together (a trainee with a trainer, a two-person install crew) are one vehicle with the combined skills and the senior person's constraints.

Build vehicles from the shift schedule, never from the roster. A technician with a day off, a half day or a training shift must not appear as available capacity, and a technician restricted to certain kinds of work (only initial visits, only on-call emergencies) carries that restriction into the problem as a skill, below.

Start and End

Where a route starts and ends changes every route in the day. The options, roughly in order of preference for a home-based workforce:

• The technician's home, for technicians who take the truck home. This is typical in residential services and saves the drive to a depot.
• The branch or depot, when trucks are parked there, or when the day starts with loading materials.
• The first stop, as a last resort when no start location is known. It quietly removes the first drive from the plan, so the route looks shorter than it is.

VROOM, for one, makes the end optional: omit it and the route ends at the last stop; set it equal to the start for a round trip. Decide this deliberately per business, and fall back through a defined order (technician's home, then the branch) instead of whatever happens to be set.

Stops: Windows, Durations and Setup

Each stop carries:

• A location, geocoded and validated (Customers, Accounts & Properties). A pin on the wrong side of a highway or a rural address geocoded to the center of its ZIP code produces routes that look fine and drive terribly. Routing engines snap coordinates to the nearest road; check that the snapped point is close to the input, because a large snap distance usually means a bad geocode.
• A time window, from the customer's arrival window. An "anytime" appointment should get the whole shift as its window, not a fake narrow one, so the solver can place it freely.
• A service duration, from what's being done: an initial visit takes longer than a routine one, a callback is shorter, a large property longer. Use the planned duration per service type and property, and correct it over time from actual time on site.
• Setup time, the fixed cost of arriving: parking, walking up, finding the customer. VROOM charges setup once per location, so two jobs at the same address pay it once. Model it explicitly; it's what makes two stops in one apartment complex cheaper than two stops across town.

Skills, Licenses and Channels

A stop that needs a capability gets that capability as a required skill, and only vehicles with every required skill can serve it. In VROOM's model, a job's skills are mandatory and a vehicle can serve it only if it has all of them. Field operations uses this for far more than technical skill:

• Service capability: termite work, irrigation repair, commercial accounts, a certified gas fitter.
• Licensing: a technician licensed in the jurisdiction where the property sits. Licenses & Permits explains why that's a hard constraint, not a preference.
• Shift type: stops that may only go to technicians on an "initial visits" shift or a training shift.
• Pinning: a skill unique to one technician, attached to a stop that must stay with them (a customer's requested technician, a technician's own personal calendar event).

Skills are the mechanism for any rule shaped like "only these people may do this work." Generate them from the same rules the booking engine uses, so a slot offered to a customer at booking time is a slot the optimizer can actually fill.

Capacity and Maximum Stops

Delivery routes have physical capacity: weight, volume, pallet positions. Service routes mostly don't, so capacity becomes a cap on stops per route, a fairness and quality limit rather than a physics one. A technician scheduled for too many stops will rush them or finish late. Expose the cap per route (and per shift type), so a trainee's route can be lighter and a route in a dense area can carry more.

Where trucks do carry limited stock (a day's supply of a material, a set number of units to install), model it as a capacity dimension too.

Breaks

Breaks are part of the plan, not something the technician fits in. Model each required break as a break with its own time window and duration, so the solver schedules it along with the stops. A route that only works if the technician skips lunch isn't a valid route, and where state law requires meal or rest breaks, it isn't a legal one either.

Priority by Due State

When there's more work than capacity, something gets left out, and the solver needs to know what matters most. VROOM's priority runs from 0 to 100, and higher-priority tasks are preferred when not every task can be served. Derive priority from how overdue the work is, using the due ranges from Recurring Schedules:

Due state	Priority	Why
Overdue	Highest	Past its window; the customer has already been let down
Inside a strict window	High	Must happen within its range, by contract or regulation
Inside a flexible window	Medium	Due now, can slip a day without harm
Not yet due	Low	Filler for spare capacity

The exact numbers matter less than the ordering being stable and explainable: a dispatcher should be able to look at an unassigned stop and know why the solver dropped it.

What the Solver Must Not Touch#

An optimizer that's allowed to change everything will. Three kinds of work are off-limits, and each needs explicit modeling:

• Pinned stops. A stop that must stay with a particular technician, or at a particular time. Customer requests ("only the technician who came last time"), commercial accounts with a contracted time, and stops the dispatcher placed by hand. Pin by skill and a narrow time window, so the solver plans around the stop instead of ignoring it.
• Locked routes. A route a person has finalized and doesn't want touched: built by hand, already communicated to customers, or sealed for the day. A locked route should be invisible to the optimizer and to automatic scheduling entirely. Don't send it at all, and remove its technician's capacity from the problem.
• Work in progress. Once a technician has started a stop, its position is fixed. In-day re-optimization (below) starts from where each technician actually is, with completed and started stops removed from the problem.

Record why a stop or route is fixed. A lock without a reason becomes permanent by accident.

When to Optimize#

Optimization runs at more than one moment, and each has different rules:

• The batch plan. The night before, or a few days ahead, build routes for the whole branch from the booked appointments and available shifts. This is the big solve, with a generous time limit. Don't overwrite days that already have hand-built routes; skip them and say so.
• On significant change. A technician calls in sick, a large commercial job is added, a weather stand-down moves a day. Re-optimize the affected routes, not the whole branch.
• In-day. Once the day starts, small re-optimizations keep it efficient: when a stop runs long, when a cancellation opens a gap, when a technician starts their first stop and you finally know where they actually are. In-day changes must respect what customers were already told (a confirmed arrival window can't silently move), so in-day optimization mostly reorders within windows rather than reassigning across technicians.

Events trigger in-day optimization, and events come in bursts. Ten cancellations in a minute shouldn't start ten solves. Debounce per route (one pending optimization per route at a time, coalescing triggers that arrive within a few minutes) and make each run idempotent.

Stale Results#

A solve takes seconds to minutes. In that time, the world moves: a customer cancels, a dispatcher drags a stop, a technician clocks out. A result computed from the old inputs and written over the new state silently undoes those changes, and they're exactly the changes people are actively watching.

The fix is an input fingerprint. Before solving, hash everything the solve depends on: the stops and their windows, durations and skills; the shifts, their hours and start points; the pins and locks. Store it with the job. When the result comes back, recompute the fingerprint from the current data:

• It matches: commit the plan, atomically, in one transaction.
• It doesn't: discard the result and, if the change is still relevant, queue a fresh solve.

This is the same reasoning as optimistic concurrency in Transactions & Concurrency, applied to a long-running computation. Without it, the optimizer and the dispatcher take turns overwriting each other, and both lose trust in the system.

Treat the optimization as a job with a lifecycle: dispatched, started, then succeeded, failed, skipped (nothing to do, or a duplicate) or cancelled. Store the request and response payloads. When someone asks why a route looks the way it does, the answer is in what the solver was given.

When It Fails#

Solvers rarely fail outright. They succeed with stops left out. VROOM, for example, reports those in an unassigned list with the stop's ID and little more, and its output summary counts them. "Unassigned" is the start of a diagnosis, not an answer, and the platform should do that diagnosis rather than leaving it to a dispatcher:

Check	What it catches
Coordinates	Missing or invalid coordinates; a large snap distance; a stop far outside the branch's area
Skills	No technician on shift has every skill the stop requires, including licensing for its jurisdiction
Time windows	The window doesn't overlap any shift, or is shorter than the service duration
Capacity	Every eligible route is at its stop cap
Pinning	The stop is pinned to a technician who isn't working, or to a locked route
Travel	The stop is reachable only by a drive longer than any route allows

Run these checks against the problem you sent, and attach the reason to the stop. The dispatcher sees "no licensed technician working in this county Tuesday," not "unassigned." Most reasons map to an action someone can take: add a shift, fix a pin, call the customer to widen the window.

Hard failures do happen: a routing-engine outage, a malformed request, a timeout. Retry with backoff (Retries & Timeouts) for transient errors only, and alert when a branch's batch plan fails, because a branch without routes at 6 a.m. is an incident.

Scoring a Route#

The solver's cost function isn't how the business judges a plan. Report the plan in operating terms, per route and per branch, and compare before and after optimization:

Metric	What it tells you
Drive time and miles	Total non-revenue time and fuel
Miles between stops	Route density; the clearest single signal of a good territory
Services per hour	Productivity, ideally weighted by service type so a long initial visit counts for more than a quick callback
Working hours vs shift length	Under- and over-loaded routes
Window adherence	Planned arrivals inside the customer's window
Unassigned work, by due state	What capacity is missing, and where

These same metrics, from actual completion data instead of the plan, feed Operating Metrics. Planned versus actual is how you calibrate durations, travel times and caps.

Travel Times Are a Model#

A travel matrix from a routing engine over road network data is free-flow time: no traffic, no parking, no time spent walking to the door. That's fine for ordering stops and wrong for promising arrival times. Correct for it deliberately:

• Scale travel time by area. VROOM, for example, has a per-vehicle speed factor (between 0 and 5, default 1) that scales all travel times. A dense city branch might run slower than the routing engine thinks; a rural one, faster.
• Calibrate from reality. Telematics and completion timestamps tell you how long drives and stops actually take. Compare them to the plan per branch and adjust the factors and durations.
• Keep setup time separate, so parking-heavy areas can be modeled without distorting road speeds.

What This Means for the System You Build#

• A routing engine and a solver as separate, replaceable components, with the travel matrix as the contract between them.
• Vehicles built from shifts, with start and end locations chosen by an explicit fallback order.
• Stops with validated coordinates, honest windows, per-service durations and setup time.
• Skills generated from the same rules as booking, including licensing, shift type and pinning.
• Breaks and stop caps modeled in the problem, not left to the technician.
• Priority derived from due state, stable and explainable.
• Locked routes excluded entirely; pinned and in-progress stops fixed.
• Optimization as a debounced, idempotent job, with stored inputs and outputs and a lifecycle.
• An input fingerprint checked before committing, so a stale plan is discarded.
• A reason attached to every unassigned stop, from automated diagnosis.
• Plans scored in operating metrics, and calibrated against actual times.

References#

Reference

• VROOM: API documentation, jobs, vehicles, skills, priority from 0 to 100, setup charged once per location, breaks, speed factor, custom matrices and the unassigned list
• Google OR-Tools: Vehicle Routing Problem with Time Windows, modeling time windows with a time dimension and slack
• Google OR-Tools: Routing Options, first-solution strategies, guided local search, and search limits that default to unlimited
• Timefold Solver: Introduction, hard and soft constraints, and the number of possible assignments for 4 vehicles and 8 visits
• Google Maps Platform: Route Optimization API, shipments, vehicles, time windows, shifts and breaks, and long-running solves
• OSRM: API documentation, the table service's duration and distance matrices, and snapping to the road network
• openrouteservice, directions, matrices, isochrones and snapping over OpenStreetMap data
• Valhalla, an OpenStreetMap routing engine with route, matrix, isochrone and map-matching services
• Wikipedia: Vehicle routing problem, Dantzig and Ramser's 1959 truck dispatching problem, NP-hardness, and the time-window variant