模型的求解步骤.doc

一、配送路线优化的意义1、配送的基本涵义：是一种综合的物流形式，几乎包括了所有的物流功能要素。强调“配”和“送”货，重点在过程的优化。2、影响配送运输效果的因素：静态因素。 配送客户的分布、交通网络、车辆运行限制、车辆额定载重量 动态因素。 车流量变化、道路施工、配送客户变动、可供调动的车辆变化、配送量变化3、配送运输方面一般存在的问题 送货不及时：信息处理流程时间长、配送方式落后 送货成本高：直接的运输成本和客户的支付成本 配送路径不合理4、配送路线优化的意义加快货物的流通，有利于库存的周转 节约的运力，缩短货运时间 提高物流服务水平二、配送路线优化的方法1、旅行商（Traveling Salesman Problem,）问题：一个推销员到N个城市推销商品，其最短路线的求解。也称为“一笔画”问题。2、多回路运输（Vehicle Routing Problem）问题：对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，并满足一定的约束条件（货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标。如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。二、 模型的求解步骤节约算法是用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。它的核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小得幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。根据节约法的原理和上述的基本思路，我们可以设计求解配送路线优化模型的步骤如下：第一，计算节约值S(i,j),令集合S=S(i,j)S(i,j)0;第二,集合中的元素按从大到小的顺序排序； 第三，如果集合S=,则计算结束，否则对第一个元素S(i,j)，考查对应的（i,j）是否满足下列条件之一：点I和点J都不在已经构成的路线上；点I和点J都在已经构成的线路上，但是不与配送中心相连；点I和点J都在已经构成的两个线路上，但不与配送中心相连。其中一个是线路的起点，另一个是线路的终点，转下一步，否则转步骤；考查点I和点J连接后线路上总的货运量Q，如果Qq,转下一步，否则转步骤；连接点I和点J到同一条线路上；令S=S- S(i,j),转步骤简单节约法的求解资料:客户及货运量（单位：吨）客户P（K）P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15货运量(t)1.62.02.12.51.51.21.41.62.01.32.01.72.21.62.4求解过程分析 （1）初始方案： 对每一个客户分别派车，空车返回。总的路线为15条。 总路程：S=2 =1106 派车情况：需5t的车15辆。（2）节约里程的路线优化方案： 表5-1各个客户之间的最短距离表（单位：公里）P07P11412P2221626P320141417P4282219228P5333120382018P637362647313013P7444230503330129P8545042543731212719P932263611273147575961P105146563145476475767420P11565160354747647676722510P1242363234221521343222405249P135144443631253749463637433816P14625659434541566865553835263519P15第一步：计算节约里程（单点）S i,j=P0,i+P0,j-P i,j：表5-2 节约里程表（单位：公里） QiP01.6 7P12.0 149P22.1 221310P32.5 20132025P41.5 2813232840P51.2 33927173343P61.4 3783212263557P71.6 449281631426572P82.0 541126223751666479P91.3 32131043252918121725P102.0 511294226322013193163P111.7 561110432937251724386397P122.2 42132430405554455474344149P131.6 5114213740544739496946596977P142.4 621317413749393141615678926994P15第二步：根据上表计算所得的结果，将节约里程值从大到小分类，如下表： 表5-3 节约里程顺序表（单位：公里）P11P12：97P7P8：72P10P11：63P5P4：54P6P14：47P3P11：42P6P15：39P5P7：35P14P15：94P12P14：69P10P12：63P6P13：54P10P14：46P8P15：41P7P14：39P10P13：34P12P15：92P13P15：69P9P15：61P8P13：54P7P13：45P11P13：41P9P12：38P4P6：33P8P9：79P9P14：69P11P14：59P5P9：51P3P12：43P3P15：41P5P12：37P2P7：32P11P15：78P6P9：66P6P7：57P5P15：49P5P6：43P4P13：40P4P15：37P5P11：32P13P14：77P6P8：65P10P15：56P8P14：49P3P10：43P4P14：40P4P9：37P4P8：31P9P13：74P7P9：64P5P13：55P12P13：49P5P8：42P4P5：40P3P14：37第三步：在节约里程表中选出最大的节约格P11P12=97，说明将用户P11,P12连接所获得的节约量最大，所以将初始方案中的用两辆车分别向P11,P12送货，改为用一辆车向P11,P12巡回送货。运输距离S=P0,11+P11,12+P12,0=51+10+56=117200. 运量Q=Q11+Q12=2.0+1.7=3.7,故用5t车运送。进一步修正方案。在节约里程表中寻找与P11,P12有关的节约量最大的格子，符合条件的是P12P15=92。考虑如果将其并入该路线是否可行。此时:运输距离S= P0,11+P11,12+P12,15+P15,0=51+10+26+62=149200;运量Q= Q11+Q12+Q15=2.0+1.7+2.4=5.1,故用8t车运送,并入可行。以同样的方法继续寻找这样的格子，我们可以将点P14并入该路线。此时:运输距离S1=P0,11+P11,12+P12,15+P15,14+P14,0=51+10+26+19+51=157km200km; 运量Q= Q11+Q12+Q15+Q14=2.0+1.7+2.4+1.6=7.7,故用10t车运送,还可配载。以同样的方法继续寻找这样的格子，我们可以将点P13并入该路线。Q= Q11+Q12+Q15+Q14+Q13=2.0+1.7+2.4+1.6+2.2=9.9.可行由于装载量的限制，如果再将其中的一用户并入该路线，优势有Q10t，而该公司没有10t以上的车型，故此路线配送结束，第一个计划配送完成。结果如下：表5-4 第一个配送计划结果配送车型5t8t10t可用的车辆数（辆）706080分配的车辆（辆）1001在剩下的与11、12、15、14、13无关的节约格子里寻找里程最大的格子，符合条件的是P8P9=79,将其连接，此时:运输距离S2= P0,8+P8,9+P9,0=44+19+54=119200;运量Q=Q8+Q9=1.6+2.2=3.8t,故用5t车运送,并入可行。按同样的方法可以把P7,P6,P5依次并入该路线，此时运输距离S=P0,5+P5,6+P6,9+P9,8+P8,7+P7,0=28+18+21+19+9+37=132200;运量Q= Q5+Q6+Q7+Q8+Q9=1.5+1.2+1.4+1.6+2.0=7.7t,故用8t车型运送。考虑到如果再将P4并入，Q=10.2t10t，超出了车型载重量，故不可行。第二个配送计划结束。结果如下：表5-5 第二个配送计划结果配送车型5t8t10t可用的车辆数（辆）706080分配的车辆（辆）511在剩下的节约格子里继续寻找里程最大的格子，符合条件的是P3P10=43，将其连接，同理可以依次并入P4,P2,P1，此时运输距离S3=P0,1+P1,3+P3,10+P10,4+P4,2+P2,0=7+16+11+27+14+14=89200;运量Q= Q1+Q3+Q10+Q4+Q2=1.6+2.1+1.3+2.5+2.0=9.5t,故用10t车型运送。结果如下： 表5-6 第三个配送计划结果配送车型5t8t10t可用的车辆数（辆）706080分配的车辆（辆）012在完成修正方案后所得的配送计划即为最终的货物运送计划。公司从货运中心P0向周边15个客户的货物配送优化调度方案如图5-4所示：最终配送优化方案如下P15P12P11P14P10P3P1P13P4P2P0P7P8P9P6P5在最终配送计划的三条配送路线中，总的运送距离S=S1+S2+S3=164+132+89=385km,和初始方案相比，节约量为S=1106-385=721km需要的车型为10t的车2辆，8t的车1辆，减少的车辆数为13辆。路线1:P0-P11-P12-P15-P14-P13-P0,用1辆10T车，装载量8.9路线2:P0-P5-P6-P9-P8-P7-P0 ,