Service Time Window

Time windows are classified by their constraint rigidity:

• Hard Time Windows: The vehicle must arrive before the window closes. Early arrivals require waiting; late arrivals are infeasible and invalidate the solution.
• Soft Time Windows: Late arrivals are permitted but incur a penalty cost in the objective function, allowing the optimizer to trade off punctuality against other costs like distance or fleet size.
• Semi-Soft Windows: A hybrid approach where a soft window exists, but a hard maximum lateness bound cannot be exceeded, reflecting real-world contractual obligations with grace periods.

A route is temporally feasible only if the arrival time at each node falls within its specified window. This requires forward propagation of time:

• Arrival Time Calculation: arrival_j = max(window_start_j, departure_i + travel_time_ij). The max function captures waiting time when arriving early.
• Service Duration: Each stop consumes a fixed service time (e.g., 15 minutes for unloading), which must be added before departure.
• Precedence Constraints: In Pickup and Delivery Problems (PDP), a pickup must occur before its corresponding delivery, creating a pairing constraint that links the time windows of two distinct nodes.

The tightness of time windows—their width relative to travel times—is the primary driver of problem difficulty:

• Wide Windows: When windows span many hours, the problem behaves like a standard Capacitated VRP (CVRP) with minimal temporal binding, and solutions are easier to find.
• Narrow Windows: Tight windows (e.g., 30-minute slots) severely restrict the permutation of stops, fragmenting the solution space and dramatically increasing computational complexity.
• Disjoint Windows: When customer windows are non-overlapping (e.g., morning-only vs. afternoon-only), the problem naturally decomposes into distinct route clusters, which can be exploited by decomposition algorithms.

Early arrival at a customer location before the window opens generates waiting time, a critical cost component:

• Driver Cost: Idle time incurs direct labor costs without productive movement.
• Regulatory Impact: In many jurisdictions, waiting time counts toward hours-of-service (HOS) limits, potentially causing downstream compliance violations.
• Optimization Trade-off: Minimizing waiting time often conflicts with minimizing total distance. A route that is geographically efficient may require significant waiting, while a longer route with precise timing may have zero idle time.
• Cold Chain Impact: For refrigerated transport, waiting with the engine running consumes fuel and increases emissions, adding an environmental cost dimension.

Time windows apply not only to customers but also to the depot and the overall route:

• Depot Opening Hours: Vehicles cannot depart before the depot opens and must return before it closes, creating a global temporal envelope for all routes.
• Maximum Route Duration: A hard constraint on the total elapsed time from departure to return, driven by driver shift limits, HOS regulations, or perishable goods shelf-life.
• Lunch Break Windows: Real-world scheduling often requires inserting a mandatory break within a specific time window (e.g., between the 4th and 6th hour of a shift), adding a complex, floating temporal constraint to the optimization model.

Time windows are formalized differently depending on the solution paradigm:

• MILP Formulation: Uses continuous variables a_i (arrival time at node i) with big-M constraints: a_i + s_i + t_{ij} - a_j ≤ M(1 - x_{ij}), where x_{ij} is a binary routing variable. The large constant M deactivates the constraint when the arc is not traversed.
• Constraint Programming (CP): Models time windows natively using interval variables with start, end, and duration, combined with endBeforeStart constraints. CP solvers excel at tightly constrained, highly disjunctive scheduling problems.
• Disjunctive Programming: The core logic that a vehicle can only serve one customer at a time, enforced by a disjunction: either a_i + s_i + t_{ij} ≤ a_j or a_j + s_j + t_{ji} ≤ a_i.

The canonical extension of the VRP where each customer must be serviced within a specified time interval. A vehicle arriving before the window must wait, incurring idle time. Arriving after the window is typically penalized or forbidden. This transforms the problem from pure spatial routing to a spatio-temporal scheduling challenge, dramatically increasing computational complexity. Exact solutions are feasible only for small instances; industrial-scale VRPTW relies on metaheuristics like Adaptive Large Neighborhood Search (ALNS).

A critical modeling distinction in service time constraints:

• Hard Time Windows: The vehicle must arrive within the interval. Late arrival is infeasible and not permitted in the solution. Common in pharmaceutical cold chain and just-in-time manufacturing.
• Soft Time Windows: Late arrivals are allowed but penalized in the objective function with a lateness cost. This creates a trade-off between minimizing fleet cost and maximizing service level.

Most real-world logistics use a mixed approach, with hard windows for critical customers and soft windows with escalating penalties for others.

Service time windows cannot be evaluated accurately without considering that travel times are not constant. A route that is feasible at midnight may be impossible during rush hour. Time-Dependent VRP (TDVRP) models incorporate time-varying travel speed profiles derived from historical GPS probe data. The travel time between two points becomes a function of the departure time, creating a complex feedback loop: the sequence of service windows determines departure times, which determine travel times, which determine arrival feasibility.

The passenger-transport variant where service time windows are paired with ride time constraints. In DARP, a passenger's total time in the vehicle from pickup to drop-off must not exceed a maximum duration, typically relative to the direct travel time. This creates a coupling between the pickup window and the delivery window, adding a quality-of-service dimension beyond simple arrival feasibility. Used extensively in paratransit and non-emergency medical transportation scheduling.

Slack time is the buffer between the planned arrival at a customer and the end of their service window. Routes with minimal slack are brittle—a minor traffic delay cascades into multiple missed windows. Robust optimization techniques explicitly maximize minimum slack or use stochastic travel time distributions to ensure a route remains feasible with a target probability (e.g., 95% on-time confidence). This is critical for attended home delivery where missed windows directly trigger costly redelivery attempts and customer dissatisfaction.