通运输上使用动态规划求解最短路径.pdf

袁佳乐1 黄兆华2Y u a nJ i a l eH u a n gZ h a o h u a(I 西安文理学院计算机科学系，陕西西安7 1 0 0 6 5；2 华东交通大学信息学院，江西南昌3 3 0 0 1 3)(1 D e p a r t m e n to fC o m p u t e rS c i e n c e，X i a nU n i v e r s i t yo fA r ta n dS c i e n c e，S h a n x ix i a n7 0 1 1 6 5；2 S c h o o lo fI n f o r m a t i o nE n g，E a s tC h i n aJ i a o t o n gU n i v e r s i t y，J i a n g x iN a n c h a n g3 3 0 0 1 3)摘要：随着我国交通运输事业的发展降低运输成本成为日益关注的问题。动态规划在工程技术、经济管理、工业生产、交通运输等众多领域都有广泛的应用其中最短路径问题是动态规划在管理领域的一个重要应用。本文通过具体实例说明动态规划在交通运输方面求解最短路径的过程方法简便，思路清晰。关键词：交通运输：动态规划：最短路径，中图分类号：T P 3 11文献标识码：A文章编号：1 6 7 1 4 7 9 2 一(2 0 0 8)5 一0 0 8 l-0 2A b s t r a c t：A l o n gw i t ht h et r a n s p o r t a t i o ns y s t e md e v e l o p m e n t，p e o p l ep u tn l o r ea t t e n t i o nt or e l e a s et h ee x p e n s ei nt r a n s p o r t a t i o n D y n a m i cp r o g r a m m i n gh a sa l r e a d ya p p l l e dt op r o j e c tt e c h n i q u e，e c o n o m ym a n a g e m e n t i n d u s t r yp r o d u c t i o na n dt r a f f i ct r a n s p o r t a t i o n T h ep r o b l e mo ft r a f f i ct r a n s p o r t a t i o ni sa ni m p o r t a n c ea p p l i c a t i o ni nt h ef i e l do fd y n a m i cp r o g r a m m i n g T h ep a p e ru s ed y n a m i cp r o g r a m m i n gt h e o r i e st os e a r c ht h es h o r t e s tr o u t ei nt h et r a n s p o r t a t i o ns y s t e m，t h ei d e ai sc l e a ra n dt h et h e o r yi sr e li a b l e K e v w o r d s：T r a n s p o r t a t i o n；D y n a m i cP r o g r a m m i n g；S h o r t e s tR o u t e0 引言随着国际油价的不断上涨，日益冲击着我国的交通运输事业。如何能快速的找到两地之间的最短路径，加快交通运输速度，提高服务质量，降低交通运输中的成本，增加经济效益成为运输公司和运输个体经营户关心的问题。在交通运输示意图中(见图一)，有n 个结点a，、a，、a，a。，计算从点a，到点a 之间的最短路径。常用d，。表示点a。到点a。之间的距离，如果两地间没有通路，则d；l *，用z(a；)表示从a。点到终点a 的最短路径。假设点a。可以通过点f 1 到达终点a，点a。到点a；的距离为d 从a。点到达终点a。的最短路径为Z(a；)，则由点a。到达终点的最短路径可表示为z(a)=m i n d，。q-Z(a。)。把网络中的结点按离终点最多的步数划分为k 个集合，为满足动态规划方法中阶段“无后效性”的限制，在阶段与阶段的空处添加若干个虚结点，对于每个添加的虚结点，使之满足从该虚结点到其后结点的值为原路径的数值，从前一结点到该虚结点的值为0。Z k。(a。)表示从第k 阶段的点a 到终点a 的最短路径，可列出方程：z。(a。)=m i n d。+z。(a；)(1)Z。(a)-O(2)其中，i k,j k+l。由公式(1)(2)向前递推可得到Z，(a。)，即是所求的最短路径z。，-z。(a。)用x。(a。)表示第k 阶段点a。的条件最优点。1实例图一交通运输网络示意图某交通运输图中有七个结点(如图一所示)，代表七个城市，每个结点间的连线代表两地之闻有通路，其上的数值表示两地之问的距离，如果图中两点问没有连线则说明这两个地区还没有建设通路。运用动态旁劲各径，集合x。=“)。它最多四步就可以到达结点A 7；薯l岛终点最；5个集如图所示将问题划分为四个阶段，即k=4 由公式(2)可得Z。(A 7)：o 在集合x 5-一，；先求第四个阶段：交集合4-J通又s,7；Z 4(A 5)=1 2+Z s。沁)=1 2x 4=7运集合x 3-z 4(A 3)=2+z 5(A，)-2X 4=A 7输集合x 2-，；z 4(B。)=4+z s(A，)=4x 4=A 7上集合X l=再求第三个阶段：使：第一阶l_Z 3。(B 2)=8+z 4。(A s)=8+1 2=2 0 x 3=A s用Iz 3。(B 3)=9+z 4(A)-9+2=IIx 3=A a动l态：rz。(B 4)=l o+z。(A 3)=1 0+2=I2x 3=规z 3(A 6)铷i n 6 屹4(A 3)=6+2=8划(，习眦。饥，4L 詈一求A解最人“X 群拶、一对于第二阶段：短(z 2(A 4)铷i n，o+z。(哟=0+2 0=2 0路L 毗3(B a)-O+l l=l I径即Z 2 (A 4)=1 1x 2=B 3图二z 2(呦=r a i n，o 屹。(B 4)=o+1 2=1 2按照集合睁咖调整L7+z。(A e)=7+4=1 1募可以得到图二，j日分即Z。(A 2)=1 1x 2 _ A。r 保证划分倒缸，可最后求第一阶段：誊生图二中加J莉后的Z。(A 1)=n t i n，5+Z 2(A 4)=5+1 1=1 6至值。添加篚雨，如L6+z 2(A 2)=6+1 1=1 7詈羔A|到点A。：点问的即Z l(A 1)=1 6x l A 4留为8，添加：白8。得到最优路径的值z。(A，)=1 6，此路径通过点A。A；3-第一阶段A 3-A，消去虚结点得到最优路径A。3-A，即所求的A。一一A，两地之间的最短路径。2 结束语。、。运用动态规划求解问题，有逆序递推和顺序递推两种方法，这两种不同的递推方法，阶段k 的划分是相同的。如果(o，一一给定的问题有固定的起点和固定的终点，则使用这两种递推、方法都可以得到相同的结果。在这里我们使用的是逆序递推；厂。州觚hAJ方法，方法简洁，思路清晰。1、v(参考文献【1】谢可新最优化算法【M 北京：清华大学出版社【2】徐渝，贾涛运筹学【M】北京：清华大学出版社，图三i2 0 0 5，2 添加虚结I【3】张莹运筹学基础【M】北京：清华大学出版社，2 0 0 2 集合x 5=Ar；6 集合x l-一缸i 凡；集合x 3 _ J蕞A，；作者简介集合x 产LJ，；袁佳乐，华东交通大学在读硕士研究生。1 4 1 在交通运输上使用动态规划求解最短路径在交通运输上使用动态规划求解最短路径作者：袁佳乐，黄兆华，Yuan Jiale，Huang Zhaohua作者单位：袁佳乐,Yuan Jiale(西安文理学院计算机科学系,陕西西安,710065)，黄兆华,HuangZhaohua(华东交通大学信息学院,江西南昌,330013)刊名：科技广场英文刊名：SCIENCE MOSAIC年，卷(期)：2008，(5)被引用次数：0次 参考文献(3条)参考文献(3条)1.谢可新 最优化算法2.徐渝.贾涛 运筹学 20053.张莹 运筹学基础 2002 相似文献(10条)相似文献(10条)1.学位论文 周辉 湖南交通运输网络动态规划及其投资专家系统 19942.学位论文 周跃 集装箱多式联运运输决策与协调问题的研究 2006 集装箱多式联运是交通运输发展的高级阶段，是现代交通运输发展的一种必然趋势，因此许多国家都将集装箱多式联运作为今后发展的重点。然而就当集装箱多式联运在实践上得到广泛应用的同时，集装箱多式联运理论方面的研究却被忽略了。本文以集装箱多式联运运输决策、集装箱多式联运的协调管理为两个研究点，对集装箱多式联运进行了较为详细地探讨：在集装箱多式联运运输决策中，本文将线路优选和运输方式优选综合起来加以考虑，路径优选中采用了国内通用的做法建立集装箱多式联运运输通道，在运输方式的优选上，建立时间限制基础上总运输成本最低的集装箱多式联运模型，另外本文采用了DHGF综合评价方法对集装箱多式联运优选线路进行了政治、经济等相关因素方面的评价；对于集装箱多式联运的协调管理，本文对集装箱多式联运涉及到的各个主体以及各个主体之间都进行了协调，这其中以集装箱多式联运企业内部的协调为重点，对于企业内部的协调，本文引入了“第四方物流”的先进的管理运营模式，以这种先进的供应链解决方案为集装箱多式联运企业提供先进协调管理方法。3.期刊论文 韩骏.徐奇.靳志宏.Han Jun.Xu Qi.Jin Zhihong 动态规划的集装箱多式联运系统运输方式组合优化-武汉理工大学学报（交通科学与工程版）2010,34(4)集装箱多式联运是一种以实现货物整体运输的最优化为目标的联合运输的组织形式,而集装箱多式联运系统中各种运输方式的优化组合直接关系到货物运输的费用、时间和运输质量.文中对集装箱多式联运系统中各种运输方式的组合优化问题建立了满足现实约束条件的基于动态规划的优化模型,进行了基于MATLAB的算法与程序设计,获得了最优的运输方式组合策略.实证研究显示了该模型与方法的可行性与有效性.4.期刊论文 张艳.ZHANG Yan 基于动态规划改进求解VRP问题节约法的DSM模型及其拓展分析-物流工程与管理2010,32(1)提出了改进求解VRP问题节约法的DSM模型(动态规划节约法),将代表启发式算法的节约法与代表精确算法的动态规划相结合,建立不断增加节约量的动态规划数学模型,使其得到全局最优解.该法计算过程平稳收敛,对增加约束条件的情况更易接受.5.学位论文 唐亚丽 收益管理在我国动车组的应用 2008 近几年，动车组以其编组灵活、方便、快捷、安全，可靠、舒适等优势备受世界各国铁路运输和城市轨道交通运输的青睐。如何有效利用动车组资源来解决我国运输问题是不可避免的事情。虽然国家逐步放宽对动车组销售的限制，但实际运作效果还有待进一步提升。通过对当前动车组运作特点的分析，本文提出了动车组在定价和存量控制方面普通存在的问题。进一步，本文提出使用差别定价来最大化地利用资源，采用动态存量控制技术来最优地管理有限的资源，以实现动车组收益最大化的目标。本文的主要研究内容如下：第一章为论文的绪论。首先，该章介绍动车组的运作情况以及动作组与航空运输、普通铁路运输的显著区别。然后，该章提出了动车组在定价和存量控制方面存在的问题。最后，提出了本篇论文的研究框架和研究方法。第二章为论文的文献回顾。该章的具体内容分别为收益管理的基本知识介绍、差别定价在国内外的研究现状及网络存量控制的研究方法。差别定价的相关知识包括其定义、经济含义、分类等。另外，通过回顾存量控制的研究文献，总结出可以适用于动车组并且能够得到较好结果的方法。第三章研究了差别定价策略在动车组的应用情况。首先，该章具体指出动车组在定价策略方面的缺点以及实施差别定价策略的必要性。然后，该章提出实施差别定价的具体过程，包括市场细分、产品细分、实施框架等。最后，通过引用个实际的案例来分析差别定价的优势和能够为动车组增加的收益。第四章研究了动车组三个站点的网络存量动态规划问题。动车组三个站点的网络问题包括三种产品。本章提出使用HamiltonJacobi方程式来动态控制这三种产品的存量分配问题。接着，构建了存量控制的动态规划模型，并且讨论模型的相关性质。然后，通过数值算例来证明了动态模型的收益价值函数以及边际价值函数的变化睛况。第五章主要介绍两种策略的比较分析。第种是第四章的动态存量控制策略，第二种是没有存量控制策略，即FCFS（先到先服务）策略。假设三种产品的需求服从泊松分布，通过做100次测试取平均值，得到两种策略下的存量控制和收益。另外，通过调节三种产品的需求值，该章分析了存量控制的变化情况。以上所有情况下，两种策略的比较结果表明第一种策略优于第二种策略。第六章是结论和展望。本章总结了论文所做出的研究成果以及存在的局限性，同时提出了该领域今后的研究方向。6.期刊论文 袁佳乐.黄兆华.曹玉红.YUAN Jia-le.HUANG Zhao-hua.CAO Yu-hong 动态规划在资源分配上的应用-西安文理学院学报(自然科学版)2008,11(3)目前动态规划在工程技术、经济管理、工业生产、交通运输等众多领域都有广泛的应用,其中资源分配问题是动态规划在管理领域的一个重要应用.在资源分配问题上使用动态规划,是将分配过程划分为多个阶段,在每一个阶段中选取其最优决策,最后达到整个过程的总体最优目标.详细阐述了动态规划算法的基本原理和解题步骤,并通过具体实例说明动态规划在资源分配方面解决问题的过程.7.学位论文 袁宝军 铁路行包运输管理信息系统中配装问题的研究 2000 该文结合作者的实际工作经验,在对全路行包运营管理进行深入分析的基础上,对于行包信息中系统总体结构方案、网络结构、应用系统结构等行包系统总体方案进行设计.同时深入探讨了行包系统中难点-行包配装,主要包括以下内容:铁路行包运输现状分析.全路行包运营管理信息系统需求分析、总体结构方案、网络结构、系统功能结构等系统总体设计.铁路行包配装计划问题的需求分析、影响行包配装的主要因素,建立了铁路行包配装问题的基本模型,并根据行包运输特点及要求探讨了模型的理论方法及复杂度,在此基础上提出了较优可行解的算法.根据该模型及其算法,对全路配装辅助决策系统的结构与功能进行了设计.8.期刊论文 陈钢铁.帅斌 在时间窗条件下应急物资运输路径优化问题研究-铁道运输与经济2010,32(3)应急物资调运主要是应急车辆在最短的时间内把应急物资运送到需求点,其研究的核心是最短路径选择问题.通过对研究问题的描述,界定其中交通网络的道路和节点均带有禁止时间窗,模型目标是通过路径选择最小化调运时间,鉴于模型的组合属性,利用动态规划和标号法算法对设计问题求解,以实例计算说明模型算法的有效性.9.期刊论文 伍学滨.邓小英 运筹学在经济管理中的应用-企业经济2005(11)运筹学是一门广泛应用于工业、农业、交通运输、商业、国防、邮电及经济管理等方面的应用科学,能帮助决策人员科学地制定方针和决策.本文主要阐述了运筹学的原则和处理问题的步骤,以及从一些例子谈起介绍了运筹学中的线性规划和动态规划在经济管理领域里的应用.10.学位论文 孙英 同尺寸矩形毛坯剪切排样算法研究 2006 在国民经济许多行业中，都会遇到板材分割问题。例如：金属制品、普通机械、专用设备、交通运输设备等制造行业的金属板材分割，家具制造业的胶合板分割，建筑和玻璃行业的平板玻璃分割等。在板材分割中应用优化排样算法，能够提高材料利用率，从而降低生产成本。板材分割时既可以按套裁排样方式下料，也可以按单一排样方式下料。前者在一张板材中，允许排入不同尺寸的毛坯；后者只允许排入相同尺寸的毛坯。虽然套裁排样方式的材料利用率较高，但单一排样方式因具有下述特点，在实践中也得到较广泛的应用：(1)下料过程易于管理；(2)下料工艺较为简单；(3)能够按单张订单组织生产，从而缩短生产周期。本文研究的是矩形毛坯单一排样问题，即要求在满足工艺约束条件的前提下，确定排样方式，使一张板材中所含相同尺寸矩形毛坯的数量达到最大。要求同时实现排样方式最优性和切割工艺最优性。排样方式最优性是指一张板材中所含毛坯数达到最大。切割工艺最优性是指在保证排样方式最优性的前提下，生成下料工艺最简单的排样方式。也可以表述为：如果毛坯数达到最大的排样方式不止一个，要求找到下料工艺最简单的排样方式，作为最优排样方式。本文的排样问题是根据剪冲工艺的要求抽象出来的。剪冲工艺是指分两步将板材分割成毛坯：第一步用平剪床将板材切成条带；第二步采用剪或冲的方式，将条带切成毛坯。所考虑的工艺约束包括最小条带长度约束和最大条带长度约束，排样方式中条带的长度，必须在最小和最大条带长度约束值之间。根据条带根数来衡量排样方式的下料工艺复杂程度，条带根数越少，排样方式越简单。因此，切割工艺最优性，是指在保证所含毛坯数达到最大的前提下，生成条带根数最少的排样方式。目前，矩形毛坯单一排样的常用算法主要有动态规划算法、递归算法、分支定界算法、连分数算法等。本文通过对研究现状的分析，指出现有算法不能直接处理本文的排样问题，不能生成条带根数最少的排样方式。本文对基本的动态规划算法加以改造，使之能够处理最小和最大条带长度约束，能够生成切割工艺最简单的排样方式。并在C+环境下，开发出同尺寸矩形毛坯排样系统UR。利用这个软件，进行了大量的例题测试，得出对生产实践具有指导意义的结论。本文的主要工作总结如下：第一，根据生产实践的要求提出要解决的排样问题，对同尺寸矩形毛坯排样的研究现状进行分析，论证本文研究的必要性。第二，对现有同尺寸矩形毛坯排样算法进行研究，选择合适的算法作为本课题研究的主要算法。第三，在现有算法的基础上设计出新的算法，用以解决本文研究的排样问题。在C+环境下，开发出同尺寸矩形毛坯排样系统，用于验证本文解决方法的可行性与有效性。第四，通过实验计算，分析测试本文所提出的算法，得到对生产实践具有指导意义的结论。通过对实验计算结果的分析，得出如下对生产实践具有指导意义的结论：(1)条带长度约束的存在，会使下料利用率下降。在实际生产活动中，应注意改进下料工艺，尽量不对条带长度形成约束。(2)最小条带长度约束值增加，会使排样方式中所含毛坯数下降，但其在一定范围内变化时，对下料利用率的影响不大。因此，实际生产中为保证冲裁工艺的安全性，可以对最小条带长度施加约束。(3)最大条带长度约束值减小，会使排样方式中所含毛坯数下降。特别是当减小到一定值时，会引起下料利用率的明显下降。对于实际生产，通过改进下料工艺，可以改变最大条带长度约束值。因此，可以应用本文算法进行分析，确定合适的最大条带长度约束值。通过权衡改进工艺的费用和因下料利用率提高所得到的收益，进行改进工艺的投资决策。(4)所含毛坯数相同的排样方式，所含条带数可能有较大差别。本文算法能够生成条带根数最少的排样方式，从而简化下料工艺，具有应用价值。本文链接：http:/