Home Visits Routing
Vehicle Routing with Time Windows
A home healthcare agency dispatches nurses to visit patients at home. Each patient has a required time window and visit duration. The goal is to minimize total travel while ensuring every patient is seen within their window — the Vehicle Routing Problem with Time Windows (VRPTW), an NP-hard extension of the classic CVRP.
Where This Decision Fits
Healthcare planning chain — the highlighted step is what this page optimizes
The Problem
Why route optimization matters for home healthcare
Over 5 million Americans receive home health services annually. A home healthcare agency employs teams of nurses who travel between patients' homes, providing services ranging from wound care and IV infusions to vital sign checks and medication management. Each patient requires a visit within a specific time window (e.g., 8:00–10:00 AM for morning insulin management), and each visit has a known service duration tied to clinical acuity.
Route optimization can reduce driving time by 20–30%, increasing direct patient care by 15–25% (Fikar & Hirsch, 2017). With each nurse carrying a limited shift capacity (measured in care-minutes), the agency must decide which patients each nurse visits and in what order — balancing travel efficiency against time window feasibility.
This is the Vehicle Routing Problem with Time Windows (VRPTW) — an NP-hard combinatorial optimization problem. Unlike the basic TSP, VRPTW must simultaneously determine the number of vehicles (nurses), assign customers (patients) to vehicles, and sequence visits so that every time window constraint [ei, li] is respected.
| Healthcare Domain | VRPTW Model | |
|---|---|---|
| Patient | Customer node | |
| Nurse | Vehicle | |
| Appointment window | Time window [ei, li] | |
| Visit duration | Service time si | |
| Care-minutes per shift | Vehicle capacity Q | |
| Agency office | Depot |
subject to
Σk Σj xijk = 1 // each patient visited exactly once
Σi di · Σj xijk ≤ Q // nurse capacity not exceeded
ei ≤ tik ≤ li // arrival within time window
tik + si + cij ≤ tjk + M(1 - xijk) // time consistency
xijk ∈ {0, 1} // binary routing decision
Where cij is the travel cost between locations i and j, xijk indicates whether nurse k travels from i to j, tik is the arrival time of nurse k at patient i, and Q is the shift capacity in care-minutes.
See full Routing theory and all algorithmsTry It Yourself
Route nurses to patient homes with time windows
Home Visits Route Optimizer
15 Patients · 200 min capacity| # | Patient | Coords | Visit (min) | Window | Acuity |
|---|
Ready. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Distance (km) | Nurses | Care % | Time (ms) |
|---|---|---|---|---|
| Click Solve & Compare All Algorithms | ||||
The Algorithms
Construction and improvement heuristics for VRPTW
Solomon I1 Insertion
O(n² · m) per route | Sequential route buildingSolomon’s I1 insertion heuristic (1987) builds routes one at a time by repeatedly inserting the unrouted customer that causes the least combined increase in distance and time penalty. For each unrouted customer, every feasible insertion position in the current route is evaluated. The customer with the best insertion cost is selected. When no more customers can be feasibly inserted, a new route begins. This method produces compact, time-window-respecting routes and is the standard benchmark constructor for VRPTW instances.
Nearest Neighbor with Time Windows
O(n²) | Greedy sequentialStarting from the depot, greedily select the nearest unvisited patient whose time window is still feasible (i.e., the nurse can arrive before the window closes). If the nurse arrives early, she waits until the window opens. When no feasible patient remains or the nurse’s capacity is exhausted, return to depot and start a new route. Simple and fast, but myopic — it ignores future consequences and may strand hard-to-reach patients for later routes.
Simulated Annealing
O(iterations × n) | Swap & relocate movesStarting from a construction heuristic solution, Simulated Annealing explores the neighborhood by randomly applying swap (exchange two patients between routes) and relocate (move one patient to a different route position) moves. Improving moves are always accepted; worsening moves are accepted with probability e−Δ/T, where T is the temperature that gradually cools. This allows escaping local optima and finding better solutions that greedy methods miss, at the cost of additional computation time.
Real-World Complexity
Why home healthcare routing goes beyond the VRPTW model
Time Windows
Patients require visits within strict clinical windows — insulin must be given before meals, wound dressings changed on schedule. Late arrivals compromise care quality and safety.
Skill Matching
Not every nurse can handle every case. IV infusions, psychiatric assessments, and palliative care each require specialized certifications, constraining which nurse can visit which patient.
Continuity of Care
Patients benefit from seeing the same nurse across visits. Continuity improves outcomes and satisfaction but limits routing flexibility and can lead to workload imbalances.
Travel Uncertainty
Traffic conditions, weather, and road closures make travel times stochastic. Robust routes must build in buffers, and real-time rerouting is often necessary during the day.
Workload Equity
Fair distribution of caseload and travel burden across nurses prevents burnout, improves retention, and ensures no single nurse is consistently overloaded or underutilized.
Key References
Foundational works in home healthcare routing
- (2017). “Home health care routing and scheduling: A review.” Computers & Operations Research, 77, 86–95. DOI: 10.1016/j.cor.2016.07.019
- (1997). “An integrated spatial DSS for scheduling and routing home-health-care nurses.” Interfaces, 27(4), 35–48. DOI: 10.1287/inte.27.4.35
- (2013). “Operations management applied to home care services.” Decision Support Systems, 55(2), 587–598. DOI: 10.1016/j.dss.2012.10.015
Need to optimize your home healthcare operations?
From nurse routing to patient scheduling and resource allocation, mathematical modeling can transform your healthcare delivery. Let’s discuss how Operations Research can work for you.