Lecture 20: Vehicle Routing Problem

TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 1
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 2

Outline
1) Introduction

2) Exact Solution Method

3) Heuristics

• Sweep Algorithm

• Savings (Clarke-Wright)
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 3

1. Introduction
• Vehicle Routing Problem
❑ Given: One origin/depot, many
destinations, sequential stops, multiple
vehicles
❑ Find: a set of routes connecting each
stop once and only once and returning
to the origin/depot
❑ It generalises the well-known travelling
salesman problem (TSP).

3
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 4

1. Introduction
• Many applications in the transportation & logistics area:
❑ Ship Routing

❑ Postman Delivery Problem

❑ School Bus Routing

❑ Last Mile Delivery

School bus routing

Liner service routing Urban logistics delivery 4

TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 5

2. Model Formulation
• Integer Programming Model
Indices: Path-based formulation:
• 𝑖: customer
• 𝑘: vehicle route
Sets: min ෍ 𝑐𝑘 𝜆𝑘
• 𝑁: set of customers 𝑘∈𝐾
• 𝐾: set of vehicle routes Subject to:
Parameters: Each customer
෍ 𝛼𝑖𝑘 𝜆𝑘 = 1 ∀𝑖 ∈ 𝑁 should be served.
• 𝛼𝑖𝑘 ∈ 0,1 : 1 if customer 𝑖 is served by
vehicle route 𝑘; 0 otherwise 𝑘∈𝐾
• 𝐷𝑖 : demand of customer 𝑖 ෍ 𝛼𝑖𝑘 𝐷𝑖 𝜆𝑘 ≤ 𝑄𝑘 ∀𝑘 ∈ 𝐾 Vehicle capacity
• 𝑐𝑘 : general cost (time, distance, etc.) of
𝑖∈𝑁
vehicle route 𝑘
• 𝑄𝑘 : loading capacity of vehicle 𝑘 ෍ 𝜆𝑘 ≤ 𝑉 Fleet size
Decision variable: 𝑘
• 𝜆𝑘 ∈ 0,1 : 1 if vehicle route 𝑘 is employed; 0 𝜆𝑘 ∈ {0,1}
otherwise
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 6

2. Model Formulation
• Integer Programming Model

6
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 7

2. Model Formulation
• Integer Programming Model
❑ How many potential routes are there?
▪ hint: Permutations of n choose k = n!/(n-k)!
▪ Over 9.8 million!!!
❑ In practice, routes are generated in a separate “sub-problem” and fed into the MILP “master
problem”
❑ Very active research area – solving very large scale optimization problems
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 8

2. Model Formulation
• Integer Programming Model
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 9

3. Heuristics
• Ideas:
Route first Cluster second Cluster first Route second
Any earlier TSP heuristic can be used • Sweep Algorithm
• Savings (Clarke-Wright)

20 20
7 7
10 10
16 16
6 6
9 9

12 12
2 2

8 1 8 1 DC
DC 5 5
8 8

4 4
3 3
4 4
0 0
0 5 10 15 20 0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 10

3. Heuristics: Sweep Algorithm

• Heuristic Procedure
❑ Step 1: Form a ray from the DC and select an angle and direction (CW vs CCW) to start
❑ Step 2: Select a new vehicle, j, that is empty, wj=0, and has capacity, cj.
❑ Step 3: Rotate the ray in selected direction until it hits a customer node, i, or reaches the
starting point (go to step 5).
❑ Step 4: If the demand at i (Di) plus current load already in the vehicle (wj) is less than the
vehicle capacity, add it to the vehicle, wj=Di + wj and go to step 3. Otherwise, close this
vehicle, and go to step 2 to start a new tour.
❑ Step 5: Solve the TSP for each independent vehicle tour.
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 11

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 0 none
12
4 54 2
5 31 DC
6 80 8 1 5
8
7 78
8 84
4
9 85 3
10 42 4
DC 0
0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 12

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 78 7
12
4 54 2
5 31 DC
6 80 8 1 5
8
7 78
8 84
4
9 85 3
10 42 4
DC 0
0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 13

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 158 7-6
12
4 54 2
5 31 DC
6 80 8 1 5
8
7 78
8 84
4
9 85 3
10 42 4
DC 0
0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 14

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 176 7-6-2
12
4 54 2
5 31 DC
6 80 8 1 5
8
7 78
8 84
4
9 85 3
10 42 4
DC 0
0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 15

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 176 7-6-2
12
4 54 176+31>200 2
5 31 DC
6 80 2 31 5 8 1 5
8
7 78
8 84
4
9 85 3
10 42 4
DC 0
0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 16

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 176 7-6-2
12
4 54 176+31>200 2
5 31 DC
6 80 2 84 5-3 8 1 5
8
7 78
8 84
4
9 85 3
10 42 4
DC 0
0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 17

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 176 7-6-2
12
4 54 176+31>200 2
5 31 DC
6 80 2 138 5-3-4 8 1 5
8
7 78
8 84
4
9 85 3
10 42 4
DC 0
0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 18

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 176 7-6-2
12
4 54 176+31>200 2
5 31 DC
6 80 2 138 5-3-4 8 1 5
8
7 78 138+84>200
8 84
4
9 85 3 84 8 3
10 42 4
DC 0
0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 19

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 176 7-6-2
12
4 54 176+31>200 2
5 31 DC
6 80 2 138 5-3-4 8 1 5
8
7 78 138+84>200
8 84
4
9 85 3 106 8-1 3
10 42 4
DC 0
0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 20

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 176 7-6-2
12
4 54 176+31>200 2
5 31 DC
6 80 2 138 5-3-4 8 1 5
8
7 78 138+84>200
8 84
4
9 85 3 191 8-1-9 3
10 42 4
DC 0
0 5 10 15 20
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 21

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 176 7-6-2
12
4 54 176+31>200 2
5 31 DC
6 80 2 138 5-3-4 8 1 5
8
7 78 138+84>200
8 84
4
9 85 3 191 8-1-9 3
10 42 4
191+42>200
DC 0
0 5 10 15 20
4 42 10
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 22

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 176 7-6-2
12
4 54 Route: DC-2-6-7-DC 23.3 miles 2
5 31 DC
6 80 2 138 5-3-4 8 1 5
8
7 78 Route: DC-5-3-4-DC 28.3 miles
8 84
4
9 85 3 191 8-1-9 3
10 42 4
Route: DC-8-1-9-DC 19.3 miles
DC 0
0 5 10 15 20
4 42 10
Route: DC-10-DC 17.2 miles
4 trucks 88.2 miles
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 23

3. Heuristics: Sweep Algorithm

• Example:
❑ Find minimum cost tours from DC to 10 destinations with demand as shown using up
to 4 vehicles of capacity of 200 units.

20
Demand 7
10
Node ID (units)
1 22 j wj clusterj 16
6
2 18 9
3 53 1 200 6-7-10
12
4 54 Route: DC-6-7-10-DC 30.6 miles 2
5 31 DC
6 80 2 191 8-1-9 8 1 5
8
7 78 Route: DC-8-1-9-DC 19.3 miles
8 84
4
9 85 3 191 2-5-3-4 3
10 42 4
Route: DC-2-5-3-4-DC 28.6 miles
DC 0
0 5 10 15 20
3 trucks 78.5 miles
Different starting points and directions can
yield different solutions! Best to use a variety or
a stack of heuristics.
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 24

3. Heuristics: Clark-Wright Savings Algorithm

• General Approach
❑ Start with a complete solution (out and back) 1
❑ Identify nodes to link to form a common tour by calculating the 2
savings:
▪ Example: joining node 1 & 2 into a single tour
✓ Current tours cost = 2cO1 + 2cO2
✓ Joined tour costs = cO1 + c12 + c2O 3
Depot
▪ So, if 2cO1 + 2cO2 > cO1 + c12 + c2O then join them
▪ That is: cO1 + c2O – c12 > 0
❑ This savings value can be calculated for every pair of nodes
❑ Run through the nodes pairing the ones with the highest 4

savings first
❑ Need to make sure vehicle capacity is not violated
❑ Also, “interior tour” nodes cannot be added – must be on end.
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 25

3. Heuristics: Clark-Wright Savings Algorithm

• Heuristic Procedure:
❑ Step 1: Calculate savings si,j = cO,i + cO,j - ci,j for every pair (i, j) of demand nodes.
❑ Step 2: Rank and process the savings si,j in descending order of magnitude.
❑ Step 3: For the savings si,j under consideration, include arc (i, j) in a route only if:
▪ No route or vehicle constraints will be violated by adding it in a route and
▪ Nodes i and j are first or last nodes to/from the origin in their current route.
❑ Step 4: If the savings list has not been exhausted, return to Step 3, processing the next
entry in the list; otherwise, stop.
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 26

3. Heuristics: Clark-Wright Savings Algorithm

• Example: Find minimum cost tours from DC to 10 destinations with demand as shown using
<= 4 vehicles of capacity of 200 units.
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 27

3. Heuristics: Clark-Wright Savings Algorithm

• Example: Find minimum cost tours from DC to 10 destinations with
demand as shown using <= 4 vehicles of capacity of 200 units.

Initial Total Distance = 133.2

20
7
Consider joining 7-6 10
w = 80 + 78= 158 ≤200 OK 16
Distance = 133.2 – 13.8 = 119.4 9
6

Consider joining 10-9 12

w = 85 + 42 = 127 ≤200 OK 2
Distance = 119.4 – 10.0 = 109.4 DC
8 1 5
8
Consider joining 4-1
w = 54 + 22 = 76 ≤200 OK 4
3
Distance = 109.4 – 9.3 = 100.1 4
0
Consider joining 4-3 0 5 10 15 20
w = 76 + 53 = 129 ≤200 OK
Distance = 100.1 – 8.9 = 91.2

27
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 28

3. Heuristics: Clark-Wright Savings Algorithm

• Example: Find minimum cost tours from DC to 10 destinations with
demand as shown using <= 4 vehicles of capacity of 200 units.
Consider joining 10-7
w = 158 + 127 = 285 >200 NO 20
7
Consider joining 10-1 10
w = 129 + 127 = 256 >200 NO 16
6
9
Consider joining 6-5
w = 158 + 160 = 318 >200 NO 12
2
Consider joining 5-3 DC
8 1 5
w = 129 + 31 = 160 ≤200 OK 8
Distance = 91.2 – 7.2 = 84
4
Consider joining 7-5 3
4
w = 158 + 160 = 318 >200 NO
0
0 5 10 15 20
Consider joining 5-2
w = 160 + 18 = 178 ≤200 OK
Distance = 84 – 5.7 = 78.3
28
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 29

3. Heuristics: Clark-Wright Savings Algorithm

• Example: Find minimum cost tours from DC to 10 destinations with
demand as shown using <= 4 vehicles of capacity of 200 units.
Final Solution:
4 Routes for total 78.3 miles 20
7
10
Blue Route
16
DC-1-4-3-5-2-DC 9
6
178 units @ 33.4 miles
Red Route 12
2
DC-6-7-DC
DC
158 units @ 22.0 miles 8 1 5
Orange Route 8
DC-9-10-DC
4
127 units @ 17.2 miles 3
Green Route 4

DC-8-DC 0
0 5 10 15 20
84 units @ 5.7 miles

29
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 30

Key Points
❑ Sweep Heuristic – very fast – clusters and requires TSP in routing
❑ Clark-Wright – widely used – builds routes in sequence – can include other
considerations
❑ MILP – requires tours to be generated – can take a long time to solve

30
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 31

GOC 城市物流运输车辆智能调度

[Link]
31
TE3709 Logistics & Supply Chain Management Lecture 20: Vehicle Routing Problem 32

GOC 城市物流运输车辆智能调度

32