两个例子 - 节约里程法

1、节约法的基本原理节约法的基本原理 假如由一家配送中心假如由一家配送中心P向两个用户向两个用户A、B送货，配送送货，配送中心到两客户的最短距离分别是中心到两客户的最短距离分别是L1和和L2，A和和B间的最短间的最短距离为距离为L3，AB的货物需求量分别是的货物需求量分别是Q1和和Q2，且，且Q1+Q2小小于车辆装载量于车辆装载量Q，如下图所示。，如下图所示。ABPL1L2L3图图81 节约法原理示意图节约法原理示意图 如果配送中心用两辆汽车分别对如果配送中心用两辆汽车分别对A、B两个用户两个用户各自往返送货时，汽车行驶的总里程各自往返送货时，汽车行驶的总里程L是是 L=2（L1+ L2） 如果用

2、一辆汽车向如果用一辆汽车向A、B两个用户巡回送货，则两个用户巡回送货，则汽车行驶总里程汽车行驶总里程L为为 L= L1+ L2 + L3 根据根据三角形的一边之长必定小于另外两边之和三角形的一边之长必定小于另外两边之和的的原理，后一种配送方案比前一种方案节约里程原理，后一种配送方案比前一种方案节约里程L为为 L=2（L1+ L2）-（L1+ L2 + L3）= L1+ L2 -L3l位于市内的百家姓配送中心（位于市内的百家姓配送中心（P P0 0）向它旗下的）向它旗下的1010家连锁商店家连锁商店p pi i(i=1,2,(i=1,2,10),10)配送商品，其配送商品，其配送网络如下图所示。

3、配送网络如下图所示。l图中括号内的数字表示每一家连锁店的需求量图中括号内的数字表示每一家连锁店的需求量（t t），），线路上的数字表示两节点之间的距离线路上的数字表示两节点之间的距离（kmkm）。配送中心现有）。配送中心现有2 2t t和和4 4t t车辆可供使用，车辆可供使用，并且每辆车配送距离不得超过并且每辆车配送距离不得超过30km30km。配送网络图配送网络图P09e1.4861076f1.58g0.6329h0.84i0.510j0.67a0.710b1.59c0.87d0.485544118配送网络图配送网络图P0e1.48f1.58g0.63h0.84i0.510j0.67a0.

4、710b1.59c0.87d0.48l初始方案运行结果：初始方案运行结果：l1 1、从百家姓配送中心出发，需要设计、从百家姓配送中心出发，需要设计1010条配条配送线路，分别向送线路，分别向1010家连锁店配送商品；家连锁店配送商品；l2 2、需要、需要1010辆辆2t2t的配送车辆（每家连锁店的需的配送车辆（每家连锁店的需要量都低于要量都低于2t2t），总配送距离为），总配送距离为148km148km。P109479581410581814968181715137313121011106414131112 128210111517181817119abcdefghij748131515151

5、0118abcdefghij1581147100361000039000015000004594000125abcdefghiPbcdefghij1381000009节约里程计算过程节约里程计算过程 1 1a ab b15152 2a aj j13133 3b bc c11111313f fg g5 51313g gh h5 51313h hi i5 51616a ad d4 41616b bi i4 41616f fh h4 44 4c cd d10104 4d de e10106 6a ai i9 96 6e ef f9 96 6i ij j9 99 9a ac c8 89 9b bj j

6、8 81111b bd d7 71212c ce e6 62121g gi i2 21919b be e3 31919d df f3 32222c cj j1 12222e eg g1 12222f fi i1 1序号序号连接点连接点节约里程节约里程序号序号连接点连接点节约里程节约里程修正结果：运距修正结果：运距109km109km，车辆，车辆4t14t1辆，辆，2t62t6辆辆修正结果：运距修正结果：运距85km85km，车辆，车辆4t24t2辆，辆，2t22t2辆辆修正结果：运距修正结果：运距80km80km，车辆，车辆4t24t2辆，辆，2t12t1辆辆练习练习 例：如图所示为配送中心例

7、：如图所示为配送中心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至各用户之间的最短距离，如表所

8、示至各用户之间的最短距离，如表所示:（3）根据节约里程表中节约数额的多少从大到小排序，根据节约里程表中节约数额的多少从大到小排序，编制编制节约里程序列表节约里程序列表，如表，如表83所示所示。 （4）根据节约里程序列表和配送中心的约束条件，根据节约里程序列表和配送中心的约束条件，先选择先选择C、D合并，考察合并后的巡回里程以及载重量合并，考察合并后的巡回里程以及载重量是否都符合配送要求。然后再考虑合并第三个站点，节是否都符合配送要求。然后再考虑合并第三个站点，节约里程数次优的为约里程数次优的为D、E合并。因此按照最大节约原则合并。因此按照最大节约原则可以考虑将客户可以考虑将客户E并入并入C、D

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