VRPTW: Time Windows

🔥 Vibe Prompt

"Solve VRPTW: 9 locations with time windows, 3 vehicles. Each customer has an earliest/latest delivery time."

data = {
    "time_matrix": [[0,6,9,...],[6,0,8,...],...],
    "time_windows": [(0,60),(5,20),(10,30),...],
    "num_vehicles": 3,
    "depot": 0
}

# Add Time dimension
routing.AddDimension(transit_callback_index, 30, 60, False, "Time")
time_dimension = routing.GetDimensionOrDie("Time")

# Set time windows for each customer
for location_idx, (early, late) in enumerate(data["time_windows"]):
    if location_idx == data["depot"]:
        continue
    index = manager.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(early, late)

This is the core algorithm behind UberEats & Foodpanda!

When you order food, the system solves VRPTW in real-time to assign the best driver.

Chapter Summary

Understand core concepts and principles
Master implementation methods and techniques
Familiar with common issues and solutions
Able to apply in real projects

Implementation Example

Basic Example

# This section provides a complete implementation example

Steps

Setup: Configure development environment
Data: Prepare required data
Implementation: Build core functionality
Testing: Verify correctness
Optimization: Improve performance

Common Errors

| Error Type | Cause | Solution | |------------|-------|----------| | Compilation | Syntax | Check code syntax | | Runtime | Environment | Verify dependencies installed | | Logic | Algorithm | Step-by-step debugging | | Performance | Efficiency | Use profilers |

Code Example

import sys

def main():
    print("Hello, World!")

if __name__ == "__main__":
    main()

References

Official documentation
API reference
Open source examples
Community discussions

Key Points

Understand the core concepts thoroughly
Practice with hands-on code examples
Apply knowledge to real-world problems
Review and reinforce through exercises

Further Learning

Official documentation
Open source projects on GitHub
Community forums and discussions
Related courses and tutorials

Time Window Constraints

In VRPTW, each customer i has:

ready_time[i]: earliest time the vehicle can arrive (e_i)
due_time[i]: latest time the vehicle can arrive (l_i)
service_time[i]: time spent at the customer (s_i)

The vehicle can arrive before e_i but must wait until e_i to start service. Arriving after l_i is not allowed.

VRPTW Formulation

Minimize: total distance traveled
Subject to:
  - All customers visited once
  - Each route starts and ends at depot
  - Vehicle capacity not exceeded
  - arrival_time[i] >= ready_time[i]
  - arrival_time[i] <= due_time[i]
  - departure_time[i] = arrival_time[i] + service_time[i]
  - travel_time[i][j] = distance[i][j] / speed

Time Window Types

| Type | Description | Example | |------|-------------|---------| | Hard | Must arrive before due time | Doctor appointments | | Soft | Can arrive late with penalty | Delivery windows | | Mixed | Some hard, some soft | Food delivery (hot food) |

Insertion Heuristic for VRPTW

def vrptw_insertion(customers, vehicles, dist_matrix, capacity):
    """
    Sequential insertion heuristic for VRPTW.
    Inserts each customer into the best feasible position.
    """
    unvisited = set(range(len(customers)))
    routes = [[] for _ in range(len(vehicles))]
    route_loads = [0] * len(vehicles)
    route_times = [[0.0] for _ in range(len(vehicles))]  # current time at each stop
    
    for customer in sorted(unvisited, key=lambda c: customers[c].due_time):
        best_cost = float('inf')
        best_route = -1
        best_position = -1
        
        for r_idx in range(len(vehicles)):
            if route_loads[r_idx] + customers[customer].demand > vehicles[r_idx].capacity:
                continue
            
            route = routes[r_idx]
            for pos in range(len(route) + 1):
                if is_feasible_insertion(route, pos, customer, customers, dist_matrix, route_times[r_idx]):
                    cost = calculate_insertion_cost(route, pos, customer, dist_matrix)
                    if cost < best_cost:
                        best_cost = cost
                        best_route = r_idx
                        best_position = pos
        
        if best_route >= 0:
            routes[best_route].insert(best_position, customer)
            route_loads[best_route] += customers[customer].demand
            update_route_times(routes[best_route], customers, dist_matrix, route_times[best_route])
            unvisited.remove(customer)
    
    return routes


def is_feasible_insertion(route, pos, customer, customers, dist_matrix, times):
    """Check if inserting customer at pos preserves all time window constraints."""
    # Simplified check — real implementation must verify all downstream times
    prev = route[pos - 1] if pos > 0 else -1  # -1 = depot
    next_c = route[pos] if pos < len(route) else -1
    
    prev_node = prev + 1  # +1 for depot offset
    cust_node = customer + 1
    next_node = next_c + 1 if next_c >= 0 else 0
    
    arrival = times[pos] + dist_matrix[prev_node][cust_node]
    if arrival > customers[customer].due_time:
        return False
    
    departure = max(arrival, customers[customer].ready_time) + customers[customer].service_time
    
    if next_c >= 0:
        arrival_next = departure + dist_matrix[cust_node][next_node]
        if arrival_next > customers[next_c].due_time:
            return False
    else:
        arrival_depot = departure + dist_matrix[cust_node][0]
        # No depot time window, always feasible
    
    return True

OR-Tools VRPTW Implementation

from ortools.constraint_solver import routing_enums_pb2, pywrapcp

def solve_vrptw_ortools(data):
    """Solve VRPTW using Google OR-Tools."""
    manager = pywrapcp.RoutingIndexManager(
        len(data['distance_matrix']),
        data['num_vehicles'],
        0  # depot
    )
    routing = pywrapcp.RoutingModel(manager)
    
    # Distance callback
    def distance_callback(from_i, to_i):
        return data['distance_matrix'][manager.IndexToNode(from_i)][manager.IndexToNode(to_i)]
    transit_cb = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_cb)
    
    # Add distance dimension (for total route distance)
    routing.AddDimension(transit_cb, 0, 3000, True, 'Distance')
    
    # Time callback
    def time_callback(from_i, to_i):
        return data['distance_matrix'][manager.IndexToNode(from_i)][manager.IndexToNode(to_i)]
    time_cb = routing.RegisterTransitCallback(time_callback)
    routing.AddDimension(time_cb, 30, 3000, False, 'Time')
    
    time_dimension = routing.GetDimensionOrDie('Time')
    for node in range(1, len(data['time_windows'])):
        start = data['time_windows'][node][0]
        end = data['time_windows'][node][1]
        time_dimension.CumulVar(node).SetRange(start, end)
    
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    
    solution = routing.SolveWithParameters(search_parameters)
    return solution, manager, routing

Applications

| Industry | Time Window Example | |----------|-------------------| | Food Delivery | "Deliver between 12:00-12:30" (30 min window) | | Medical | "Appointment at 14:00" (hard window) | | E-commerce | "Deliver between 9:00-17:00" (wide window) | | Field Service | "Repair between 10:00-12:00" (narrow window) | | Waste Collection | "Collect before 8:00 AM" (deadline) |

Summary

VRPTW adds time windows to the VRP. Each customer has a ready time and a due time. Hard windows must be strictly met; soft windows allow late arrivals with a penalty. Insertion heuristics build feasible routes, and OR-Tools finds optimal solutions for small instances.

Key takeaways:

VRPTW: each customer has [ready_time, due_time] window
Hard windows: must arrive before due time
Soft windows: can be late with penalty
Insertion heuristic: place in best feasible position
OR-Tools: optimal for small instances
Time dimension tracks cumulative travel time
Applications: food delivery, medical, field service

What's Next: Large-Scale VRP

The next chapter covers large-scale VRP — decomposition strategies, cluster-first-route-second, and metaheuristics for problems with hundreds of customers.