Clark and Wright's Saving Method Only consider situation of c Suppose that initially a separate vehicle is assigned to each customer location.Then the initial solution consists of n separate routes from the depot to each customer location and back,so that the initial solution is2 ● Suppose that link customer i and j,then save two trips 0-j and 0-i, however add one trip i-j.The saved cost by linking i and j is Si-coi-cor Ci
Clark and Wright’s Saving Method • Only consider situation of cij = cji. • Suppose that initially a separate vehicle is assigned to each customer location. Then the initial solution consists of n separate routes from the depot to each customer location and back, so that the initial solution is 0 1 2 n j j c • Suppose that link customer i and j, then save two trips 0-j and 0- i, however add one trip i -j. The saved cost by linking i and j is : 0 i j sij = c 0 i + c 0j - cij
Clark and Wright's Saving Method The total number of calculation of s,is: Procedures: n! n(n-1) 2(n-2)！ 2 1.Compute s,for all possible pairs of customer locations i andj, and rank the s in decreasing order. 2.According to descending order of savings,include link(i,in a route if it does not violate feasibility constraints. 3.If including the current link(i,violates the feasibility, consider other feasible link (i,until all the lists is exhausted,and then stop the current route. 4.If the current route includes all the remaining locations,stop; otherwise,go to Step 2 to form a new route
Clark and Wright’s Saving Method Procedures: 1. Compute sij for all possible pairs of customer locations i and j, and rank the sij in decreasing order. 2. According to descending order of savings, include link ( i, j) in a route if it does not violate feasibility constraints. 3. If including the current link ( i, j) violates the feasibility, consider other feasible link ( i, j) until all the lists is exhausted, and then stop the current route. 4. If the current route includes all the remaining locations, stop; otherwise, go to Step 2 to form a new route. The total number of calculation of is: ! ( 1) 2 2!( 2)! 2 ij s n n nn n
Determining Delivery Routes in Supply Chains Custom Location Example 6.4-Whole Grains is a bakery that Daily Req. supplies five major customers with bread each (Loaves) morning.The locations of the bakery and the five 1 (15,30) 85 customers and their demand are given as 2 (5,30) 162 described in a grid.The bakery has several 3 (10,20) 26 delivery trucks,each having a capacity of 300 4 (5,5) 140 loaves. 5 (20,10) 110 Cost Matrix(c)(=distance) 30 ⊙ Customer 2 Customer 1 TO g25 0 2 34 5 20 ◇Customer3 F 0 33.530.4 22.47.1 22.4 15 R 1 10.0 11.2 26.9 20.6 Customer 5 0 2 11.2 25.0 25.0 10 Customer 4 M 3 15.8 14.1 5 4 15.8 Bakery 5 10 15 2025
Determining Delivery Routes in Supply Chains Example 6.4-Whole Grains is a bakery that supplies five major customers with bread each morning. The locations of the bakery and the five customers and their demand are given as described in a grid. The bakery has several delivery trucks, each having a capacity of 300 loaves. Custom Location Daily Req. ( Loaves) 1 2 3 4 5 (15, 30) (5, 30) (10, 20) (5, 5) (20, 10) 85 162 26 140 110 Cost Matrix (cij) (=distance) TO F 0 R 1 O 2 M 3 4 0 1 2 3 4 5 33.5 30.4 22.4 7.1 22.4 10.0 11.2 26.9 20.6 11.2 25.0 25.0 15.8 14.1 15.8
Determining Delivery Routes in Supply Chains Saving for all pairs (i,j),i,j=1~5: 85+162=247<300 S12=C01+c02-C12-33.5+30.4-10=53.9 30 S13-44.7,S14=13.7,S15=35.3,S23=41.6 Customer 2 Customer 1 S24-12.5,S25=27.8 25 S34=13.7,S35=30.7,s45=13.7 247+26=273<300 .Rank the customer pairs in the 20 Customer 3 decreasing order of all the saving values:(1,2)→(1,3)>(2,3)→(1,5) 15 →(1,4)(3,4)，(4,5)→(2,4) Customer 5 10 Customer 4 Customer Daily Req.(Loaves) 5 110+140=250<300 1 85 2 162 3 26 Bakery 5 1015 2025 4 140 XI- 5 110
Determining Delivery Routes in Supply Chains • Saving for all pairs (i, j), i, j=1~5: s12=c01+c02-c12=33.5+30.4-10=53.9 s13=44.7, s14 =13.7, s15=35.3, s23=41.6, s24=12.5, s25=27.8 s34=13.7, s35=30.7, s45=13.7 •Rank the customer pairs in the decreasing order of all the saving values: (1, 2) (1, 3) (2, 3) (1, 5) (1, 4), (3, 4), (4, 5) (2, 4) Customer Daily Req.( Loaves) 1 2 3 4 5 85 162 26 140 110 85+162=247<300 247+26=273<300 110+140=250<300