两个例子 - 节约里程法.ppt

1、节约法的基本原理,假如由一家配送中心P向两个用户A、B送货，配送中心到两客户的最短距离分别是L1和L2，A和B间的最短距离为L3，AB的货物需求量分别是Q1和Q2，且Q1+Q2小于车辆装载量Q，如下图所示。,图81 节约法原理示意图,如果配送中心用两辆汽车分别对A、B两个用户各自往返送货时，汽车行驶的总里程L是 L=2（L1+ L2） 如果用一辆汽车向A、B两个用户巡回送货，则汽车行驶总里程L为 L= L1+ L2 + L3 根据三角形的一边之长必定小于另外两边之和的原理，后一种配送方案比前一种方案节约里程L为 L=2（L1+ L2）-（L1+ L2 + L3）= L1+ L2 -L3,示例,

2、位于市内的百家姓配送中心（P0）向它旗下的10家连锁商店pi(i=1,2,10)配送商品，其配送网络如下图所示。 图中括号内的数字表示每一家连锁店的需求量（t），线路上的数字表示两节点之间的距离（km）。配送中心现有2t和4t车辆可供使用，并且每辆车配送距离不得超过30km。 请为百家姓配送中心制定最优的配送方案。,配送网络图,P0,百家姓配送中心交通图,配送网络图,P0,初始方案：从P点向各点分别派车送货。,初始方案运行结果： 1、从百家姓配送中心出发，需要设计10条配送线路，分别向10家连锁店配送商品； 2、需要10辆2t的配送车辆（每家连锁店的需要量都低于2t），总配送距离为148km。

3、,最短距离矩阵,第一步：作出最短距离矩阵，从配送网络图中列出配送中心至用户相互间的最短距离矩阵 。,准备相关资料：,第二步：从最短矩阵中，计算用户相互间的节约里程。,节约里程计算过程,准备相关资料：,第三步：将节约里程按大小顺序排列分类。,节约里程排序表,修正初始方案：按节约里程大小顺序，组成配送线路。,P0,J,I,H,G,F,E,D,C,B,A,5,4,7,4,7,8,8,8,3,4,10,（0.7）,（1.5）,（0.8）,（0.6）,线路1：运距27km，4t车一辆,修正结果：运距109km，车辆4t1辆，2t6辆,9,10,（0.4）,（0.5）,5,修正1套方案：按节约里程大小顺序

4、，组成配送线路。,P0,J,I,H,G,F,E,D,C,B,A,5,4,7,4,7,8,8,8,3,4,10,（0.7）,（1.5）,（0.8）,（0.6）,（0.4）,（1.4）,6,（1.5）,7,（0.6）,6,线路1：运距27km，4t车一辆,线路2：运距30km，4t车一辆,修正结果：运距85km，车辆4t2辆，2t2辆,（0.5）,修正2套方案：按节约里程大小顺序，组成配送线路。,P0,J,I,H,G,F,E,D,C,B,A,5,4,7,4,7,8,3,4,10,（0.7）,（1.5）,（0.8）,（0.6）,（0.4）,（1.4）,6,（1.5）,7,（0.6）,6,线路1：运距

5、27km，4t车一辆,修正结果：运距80km，车辆4t2辆，2t1辆,线路2：运距30km，4t车一辆,（0.5）,（0.8）,9,线路3：运距23km，2t车一辆,练习,例：如图所示为配送中心P的配送网络图，某配送中心P向A、B、C、D、E五个客户配送物品。图中边线上的数字表示公路里程（km）。靠近各用户括号里的数字表示对货物的需求量（t）。配送中心备有2t和4t载重量的汽车，汽车一次巡回行驶里程不能超过30km。求解配送路线方案。,（1）计算配送中心P至各用户之间的最短距离，如表所示:,（3）根据节约里程表中节约数额的多少从大到小排序，编制节约里程序列表，如表83所示。,（4）根据节约里程

6、序列表和配送中心的约束条件，先选择C、D合并，考察合并后的巡回里程以及载重量是否都符合配送要求。然后再考虑合并第三个站点，节约里程数次优的为D、E合并。因此按照最大节约原则可以考虑将客户E并入C、D站点群；但是，首先要考虑合并后车辆的载重量以及行驶里程的限制，即使其中一个突破了约束，也应该舍弃该合并方案。这里合并后车辆的载重量为3.5t（2+1+0.5=3.5），行驶里程刚好为30km，符合约束条件，需要一辆4t车。并且，并入E点后，再不能并入其他任何站点，该路线设计完毕。,现在只剩下A、B两个客户还没有安排配送路线，由于两个客户的货物需求总量为4.5t，已经超过4t车的最大载重量，因此只能是分别进行配送，还需要一辆4t车和一辆2t车。由此分析得出的配送路线如图83所示。,图83 配送路线,因此，按照节约法设计的配送方案是使用2辆4t车, 1辆2t车, 总行驶里程为52km。 其中：