一、节省矩阵法1、建立距离矩阵距离矩阵确定点与点之间的距离，包括点到仓库的距离和各点之间的距离。两点之间的距离用公式（1）计算：（1）Dist(A, B) = V(xA -XB)? +(YA -YB)2
1、建立距离矩阵 距离矩阵确定点与点之间的距离，包括各点到仓库的距离和各点之间 的距离。两点之间的距离用公式(1)计算： 2 2 ( , ) ( ) ( ) Dist A B = xA − xB + YA −YB （1） 一、节省矩阵法
一、节省矩阵法由此，我们可以得到距离矩阵如表3所示：表3距离矩阵（对称矩阵）2391456813DC7101112011228908301710940481595151701411660201623152040752213201617880179191611141060962220172018121684801691410231422196570112128182622111319579012112214242114161213927203028222320121601315208(8)
由此，我们可以得到距离矩阵如表3所示： 表3 距离矩阵(对称矩阵） DC 1 2 3 4 5 6 7 8 9 10 11 12 13 1 12 0 2 8 9 0 3 17 8 10 0 4 15 9 8 4 0 5 15 17 9 14 11 0 6 20 23 15 20 16 6 0 7 17 22 13 20 16 5 4 0 8 8 17 9 19 16 11 14 10 0 9 6 18 12 22 20 17 20 16 6 0 10 16 23 14 22 19 9 8 4 8 14 0 11 21 28 18 26 22 11 7 6 13 19 5 0 12 11 22 14 24 21 14 16 12 5 7 9 13 0 13 15 27 20 30 28 22 23 20 12 9 16 20 8(8) 0 一、节省矩阵法
一、节省矩阵法2、建立节省矩阵如果一辆卡车把两个点的货物压缩到一条路线送，自然要比分别运送一个点返回DC，再去运送第二个点的货物要节省，这样节省矩阵就生成了。即把路线DC-A-DC和DC-B-DC合并成DC-A-B-DC，这将节省卡车走的距离，可以由公式2求得：S(A,B) = Dist(DC, A)+ Dist(DC,B)- Dist(A, B) (2)AADCDCBB
2、建立节省矩阵 如果一辆卡车把两个点的货物压缩到一条路线送，自然要比分别 运送一个点返回DC，再去运送第二个点的货物要节省，这样节省矩阵 就生成了。即把路线DC-A-DC和DC-B-DC合并成DC-A-B-DC，这将 节省卡车走的距离，可以由公式2求得： S(A,B) = Dist(DC, A) + Dist(DC,B) − Dist(A,B) （2） DC A B A B DC 一、节省矩阵法
一、节省矩阵法则可以得到如表4节省矩阵：表4节省矩阵123958DC46710111213010211302115041815285010181914960192913177701214162733837670121415046709211858010101129122228165801111121425321632341545012121516141018190322812121112151601318
则可以得到如表4节省矩阵： 表4 节省矩阵 DC 1 2 3 4 5 6 7 8 9 10 11 12 13 1 0 2 11 0 3 21 15 0 4 18 15 28 0 5 10 14 18 19 0 6 9 13 17 19 29 0 7 7 12 14 16 27 33 0 8 3 7 6 7 12 14 15 0 9 0 2 1 1 4 6 7 8 0 10 5 10 11 12 22 28 29 16 8 0 11 5 11 12 14 25 34 32 16 8 32 0 12 1 5 4 5 12 15 16 14 10 18 19 0 13 0 3 2 2 8 12 12 11 12 15 16 18 0 一、节省矩阵法
一、节省矩阵法首先，从上述矩阵中可以得到，合并路线6和路线11可以节省34，是其中最大的节省量。我们将这两条路线合并起来，合并这两条路线是可行的，因为路线6和路线11的载重之和为16+91=107，小于卡车的载重量200。34被排除后，节省量最大的是33，即将顾客7合并到路线6中，可以节省33，这也是可行的，因为顾客7的载重量为56，107+56=163，仍然低于200。因此顾客7合井到路线6中，如表5
首先，从上述矩阵中可以得到，合并路线6和路线11可以节 省34，是其中最大的节省量。我们将这两条路线合并起来，合并 这两条路线是可行的，因为路线6和路线11的载重之和为16＋91 ＝107，小于卡车的载重量200。34被排除后，节省量最大的是 33，即将顾客7合并到路线6中，可以节省33，这也是可行的，因 为顾客7的载重量为56，107＋56＝163，仍然低于200。因此顾 客7合并到路线6中，如表5。 一、节省矩阵法