顺序排位 连接线 节约里程 顺序排位 连接线 节约里程
1 2 3 4 4 6 6 6 9 9 11 12
A－B A－J B－C D－E C－D A－I E－F I－J A－C B－J B－D C－E
15 13 11 10 10 9 9 9 8 8 7 6
13 13 13 16 16 16 19 19 21 22 22 22
D
C
B
A E
P
J
F
G H
图1 配送网络图
I
表1 各连锁分店需求量
分店 数量 重量
重量单位：吨
I J
合计
A
B
C
D
E
F
G
H
41
用节约里程法进行求解，其步骤如下： 用节约里程法进行求解，其步骤如下： 第一步： 第一步 ： 从配送网络图中计算出配送中心至各连锁分店及各连锁分店之间的最 短距离，并做出最短距离表（见表2） 短距离，并做出最短距离表（见表 ）。
表3 节约里程表
A A B C D E F G H I J
B
C
D
E
F
G
H
I
J
第三步：将节约里程由大到小顺序排列， 第三步：将节约里程由大到小顺序排列，列出节约里程排序表 见表4），以便尽量使节约里程最多的点组合装车配送。 ），以便尽量使节约里程最多的点组合装车配送 （见表 ），以便尽量使节约里程最多的点组合装车配送。
0.32 0.40 0.40
D
C
B
A
0.24
0.32路线1 2EP路线2 2J
0.24
F
0.16
G
0.48
路线3 2
H
0.40
图2 配送路线图
I
0.32
从配送路线图可看出， 从配送路线图可看出 ，依次确定的三条配送路线均符合配送中心的约 束条件，需要2t货车 货车3辆 总走行里程为70km，若简单地每个连锁分店 束条件，需要 货车 辆，总走行里程为 ， 送货，需要2t货车 货车10辆 走行总里程148km。 送货，需要 货车 辆，走行总里程 。
节约里程法作业
某连锁零售店，下设有一个配送中心P 某连锁零售店，下设有一个配送中心P 10个连锁分店 个连锁分店A 和10个连锁分店A～J，配送中心和各连锁 分店及各连锁分店之间的位置关系如下图 所示， 1所示，两点间连线上的数字为两点间的 路线长度（单位：公里）。 ）。各连锁分店对 路线长度（单位：公里）。各连锁分店对 某种商品的需求量见表1 某种商品的需求量见表1，该商品由配送 中心统一采购并进行配送。 中心统一采购并进行配送。配送中心备用 2t和4t的货车 的货车， 2t和4t的货车，限定送货车辆一次巡回距 离不超过35公里， 35公里 离不超过35公里，设送到时间均符合用户 要求，求配送中心的最优送货方案。 要求，求配送中心的最优送货方案。
P P A B C D E F G H I J
A
B
表2 最短距离表 C D E F
G
H
I
J
第二步：由最短距离表，利用“节约里程” 第二步：由最短距离表，利用“节约里程”法计算出各连锁分 店之间的节约里程，做出节约里程表（见表3）， ），计算结果有正 店之间的节约里程，做出节约里程表（见表 ），计算结果有正 有负，节约里程为负数时，无实际意义，在表内写0。 有负，节约里程为负数时，无实际意义，在表内写 。
F－G G－H H－I B－I A－D F－H B－E D－F G－I C－J E－G F－I
5 5 5 4 4 4 3 3 2 1 1 1
第四步： 第四步：根据节约里程排序表和配送车辆载重及行驶里程等约束 条件，渐近绘出如图 所示的配送路线图 所示的配送路线图。 条件，渐近绘出如图2所示的配送路线图。