VRPTW Routing › Example

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.

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

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:

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

• Customer 1 ($i=1$):

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

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

• Customer 2 ($i=2$):

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

(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$):

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

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

Constraint 2 (Capacity):

For vehicle 1 ($k=1$):

$$\sum_{i \in V \setminus \{0\}} d_i \sum_{j \in V, j \neq i} x_{ijk} = d_1 \cdot \sum_{j \neq 1} x_{j,1,1} + d_3 \cdot \sum_{j \neq 3} x_{j,3,1}$$

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

$$= d_1 \cdot x_{0,1,1} + d_3 \cdot x_{1,3,1} = 3 \cdot 1 + 4 \cdot 1 = 3 + 4 = 7 \leq Q_1 = 10$$

For vehicle 2 ($k=2$):

$$\sum_{i \in V \setminus \{0\}} d_i \sum_{j \in V, j \neq i} x_{ijk} = d_2 \cdot \sum_{j \neq 2} x_{j,2,2} + d_4 \cdot \sum_{j \neq 4} x_{j,4,2}$$

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

$$= d_2 \cdot x_{0,2,2} + d_4 \cdot x_{2,4,2} = 2 \cdot 1 + 3 \cdot 1 = 2 + 3 = 5 \leq Q_2 = 10$$

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

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:

$$\sum_{(i,j) \in \text{route}} t_{ij} = t_{0,1} + t_{1,3} + t_{3,0} = 2 + 3 + 4 = 9$$

• Demand served:

$$\sum_{i \in \{1,3\}} d_i = d_1 + d_3 = 3 + 4 = 7 \text{ units}$$

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

$$\sum_{(i,j) \in \text{route}} t_{ij} = t_{0,2} + t_{2,4} + t_{4,0} = 3 + 3 + 5 = 11$$

• Demand served:

$$\sum_{i \in \{2,4\}} d_i = d_2 + d_4 = 2 + 3 = 5 \text{ units}$$

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

$$\sum_{k \in K} \sum_{(i,j) \in A} c_{ij} x_{ijk} = 9 + 11 = 20$$

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.

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 search this constraint space efficiently.