Vehicle routing problem with time windows (VRPTW)
Updated October 8, 2026 · 2 min read
The vehicle routing problem with time windows (VRPTW) is the problem of planning routes for a fleet so that every stop is visited once and service there starts between its earliest and latest allowed times, at the lowest total travel cost. Home visit routing is a VRPTW with health care rules added, such as matching skills and keeping the same clinician with the same patient.
The parts of a VRPTW
- Depot: where each vehicle, or clinician, starts and ends the day.
- Vehicles: the vans or people that travel, each with a capacity or a shift length.
- Stops: the places to visit, each with a service time, the minutes the stop takes.
- Time window: the earliest and latest time service may start at a stop. Arriving early means waiting for the window to open.
- Travel times: the minutes between every pair of stops.
- Goal: the lowest total travel cost, with every stop visited once.
The plain vehicle routing problem asks only for the cheapest routes that visit every stop once. Adding a window at each stop gives the VRPTW, one of its best-known extensions.
Hard and soft windows
A hard window must be met; a plan that misses it is not allowed. A soft window can be missed at a penalty, such as a cost for each minute late. Home care models use both. A 2025 review groups legal working hours, qualifications and required visit windows as hard limits, and patient or clinician preferences, continuity and workload balance as soft ones.
Example: two patients admitted from the ED overnight
The emergency department admitted two patients to a hospital-at-home program overnight. Tomorrow one nurse sees both. Patient P has a medicine due between 09:00 and 09:30; patient Q can be seen from 08:00 to 12:00. Each visit takes 40 minutes, each home is 15 minutes from the office, the homes are 20 minutes apart, and the nurse leaves at 08:00.
| Order | Drive | Waiting | Back at office | Windows met |
|---|---|---|---|---|
| Q, then P | 50 min | 0 min | 10:10 | Both |
| P, then Q | 50 min | 45 min | 10:55 | Both |
Both orders drive the same 50 minutes. Going to P first means arriving at 08:15 and waiting 45 minutes for its window, so the nurse is back 45 minutes later. With 20 patients and 4 nurses, the number of possible orders is far too large to compare by hand.
How the problem gets solved
Solomon's 1987 paper in Operations Research argued that the problem is hard enough that approximate methods are the practical route for real-size problems. He compared several heuristics on test problems that varied how many customers had windows and how tight they were, and an insertion-type method consistently gave very good results. A 2025 review lists a home care routing dataset whose patient locations were generated following his methods.
Exact methods suit small and medium problems; for large or tightly constrained ones, heuristics that improve a plan step by step scale better. Capillary's routing, shown as a demo, plans home visits for clinicians, couriers and equipment around visit windows, skills and travel time. See Capillary for hospital-at-home programs and the dispatch vs. routing glossary.
Common questions
- What is the difference between the VRP and the VRPTW?
- The VRP finds the cheapest routes that visit every stop once. The VRPTW adds a window at each stop for when service may start, which can force waiting or a different order.
- Is home health care routing a VRPTW?
- Mostly. Reviews describe it as an extension of the vehicle routing problem that adds time windows and health care rules: clinician skills, visits that need two clinicians at once, and continuity of care.
- Can a solver guarantee the best possible route?
- Exact methods can for small and medium problems. For a full day across a team, most tools use heuristics that find good routes quickly without proving they are the best, the approach Solomon recommended for practical-size problems.
Plan home visits around windows, skills and drive time.
Capillary's routing module plans the day for clinicians, couriers and equipment. See it with sample data.