Technician Visit Scheduling
Vehicle Routing with Time Windows
Optimizing field service operations in Quebec City using the Vehicle Routing Problem with Time Windows (VRPTW). Each service call has a specific time window during which a technician must arrive, a required service duration, and a geographic location. The goal: minimize total travel distance while respecting every constraint.
The Problem
Field service scheduling as a vehicle routing challenge
VRPTW in Field Service
A field service company dispatches technicians from a central depot to perform maintenance, repairs, or installations at customer sites across Quebec City. Each service call specifies a time window — an interval [earliest, latest] during which the technician must arrive. If a technician arrives before the window opens, they must wait. Arriving after the window closes violates the constraint and renders the schedule infeasible.
Each visit also requires a service time — the duration the technician spends on site. The planning horizon runs from 8:00 to 17:00. Technicians depart from and return to the depot. The objective is to minimize the total distance traveled (equivalently, total travel time) across all technician routes while ensuring every customer is visited exactly once within their time window.
s.t. ∑k ∑j xijk = 1 ∀ i ∈ C /* each customer visited once */
ei ≤ si ≤ li ∀ i ∈ C /* arrival within time window */
sj ≥ si + servi + tij - M(1 - xijk) /* time consistency */
xijk ∈ {0, 1} /* route assignment */
The VRPTW is NP-hard — it generalizes both the Traveling Salesman Problem (TSP) and the Bin Packing Problem. Even finding a feasible solution that satisfies all time windows can be computationally challenging. Practical instances with hundreds of customers require heuristic and metaheuristic approaches.
Try It Yourself
Schedule technician visits across Quebec City
Interactive Solver
6 Service Calls · 2 Technicians · Click any cell to edit| # | Location | Lat | Lng | Window Start | Window End | Service (min) |
|---|
| Algorithm | Distance | Vehicles | TW Satisfied | Time |
|---|
Select an algorithm and click Solve.
Algorithm Implementations
Construction heuristics for time-windowed routing
Solomon I1 Insertion
The Solomon I1 insertion heuristic (1987) is the gold standard for constructing VRPTW solutions. It initializes each route with a seed customer — typically the one with the earliest deadline or farthest from the depot — then iteratively inserts unrouted customers into their best feasible position.
For each unrouted customer u and each arc (i, j) in an existing route, the insertion cost is evaluated as:
/* α1 = distance increase, α2 = time push-forward */
/* Using α1 = 1, α2 = 0 for distance-focused insertion */
Feasibility check: arrivalu ≤ lu AND push-forward propagation feasible for all successors
Before inserting, the algorithm verifies time window feasibility: the technician must be able to arrive at customer u before its window closes, and the resulting push-forward in arrival times must not cause any subsequent customer in the route to violate their time window. When a route can accept no more customers, a new route is opened.
Nearest Neighbor TW
A greedy construction heuristic adapted for time windows. For each technician, the algorithm starts at the depot and repeatedly selects the nearest unvisited customer that can be reached within its time window. If the technician arrives before the window opens, they wait until the earliest service time. When no feasible customer remains reachable before the planning horizon ends, the technician returns to the depot and a new route begins.
current ← depot, time ← 08:00
while unvisited customers exist:
candidates ← {u : arrival(current, u) ≤ lu AND arrival + servu + travel(u, depot) ≤ 17:00}
if candidates = ∅: return to depot, break
next ← argminu ∈ candidates d(current, u)
time ← max(arrival(current, next), enext) + servnext
current ← next
Real-World Complexity
Beyond the basic VRPTW model
Why It's More Complex
The interactive solver above demonstrates the core VRPTW model. In practice, field service scheduling involves additional dimensions of complexity that extend the problem significantly:
- Technician skills and certifications — not every technician can handle every job type. Electrical, plumbing, and HVAC calls each require specific qualifications, turning the problem into a heterogeneous fleet VRPTW.
- Priority customers — some service calls are urgent (e.g., heating failure in winter) and must be scheduled with higher priority or tighter time windows, introducing weighted objectives.
- Break times and labor regulations — technicians require mandatory lunch breaks and rest periods, adding intra-route time constraints that fragment the planning horizon.
- Traffic patterns — travel times between locations vary throughout the day (rush hour congestion), requiring time-dependent travel time matrices instead of static distances.
- Cancellations and no-shows — customers may cancel or reschedule, requiring dynamic re-optimization during the day. Stochastic models account for this uncertainty.
- Multi-day planning — recurring maintenance schedules span weeks or months, introducing periodic VRPTW with consistency constraints (same technician for the same customer).
Key References
Foundational literature on VRPTW algorithms
- Solomon, M. M. (1987). "Algorithms for the vehicle routing and scheduling problems with time window constraints." Operations Research, 35(2), 254–265. — Introduced the I1 insertion heuristic and the canonical Solomon benchmark instances (C/R/RC classes).
- Bräysy, O., & Gendreau, M. (2005). "Vehicle routing problem with time windows, Part I: Route construction and local search algorithms." Transportation Science, 39(1), 104–118. — Comprehensive survey of VRPTW construction and improvement methods, covering 60+ algorithms.
Need to optimize field service scheduling?
Custom VRPTW solutions for workforce routing, technician dispatch, and last-mile delivery.