模型的求解步骤

《模型的求解步骤》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、配送路线优化的意义1、配送的基本涵义：是一种综合的物流形式，几乎包括了所有的物流功能要素。强调“配”和“送”货，重点在过程的优化。2、影响配送运输效果的因素：⑴静态因素。配送客户的分布、交通网络、车辆运行限制、车辆额定载重量⑵动态因素。车流量变化、道路施工、配送客户变动、可供调动的车辆变化、配送量变化3、配送运输方面一般存在的问题⑴送货不及时：信息处理流程时间长、配送方式落后⑵送货成本高：直接的运输成本和客户的支付成本⑶配送路径不合理4、配送路线优化的意义⑴加快货物的流通，有利于库存的周转⑵节约的运力，缩短货运时间⑶提高物流服务水平二、配送路线优化的方法1

2、、旅行商（TravelingSalesmanProblem,）问题：一个推销员到N个城市推销商品，其最短路线的求解。也称为“一笔画”问题。2、多回路运输（VehicleRoutingProblem）问题：对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，并满足一定的约束条件（货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标。如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。二、模型的求解步骤节约算法是用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。它的核心思想是依次将运输问题中的两个回

3、路合并为一个回路，每次使合并后的总运输距离减小得幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。根据节约法的原理和上述的基本思路，我们可以设计求解配送路线优化模型的步骤如下：第一，计算节约值S(i,j),令集合S=﹛S(i,j)︱S(i,j)＞0﹜;第二,集合中的元素按从大到小的顺序排序；第三，如果集合S=Φ,则计算结束，否则对第一个元素S(i,j)，考查对应的（i,j）是否满足下列条件之一：①点I和点J都不在已经构成的路线上；②点I和点J都在已经构成的线路上，但是不与配送中心相连；③点I和点J都在已经构成的两个线路上，但不与配送中心相连。其中一个

4、是线路的起点，另一个是线路的终点，转下一步，否则转步骤⑤；④考查点I和点J连接后线路上总的货运量Q，如果Q＜q,转下一步，否则转步骤⑥；⑤连接点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辆。

5、（2）节约里程的路线优化方案：表5-1各个客户之间的最短距离表（单位：公里）P07P11412P2221626P320141417P4282219228P5333120382018P637362647313013P7444230503330129P8545042543731212719P932263611273147575961P105146563145476475767420P11565160354747647676722510P1242363234221521343222405249P135144443631253749463637433816P14625

6、659434541566865553835263519P15第一步：计算节约里程（单点）Si,j=P0,i+P0,j-Pi,j：表5-2节约里程表（单位：公里）QiP01.67P12.0149P22.1221310P32.520132025P41.52813232840P51.233927173343P61.43783212263557P71.6449281631426572P82.0541126223751666479P91.332131043252918121725P102.0511294226322013193163P111.75611104329372

7、51724386397P122.242132430405554455474344149P131.65114213740544739496946596977P142.4621317413749393141615678926994P15第二步：根据上表计算所得的结果，将节约里程值从大到小分类，如下表：表5-3节约里程顺序表（单位：公里）P11P12：97P7P8：72P10P11：63P5P4：54P6P14：47P3P11：42P6P15：39P5P7：35P14P15：94P12P14：69P10P12：63P6P13：54P10P14：46P8P15：41P

8、7P14：39P10P13：34P12