一、节省矩阵法表5由节省矩阵得到的修正路线2234591678101113路线121102021133021154401815285510141819066901317192967701214162733883767012141599021146780580101010122229161128658011121425343216321115450121215161410181912203281312121112151618013
表5由节省矩阵得到的修正路线2 路线 1 2 3 4 5 6 7 8 9 10 11 12 13 1 1 0 2 2 11 0 3 3 21 15 0 4 4 18 15 28 0 5 5 10 14 18 19 0 6 6 9 13 17 19 29 0 7 6 7 12 14 16 27 33 0 8 8 3 7 6 7 12 14 15 0 9 9 0 2 1 1 4 6 7 8 0 10 10 5 10 11 12 22 28 29 16 8 0 11 6 5 11 12 14 25 34 32 16 8 32 0 12 12 1 5 4 5 12 15 16 14 10 18 19 0 13 13 0 3 2 2 8 12 12 11 12 15 16 18 0 一、节省矩阵法
一、节省矩阵法下一个最大节省量为32，即把顾客10合并到路线6中（我们不必考虑顾客7和顾客11合并之后的节省量，因为这两个点已经在路线6中了）。但是，这是不合理的，因为顾客10的载重量为47，47+163>200，而下一个最大节省量是29，即合并顾客5或顾客10合并到线路6中，但这也同样超过了卡车的转载量。继续反复以上过程可以得到路线合并矩阵（如表6），即可以得到（1，3，4){2，9)67，8，11)5，10，12，13)，每一个路线由一辆卡车运输。下一步确定卡车访问顾客的顺序
下一个最大节省量为32，即把顾客10合并到路线6中（我们不 必考虑顾客7和顾客11合并之后的节省量，因为这两个点已经在路线 6中了）。但是，这是不合理的，因为顾客10的载重量为47，47＋ 163 > 200，而下一个最大节省量是29，即合并顾客5或顾客10合 并到线路6中，但这也同样超过了卡车的转载量。继续反复以上过程 可以得到路线合并矩阵（如表6），即可以得到{1，3，4}{2，9}{6， 7，8，11}{5，10，12，13}，每一个路线由一辆卡车运输。下一步 确定卡车访问顾客的顺序。 一、节省矩阵法