节约里程法详解图

例：有一配送（P）具有如图所示的配送网络，其中A-J表示收货站，（）内数字表示发送量（吨），路线上的数字表示道路距离（公里）。问为使行走距离尽量小，应该如何去求配送线路？假设能够利用的车是2吨车（即最大载重量是2吨）和4吨车两种，并限制车辆一次运行的初步距离是30公里。解题步骤：1.第一步：作出最短距离矩阵，首先从配送网络图中计算出配送中心与收货点之间以及收货点相互之间的最短距离矩阵，见下表所示：表一：最短距离矩阵（单位：公里）PABCDEFGHIJP109788834107A491418181314114B51014171213158C591510111713D61311121815E710121815F681715G21110H911I8J2.第二步：作出节约里程项目，其次，从最短距离矩阵中计算出收货点相互之间的节约里程。DPCBAJIEFGH554114810924346536786456210797（0.4）（0.8）（1.5）（0.7）（0.5）（1.4）（1.5）（0.6）（0.8）（0.6）表二：节约里程项目（单位：公里）ABCDEFGHIJA15840000913B117300048C10600001D1030000E91000F5410G520H50I9J例如：计算A-B的节约里程项目如下：P-A的距离是：a=10P-B的距离是：b=9A-B的距离是：c=4节约里程项目为：a+b-c=10+9-4=15公里3.第三步：节约项目分类，再把节约项目由大到小顺序排列。表三：节约里程项目分类表（单位：公里）顺位连接线节约里程顺位连接线节约里程1A-B1513F-G52A-J1313G-H53B-C1113H-I54C-D1016A-D44D-E1016B-I46A-I916F-H46E-F919B-E36I-J919D-F39A-C821G-I29B-J822C-J111B-D722E-G112C-F622F-L14.第四步：作成配送线路，从节约项目分类表中，按节约里程大小的顺序，组成线路图。（1）.初次解。线路数：10总行走距离：(10+9+7+8+8+8+3+4+10+7)*2=148公里车辆台数：2吨车10台（2）.二次解。按节约里程由大到小的顺序，连接A-B，A-J，B-C连接线。线路A：装载量3.6吨行走距离27公里线路数：7DPCBAJIEFGH104388810797（0.4）（0.8）（1.5）（0.7）（0.5）（1.4）（1.5）（0.6）（0.8）（0.6）DPCBAJIEFGH104388877（0.4）（0.8）（1.5）（0.7）（0.5）（1.4）（1.5）（0.6）（0.8）（0.6）544总行走距离：148-15-13-11=109公里车辆台数：2吨车6台，4吨车1台（3）.三次解。其次节约里程最大的是C-D和D-E。C-D，D-E两者都有可能与二次解的线路A连接，但由于A的车辆载重量与行走距离有限，不能再增加收货点。为此，略去C-D而连接D-E。线路B：线路A：装载量1.8吨，行走距离22公里线路数：6总行走距离：109-10=99公里车辆台数：2吨车5台，4吨车1台（4）.四次解。接下来节约里程大的是A-I和E-F。由于A已组合在完成的线路A中，所以略去，不能再增加收货点。为此，略去A-I而将E-F连接在线路B上。线路B：线路A：装载量3.3吨，行走距离29公里DPCBAJIEFGH104388877（0.4）（0.8）（1.5）（0.7）（0.5）（1.4）（1.5）（0.6）（0.8）（0.6）5446DPCBAJIEFGH10438877（0.4）（0.8）（1.5）（0.7）（0.5）（1.4）（1.5）（0.6）（0.8）（0.6）54467线路数：5总行走距离：99-9=90公里车辆台数：2吨车3台，4吨车2台（5）.五次解。再继续按节约里程由大到小排出I-J，A-C，B-J，B-D，C-E。由于同一组总有一头或两头包含在已完成的线路A中，不能再作出新的线路。只考虑把下一组F-G组合在完成的线路B中。线路B：线路A：装载量3.9吨，行走距离30公里线路数：4总行走距离：85公里车辆台数：2吨车2台，4吨车2台（6）.最终解。其次是G-H。由于受车辆载重量与行走距离有限，它不能组合进线路B中，故除去。连接H-I，作出线路C。线路B：线路A：装载量3.9吨，行走距离30公里线路C：DPCBAJIEFGH10436877（0.4）（0.8）（1.5）（0.7）（0.5）（1.4）（1.5）（0.6）（0.8）（0.6）54467DPCBAJIEFGH10436877（0.4）（0.8）（1.5）（0.7）（0.5）（1.4）（1.5）（0.6）（0.8）（0.6）544679线路A：4吨车，总行走距离27公里，装载量3.6吨。线路B：4吨车，总行走距离30公里，装载量3.9吨。线路C：2吨车，总行走距离23公里，装载量1.3吨。这样整个配送线路做完，共3条线路总行走距离80公里，必要车辆是2吨车1台，4吨车2台。采用节约里程法注意事项：1.适用于需要稳定的顾客。2.对于非固定需要的顾客，采用其它途径配车，或并入有宽裕的线路中。3.最终确定的配送线路，要有司机和现场意见。4.挑战配送线路的负荷量使其平衡。5.充分考虑道路交通情况。6.考虑需要的变动。7.考虑在收货站的停留的时间。8.注意司机的休息时间和指定交货时间。9.为找出交通情况和需要变化所造成的影响，研究采用模拟方式的可能性。10.车辆安排程序作为大部分计算机应用程序组已很完善，对规模较大的网络，需要采用电子计算机处理。