VRP with Time Windows (VRPTW)

The defining constraint of VRPTW. A vehicle must arrive at a customer location within the specified interval [e_i, l_i], where e_i is the earliest service start time and l_i is the latest. Arrival before e_i forces the vehicle to wait, incurring waiting time. Arrival after l_i renders the solution infeasible in the strict variant. This constraint models real-world delivery slots, retail receiving hours, and appointment-based services.

A practical relaxation where violations of the time window are permitted but penalized in the objective function. A penalty cost is applied per unit of time for early or late arrivals. This formulation acknowledges that missing a preferred delivery window is undesirable but not catastrophic, allowing the solver to trade off between temporal adherence and route distance when finding a globally optimal solution.

Each customer node i has an associated service duration s_i representing the time required to unload goods, obtain signatures, or perform the required task. This time is added to the vehicle's schedule upon arrival. Service time directly consumes the available time window and must be completed before departure. In VRPTW formulations, the departure time from node i is max(arrival_time, e_i) + s_i.

VRPTW relies on a time-dependent cost matrix rather than simple Euclidean distances. Each arc (i, j) has an associated travel time t_ij that accounts for road network distances, speed limits, and historical congestion patterns. This matrix is often asymmetric in urban logistics due to one-way streets. Accurate travel time data is critical, as errors compound across the route and directly impact time window feasibility.

Unlike the basic VRP, VRPTW requires explicit modeling of vehicle departure times from the depot. A vehicle may need to delay its start to avoid arriving too early at its first customer. The departure time becomes a decision variable. This introduces a scheduling dimension to the routing problem, where the optimizer must simultaneously determine the sequence of visits and the precise timing of each stop.

A core subroutine in any VRPTW solver. For a proposed route, the algorithm propagates arrival times forward, checking that each customer's window is respected. The arrival at node j from node i is arrival_j = departure_i + t_ij. If arrival_j > l_j, the route is infeasible. Efficient forward time slack calculations allow solvers to evaluate insertions in constant time, which is essential for the performance of local search heuristics like Large Neighborhood Search (LNS).

A critical subroutine that determines whether a proposed insertion into a route violates any time window constraints. The check propagates arrival times forward through the route, verifying that each customer can be served within their hard time window without waiting beyond the latest allowable start time. Efficient O(1) feasibility checks using precomputed forward time slack are essential for high-performance local search operators in VRPTW solvers.

Hard time windows prohibit service outside the specified interval entirely, making the constraint inviolable. Soft time windows allow violations but penalize them in the objective function with a cost proportional to the degree of lateness or earliness. Many real-world logistics problems use a hybrid approach—hard windows for regulatory or contractual requirements (e.g., school bus arrivals) and soft windows for customer convenience, enabling the solver to trade off on-time performance against route cost.

A constructive heuristic for VRPTW that builds routes by iteratively inserting unrouted customers into the position that minimizes a weighted cost function combining added distance and time window displacement. The algorithm evaluates every feasible insertion point across all existing routes, selecting the one that causes the least increase in total route duration while maintaining temporal feasibility. This method, introduced by Solomon in 1987, remains a foundational benchmark for VRPTW solution quality.

A secondary temporal constraint often paired with time windows that limits the maximum elapsed time from depot departure to return. This enforces driver shift limits, regulatory hours-of-service rules, or perishable goods shelf-life constraints. In VRPTW formulations, the duration constraint is modeled as a time window on the depot itself, where the return must occur before a latest possible arrival time, creating a closed time window for the entire route.

When a vehicle arrives before a customer's earliest service time, it incurs waiting time—idle time that increases route duration without productive activity. Advanced VRPTW objective functions often include a penalty for excessive waiting to improve driver utilization and reduce labor costs. Some formulations allow strategic waiting at specific nodes to avoid traffic congestion later, transforming waiting from a constraint artifact into an optimization variable.