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第1页/共18页 位于市内位于市内的百家姓配送中心（的百家姓
2、配送中心（P P0 0）向它旗下向它旗下的的1010家连锁商店家连锁商店p pi i(i=1,2,(i=1,2,10),10)配送商品配送商品，其配送网络如下图所示。，其配送网络如下图所示。图中括号内的数字表示每一家连锁店的需图中括号内的数字表示每一家连锁店的需求量（求量（t t），），线路上的数字表示两节点之间线路上的数字表示两节点之间的距离（的距离（kmkm）。配送中心现有）。配送中心现有2 2t t和和4 4t t车辆车辆可供使用，并且每辆车配送距离不得超过可供使用，并且每辆车配送距离不得超过30km30km。第2页/共18页配送网络图P09e1.4861076f1.58g0.6329h
3、0.84i0.510j0.67a0.710b1.59c0.87d0.485544118第3页/共18页配送网络图P0e1.48f1.58g0.63h0.84i0.510j0.67a0.710b1.59c0.87d0.48第4页/共18页 初始方案运行结果：初始方案运行结果：1 1、从百家姓配送中心出发，需要设计、从百家姓配送中心出发，需要设计1010条条配送线路，分别向配送线路，分别向1010家连锁店配送商品；家连锁店配送商品；2 2、需要、需要1010辆辆2t2t的配送车辆（每家连锁店的的配送车辆（每家连锁店的需要量都低于需要量都低于2t2t），总配送距离为），总配送距离为148km148k
4、m。第5页/共18页P109479581410581814968181715137313121011106414131112 128210111517181817119abcdefghij7481315151510118abcdefghij第6页/共18页1581147100361000039000015000004594000125abcdefghiPbcdefghij1381000009节约里程计算过程 第7页/共18页1ab152aj133bc1113fg513gh513hi516ad416bi416fh44cd104de106ai96ef96ij99ac89bj811bd712ce62
5、1gi219be319df322cj122eg122fi1序号连接点节约里程序号连接点节约里程第8页/共18页修正结果：运距修正结果：运距109km109km，车辆，车辆4t14t1辆，辆，2t62t6辆辆第9页/共18页修正结果：运距修正结果：运距85km85km，车辆，车辆4t24t2辆，辆，2t22t2辆辆第10页/共18页修正结果：运距修正结果：运距80km80km，车辆，车辆4t24t2辆，辆，2t12t1辆辆第11页/共18页练习 例：如图所示为配送中心例：如图所示为配送中心P的配送网络图，某配送中的配送网络图，某配送中心心P向向A、B、C、D、E五个客户配送物品。图中边线上五个客
6、户配送物品。图中边线上的数字表示公路里程的数字表示公路里程（km）。靠近各用户括号里的数字。靠近各用户括号里的数字表示对货物的需求量表示对货物的需求量（t）。配送中心备有。配送中心备有2t和和4t载重量载重量的汽车，汽车一次巡回行驶里程不能超过的汽车，汽车一次巡回行驶里程不能超过30km。求解配。求解配送路线方案。送路线方案。PE(2)D(1)A(1.5)B(3)C(0.5)677998531443108第12页/共18页 （1）计算配送中心计算配送中心P至各用户之间的最短距离，如表所示至各用户之间的最短距离，如表所示:第13页/共18页（3）根据节约里程表中节约数额的多少从大到小排序，根据节
7、约里程表中节约数额的多少从大到小排序，编制编制节约里程序列表节约里程序列表，如表，如表83所示所示。第14页/共18页 （4）根据节约里程序列表和配送中心的约束条件，根据节约里程序列表和配送中心的约束条件，先选择先选择C、D合并，考察合并后的巡回里程以及载重量合并，考察合并后的巡回里程以及载重量是否都符合配送要求。然后再考虑合并第三个站点，节是否都符合配送要求。然后再考虑合并第三个站点，节约里程数次优的为约里程数次优的为D、E合并。因此按照最大节约原则合并。因此按照最大节约原则可以考虑将客户可以考虑将客户E并入并入C、D站点群；但是，首先要考虑站点群；但是，首先要考虑合并后车辆的载重量以及行驶
8、里程的限制，即使其中一合并后车辆的载重量以及行驶里程的限制，即使其中一个突破了约束，也应该舍弃该合并方案。这里合并后车个突破了约束，也应该舍弃该合并方案。这里合并后车辆的载重量为辆的载重量为3.5t（2+1+0.5=3.5），），行驶里程刚好为行驶里程刚好为30km，符合约束条件，需要一辆，符合约束条件，需要一辆4t车。并且，并入车。并且，并入E点点后，再不能并入其他任何站点，该路线设计完毕。后，再不能并入其他任何站点，该路线设计完毕。第15页/共18页 现在只剩下现在只剩下A、B两个客户还没有安排配送路线，由于两两个客户还没有安排配送路线，由于两个客户的货物需求总量为个客户的货物需求总量为4
9、.5t，已经超过，已经超过4t车的最大载重车的最大载重量，因此量，因此只能是分别进行配送只能是分别进行配送，还需要一辆，还需要一辆4t车和一辆车和一辆2t车。由此分析得出的配送路线如图车。由此分析得出的配送路线如图83所示。所示。PE(2)D(1)A(1.5)B(3)C(0.5)6778310路线路线1路线路线2路线路线3图83 配送路线 第16页/共18页 因此，按照节约法设计的配送方案是使用因此，按照节约法设计的配送方案是使用2辆辆4t车车,1辆辆2t车车,总行驶里程为总行驶里程为52km。其其中：中：路线路线1：4t车，载货量车，载货量3.5t，行驶里程，行驶里程30km；路线路线2：2t车，载货量车，载货量1.5t，行驶里程，行驶里程16km；路线路线3：4t车，载货量车，载货量3t，行驶里程，行驶里程6km。第17页/共18页感谢您的观赏！第18页/共18页
