两个例子 - 节约里程法

节约法的基本原理假如由一家配送中心P向两个用户A、B送货，配送中心到两客户的最短距离分别是L1和L2，A和B间的最短距离为L3，AB的货物需求量分别是Q1和Q2，且Q1+Q2小于车辆装载量Q，如下图所示。ABPL1L2L3图8－1节约法原理示意图如果配送中心用两辆汽车分别对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示例位于市内的百家姓配送中心（P0）向它旗下的10家连锁商店pi(i=1,2,…,10)配送商品，其配送网络如下图所示。图中括号内的数字表示每一家连锁店的需求量（t），线路上的数字表示两节点之间的距离（km）。配送中心现有2t和4t车辆可供使用，并且每辆车配送距离不得超过30km。请为百家姓配送中心制定最优的配送方案。配送网络图P09e1.4861076f1.58g0.6329h0.84i0.510j0.67a0.710b1.59c0.87d0.485544118百家姓配送中心交通图配送网络图P0e1.48f1.58g0.63h0.84i0.510j0.67a0.710b1.59c0.87d0.48初始方案：从P点向各点分别派车送货。初始方案运行结果：1、从百家姓配送中心出发，需要设计10条配送线路，分别向10家连锁店配送商品；2、需要10辆2t的配送车辆（每家连锁店的需要量都低于2t），总配送距离为148km。P109479581410581814968181715137313121011106414131112128210111517181817119abcdefghij7481315151510118abcdefghij最短距离矩阵第一步：作出最短距离矩阵，从配送网络图中列出配送中心至用户相互间的最短距离矩阵。准备相关资料：第二步：从最短矩阵中，计算用户相互间的节约里程。1581147100361000039000015000004594000125abcdefghiPbcdefghij1381000009节约里程计算过程准备相关资料：第三步：将节约里程按大小顺序排列分类。1a—b152a—j133b—c1113f—g513g—h513h—i516a—d416b—i416f—h44c—d104d—e106a—i96e—f96i—j99a—c89b—j811b—d712c—e621g—i219b—e319d—f322c—j122e—g122f—i1节约里程排序表序号连接点节约里程序号连接点节约里程修正初始方案：按节约里程大小顺序，组成配送线路。P0JIHGFEDCBA547478883410（0.7）（1.5）（0.8）（0.6）线路1：运距27km，4t车一辆修正结果：运距——109km，车辆——4t1辆，2t6辆910（0.4）（0.5）5修正1套方案：按节约里程大小顺序，组成配送线路。P0JIHGFEDCBA547478883410（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套方案：按节约里程大小顺序，组成配送线路。P0JIHGFEDCBA5474783410（0.7）（1.5）（0.8）（0.6）（0.4）（1.4）6（1.5）7（0.6）6线路1：运距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。求解配送路线方案。PE(2)D(1)A(1.5)B(3)C(0.5)677998531443108（1）计算配送中心P至各用户之间的最短距离，如表所示:（3）根据节约里程表中节约数额的多少从大到小排序，编制节约里程序列表，如表8－3所示。（4）根据节约里程序列表和配送中心的约束条件，先选择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车。由此分析得出的配送路线如图8－3所示。PE(2)D(1)A(1.5)B(3)C(0.5)6778310路线1路线2路线3图8－3配送路线因此，按照节约法设计的配送方案是使用2辆4t车,1辆2t车,总行驶里程为52km。其中：路线1：4t车，载货量3.5t，行驶里程30km；路线2：2t车，载货量1.5t，行驶里程16km；路线3：4t车，载货量3t，行驶里程6km。