Skip to main content

Time windows in CPVRPTW problems

The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) extends the classic VRP by incorporating two key real-world constraints: vehicle capacity and time windows. Time windows, which restrict when a customer can be serviced, are crucial for modeling realistic scenarios and significantly impact solution feasibility and cost.

Time windows are essential for representing real-world situations where delivery or service times are limited. Think of industries like grocery or package delivery, or field services. Customers often specify preferred or mandatory delivery times, and businesses must adhere to these to maintain customer satisfaction and operational efficiency. Ignoring these constraints can lead to missed deliveries, increased costs due to revisits, and dissatisfied customers. Effectively incorporating time windows allows for optimized routes that respect customer preferences, minimize travel time, and maximize vehicle utilization, ultimately leading to improved service levels and reduced operational costs.

Time windows are defined by a start time (earliest arrival time) and an end time (latest arrival time). They are typically categorized as:

  • Hard Time Windows: Service must occur within the specified window. Arriving before the start or after the end time is unacceptable and renders the solution infeasible.
  • Soft Time Windows: Service within the window is preferred, but deviations are allowed, often at a penalty. Arriving early might incur waiting time, while arriving late could result in a penalty cost.

Time windows can apply to various entities within the CVRPTW:

  • Customers: This is the most common application, representing the customer's desired service time.
  • Depots: The depot (starting and ending location for vehicles) might also have time window constraints, restricting when vehicles can depart and return.
  • Vehicles: Vehicles themselves might have time windows due to driver availability or vehicle restrictions.

In SWAT APIs the timing model for the booking (order):

Order timestamps

Additionally, the SWAT model supports time limits for vehicles. Leverage vehicle.start_time and vehicle.end_time properties to regulate driver working hours. Any time combination can be utilized, enabling both limited and unlimited time windows for each vehicle. api

For more complex cases, when the nodes (for example, stores) may have gaps in their working hours when they can accept vehicles, SWAT model support multiple time windows for each booking(or node) api via booking.pickup_time_windows or booking.dropoff_time_windows.

This allows setting multiple working hours at the order or location level, such as

"8am-11am; 11am-3pm; 7pm-8pm"
tip

In the classic Pickup and Delivery Problem with Time Windows (PDP-TW), and the SWAT optimization model requires vehicles to arrive at a node within its specified time window (between the node's open and close times). However, departure is allowed after the node's close time, accommodating the service time required at that node. Therefore, a vehicle leaving a node after its close time—where node.scheduled_ts + node.service_time > node.close_time_ts—is a valid scenario.

The diagram below illustrates the sequence of events and time components for a vehicle's journey from one node to the next. It visualizes how various time-based constraints and activities, such as travel time, service time, and breaks, are scheduled within the operational timeline.