节约里程法-应用

1、节约里程的定义节约里程的定义ABPABP运输方式由（一）变成（二），可节省的运输方式由（一）变成（二），可节省的运输距离为（运输距离为（2a+2b）-（a+b+c）= a+b-c 0，这一节省的运输距离称为，这一节省的运输距离称为“节约里程节约里程”（一）（二）ababc配送的是同一种货物配送的是同一种货物各客户的坐标及需求量均为已知各客户的坐标及需求量均为已知配送中心有足够的运输能力配送中心有足够的运输能力实例：有一工厂实例：有一工厂P，AJ表示表示P附近的客户，（）内数字表示附近的客户，（）内数字表示运输量（吨），路线上的数字表示道路的距离（公里）。运输量（吨），路线上的数字表示道路的距离

2、（公里）。假设工厂只拥有假设工厂只拥有2吨车和吨车和4吨车两种，并且限制车辆一次吨车两种，并且限制车辆一次运输的最远距离为运输的最远距离为30公里，请问怎样安排运输路线，使公里，请问怎样安排运输路线，使运输距离最小？运输距离最小？PABCDEFGHIJ766554114810 4685624 32791074359（0.7)（1.5)（0.8)（0.4)（1.4)（1.5)（0.6)（0.8)（0.5) （0.6)PABCDEFGHIJP109788834107A491418181314114B51014171213158C591510111713D61311121815E710121815F

3、681715G21110H911I8JABCDEFGHIJ117300048C10600001D1030000E91000F5410G520H50I9J顺位顺位连接线连接线节约里程节约里程 顺位顺位连接线连接线节约里程节约里程1AB1513FG52AJ1313GH53BC1113HI54CD1016AD44DE1016BI46AI916FH46EF919BE36IJ919DF39AC821GI29BJ822CJ111BD722EG112CE622FL1PABCDEFGHIJ104883791078初解：初解：线路数：线路数：10条条总运输距离：总运输距离：148KM车

4、辆台数：车辆台数：2吨吨车车10台台(0.7)(1.5)(0.8)(0.4)(1.4)(1.5)(0.6)(0.8)(0.5)(0.6)二次解：二次解：按节按节约里程的大小，约里程的大小，连接连接A AB B，A AJ J，B BC C 线路数：线路数：7 7条条总运输距离：总运输距离：109KM109KM车辆台数：车辆台数：2 2吨车吨车6 6台，台，4 4吨吨车车1 1台台(0.5)线路线路A A：装载量装载量3.63.6运输距离运输距离27KM27KMPABCDEFGHIJ10488375478(0.7)(1.5)(0.8)(0.4)(1.4)(1.5)(0.6)(0.8)(0.6)4(

5、1.4)PABCDEFGHIJ104883754783 3次解：次解：按节约里程按节约里程的大小，连接的大小，连接C CD D 和和D DE E ，但因为限，但因为限制，不能连接制，不能连接C CD D，所以只能连接所以只能连接D-ED-E线路数：线路数：6 6条条总运输距离：总运输距离：99KM99KM车辆台数：车辆台数：2 2吨车吨车5 5台，台，4 4吨车吨车1 1台台(0.7)(1.5)(0.8)(0.4)(1.5)(0.6)(0.8)(0.5)(0.6)4线路线路A A：装载量装载量 3.63.6运输距离运输距离27KM27KMPABCDEFGHIJ10483754784 4次解次解

6、：按节约里程：按节约里程的大小，连接的大小，连接A AI I 和和E EF F ，但因为，但因为A A已已组合在完成的线路组合在完成的线路A A中，不能连接中，不能连接A AI I，所以只能连接所以只能连接E EF F 线路数：线路数：5 5条条总运输距离：总运输距离：90KM90KM车辆台数：车辆台数：2 2吨车吨车3 3台，台，4 4吨车吨车2 2台台(0.7)(1.5)(0.8)(0.4)(1.4)(1.5)(0.6)(0.8)(0.5)(0.6)4线路线路A A：装载量装载量3.63.6运输距离运输距离27KM27KM5次解：次解：按节约里程的大按节约里程的大小，连接小，连接IJ 、A

7、C 、BJ、BD、CE 。但由于同一组中总有一但由于同一组中总有一头或两头包含在已完成头或两头包含在已完成线路线路A中，不能再作出中，不能再作出新的线路。新的线路。所以考虑下一组所以考虑下一组FG组组合到线路合到线路B组组线路数：线路数：4条条总运输距离：总运输距离：85KM车辆台数：车辆台数：2吨车吨车2台，台，4吨车吨车2台台PABCDEFGHIJ104837547(0.7)(1.5)(0.8)(0.4)(1.4)(1.5)(0.6)(0.8)(0.5)(0.6)4676线路线路A：装载量装载量 3.6运输距离运输距离27KM线路线路B：装载量装载量 3.9运输距离运输距离30KM最终解：最终解：按节约里程按节约里程的大小，下面考虑的大小，下面考虑GH ，HI ，由，由GH 于受运输距离于受运输距离和载重量的限制，所和载重量的限制，所以不能组合进线路以不能组合进线路B。只能连接只能连接HI ，作出，作出线路线路C线路数：线路数：3条条总运输距离：总运输距离：80KM车辆台数：车辆台数：2吨车吨车1台，台，4吨车吨车2台台PABCDEFGHIJ104837547(0.7)(1.5)(0.8)(0.4)(1.4)(1.5)(0.6)(0.8)(0.5)(0.6)4676线路线路A：装载量装载量 3.6运输距离运输距离27KM线路线路B：装载量装载量