Savings Matrix Method
This method is simple to implement and can be used to assign customers to vehicles even
when delivery time windows or other constraints exist. The major steps in the
savings matrix method are
1. Identify the distance matrix
2. Identify the savings matrix
3. Assign customers to vehicles or routes
4. Sequence customers within routes
Identify the Distance Matrix
The distance matrix identifies the distance between every pair of locations to be visited. The
distance is used as a surrogate for the cost of traveling between the pair of locations.
If the transportation costs between every pair of locations are known, the costs can
be used in place of distances. The distance Dist(A,B) on a grid between a point A
with coordinates (xA, yA) and a point B with coordinates (xB, yB) is evaluated as
Dist(A, B) = (xA-x
B)2+ (yA-y
B)2 (14.1)
The distance between every pair of location for Peapod is shown in Table 14.12.
The distances between every pair of locations are next used to evaluate the savings matrix.
14.7 ROUTING AND SCHEDULING IN TRANSPORTATION
DC Cust
1Cust
2Cust
3Cust
4Cust
5Cust
6Cust
7Cust
8Cust
9Cust
10 Cust
11 Cust
12 Cust
13
DC 0
Cust 1 12 0
Cust 2 8 9 0
Cust 3178100
Cust 4159840
Cust 5 15 17 9 14 11 0
Cust 6 20 23 15 20 16 6 0
Cust 7 17 22 13 20 16 5 4 0
Cust 8 8 17 9 19 16 11 14 10 0
Cust 9 6 18122220172016 6 0
Cust 101623142219 9 8 4 8 14 0
Cust 11212818262211 7 6 1319 5 0
Cust 121122142421141612 5 7 9 13 0
Cust 13152720302822232012 9 1620 8 0
TABLE 14.12 Distance Matrix for Peapod Deliveries
S(x, y) = Dist(DC, x) + Dist(DC, y) – Dist(x, y) (14.2)
Cust
1Cust
2Cust
3Cust
4Cust
5Cust
6Cust
7Cust
8Cust
9Cust
10 Cust
11 Cust
12 Cust
13
Cust 1 0
Cust 2 11 0
Cust 3 21 15 0
Cust 4 18 15 28 0
Cust 5 10 14 18 19 0
Cust 6 9 13171929 0
Cust 7 7 1214162733 0
Cust 837671214150
Cust 9021146780
Cust 10 5 10 11 12 22 28 29 16 8 0
Cust 11 5 11 12 14 25 34 32 16 8 32 0
Cust 121 5 4 5 12151614101819 0
Cust 13 0 3 2 2 8 12 12 11 12 15 16 18 0
TABLE 14.13 Savings Matrix for Peapod Deliveries
Identify the Savings Matrix
