基于动态规划的物流网络路径优化

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2013/6/22,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2013/6/22,#,基于动态规划的物流网络路径优化,本科毕业设计（论文）,各级机场为基础的航空网络,高速，国道，省道等组成的公路网络,高铁，普通铁路，地铁等共同构建的轨道交通,网络,海运和内河航运共同组成的航运网络,研究背景,“十一五”期间的物流成本达到,GDP,的,18%,以上，而欧美及日本等发达国家物流成本都控制在,10%,左右,公司的经营成本仅,10%,来自原料，而物流成本占到,40%,物流产业现状,“十一五”期间年均,21%,的增长率，产业附加值现超过,2.7,万亿人民币,2009,年国务院再次发布公告将物流产业作为支柱产业扶持,公路,全年的运输量为,18,万吨，最大周转量为,1.8,万吨,据估算，全国一年蔬菜损失价值达,1354,亿元，粮食损失价值,35,7,亿元，钢材锈蚀损失价值,1000,亿元，每年造成的货物积压近,2,万亿,公路物流的现状,第一利润源,原料成本,第二利润源,人工成本,第三利润源,物流成本,利润源组成,国内外研究现状,Dijkstra,算法、,A*,算法、动态规划法等,忌算法、人工神经网络法、模拟退火算法、遗传算法等,传统的路径优化算法,近代路径规划算法,动态规划算法,动态规划算法的提出,这一方法最初是由美国,数,学家,R.Bellman,等人在,20,世纪,50,年代提出,先按照整体最优思想逆序求出各个可能状态的最优策略，然后顺序求出整个问题的最优策略和最优路径,。,由于把最优化应用到每个子问题上，就系统的删减去了所有中间非最优方案，使得计算量比穷举法大大减少,动态规划算法的主要原理,将实际问题的过程划分成恰当阶段，确定阶段变量,确定决策变量及允许的决策集合,列出指标函数,写出动态规划函数基本方程,确定状态，正确选择状态变量,写出状态转移方程,动态规划的使用条件,两个先决条件：,最优化原理,（最优子结构性质）,无后效性,一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略,各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态,本文讨论的动态规划实例,在多节点路径中选择距离最短，时间最省，成本最低的线路，为企业赢得综合优势。重点放在各种外界客观条件的约束下，权衡利弊，具体问题具体分析,。,2012,年突破,410,万公里。新增公路通车里程达,8.4,万公里，其中高速公路通车里程增长,1.1,万公里,。高速,总通车里程达,9.6,万公里，超越美国跃居世界第一，基本完成了五纵七横的高速和国道网络框架。近年来我国高速公路新增通里程连年突破,1,万公里，每年改建的公路里程达,8,万公里以上,我国的公路现状,我国公路等级的划分,高速公路,全封闭，最低限速在,60km/h,的双向多车道公路,年平均每昼夜汽车通过量,2.5,万辆以上,一级公路,一级公路要求汽车分向、分车道行驶,多为国道、省道等国家干线公路,二级公路,连接经济、政治中心或大工矿区等地的干线公路,或运输繁忙的城郊公路,沟通县及县以上城镇的一般干线公路,沟通县、乡、村等的支线公路,其他等级公路,谷歌地图,通过谷歌地图可以浏览不同地点的局部详细的卫星照片,同时谷歌地图不仅具有传统矢量地图的功能，而且还提供地形地貌的三维地图，显示高度等信息,测量工具可以轻松的测量两点之间的实际距离，同时也可轻松测量线路的实际距离,对路线设计的影响因素,油耗因素,平原高速路段设计为油耗,20L/,百公里（长江中下游平原）,平原一级公路油耗为,22 L/,百公里,(,长江中下游平原,),山地高速路段油耗为,24 L/,百公里（三峡、大别山区）,平原二级公路油耗为,24 L/,百公里（长江中下游平原）,丘陵二级公路耗油为,26 L/,百公里（四川盆地内部）,山地二级公路油耗为,28 L/,百公里（大别山区）,时间因素,每小时损耗估算为为人民币,50,元,路桥费用,公路建设普遍采取贷款修路或者,BTO,方式,，,建设费用最终会转嫁到消费者身上,其他因素,道路的路面状况不佳造成的时间及油耗损失将酌情考虑,计算公式,宣城,上海,合肥,庐江,铜陵,南京,安庆,岳西,六安,遂宁,仙桃,汉川,黄石,新洲,麻城,宜昌,广安,成都,A,F,E,D,C,B,J,I,H,G,高速公路,一级公路,二级公路,计算模型的建立,成都上海的路径分布,成都,遂宁,遂宁,遂宁,广安,垫江,宜昌,武汉,鄂州,黄石,黄梅,潜山,安庆,铜陵,宣城,长兴,南浔,上海,G318,国道,G318,国道,G42,高速,G50,高速,G318,国道,G316,国道,G318,国道,G318,国道,G50,高速,S235,省道,G105,国道,G50,高速,G318,国道,G318,国道,整体最优路线,论文小结,成都到上海全长,2191.8,公里，其中高速公路,889.6,公里，,占总里程的,40.4%,。占,耗时,31,小时,53,分钟收费为,1589,元（含桥梁和隧道收费），耗时,11,小时,30,分钟。平均时速约,75km/h,，每公里收费,1.78,元。一级公路总里程,236.2,公里，确定收费路段,52.6,公里（,30,元），占到总路程的,10.77%,。,不收费路段为,27.6,公里，其他路段收费待定。耗时,2,小时,15,分。二级公路,1066,公里，耗时,18,小时,8,分，均不缴费，,占总里程的,48.83%,，,平均时速约,59km/h,行业展望,我国公路通车里程每年增长,8,万公里，每年通车的高速超过,1,万公里。各地都将发展高速公路作为“十二五”期间的重点规划,东、中部省市还将原有二级公路升级改造升级为一级公路纳入发展规划，形成高速公路、一级公路、二级公路的三级立体式公路网络,PMI,连续半年以上保持在,50%,以上，制造业正经历温和增长,交通部正在研究取消政府还贷一级公路的可行性,