VRPTW Routing › Formula

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.

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.

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 Parameters:

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

• Locations ($V$): The depot (node 0) is 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.

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.

$$\min \sum_{k \in K} \sum_{(i,j) \in A} c_{ij} x_{ijk}$$

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 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 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.

$$\sum_{k \in K} \sum_{j \in V, j \neq i} x_{ijk} = 1 \quad \forall i \in V \setminus \{0\}$$

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.

$$\sum_{i \in V \setminus \{0\}} d_i \sum_{j \in V, j \neq i} x_{ijk} \leq Q_k \quad \forall k \in K$$

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.

$$\sum_{j \in V, j \neq i} x_{ijk} = \sum_{j \in V, j \neq i} x_{jik} \quad \forall i \in V, \forall k \in K$$

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.

$$a_i \leq w_{ik} \leq b_i \quad \forall i \in V, \forall k \in K$$

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.

$$w_{ik} + s_i + t_{ij} - w_{jk} \leq M(1 - x_{ijk}) \quad \forall (i,j) \in A, \forall k \in K$$

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 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:

$$w_{ik} + s_i + t_{ij} \leq w_{jk}$$

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:

$$w_{ik} + s_i + t_{ij} - w_{jk} \leq M$$

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.

$$x_{ijk} \in \{0,1\} \quad \forall (i,j) \in A, \forall k \in K$$

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 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 maps a tractable linear program into the NP-hard mixed-integer program that VRPTW is known to be.

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.

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.