InteractiveVehicle Routing Problem with Time Windows: Complete Guide to VRPTW Optimization with OR-Tools

Vehicle Routing Problem with Time Windows (VRPTW)Link Copied

The Vehicle Routing Problem with Time Windows (VRPTW) is a fundamental optimization challenge in logistics and supply chain management. At its core, VRPTW seeks to determine the most efficient routes for a fleet of vehicles to serve a set of customers, where each customer must be visited within a specific time window. This problem extends the classic Vehicle Routing Problem (VRP) by incorporating temporal constraints that reflect real-world delivery scenarios where customers have preferred or required service times.

The VRPTW is particularly relevant in modern logistics operations, from e-commerce delivery to field service management. Unlike simple routing problems that only consider distance or travel time, VRPTW must balance multiple competing objectives: minimizing total travel cost, respecting vehicle capacity constraints, and ensuring all customers are served within their specified time windows. This makes it a complex combinatorial optimization problem that often requires sophisticated algorithms to solve efficiently.

The problem becomes exponentially more complex as the number of customers and vehicles increases, making it computationally challenging for large-scale instances. However, modern optimization tools like Google OR-Tools provide powerful solvers that can handle realistic problem sizes while finding high-quality solutions in reasonable time.

AdvantagesLink Copied

VRPTW solutions can significantly reduce total travel time and distance, leading to lower fuel costs, reduced vehicle wear, and improved driver productivity. By optimizing routes, companies can serve more customers with the same fleet size or maintain service levels with fewer vehicles. These operational efficiencies translate directly to bottom-line savings, making VRPTW optimization a high-value investment for logistics operations of any scale.

Time window constraints ensure that deliveries arrive when customers expect them, improving service quality and customer satisfaction. This is particularly important for time-sensitive deliveries like medical supplies, perishable goods, or scheduled appointments where late arrivals can have serious consequences. By explicitly modeling customer preferences, VRPTW solutions help businesses build trust and maintain strong customer relationships.

Modern VRPTW solvers can handle problems with hundreds of customers and dozens of vehicles, making them suitable for real-world applications. The solutions can be updated dynamically as new orders arrive or conditions change, allowing dispatchers to respond to evolving circumstances throughout the day. This scalability and adaptability make VRPTW a practical tool for both strategic route planning and day-to-day operational decisions.

DisadvantagesLink Copied

As a variant of the Traveling Salesman Problem, VRPTW is NP-hard, meaning solution time grows exponentially with problem size. While modern solvers can handle realistic instances with hundreds of customers, very large problems may require heuristic approaches or problem decomposition strategies that sacrifice guaranteed optimality for computational tractability.

Finding optimal solutions for large instances can be computationally expensive, forcing practitioners to balance solution quality with computation time. In practice, this often means accepting near-optimal solutions that can be found quickly rather than waiting hours or days for provably optimal routes. The gap between the best-known solution and the theoretical optimum may be acceptable for operational purposes but can be frustrating when marginal improvements matter.

Real-world routing often involves dynamic changes such as new orders arriving throughout the day, unexpected traffic conditions, or vehicle breakdowns that can invalidate pre-computed solutions. This volatility requires either frequent re-optimization, which adds computational overhead, or robust solution approaches that build in slack to accommodate changes. Neither approach is perfect, and dispatchers must often make real-time adjustments that deviate from the optimized plan.

FormulaLink Copied

Every optimization problem tells a story of choices and consequences. In VRPTW, the story begins with a simple question: How do we teach a computer to make the same decisions a skilled dispatcher makes instinctively? A human dispatcher juggles multiple concerns simultaneously: which truck goes where, what time to arrive, how much each vehicle can carry. To solve this problem computationally, we must translate this intuition into precise mathematical language.

This section develops the mathematical formulation step by step. For each component, we'll ask: Why do we need this? and What happens if we leave it out? By the end, you'll understand both what the formulas say and why each component is important for capturing the real-world complexity of vehicle routing.

The Dispatcher's Dilemma: Three Intertwined DecisionsLink Copied

Picture yourself as a logistics dispatcher on a Monday morning. You have a fleet of delivery trucks, a list of customers expecting packages, and a day's worth of time windows to honor. Your job is to answer three fundamental questions:

1. Assignment: Which vehicle should visit which customers?
2. Sequencing: In what order should each vehicle make its stops?
3. Timing: When exactly should each vehicle arrive at each location?

At first glance, these might seem like separate problems. But consider what happens when you try to solve them independently:

• You assign Customer A to Truck 1 because it's nearby, but Truck 1 is already overloaded.
• You sequence Customer B before Customer C because B is closer to the depot, but Customer B's time window doesn't open until the afternoon.
• You schedule an arrival at 10:00 AM, but given travel times, the truck can't possibly get there before noon.

The fundamental insight is that these three decisions are deeply interconnected. The sequence of visits determines travel times, which determine arrival times, which must fit within time windows, which constrain which sequences are feasible, which affects how we assign customers to vehicles. It's a web of dependencies that we must capture mathematically.

The Language of Optimization: Parameters and VariablesLink Copied

Before we can express our dispatcher's decisions mathematically, we need to establish a precise vocabulary. In optimization, we distinguish between two types of quantities:

• Parameters: Fixed information about the problem that we cannot change
• Decision variables: The unknowns that the solver must determine

Think of parameters as the rules of the game, and decision variables as the moves we're trying to optimize.

The Problem Landscape (Parameters):

The world we're optimizing within is defined by several fixed quantities:

• Locations ($V$): The depot (node 0) serves as home base, where all vehicles start and must return. The remaining nodes $\{1, 2, ..., n\}$ represent customers awaiting service.

• Fleet ($K$): We have $m$ vehicles at our disposal. Each vehicle $k$ has a capacity $Q_k$ representing the maximum total demand it can carry. A delivery van might hold 20 packages; a truck might have a 10-ton weight limit.

• Network ($A$): Between any two locations, there exists a potential route. The arc $(i,j)$ represents the possibility of traveling directly from $i$ to $j$, with travel time $t_{ij}$ and cost $c_{ij}$.

• Customer Requirements: Each customer $i$ has a demand $d_i$ (how much they need), a time window $[a_i, b_i]$ (when they can receive service), and a service time $s_i$ (how long the delivery takes once the vehicle arrives).

The Decisions We Must Make (Variables):

Our mathematical model must determine two types of quantities:

• Route structure ($x_{ijk}$): For every possible arc $(i,j)$ and every vehicle $k$, we must decide: does vehicle $k$ use this arc? The binary nature of this variable (it can only be 0 or 1) reflects the discrete reality of routing: a truck either takes a road or it doesn't.

• Arrival schedule ($w_{ik}$): For every location and vehicle, we must determine the arrival time. Unlike routing decisions, timing is continuous: a vehicle might arrive at 10:15 or 10:16 or any time in between.

These two variable types encode the spatial dimension (where do vehicles go?) and the temporal dimension (when do they get there?) of our solution. The constraints we'll develop ensure these two dimensions remain consistent with each other and with real-world requirements.

The Objective: What Are We Trying to Achieve?Link Copied

With our vocabulary established, we can now state what we're trying to accomplish. In most routing problems, efficiency means minimizing total cost, whether that's travel time, distance, fuel consumption, or some combination.

Reading the formula: This expression says: "For every vehicle $k$ and every possible arc $(i,j)$, if that vehicle uses that arc ($x_{ijk} = 1$), add the arc's cost $c_{ij}$ to our total. If the arc isn't used ($x_{ijk} = 0$), add nothing."

The binary variable $x_{ijk}$ acts as a switch: it "turns on" the cost $c_{ij}$ only when the arc is actually part of a route. Summing over all vehicles and all arcs gives us the total operational cost of our solution.

What does "cost" mean in practice?

This formulation is flexible. The cost $c_{ij}$ could represent:

• Travel time (minimize total driving hours)
• Distance (minimize fuel consumption)
• Monetary cost (including tolls, fuel, driver wages)
• Environmental impact (minimize carbon emissions)

The mathematical structure remains identical regardless of which metric we optimize.

The Constraints: Rules That Solutions Must ObeyLink Copied

The objective function tells us what we want to achieve, but without constraints, the solver would trivially "solve" the problem by not sending any vehicles anywhere: zero cost! Constraints encode the rules that separate valid solutions from invalid ones.

Each constraint we introduce addresses a specific way that a solution could fail in the real world. As we develop each constraint, we'll ask: What goes wrong if we omit this rule?

Constraint 1: Complete Service CoverageLink Copied

The requirement: Every customer must be visited exactly once by exactly one vehicle.

What could go wrong without it: A cost-minimizing solver might skip difficult-to-reach customers entirely, or send multiple vehicles to easy customers while ignoring others.

where:

• $K$: set of vehicles $\{1, 2, ..., m\}$
• $V$: set of all nodes (depot and customers)
• $x_{ijk}$: binary variable equal to 1 if vehicle $k$ travels from node $i$ to node $j$
• $i$: customer node (the constraint applies to all customers, i.e., $V \setminus \{0\}$)

Interpreting the mathematics: For each customer $i$ (excluding the depot), count how many arcs leave that customer across all vehicles and all possible destinations. That count must equal exactly 1.

The summation $\sum_{j \in V, j \neq i} x_{ijk}$ counts arcs of the form "$i$ → something" for vehicle $k$, that is, arcs departing from customer $i$. Summing over all vehicles $k$ gives the total number of departures from customer $i$. Since every visit requires exactly one departure, requiring this sum to equal 1 ensures:

• No customer is skipped (sum ≥ 1)
• No customer is visited multiple times (sum ≤ 1)

This constraint forms the foundation of our model. It defines what it means to "serve" all customers.

Constraint 2: Vehicle Capacity LimitsLink Copied

The requirement: No vehicle can carry more than its capacity allows.

What could go wrong without it: The solver might assign every customer to a single vehicle if that minimizes travel cost, ignoring physical impossibility.

where:

• $V \setminus \{0\}$: set of customer nodes (excluding the depot)
• $d_i$: demand at customer $i$ (units of capacity required)
• $x_{ijk}$: binary variable equal to 1 if vehicle $k$ travels from $i$ to $j$
• $Q_k$: capacity of vehicle $k$ (maximum total demand it can serve)
• $k$: vehicle index

Interpreting the mathematics: For each vehicle $k$, we compute the total demand it serves. The inner sum $\sum_{j \neq i} x_{ijk}$ equals 1 if vehicle $k$ visits customer $i$, and 0 otherwise. Multiplying by demand $d_i$ and summing over all customers gives the total load. This must not exceed the vehicle's capacity $Q_k$.

Step-by-step logic:

1. Does vehicle $k$ visit customer $i$? Check if $\sum_{j \neq i} x_{ijk} = 1$ (yes) or 0 (no)
2. If yes, that customer's demand $d_i$ counts toward the vehicle's load
3. Sum all such demands: $\sum_i d_i \cdot (\text{visited?})$
4. Ensure total ≤ capacity: the inequality $\leq Q_k$

This constraint bridges the abstract routing model with physical reality. Trucks have finite space, and our solution must respect this.

Constraint 3: Flow Conservation (Route Continuity)Link Copied

The requirement: If a vehicle enters a location, it must also leave that location.

What could go wrong without it: The solver might create "broken" routes where vehicles appear at customers without a connected path from the depot, or routes that form isolated loops disconnected from the depot.

where:

• $x_{ijk}$: binary variable equal to 1 if vehicle $k$ travels from $i$ to $j$ (arc leaving $i$)
• $x_{jik}$: binary variable equal to 1 if vehicle $k$ travels from $j$ to $i$ (arc entering $i$)
• The constraint applies to all nodes $i \in V$ and all vehicles $k \in K$

Interpreting the mathematics: This is a classic "flow balance" constraint from network optimization. For any node $i$ and vehicle $k$:

• Left side: $\sum_{j \neq i} x_{ijk}$ counts arcs leaving $i$ (from $i$ to anywhere)
• Right side: $\sum_{j \neq i} x_{jik}$ counts arcs entering $i$ (from anywhere to $i$)

These must be equal. Since all variables are binary, this means: enter a node exactly once → leave exactly once. Never enter → never leave.

Why this works: Combined with the service coverage constraint, flow conservation ensures that every vehicle's route forms a connected path starting at the depot, visiting some customers, and returning to the depot. There are no gaps, no teleportation, no vehicles stuck at customers.

Constraint 4: Time Window ComplianceLink Copied

The requirement: Arrivals must fall within each customer's specified time window.

What could go wrong without it: The solver might schedule arrivals at 3 AM for customers who are only open 9-5, or create routes that are spatially efficient but temporally infeasible.

where:

• $a_i$: earliest acceptable arrival time at location $i$ (lower bound of time window)
• $b_i$: latest acceptable arrival time at location $i$ (upper bound of time window)
• $w_{ik}$: continuous variable representing when vehicle $k$ arrives at location $i$
• The constraint applies to all nodes $i \in V$ and all vehicles $k \in K$

Interpreting the mathematics: This is a simple bound constraint on the arrival time variable. For each location $i$ and vehicle $k$, the arrival time $w_{ik}$ must be:

• Not earlier than the earliest acceptable time $a_i$
• Not later than the latest acceptable time $b_i$

The "TW" in VRPTW: This constraint is what distinguishes VRPTW from basic vehicle routing. Time windows add a temporal dimension that interacts with spatial routing decisions. You can't just find the shortest path; you must find a path that's also timely.

Constraint 5: Temporal Precedence (The Big-M Technique)Link Copied

The requirement: If a vehicle travels from $i$ to $j$, the arrival time at $j$ must be consistent with departing from $i$.

What could go wrong without it: The solver might set arrival times arbitrarily, claiming a vehicle arrives at customer B before customer A even though the route visits A first. The route structure and the timing schedule would be disconnected from each other.

where:

• $w_{ik}$: arrival time of vehicle $k$ at node $i$
• $s_i$: service time at node $i$ (time spent performing the delivery)
• $t_{ij}$: travel time from node $i$ to node $j$
• $w_{jk}$: arrival time of vehicle $k$ at node $j$
• $x_{ijk}$: binary variable equal to 1 if vehicle $k$ travels directly from $i$ to $j$
• $M$: a sufficiently large constant (the "big-M" value)
• $A$: set of all arcs (possible direct connections)

This is the most subtle constraint in our formulation. It must accomplish something tricky: enforce a timing relationship only when an arc is actually used. The Big-M technique achieves this through clever algebraic manipulation.

Case 1: When the arc IS used ($x_{ijk} = 1$):

The right-hand side becomes $M(1-1) = 0$, so the constraint simplifies to:

This says: arrival at $j$ must be at least arrival at $i$ + service time at $i$ + travel time from $i$ to $j$. Time moves forward along the route.

Case 2: When the arc is NOT used ($x_{ijk} = 0$):

The right-hand side becomes $M(1-0) = M$, where $M$ is a very large number. The constraint becomes:

Since $M$ is huge, this is essentially always satisfied. The arrival times at $i$ and $j$ are independent, as they should be, since there's no direct route connecting them.

Choosing $M$: The value must be large enough that the constraint is non-binding when $x_{ijk} = 0$, but not so large as to cause numerical instability. A safe choice is $M = \max(b_i) - \min(a_i) + \max(t_{ij}) + \max(s_i)$, which represents the maximum possible time span in the problem.

The diagram above makes the Big-M mechanism visible. The key insight is that this single constraint accomplishes two things: it enforces physical causality when routes are used, while remaining "invisible" for routes that don't exist in the solution. This conditional behavior is what makes Big-M constraints effective for modeling conditional relationships in optimization problems.

Constraint 6: The Binary DomainLink Copied

The requirement: Routing decisions must be discrete: either a vehicle takes an arc, or it doesn't.

where:

• $x_{ijk}$: the routing decision variable for arc $(i,j)$ and vehicle $k$
• $\{0,1\}$: the binary domain (variable can only take value 0 or 1)
• $A$: set of all arcs
• $K$: set of all vehicles

This might seem like a trivial "constraint," but it's actually what makes VRPTW computationally challenging. If we allowed $x_{ijk}$ to take any value between 0 and 1 (a "relaxation"), we could solve the problem much faster using continuous optimization techniques. A solution might say "send 0.3 of a vehicle from A to B," which is mathematically valid but operationally meaningless.

The binary requirement forces discrete decisions: a truck either takes a road or it doesn't. There's no "half a route." This discreteness is what transforms a tractable linear program into the NP-hard mixed-integer program that VRPTW is known to be.

Seeing the System: How Constraints InteractLink Copied

We've now developed six constraints, but they don't operate in isolation. They form an interconnected system where a change in one part ripples through the others. Understanding this interaction is key to understanding why VRPTW is both powerful and challenging.

The Two Decision Dimensions:

Our model has two types of decision variables that the solver must determine simultaneously:

These two dimensions are coupled through the precedence constraint (Big-M): the route structure determines which temporal relationships must hold.

The Constraint Ecosystem:

Think of the constraints as forming an ecosystem where each one addresses a potential failure mode:

1. Service coverage ensures no customer is forgotten
2. Capacity limits prevent physical overloading
3. Flow conservation ensures routes are connected paths
4. Time windows honor customer requirements
5. Temporal precedence links space and time
6. Binary domain forces discrete decisions

The solver's task is to find values for all variables that satisfy every constraint simultaneously while minimizing total cost. This is like solving a puzzle where each piece constrains what other pieces can be, except this puzzle has an exponentially large number of possible configurations.

The diagram above visualizes this architecture. Notice how the routing variables ($x_{ijk}$) flow downward into spatial constraints (coverage, capacity, flow), while timing variables ($w_{ik}$) connect to temporal constraints (time windows). The precedence constraint sits at the center, serving as the bridge that couples these two worlds. This coupling is what makes VRPTW fundamentally more challenging than solving routing and scheduling as separate problems. The two dimensions must be optimized jointly.

The Computational Challenge: Why VRPTW Is HardLink Copied

Having built our mathematical model, we should understand what we're asking a computer to do when we hand it this formulation.

The Curse of Combinatorics:

VRPTW inherits its difficulty from the Traveling Salesman Problem (TSP), which asks: "What's the shortest route visiting $n$ cities exactly once?" TSP is NP-hard, meaning no known algorithm can solve all instances quickly. VRPTW is strictly harder: it's TSP with additional constraints layered on top.

Consider the size of the search space for a modest problem with $n$ customers and $m$ vehicles:

For 20 customers and 3 vehicles, there are roughly $3^{20} \approx 3.5 \times 10^9$ possible customer-vehicle assignments, and for each assignment, we must consider many possible orderings. The total number of potential solutions dwarfs the number of atoms in the observable universe for even moderately sized problems.

Why We Need Sophisticated Algorithms:

Enumeration (checking every possible solution) is clearly infeasible. Instead, modern solvers employ clever strategies:

• Branch-and-bound: Systematically explore the solution space while pruning branches that can't lead to optimal solutions
• Constraint propagation: Use constraints to eliminate infeasible variable values early
• Metaheuristics: Use local search, simulated annealing, or genetic algorithms to find good (if not optimal) solutions quickly
• Hybrid approaches: Combine exact methods with heuristics for the best of both worlds

The mathematical formulation we've developed is the foundation upon which all these algorithms operate. It precisely defines what we're looking for. The algorithms provide strategies for finding it.

Visualizing VRPTWLink Copied

Let's create visualizations to understand the VRPTW problem structure and solution characteristics.

ExampleLink Copied

Now let's see how the mathematical formulation works in practice by solving a small, concrete example. This hands-on walkthrough will help you understand how the constraints interact and how a valid solution satisfies all requirements simultaneously.

Problem Setup: A Simple Delivery ScenarioLink Copied

Imagine you run a small delivery service with:

• 1 depot (your warehouse, location 0)
• 4 customers (locations 1-4) needing deliveries
• 2 vehicles, each with capacity 10 units

Each customer has specific requirements: a demand (how much they need), a time window (when they can receive delivery), and travel times between locations. Let's examine the data:

Key observations from the data:

• Customer 1 has the earliest time window (1-4) and is closest to the depot (travel time 2)
• Customer 4 has the latest time window (4-7) and is farthest from the depot (travel time 5)
• Total demand is 3+2+4+3 = 12 units, which exceeds either vehicle's capacity (10), so we need both vehicles
• The time windows overlap, creating flexibility in sequencing

Building a Solution: Step-by-Step Constraint CheckingLink Copied

Let's construct a feasible solution manually, checking each constraint as we go. This demonstrates how the mathematical formulation translates to practical routing decisions.

Step 1: Assigning Customers to VehiclesLink Copied

We need to partition the 4 customers between 2 vehicles. Let's try:

• Vehicle 1: Customers 1 and 3 (demands: 3 + 4 = 7 units)
• Vehicle 2: Customers 2 and 4 (demands: 2 + 3 = 5 units)

Capacity check (Constraint 2):

• Vehicle 1: 7 ≤ 10
• Vehicle 2: 5 ≤ 10

Both assignments satisfy capacity constraints. Now we need to determine the sequence of visits for each vehicle.

Step 2: Sequencing Visits for Vehicle 1Link Copied

Vehicle 1 must visit Customers 1 and 3. Let's consider the sequence: Depot → Customer 1 → Customer 3 → Depot

Time window check (Constraints 4 and 5):

Let's trace the route step by step, using our notation:

• Start at depot: $w_{0,1} = 0$ (vehicle 1 starts at depot at time 0)
• Travel to C1: $t_{0,1} = 2$ (travel time from depot to customer 1)
  • Arrival at C1: $w_{1,1} = w_{0,1} + t_{0,1} = 0 + 2 = 2$
  • Time window check: $a_1 = 1 \leq w_{1,1} = 2 \leq b_1 = 4$ (Constraint 4 satisfied)
  • Service at C1: $s_1 = 0$ (assume 0 service time for simplicity)
• Travel to C3: $t_{1,3} = 3$ (travel time from customer 1 to customer 3)
  • Arrival at C3: $w_{3,1} = w_{1,1} + s_1 + t_{1,3} = 2 + 0 + 3 = 5$
  • Time window check: $a_3 = 3 \leq w_{3,1} = 5 \leq b_3 = 6$ (Constraint 4 satisfied)
  • Precedence check: $w_{1,1} + s_1 + t_{1,3} = 2 + 0 + 3 = 5 \leq w_{3,1} = 5$ (Constraint 5 satisfied)
• Return to depot: $t_{3,0} = 4$ (travel time from customer 3 to depot)
  • Arrival at depot: $w_{0,1} = w_{3,1} + s_3 + t_{3,0} = 5 + 0 + 4 = 9$

Flow conservation check (Constraint 3):

• Vehicle 1 enters C1: 1 arc (from depot)
• Vehicle 1 leaves C1: 1 arc (to C3)
• Vehicle 1 enters C3: 1 arc (from C1)
• Vehicle 1 leaves C3: 1 arc (to depot)

Route 1 is feasible! In terms of our decision variables:

• $x_{0,1,1} = 1$ (vehicle 1 travels depot→C1)
• $x_{1,3,1} = 1$ (vehicle 1 travels C1→C3)
• $x_{3,0,1} = 1$ (vehicle 1 travels C3→depot)
• $w_{1,1} = 2$, $w_{3,1} = 5$ (arrival times)

Step 3: Sequencing Visits for Vehicle 2Link Copied

Vehicle 2 must visit Customers 2 and 4. Let's try: Depot → Customer 2 → Customer 4 → Depot

Time window check:

Tracing route 2 with our notation:

• Start at depot: $w_{0,2} = 0$ (vehicle 2 starts at depot at time 0)
• Travel to C2: $t_{0,2} = 3$ (travel time from depot to customer 2)
  • Arrival at C2: $w_{2,2} = w_{0,2} + t_{0,2} = 0 + 3 = 3$
  • Time window check: $a_2 = 2 \leq w_{2,2} = 3 \leq b_2 = 5$ (Constraint 4 satisfied)
  • Service at C2: $s_2 = 0$ (assume 0 service time)
• Travel to C4: $t_{2,4} = 3$ (travel time from customer 2 to customer 4, from distance matrix row 2, column 4)
  • Arrival at C4: $w_{4,2} = w_{2,2} + s_2 + t_{2,4} = 3 + 0 + 3 = 6$
  • Time window check: $a_4 = 4 \leq w_{4,2} = 6 \leq b_4 = 7$ (Constraint 4 satisfied)
  • Precedence check: $w_{2,2} + s_2 + t_{2,4} = 3 + 0 + 3 = 6 \leq w_{4,2} = 6$ (Constraint 5 satisfied)
• Return to depot: $t_{4,0} = 5$ (travel time from customer 4 to depot)
  • Arrival at depot: $w_{0,2} = w_{4,2} + s_4 + t_{4,0} = 6 + 0 + 5 = 11$

Route 2 is also feasible! Decision variables:

• $x_{0,2,2} = 1$, $x_{2,4,2} = 1$, $x_{4,0,2} = 1$
• $w_{2,2} = 3$, $w_{4,2} = 6$

Step 4: Verifying All ConstraintsLink Copied

Let's verify that our complete solution satisfies all constraints:

Constraint 1 (Each customer visited exactly once):

For each customer $i \in V \setminus \{0\}$, we verify:

• Customer 1 ($i=1$):

(Only $x_{0,1,1} = 1$, all others are 0)

• Customer 2 ($i=2$):

(Only $x_{0,2,2} = 1$)

• Customer 3 ($i=3$):

  $$\sum_{k \in \{1,2\}} \sum_{j \in \{0,1,2,4\}} x_{j,3,k} = x_{1,3,1} + x_{1,3,2} + \cdots = 1 + 0 + \cdots = 1$$

  (Only $x_{1,3,1} = 1$)

• Customer 4 ($i=4$):

(Only $x_{2,4,2} = 1$)

Constraint 2 (Capacity):

For vehicle 1 ($k=1$):

Since $x_{0,1,1} = 1$ and $x_{1,3,1} = 1$ (and all other $x_{ijk} = 0$ for vehicle 1):

For vehicle 2 ($k=2$):

Since $x_{0,2,2} = 1$ and $x_{2,4,2} = 1$ (and all other $x_{ijk} = 0$ for vehicle 2):

Constraint 3 (Flow conservation): Already verified in Steps 2 and 3

Constraint 4 (Time windows): Already verified in Steps 2 and 3

Constraint 5 (Temporal precedence): Already verified in Steps 2 and 3

Constraint 6 (Binary variables): All $x_{ijk}$ are 0 or 1

Solution SummaryLink Copied

Our complete solution:

Route 1 (Vehicle 1): Depot → Customer 1 → Customer 3 → Depot

• Arcs used: $x_{0,1,1} = 1$, $x_{1,3,1} = 1$, $x_{3,0,1} = 1$
• Travel time calculation:

• Demand served:

• Arrival times: $w_{1,1} = 2$ (within window $[a_1, b_1] = [1, 4]$), $w_{3,1} = 5$ (within window $[a_3, b_3] = [3, 6]$)

Route 2 (Vehicle 2): Depot → Customer 2 → Customer 4 → Depot

• Arcs used: $x_{0,2,2} = 1$, $x_{2,4,2} = 1$, $x_{4,0,2} = 1$
• Travel time calculation:

• Demand served:

• Arrival times: $w_{2,2} = 3$ (within window $[a_2, b_2] = [2, 5]$), $w_{4,2} = 6$ (within window $[a_4, b_4] = [4, 7]$)

Total travel time (objective value):

where $c_{ij} = t_{ij}$ (using travel time as cost).

The visualizations above show the complete worked example. The first figure displays the spatial routes with travel times annotated on each arc, customer demands (d), and time windows (TW). The second figure shows the timeline for how each vehicle progresses through time, with shaded regions representing time windows and vertical bars marking actual arrival times. Notice how all arrivals fall within their respective time windows, confirming the solution's feasibility.

Why This Solution WorksLink Copied

This example illustrates several key insights:

1. Capacity constraints force customer partitioning: Since total demand (12) exceeds individual vehicle capacity (10), we need to use both vehicles. The capacity constraint guides how we group customers.

2. Time windows influence sequencing: Customer 1's early window (1-4) makes it a natural first stop. Customer 4's later window (4-7) provides flexibility for later visits.

3. Travel times affect feasibility: The sequence C1→C3 works because travel time 3 allows arrival at C3 (time 5) within its window [3,6]. A different sequence might violate time windows.

4. Constraints are interdependent: We can't optimize routes independently. The capacity constraint affects which customers can be grouped, which affects sequencing options, which affects time window feasibility.

This small example demonstrates the complexity that emerges even with just 4 customers. Real-world problems with hundreds of customers require sophisticated algorithms to navigate this constraint space efficiently.

Implementation in Google OR-ToolsLink Copied

Now that we understand the mathematical formulation and have worked through a manual example, let's see how to implement VRPTW using Google OR-Tools. This implementation translates our mathematical constraints into code, allowing the solver to automatically find optimal or near-optimal solutions.

From Mathematics to Code: Mapping ConstraintsLink Copied

OR-Tools uses a constraint programming approach that implements our mathematical formulation through "dimensions" and "callbacks." Each constraint from our formulation maps to specific OR-Tools constructs:

• Routing decisions ($x_{ijk}$): Handled automatically by the routing model's internal variables
• Time tracking ($w_{ik}$): Implemented through a "Time" dimension
• Capacity constraints: Implemented through a "Capacity" dimension
• Time windows: Set as bounds on the Time dimension
• Flow conservation: Enforced automatically by the routing model structure

Let's build the implementation step by step, connecting each code section to its corresponding mathematical concept.

We'll implement VRPTW step by step, starting with the data model and then building the solver configuration. This approach helps understand how each component maps to the mathematical formulation.

Now we'll create the solver function that implements all the constraints from our mathematical formulation:

Now let's solve the problem and extract the solution:

Display the solution results:

The objective value represents the sum of all arc costs used in the routes, corresponding to our mathematical objective function $\min \sum_{k \in K} \sum_{(i,j) \in A} c_{ij} x_{ijk}$. The solution assigns customers to vehicles such that all capacity constraints are satisfied (each vehicle carries at most 8 units of demand) and all time windows are respected. Finding a feasible solution confirms that all constraints can be satisfied simultaneously for this problem instance.

Let's visualize the solution to see how vehicles are assigned to customers: