8/16/2020
Vehicle Routing Problems
Vehicle Routing
Applications
HUL serve consumer goods to all dealers within geographical region once
MilkDairies such as Amul collect the milk from farmers who geographically
dispersed and bring the milk to a central dairy for processing, twice every
day
GPO Postal van goes to number of post offices to collect speed post/other
posts every day
School bus goes to pick up a students
Problem of visiting n demand nodes from central depots using k number of
vehicles having c capacity
1
8/16/2020
Vehicle Routing Problem
• Suppose that a company owns several trucks. The company needs to deliver items to
various customers within the City.
• The manager takes a map of the city, plots all the customers on the map and finds that the
customers are scattered over the entire city area.
• Such problems may appear in case of e.g., an on-line grocery stores such as AMAZON
The orders are taken 24 hours on-line. When the manager starts working in the morning at
distribution hub, the manager has to decide number of vehicles and their routes.
Vehicle Routing Problem
Assume that
There are orders from 5 different customers
There are 2 trucks each capable of carrying 200 units
The manager must solve two sub-problems
1. Split the city into several smaller regions, each of which will be served
by one vehicle.
This can be done by considering a customer first, assigning the customer to a
vehicle, and then assigning other nearby customers to the same vehicle.
So, this sub-problem will be called assigning customers to vehicles.
2. Sequence customers served by the same vehicle.
2
8/16/2020
Vehicle Routing Problem
The objectives of the vehicle scheduling problem can be many.
Following are some examples:
Minimize total distance traveled
Minimize total travel time
Minimize cost
Let’s consider the problem with the objective of minimizing total distance
traveled.
Vehicle Routing Problem
X Coordinate Y Coordinate Order Size
W 0 0
1 0 12 48
2 6 5 60
3 7 15 43
4 9 12 92
5 15 3 80
Assume that the customer locations and order sizes are as shown above.
3
8/16/2020
Vehicle Routing Problem
1 4
5
2
W
Location of Warehouse and Customers
Solving Vehicle Routing Problem
Saving Matrix Method
Following are the steps of the Savings Matrix Method:
1. Identify distance matrix
2. Identify savings Matrix
3. Rank savings
4. Assign customers to vehicles
5. Sequence customers within routes
4
8/16/2020
Generating Distance Matrix
First, the Euclidean distances are computed. The formula
and a sample computation is shown below. The other
distances are computed similarly and shown on the next
slide.
Generating Distance Matrix
Distance Matrix
W Cust 1 Cust 2 Cust 3 Cust 4 Cust 5
Warehouse 0 12.0 7.8 16.6 15.0 15.3
Customer 1 0 9.2 7.6 9.0 17.5
Customer 2 0 10.0 7.6 9.2
Customer 3 0 3.6 14.4
Customer 4 0 10.8
Customer 5 0
5
8/16/2020
Generating Saving Matrix
The savings are computed for all pairs of customers using the
data from the distance matrix. The formula and a sample
computation is shown below. The other savings are computed
similarly.
Generating Saving Matrix
Savings Matrix
Cust 1 Cust 2 Cust 3 Cust 4 Cust 5
Customer 1 0 10.6 20.9 18.0 9.8
Customer 2 0 14.3 15.2 13.9
Customer 3 0 27.9 17.4
Customer 4 0 19.5
Customer 5 0
6
8/16/2020
Rank the Savings
• The next step is to rank the savings. The idea is to
merge those two customers to the same vehicle, whose
merging gives the highest savings.
• The savings are ranked from high to low.
• From the savings matrix shown on the previous slide,
the highest savings of 27.9 is obtained by merging
Customers 3 and 4 to the same vehicle.
• Next highest savings of 20.9 is obtained by merging
Customers 1 and 3 to the same vehicle.
• Similarly the other savings are ranked and shown on
the next slide.
Rank the Savings
Savings Matrix
Cust 1 Cust 2 Cust 3 Cust 4 Cust 5
Customer 1 0 10.6 20.9 18.0 9.8
Customer 2 0 14.3 15.2 13.9
Customer 3 0 27.9 17.4
Customer 4 0 19.5
Customer 5 0
Rank (3,4) (1,3) (4,5) (1,4) (3,5)
(2,4) (2,3) (2,5) (1,2) (1,5)
7
8/16/2020
Assign the customers to Vehicles
Next, merge the 3 Order
Customer
customers. The Size
pair giving the
1 4 1 48
highest savings
2 60
is merged first if
the capacity is 3 43
available. 5 4 92
2 5 80
W
Location of Warehouse and Customers
Rank (3,4) (1,3) (4,5) (1,4) (3,5)
(2,4) (2,3) (2,5) (1,2) (1,5)
Assign the customers to Vehicles
To merge the lowest
ranked pair (3,4),
the capacity
3 Order
required = 43+92= Customer
135 < 200 = Size
capacity available. 1 4 1 48
So, merge 3 and 4. 2 60
3 43
5 4 92
2 5 80
W
Location of Warehouse and Customers
Rank (3,4) (1,3) (4,5) (1,4) (3,5)
(2,4) (2,3) (2,5) (1,2) (1,5)
8
8/16/2020
Assign the customers to Vehicles
To merge the next
pair (1,3), capacity
required =
3 Order
43+92+40= 175 < Customer
200 = capacity Size
available. So, 1 4 1 48
merge 1 and 3 (and 2 60
4).
3 43
5 4 92
2 5 80
W
Location of Warehouse and Customers
Rank (3,4) (1,3) (4,5) (1,4) (3,5)
(2,4) (2,3) (2,5) (1,2) (1,5)
Assign the customers to Vehicles
Merging (4,5), (3,5),
(2,4) and (2,3)
requires more
3 Order
capacity than Customer
available. The pair Size
(1,4) is already 1 4 1 48
merged. So, the 2 60
pairs are crossed
out. 3 43
5 4 92
2 5 80
W
Location of Warehouse and Customers
Rank (3,4) (1,3) (4,5) (1,4) (3,5)
(2,4) (2,3) (2,5) (1,2) (1,5)
9
8/16/2020
Assign the customers to Vehicles
The next pair (2,5)
are merged and
assigned to a new
3 Order
vehicle as the Customer
capacity available = Size
200 > 60 + 80 = 140 1 4 1 48
= capacity required. 2 60
3 43
5 4 92
2 5 80
W
Location of Warehouse and Customers
Rank (3,4) (1,3) (4,5) (1,4) (3,5)
(2,4) (2,3) (2,5) (1,2) (1,5)
Questions?
hasmukh@[Link]
20
10