BA 308B
Dr. Campbell
VEHICLE ROUTING
I. The Traveling Salesman Problem (TSP)
Imagine a salesman that must visit n customers or cities. He starts at one city and must visit each of the other n1 cities exactly once and then return to the original city. The cost of traveling from city i to city j is given as cij for all pairs of cities. The problem is to design a route or tour of minimum cost that visits each of the n cities exactly once.
If the cost to travel from city i to city j equals the cost to travel from city j to city i, (cij=cji) for all cities, then the problem is symmetric. If cij cji for some pair of cities, then the problem is asymmetric.
ClarkeWright Savings
1. Select any city as the "central city" and call it city k.
2. Calculate the savings sij=cik+ckjcij for i=1,2...n, j=1,2...n, ik, jk,ij
(If k = 1, then sij = ci1 + c1j cij for i=2,3...n, j=2,3...n ij)
3. Order the savings, sij, from largest to smallest.
4. Starting with the largest savings, do the following:
(a)If linking cities i and j results in a feasible route, then add this link to the tour; if not, reject the link.
(b)Try the next savings in the list and repeat (a)
Do not break any links formed earlier.
Stop when all cities are in the tour.
1
BA 308B
Dr. Campbell
II. Distribution from one warehouse to n customers (cities)
Given:1) n customers with known locations and demands
2) identical delivery vehicles of known capacity
3) a distance or time limit for every vehicle route
Design vehicle routes so that the total length is minimized and
a) the requirements of all customers are satisfied,
b) the vehicle capacities are not exceeded, and
c) the distance or time limit is not violated.
ClarkeWright Savings
Label the customers as cities 1,2,...,n and let the warehouse be city 0.
Determine the costs cij to travel between all pairs of cities and the warehouse i=0,1,..,n; j=0,...,n.
1.Select the warehouse as the central city.
2.Calculate the savings sij=ci0+c0jcij for all pairs of cities (customers) i, j
(i=1,2...n; j=1,2...n; ij).
3.Order the savings, sij, from largest to smallest.
4.Starting with the largest savings, do the following:
(a)If linking cities i and j results in a feasible route, then add this link to the route; if not, reject the link.
(b) Try the next savings in the list and repeat (a).
Do not break any links formed earlier.
Start new routes when necessary.
Stop when all cities are on a route.
CLARKE-WRIGHT SAVING HEURISTIC - EXAMPLE
The warehouse is located at (40,40).
Customer / Location / Demand / cij / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 81 / (22,22) / 18 / 0 / - / 26 / 15 / 20 / 7 / 25 / 16 / 24 / 29
2 / (36,26) / 26 / 1 / - / 15 / 23 / 26 / 33 / 40 / 38 / 54
3 / (21,45) / 11 / 2 / - / 24 / 13 / 20 / 27 / 35 / 43
4 / (45,35) / 30 / 3 / - / 26 / 42 / 34 / 15 / 39
5 / (55,20) / 21 / 4 / - / 18 / 14 / 31 / 32
6 / (55,45) / 16 / 5 / - / 25 / 49 / 45
7 / (26,59) / 29 / 6 / - / 32 / 20
8 / (55,65) / 37 / 7 / - / 30
10 units
1
BA 308B
Dr. Campbell
Savings: (sij = sji because the cost is symmetric)
s12 = 26= 26 + 15 - 15 (c10 + c02 - c12 = c01 + c02 - c12 )
s13 = 23 = 26 + 20 - 23(c10 + c03 - c13 = c01 + c03 - c13 )
s14 = 7= 26 + 7 - 26(c10 + c04 - c14 = c01 + c04 - c14 )
s15 = 18= 26 + 25 - 33(c10 + c05 - c15 = c01 + c05 - c15 )
s16 = 2= 26 + 16 - 40(c10 + c06 - c16 = c01 + c06 - c16 )
s17 = 12= 26 + 24 - 38(c10 + c07 - c17 = c01 + c07 - c17 )
s18 = 1= 26 + 29 - 54(c10 + c08 - c18 = c01 + c08 - c18 )
s23 = 11= 15 + 20 - 24(c20 + c03 - c23 = c02 + c03 - c23 )
s24 = 9= 15 + 7 - 13(c20 + c04 - c24 = c02 + c04 - c24 )
s25 = 20= 15 + 25 - 20(c20 + c05 - c24 = c02 + c05 - c25 )
s26 = 4= 15 + 16 - 27(c20 + c06 - c24 = c02 + c06 - c26 )
s27 = 4= 15 + 24 - 35(c20 + c07 - c24 = c02 + c07 - c27 )
s28 = 1= 15 + 29 - 43(c20 + c08 - c28 = c02 + c08 - c28 )
s34 = 1= 20 + 7 - 26(c30 + c04 - c34 = c03 + c04 - c34 )
s35 = 3= 20 + 25 - 42(c30 + c05 - c35 = c03 + c05 - c35 )
s36 = 2= 20 + 16 - 34(c30 + c06 - c36 = c03 + c06 - c36 )
s37 = 29= 20 + 24 - 15(c30 + c07 - c37 = c03 + c07 - c37 )
s38 = 10= 20 + 29 - 39(c30 + c08 - c38 = c03 + c08 - c38 )
s45 = 14= 7 + 25 - 18(c40 + c05 - c45 = c04 + c05 - c45 )
s46 = 9= 7 + 16 - 14(c40 + c06 - c46 = c04 + c06 - c46 )
s47 = 0= 7 + 24 - 31(c40 + c07 - c47 = c04 + c07 - c47 )
s48 = 4= 7 + 29 - 32(c04 + c08 - c48 = c04 + c08 - c48 )
s56 = 16= 25 + 16 - 25(c50 + c06 - c56 = c05 + c06 - c56 )
s57 = 0= 25 + 24 - 49(c50 + c07 - c57 = c05 + c07 - c57 )
s58 = 9= 25 + 29 - 45(c50 + c08 - c58 = c05 + c08 - c58 )
s67 = 8= 16 + 24 - 32(c60 + c07 - c67 = c06 + c07 - c67 )
s68 = 25= 16 + 29 - 20(c60 + c08 - c68 = c06 + c08 - c68 )
s78 = 23= 24 + 29 - 30(c70 + c08 - c78 = c07 + c08 - c78 )
1
BA 308B
Dr. Campbell
Order the Savings from Largest to Smallest
s37
s12
s68
s13, s78(tie)
s25
s15
s56
s45
s17
s23
s38
s24, s58, s49(tie)
etc.
Form Vehicle Routes Based on Vehicle Capacities
Example a) Vehicle Capacity = 200note: only 1 route will be needed (TSP)
At first tie, use s13 before s78
s370-3-7-0
s120-3-7-0 , 0-1-2-0
s680-3-7-0 , 0-1-2-0 , 0-6-8-0
s130-2-1-3-7-0 , 0-6-8-0
s780-2-1-3-7-8-6-0
s250-5-2-1-3-7-8-6-0
s15x
s56x
s450-4-5-2-1-3-7-8-6-0
Cost = 7 + 18 + 20 + 15 + 23 + 15 + 30 + 20 + 16 = 164
Now, at first tie use s78 before s13
s370-3-7-0
s120-3-7-0 , 0-1-2-0
s680-3-7-0 , 0-1-2-0 , 0-6-8-0
s780-6-8-7-3-0 , 0-1-2-0
s130-6-8-7-3-1-2-0same as with s13 first, so solution is same as above
1
BA 308B
Dr. Campbell
Example b) Vehicle Capacity = 100note: at least 2 routes will be needed
At first tie, use s13 before s78
s370-3-7-0 d=40
s120-3-7-0 d=40 , 0-1-2-0 d=44
s680-3-7-0 d=40 , 0-1-2-0 d=44 , 0-6-8-0 d=53
s130-2-1-3-7-0 d=84 , 0-6-8-0 d=53
s78x
s25x
s15x
s560-2-1-3-7-0 d=84 , 0-5-6-8-0 d=74
s45, s17, s23x
Note: only remaining customer is #4 with demand=30, so start a new route
0-2-1-3-7-0 d=84 , 0-5-6-8-0 d=74 , 0-4-0 d=30
Cost = 92 + 99 + 14 = 205
Now, at first tie use s78 before s13
s370-3-7-0 d=40
s120-3-7-0 d=40 , 0-1-2-0 d=44
s680-3-7-0 d=40 , 0-1-2-0 d=44 , 0-6-8-0 d=53
s780-3-7-8-6-0 d=93 , 0-1-2-0 d=44
s13x
s250-3-7-8-6-0 d=93 , 0-1-2-5-0 d=65
s15x
s56x
s450-3-7-8-6-0 d=93 , 0-1-2-5-4-0 d=95
Cost = 101 + 86 = 187
This solution has two routes and is better than solution above (187 versus 205)!
1
BA 308B
Dr. Campbell
Example c) Vehicle Capacity = 70note: at least 3 routes will be needed
At first tie, use s13 before s78
s370-3-7-0 d=40
s120-3-7-0 d=40 , 0-1-2-0 d=44
s680-3-7-0 d=40 , 0-1-2-0 d=44 , 0-6-8-0 d=53
s13x
s78x
s250-3-7-0 d=40 , 0-1-2-5-0 d=65 , 0-6-8-0 d=53
s15x
s56x
s45, s17, s23, ...x (none can be used)
Note: Only remaining customer is #4 with demand=30.
This will only fit on the first route (next to customer 3 or 7), so compare these two options:
s43 = s34= 1 > s74 = s47= 0.
0-4-3-7-0 d=70 , 0-1-2-5-0 d = 65 , 0-6-8-0 d=53
Cost = 72 + 86 + 65 = 223.
Now, at first tie use s78 before s13
s370-3-7-0 d=40
s120-3-7-0 d=40 , 0-1-2-0 d=44
s680-3-7-0 d=40 , 0-1-2-0 d=44 , 0-6-8-0 d=53
s78x
s13x
Note this is the same as above, so the order for s13 and s78 does not matter in this case. These savings can not be used either way!
1
BA 308B
Dr. Campbell
VEHICLE ROUTING PRACTICE PROBLEMS
1. Given the following cij matrix, find the shortest traveling salesman tour:
(Use the Nearest Neighbor and ClarkeWright heuristics. Use City 1 as the central city.)
to1 / 2 / 3 / 4 / 5
1 / - / 17 / 8 / 19 / 10
2 / 17 / - / 6 / 2 / 3
3 / 8 / 6 / - / 7 / 4
4 / 19 / 2 / 7 / - / 5
5 / 10 / 3 / 4 / 5 / -
Answer: route = 1-5-2-4-3-1 length or cost = 30
2. Given the following cij matrix, determine the shortest vehicle routes and their lengths to distribute goods from one warehouse, denoted 0 below, to the seven customers, denoted 17 below, when:
a) all vehicles have a capacity of 80 units.
b) all vehicles have a capacity of 25 units.
c) all vehicles have a capacity of 16 units.
to0 / 1 / 2 / 3 / 4 / 5 / 6 / 7
0 / - / 4 / 8 / 3 / 9 / 6 / 5 / 11
1 / - / 9 / 6 / 10 / 3 / 4 / 6
2 / - / 8 / 4 / 8 / 12 / 5
3 / - / 9 / 8 / 7 / 3
4 / - / 11 / 12 / 2
5 / - / 8 / 15
6 / - / 12
7 / -
The demand at each customer is as follows:
Customer1234567
Demand (units)46881257
Answers:
a) length or cost = 39
b) length or cost = 48
c) length or cost = 64
1