（计算机应用技术专业论文）基于动态规划的公交车调度问题的研究.pdf

湖北工业大学硕士学位论文 摘要 随着社会经济的高速增长，在城市人口商速增长的同时，城市居民出行量迅 速提离，造成交通拥挤。而城市公共交通系统的顺畅与否直接影响着城市经济运 行的效率和居民生活的质量。我国目前的城市公交车辆调度方法普遍落后：一方 面造成居民乘车过于捌挤，候车时间过长：而另一方面造成公交公司有限的资源 大量浪费。在这种前提下，探索城市公共交通车辆优化调度方法对提商现有城市 公共交通的效率具有重要的现实指导意义。 城市公交车调度问题是指根据城市中某条公交线路各个时段的客流信息，确 定此条线路各个时段的发车次数和发车间隔，最后制定出优化的发车时刻表，用 以指挥安排公交车辆的运营。公交车调度问题是一个双目标问题，既要考砖公交 公司利益，又要考虑乘客利益，公司利益表现为减少总发车次数和提高车辆满载 率，乘客利益表现为减少平均候车时间和提高乘车舒适度。 本文针对此问题依据动态规划理论，研究建立了一个公交车调度的动态规 划模型，同时给出了该模型的评价指标。并通过实例对模型进行了验证，实验结 果表明，该模型是有效的。 本文首先分析了国内外城市公交车调度的现状，指出了我国公交车调度存在 的问题。在此基础上，提出了本课题研究的主要内容和方法以及研究的意义。 然后阐述了动态规划理论的基本原理和基本思想，介绍了动态规划的基本概 念和基本方程，提出了应用动态规划的前提条件。 接着本文对公交车调度问题进行分析和简化处理，并给出合理的假设。在这 些假设的基础上逐步深入分析，根据动态规划理论，设计出公交车辆调度的动态 规划模型。 最后对设计的动态规划模型进行实例检验，并对模型结果给予分析和评价。 检验结果表明，该动态规划模型是有效的。 关键蠲：公共交通，公交车调度，动态规划，馥线拟合 湖北工业大学硕士学位论文 a b s t r a e t w i t ht h eh i g hs p e e dg r o w t ho fb o t hs o c i a le c o n o m ya n du r b a np o p u l a t i o n ，t h e d e m a n do fu r b a nc i t i z e nf o rt r a v e li nt h es a n r l ec i t yi si n c r e a s i n g l yg r o w i n g ，w h i c h u s u a l l ye x c e e d st h es u p p l yo fp u b l i ct r a f f i c sc a p a c i t y 。a n dr e s u l t si ns e v e r et r a f f i c c r o w d i n g h o wt os o l v et h i sp r o b l e mi si m p o r t a n tt oe a c hc o u n t r y , e s p e c i a l l yt ot h e d e v e l o p i n gc o u n t r ya tp r e s e n t ，t h em e t h o do f t h eb u ss c h e d u l i n gi no a fc o u n t r yi sp o o r s oi ti sm o r ew i s ea n dm o r er e a l i s t i ct ot r yi m p r o v i n gt h el e v e lo f t h eb u ss c h e d u l i n g t h eb u s ：s c h e d u l ；m gp r o b l e mp r e s e n t e di nt h i sp a p e ri sc o n c e r n e dw i t hc o m p i l i n g a 1 1o p t i r e a lt i m e t a b l eb a s e do nt h ep a s s e n g e rd e m a n d si nd i f f e r e n tt i m er a n g e s7 lh e 口r o b l e n lc o n t a i n st w oo b j e c t i v e s ，w h i c ha r ec o n f l i c t o n ei st om i n i m i z et h eh e a d w a y ， w h i c hc o n c e r n st h ep a s s e n g e r s w a i t i n gt i m e s a n o t h e ri st om i n i m i z et h en u m b e ro f f l i p s ，w h i c hc o n c e r n st h eo p e r a t i o n a lc o s to f ab u sc o m p a n y t h i sp a p e r , o i lt h eb a s i so f p a s s e n g e r - f l o wo f a nu r b a nr o u t e ，a p p l i e st h et h e o r y o fd y n a m i cp r o g r a m m i n gt ot h eb u ss c h e d u l i n gs y s t e ma n de s t a b l i s h e sad y n a m i c p r o g r a m m i n gm o d e lo nt h er o u t et h a th a sb e e nf i n a l l yg i v e na ne x a m p l et ot e s t i ：i r s to f a l l ，t h i sp a p e rr e v i e w st h eh i s t o r yo f d e v e l o p m e n to f u r b a np u b l i ct r a f f i c b o t hi nc h i n aa n di no t h e rc o u n t r i e s ，a n a l y z e st h et e n d e n c yo fd e v e l o p m e n t ，i l l u s t r a t e s t h ei m p o r t a n tr o l eo fu r b a np u b l i ct r a f f i c ，r e s e a r c h e sp r o b l e m so fc u r r e n tb u ss c h e d u l i n g s y s t e mt h a te x i s t si no k l rc o u n t r yt o d a y ，a n d p u t sf o r w a r dt h em a i nc o n t e n t ，m e t h o d sa n d t h es i g n i f i c a n c eo f t h er e s e a r c h s e c o n d ，i ts t a t e st h ef u n d a m e n t a lt h e o r ya n dt h o u s a to fd y n a m i cp r o g r a m m i n g ， i n t r o d u c e st h eb a s i cc o n c e p t sa n de q u a t i o n ，r e f e r st ot h ea p p l i c a t i o np r e m i s eo f d y n a m i cp r o g r a m m h i g i b i r d a s s a yt ot h eb u ss c h e d u l i n gs y s t e mh a sb e e ng i v e ni n 廿1 ep a p e r , i ts e l e c t s t h eb e n e f i to fb u s c o m p a n i e sa sa no b j e c t i v ef u n c t i o na n dt h a to fp a s s e n g a r s a s c o n s t r a i n s ，a n dt u r n sad o u b l e - o b j e c t i v ep r o b l e mt oas i n g l e - o b j e c t i v ep r o b l e m t h e ni t g i v e ss i m p l i f i e dt r e a t m e n t ot h e b u ss c h e d u l i n gs y s t e ma n dp m s e n t ss o m em a s o n a b l e a s s u m p t i o n s f i n a l l yo n f i l i t h e rd i s c u s s e s 。i ts e t su pam o d e li nt e r m so fd y n a m i c p r o g r a r m n i n g 湖北工业大学硕士学位论文 f i n a l l y , t h em o d e lh a sb e e nv e r i f i e db yr ni n z t a x l c e a tt h es 8 1 t i et i m e ，t h er e s u l t s r e q u i r e dh a sb e e nm a a l y z e da n de v a l u a t e d k e y w o r d s ：p u b l i ct r a f f i c ，b u ss c h e d u l i n g ，d y n a m i cp r o g r a m m i n g ，c u r v ef i t t i n g 湖北工业大学硕士学位论文 第1 章绪论 1 1 公交车调度问题描述 公交车调度是指根据客流量的情况，即某条线路上下行两个方向上各时段内 各站的上车乘客数及下车乘客数，确定此条线路各时段的发车次数以及发车i n j 隔， 最后制定出发车时刻表用以指挥公交车辆运营。公交车的调度过程是一个多目标 决策过程，既要考虑到公交公司的利益，又要考虑到乘客的利益。公交公司的利 益表现为减少发车总次数和总车辆数，乘客利益表现为减少候车时间和乘车捌挤 程度。本课题在综合考虑这两者利益的基础上，结合乘客流量的情况，提出了一 种有效的调度方案。 1 2 国内外公交车辆调度的研究现状 1 2 。1 国外公交车辆调度系统的研究现状 在国外发达国家，公共交通建设普遍受到高度重视。经过一个多世纪的建设， 国外发达国家的大城市的公共交通大都具有了相当的规模，有一套完整的城市公 共交通理念与管理体系。现今已经建成了许多具有不同风格和特点的诸如：法国 巴黎的以多层地铁为主的公共交通系统1 2 】：日本东京的直接连接高层建筑的多层立 体公共交通系统【3 】；英国的伦敦以矩形网络状地铁为主的公共交通系统和加拿大的 多伦多以地铁、巴士、出租车与租车综合发展的公共交通系统等p 1 ；还有现今受到 人们普遍认同的巴西的库里蒂巴市【4 】和美国洛杉矶市【5 l 的快速公共汽车( b a sr a p i d t r a n s i t ，b r t ) 运输系统等公共交通模式。这些城市的道路交通建设和运输车辆调 度都处于世界先进水平。 在发达国家，不仅公共交通运输的建设与管理已经有了一套完整的体系，而 且随着经济的发展而不断的完善与进步，特别是城市公菇交通运输的经营决策何 较完整和相对比较科学的方法，城市的公共交通规模，公共交通形式，公共交通 网络的形成和公共交通车辆调度等等都有一定的科学依据。在经济上，欧、美、 湖北工业大学硕士学位论文 日等国特别关注降低公共交通成本、提高公共交通运输效率【6 】- 【”】。荚因对先进的 公共运输系统研究集中于使公共运输系统更有效和可靠 13 】。它包括向出行者传 达可靠和精确的情报，有了这些信息，更多的人可以使用这些各选出行方式。美 国公关运输系统的用户服务功能包括：公共运输辅助管理、提供公共运输信息、 满足个人需要的非定线或准定线公共运输、公共运输安全等四项f 2 0 l 。 可见，发达国家无论是宏观交通规划还是具体道路管理系统方面均很重视公 共交通。各国对城市公共交透车辆的调度管理，由于各自的客观条件和发展历史 不同，采取的方法也不同。 1 2 2 我国城市公交车调度的研究现状 公交车调度的主要任务是按照行车作业时刻表，结合线路运输供求的实际情 况调度车辆，以保证城市公交客运任务按期、保质、保量地完成。 1 2 2 1 传统公交车调度的基本方法 我国传统的公交车调度的基本思想是以最大限度地满足乘客地出行需求为l ! i 标。它基于这样一个基本假设：乘车的乘客越多，则公司收入越多，于是，公司 的效益越好。其具体作法是：首先，根据调查掌握居民的出行需求或根据线路周 围吸引区范围的居民人口数量乘上居民出行系数得出的居民出行需求( 估计值) ； 然后，测算最大断面客流密度( 包括产生的位置和时间) ：最后，以满足摄大断面 客流为目标调度安排车辆。其具体调度排班形式主要有两种类型：按车辆在线 路的工作时间不同，分正班车、加班车和夜班车；按运行区域和停站方式不 同，分全程车、区间车、快车等形式。各公共汽车营运线路均以正班车、全 程车为基本调度排班形式。并根据线路客流的分布情况辅以其他调度形式。 区间车调度形式通过计算路段客流分布不均匀系数或路段客流量差的方法 来确定是否采用：快车调度形式通过计算客流沿方向分布不均匀系数或站点 集散量不均匀系数的方法确定是否采用；加班车调度彤式是否采用则通过计 算客流的时间不均匀系数来确定。 1 2 2 2 传统公交车调度方法的主要弊端 以上这种传统的公交车调度理论与方法为我国各大城市所广泛采用。但 是，传统公共交通过分强调服务性，企业亏损依靠政府补贴，企业不关心公 湖北工业大学硕士学位论文 共交通的内在规律，不研究公交车辆的科学调度问题。在市场经济越柬越发 展的今天，传统公交车调度方法已越来越不能适应了。而且，从上世纪4 0 年代沿用至今的“定点发车、两头卡点”的传统调度作业方式，由于信息不 灵、容易出现调度失控，车辆运行经常出现“串车”、“大间隔”现象，要 么使乘客候车时间过长；要么前车提前进站、后车拥挤不堪，甚至导致全线 运行秩序混乱，严重影响了公共客运的服务质量和社会信誉。笔者认为，公 交企业虽然在满足居民的出行要求的同时取得了收益，但收益并不等同于企 业效益。公交企业应在完成其服务功能的同时追求企业效益的最大化。公交 企业只有在效益增长的基础上才能逐步发展壮大，才具备了进一步提供新的 更好的服务的能力；有能力提供新的乘客所需服务，企业才能获得更好的效 益，这是一个良性循环。如果只强调公交行业的特殊性，只强调服务，不注 重企业的效益，则企业没有积极性。在政府补贴逐渐减少的情况下，企业的 发展越来越困难，也就没有能力满足居民的现行出行服务要求，更不用说提 供新的更好的服务了似l 】i 【”j 。 所以，公交企业同其他企业一样要在生产组织管理过程中强调提高企业 效益的目标，要研究和探索科学的调度方式。企业效益与社会服务是同样重 要的。 1 2 2 3 公交车调度的未来发展趋势 公交企业的调度管理包括调度计划的生成和调度的执行与监控。传统的 公交企j 止调度计划的制定主要依靠调度管理人员的经验和若干简单的服务 指标控制，不能根据客流的变化动态地调整计划。公交运营企业对调度计划 的监控，目前只能做到在线路一头一尾的首末站进行控制管理，对于车辆在 各个中途站点的情况无法监控。所以，公交车调度的发展趋势是利用现代科 学技术，实行准适时及适时摊班。为了改善城市公共客运系统的服务质量、 提高公交车辆有效利用水平，使运行车辆处于全面受控状态。装备现代化的 车辆运行自动监控系统是一个很重要的环节，但这一技术在我国公交企业应 用存在投入大、成本高，对外部环境要求高的缺点。对于我国大多数公交企 业，当前实际应用的条件并不成熟：另外，光有先进的硬件装备还不够，还 必须要有科学的调度手段。所以，现阶段加强公交车调度的科学研究，探讨 科学的调度方法是非常必要的。目前，随着市场经济的发展，政府对公共交 通运输企业的补贴越来越少，更要求公交企业改革管理，科学调度，提高企 湖北工业大学硕士学位论文 业经济效益1 2 6 j 【2 9 j 。 目前，我国城市公共交通车辆调度方法比较落后。不仅如此而且在公 交调度领域的理论研究起步也比较晚，并且可查到的相关文献多为一些宏观的理 论探讨的内容【3 0 l - i ”i ，在具体调度的研究方面，近两、三年来j 。开始出现一些报道， 所采用的方法大体相似，基本上是使用遗传算法1 3 9 。【删，偶有用组合优化【4 5 】的。遗 传算法是一类模拟生物界自然选择和自然遗传机制的随机化搜索算法，其内涵哲 理启迪于自然界生物从低级到高级、简单到复杂的漫长而绝妙的进化过程，是借 鉴达尔文的物竞天演、优胜劣汰的生物进化过程的计算模型口9 1 。在遗传算法用于 解决公交车辆调度问题的研究中，主要有以下两个因素与本文考虑不同：( 1 ) 将 车容量定为无限大，每一趟车到站，站点的所有等待乘客都可以上车：( 2 ) 不考 虑下车乘客的情况。而实际上，车容量是有限的本研究中将车容量设为1 个参 数，它的值可以根据公交车的实际大小来确定。另外，下车乘客的情况对线路的 调度计划是有影响的，因为乘客的实际能够上车的人数是随下车人数的变化而变 化的，特别是在车辆满载的情况下，下车的人数越多，能够上车的乘客就越多。 因此，本文将同时考虑下车乘客的情况。 1 3 研究方法 随着市场竞争的日益激烈，需要提供低廉、高效的服务。在一定的约束 条件下，如何合理、有效地安排其组成部分所占资源、运行时问及先后顺序， 以获得时间或者成本的最优化。也即是说，在满足一定约束条件的前提下 寻求某一个目标最优的过程，在有限资源基础上确定最优的行为序列。公交 车调度问题就是一类典型的优化问题，最终目的是求得优化的发车次数和优化 的发车时刻表。然而，在求解各个时间段的发车次数时对各时间段所采取的决 燕是不确定的，对于这种含有客观的或人为的不确定性的决策问题，线路规划、 整数规划等优化方法通常是无能为力的，虽然随机规划和模糊规划可以解决一部 分不确定优化问题，但又远远不能满足解决具有多重不确定性的优化问题的需求。 而动态规划的快速发展，给问题研究带来了崭新的局面。动态规划方法不但在经 济管理、工程技术和最优控制等方面有着广泛的应用，而且在优化调度问题中， 尤其在水库调度和车辆调度等这些不确定性优化调度问题中的应用越来越 居于重要的地位，并取得了显著的研究成果。 湖北工业大学硕士学位论文 随着计算机技术的飞速发展以及智能计算技术的不断涌现。许多复杂的优化 问题已经能够通过计算机求解。尽管目前优化问题的求解规模常常与计算机的运 行速度有关，但是随着计算机的更新换代，问题的主要矛盾不在于运行速度而在 于建立问题的数学模型和求解算法。从这个意义上说，计算机的飞速发展解除了 动态规划求解速度有些慢的缺陷。另外，动态规划具有求解效果好的特点，它能 够求得问题的全局最优解。因此，对公交车调度问题，本文将采取动念规划方法 来求解。 1 4 研究意义 公共交通是城市交通不可缺少的一部分，是保证城市生产、生活正常运转的 动咏，是提高城市综合功能的重要基础设施之一，它对城市各产业的发展，经济、 文化事业的繁荣，城乡间联系等起着重要的纽带和促进作用。而一般城市的现行 公共交通车辆调度方法普遍落后，造成了现有的公共交通资源大量浪费。因此， 探索一般城市公共交通车辆优化调度管理方法，从“软件”入手改革现有城市公 共交通车辆调度管理系统，提高城市公共交通的效率是很有意义的。 公交车调度问题一直是一个很受关注的研究课题，但是现有的求解方法还存 在很大的不足，因此尝试建立不同的模型和研制不同的求解方法具有很大的理论 研究价值。本文采用动态规划的方法来解决公交车调度问题，不仅可以帮助公交 公司提高车辆利用效率、降低运营成本，同时还能提高乘客满意率。这对缓解我 国公交公司目前运营资源短缺、服务质量落后的现状具有较大的现实意义。此外。 该系统的成功研制还可以将发车时刻表的手工编制方式提升为利用计算机自动编 制方式，从而提高时刻表的质量、降低编制人员的工作负担。因此，本课题的研 究既具有理论意义，又具有实用价值。 1 5 研究内容 动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种方法。 大约产生于5 0 年代。1 9 5 1 年美国数学家贝尔曼等人根据一类多阶段决策问题的 特性，提出了解决这类问题的“最优化原理”，并研究了许多实际问题，从而创建 了解决最优化问题的一种新的方法动态规划【4 6 】。本文结合动态规划原理和方 法，旨在研究以下三个方面的内容： 湖北工业大学硕士学位论文 1 根据客流信息，即乘客上下车情况，运用动态规划理论，设计一个适用寸： 公交车调度的动态规划模型。该模型的结果期望能够同时满足乘客和公交公司的 利益，即达到使公交公司发车次数尽量少，以提高公交公司平均满载率，同时锼 乘客的平均候车时间尽量少，以提高乘客的平均满意率的目标。 2 动态规划问题属于最优化问题的一种，本模型的目的是在满足乘客基本要 求的前提下，求优化的发车次数和发车间隔，最终生成优化的发车时刻表。在最 优化问题的数学模型建立后，主要问题是如何通过不同的求解方法解决寻优问题。 根据动态规划求解问题的特点，本文给出了模型的求解方法及主要算法流程。 3 通过实例对模型进行测试检验，并对结果进行分析和评价，证明所设计的 动态规划模型是有效的。 6 湖北工业大学硕士学位论文 第2 章动态规划方法 近几十年来，由于实际和理论的需要，运筹学的各种理论和方法蓬勃发展， 在很多领域都取得了突出的成就，动态规划作为运筹学的一个分支，在工程技术、 经济、工业生产及军事等部门都得到了广泛的应用，并获得了显著的效果许多 问题，利用动态规划去处理，常比线性规划和非线性规划这样一些“静态”的优 化方法更有成效特别是对于离散性质的问题，传统的解析数学方法无法施展其 技，动态规划就常常成为一种有用的工具对于某些问题，利用动态规划方法处 理，不仅能对阃题作出定性的分析，而且也能给出利用电子计算桃求其数值解的 方法。 2 1 动态规划概述 动态规划( d y n a m i cp r o g r a m m i n g 简称d p ) 是最优化技术中一种适用范围很广 的基本的数学方法。它用于分析系统的多阶段决策过程( m u l t i s t a g ed e c i s i o n p r o c e s s e s ) ，以求得整个系统的最优决策序列。 当一个系统中含有时间变量或与时间有关的变量，且其现时的状态与过去和 未来的状态有关联时，这个系统称为动态系统。动态系统的优化问题是一个与“时 间过程”有关的优化问题。就是说，在寻求动态系统的状态与最优决策时，不能 只从某一时刻着眼，得到一个状态和决策的优化结果，就算完结。而是要在某一 段时期内，连续不断地做出多次决策，得到一系列状态和最优的决策，使得系统 在整个过程中，由这一系列决策造成的总的效果为最优。换句话说，就是在时川 过程中，依次采取一系列最适当的决策，来求得整个动态过程的最优化问题的解 这种动态过程寻优的一种基本的数学方法，被称为动态规划法1 4 “。 2 2 多阶段决策过程 多阶段决策过程，是指这样一类活动的过程：由于它的特殊性，可将过程划 分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，并且一个阶段 湖北工业大学硕士学位论文 的决策确定以后，常影响下一个阶段的决策，从而影响整个过程的活动路线。各 个阶段所确定的决策就构成一个决策序列，通常称为一个策略。由于每一个阶段 可供选择的决策往往不止一个，因而就形成有许多策略可供我们选取，对应 二一 个策略就有确定的活动效果，这个效果是可用数量来衡量的。这样，不同策略， 效果也不同。多阶段决策问题，就是要在允许选择的那些策略之间，选择个最 优策略，使在预定的标准下达到最好的效果1 4 ”。 在多阶段决策过程中，任一阶段的演变特征是用状态的变化来描述的状态 变化或转移的效果取决于该阶段决策变量的变化。前一阶段末的状态就是下一阶 段初的状态。 比如最短路径问题：如图2 1 ，给出个线路网络，从a 点要铺设一条管道到 g 点，其两点之间连线上的数字表示两点间的距离。今求选择一条由a 到g 的铺管 线路，使总距离最短。 圈2 1 最短路问题 这是一个典型的多阶段决策问题。从a 到g 可以分为6 个阶段，从a 点开始 到8 点为第一阶段。这时有两个选择：一是到8 l 点；一是到b 2 点。若选择到8 2 点的决策，则b 2 点就是第一阶段决策的结果，它既是第一阶段的终点，又是f 一 阶段( 第二阶段) 路线的始点。在第二阶段，再从b 2 点出发，对应于b 2 点就有 一个可供选择的终点集合 c 2 ，c 3 ，c 4 ) 。若选择由b 2 到c 2 为第二阶段的决策，则 c 2 就是第二阶段的终点，同时又是第三阶段的始点。类似地可以递推下去，直到 终点g 。可以看到：各个阶段地决策不同，所走的路线就不同。在各个阶段中选耿 一个恰当的决策，就可使铺设的管道线路最短。其按阶段的计算过程如下： 第一步：看最后一个阶段，即第6 阶段。由f 1 到终点g ，只有一个选择t 距 湖北工业大学硕士学位论文 离为4 ；由f 2 到g 也只有一个选择，距离为3 。即 从f 1 到g 的最短距离f 。( f 1 ) = 4路线为f i 一 g 从f 2 到g 的最短距离厶( f 2 ) = 3路线为f 2 一 g 第二步：看第5 阶段。由e t 到g 有两个方案可供选择，即e 1 一 f 1 一 g 和e 1 一 f 2 一 g ，它们的距离分别为决策取道f l 的距离为v 。( e 1 ，f 1 ) + f 6 ( f i ) = 7 ，决策取道 f 2 的距离为v 。( e 1 ，f 2 ) + f 。( f 2 ) = 8 。然后在两者中选择最小者作为e 1 到g 的最优线 路即e 1 到g 的最短距离为f 。( e i ) = m i n v s ( e l ，f i ) + 凡( f 1 ) ，v i ( e l ，f 2 ) + 厶( f 2 ) 卜7 。 最优路线为e 1 一 f 1 一 g 。同理，e 2 到g 的最短距离为 f 5 ( e 2 ) = m i i 1 fv 。( e 2 ，f 1 ) + f 6 ( f 1 ) ，v 。( e 2 ，f 2 ) + 厶( f 2 ) - 5 ，最优路线为e 2 一 f 2 一 g ： b 3 到g 的最短距离为f ；( e 3 ) = m i n v s ( e 3 ，f 1 ) + ( f 1 ) ，v 。( e 3 ，f 2 ) + ( f 2 ) = 9 ，最优 路线为e 3 f 2 一 g 。 同理，第三步：看第4 阶段。 f 。( d i ) = m i n v ；( d l ，e 1 ) + f s ( e 1 ) f 2 一 g ： f 4 ( d 2 ) = m ir l v 4 ( i ) 2 ，e 2 ) 十厶( e 2 ) f 2 一 g ： v 。( d i ，e 2 ) + f 5 ( e 2 ) = 7 ，最优路线为d 1 一 e 2 一 v 。( d 1 ，e 3 ) + 厶( e 3 ) ) = 6 ，最优路线为d 2 一 e 2 一 r ( d 3 ) = m i n v 。( d 3 ，e 2 ) + f ；( e 2 ) ，v 。( d 3 ，e 3 ) + f 5 ( e 3 ) 卜8 ，最优路线为d 3 一 e 2 一 f 2 g 。 第四步：看第3 阶段。 f ，( c 1 ) = m i n v 。( c l ，d 1 ) + f ( d 1 ) ，v ，( c l ，d 2 ) + t ( d 2 ) = 1 3 ，最优路线为c 1 一 d 1 一 e 2 一 f 2 一 g ： f 。( c 2 ) = m i l 1 v 。( c 2 ，d 1 ) + ( d 1 ) ，v 。( c 2 ，d 2 ) + f 4 ( d 2 ) - 1 0 ，最优路线为c 2 - - d 1 一 e 2 一 f 2 一 g ： f 。( c 3 ) = m i n v 。( c 3 ，d 2 ) + ( d 2 ) ，v 。( c 3 d 3 ) + 乱( d 3 ) ) - 9 ，最优路线为c 3 一 d 2 一 e 2 一 f 2 一 g ： f 1 ( c 4 ) = m i n v a ( c 4 ，d 2 ) + ( d 2 ) ， v a ( c 4 ，d 3 ) + f d ( d 3 ) = 1 2 ，最优路线为c 4 - - d 3 一 e 2 一 f 2 一 g 。 第五步：看第2 阶段。 9 湖北工业大学硕士学位论文 f z ( b 1 ) 2 m i n v z ( b l ，c 1 ) + f 3 ( c 1 ) ，v ：( b l ，c 2 ) + f 3 ( c 2 ) ，v ：( b l ，c 3 ) + ( c 3 ) j - 1 3 ，最 优路线为b 1 一) c 2 一 d l 一 e 2 一 f 2 一 g ： f 2 ( b 2 ) = m i n v z ( b 2 ，c 2 ) + f 3 ( c 2 ) ，v 。( b 2 ，c 3 ) + ( c 3 ) ，v ：( b 2 ，c 4 ) + f 3 ( c 4 ) ) = 1 6 ，最 优路线为b 2 一 c 3 一 d 2 一 e 2 一 f 2 一 g ； 第六步：看第1 阶段。 f ( a ) = m i n v ( a 。b 1 ) + f 2 ( b 1 ) ，v 、( a ，b 2 ) + f 。( b 2 ) = 1 8 ，最优路线为a 一 b l 一) c 2 一 d 】一 e 2 一 f 2 一 g ： 2 3 最优化原理 最优化原理是动态规划的理论基础，其内涵可作如下表述：一个过程的最优 策略具有如此性质，即无论其初始状态和初始决策如何，其今后诸决策对以第 个决策所形成的状态作为初始状态的系统而言，必须构成最优策略【4 ”。简单地说 就是，一个整体过程的最优策略的子策略一定是最优策略。比如图1 中的例子： 如果a 一 b 1 - - c 2 - - d 1 一 e 2 一 f 2 - - g 是最优线路，那么无论从该线路中的 哪一点开始( 如从d 1 点开始) 到终点g 的那一段线路，仍然是从该点( 即d 】点) 到终点g 的所有可能选择的不同线路的最优线路。要不然，如果从d 1 到终点还 有另条更短的子线路存在，就会形成一条比原来最短路线更短的路线，而这是 不可能的。这一事实就称为最优化原理。 2 4 动态规划的基本概念和基本方程 2 4 1 动态规划的基本概念 1 阶段( s t a g e ) ：把所给定问题发展变化的全过程恰当地离散化，划分为若 干个相互联系的序列单元，称为阶段。有时也叫级或步。常用k 表示阶段变量， 阶段的序列编号k = l ，2 ，n ，当问题本身是离散的，可按离散的空间位置划分 为若干位置阶段，k = 】，2 ，3 ，4 。当问题的变化过程是依时间连续变化时，则阶 段变量可用t 表示，并把连续的阶段变量按相等的时问增量t 离散化，离散化_ f 吾 的t 可由序列t 。( i ：1 ，2 ，n ) 表示，并定义在每一单元i ( 阶段) 中 湖北工业大学硕士学位论文 t ，嫱茎t 。s t i 终1 2 l ，2 ，n 相应若i = k 阶段初的t 值为t 。 t x = t 。+ ( k 1 ) t 式中t 一初始瞬间的t 值 2 状态( s t a t e ) ：系统在某阶段中，过程演变的各种可能发生的情况，称为 该阶段过程的状态。描述状态的变量，称为状态变量，以s 表示。整个系统的状 态，可由一个或数个状态变量的各种不同数值来表示。状态变量的选定，需根据 该系统的数学模型的性质和范围而定。如最短路径问题中，各阶段都有若干个站 点，这些站既是该段以后某路径的出发点，又是前一段路径的终点，这些站叫做 状态。选择线路通过的站点位置作为状态变量( 用x 。来表示) ，在第阶段卡刀只有 一个状态就是a 点。在第二阶段初有两个状态，即b l 点和b 2 点。依此，在第k 阶段初的状态，可用第k 阶段初状态点的集合( 称为状态集合) 来表示，记为 x i = s ，s 。，s ) 或x k x i = x k ”，x k ”，x k ) 式中 i 一表示阶段号，i = 1 ，2 ，n ； r m 一表示该阶段可能方式的状态数。 因此，描述问题第i 阶段状态的变量，是个向量，简记为s ，。 3 决策( d e c i s i o n ) ：决策就是某阶段状态给定以后，从该状态演变到下一 阶段某状态的选择。就是说，在某阶段中，若阶段的初始状态给定后，作出某一 决策，则该初始状态为相应的末端状态。作出不同的决策，得到不同的末端状念。 描述决策变化的量，称为决策变量。常用山( s j ) 表示第k 阶段状态处于第s - 状态时 的决策变量，d 。是第k 阶段决策向量。在实际问题中，决策变量的取值常限制在一 定的范围中，此范围称为允许决策集，通常以d 、( s ) 表示第k 阶段第s j 状态的允许 决策集合。显然有 d 。( s 。) d t ( s ) 4 策略( p o li c y ) ：是指一个决策序列。由过程的第一阶段开始到终点为止 的过程，称为问题的全过程。由每一阶段的决策也( s 。) ，k - - - - 1 ，2 ，n 组成的决策 序列，称为全过程镱略，简称策略，记为m 湖北工业大学硕士学位论文 目口p ( - 一) ( s ) = d 。( s 。) ，d 。( s 。) ，d 。( s 。) ) 由第k 阶段丌始到终点的过程，称为原过程的后部子过程( 或称为k 予过程) 。 其决策序列，称为k 子过程策略，简称子策略。即 p ( 、) ( s 。) = d 。( s 。) ，d 。，( s 。) ，d ( s 。) 在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合， 用p 表示。从允许策略集合中，找出达到最优效果的策略。称为最优策略。记为 n 】胂( s ；) 。 5 报酬函数：当过程处于状态s 。并采取决策的d 。而得到的报酬或费用。它 是定义在k x d 。上的函数，称为第k 段的报酬函数，记为v 。( s - ，d - ) 。 6 目标函数：在决策过程问题中，从s 。出发，采取策略p 。、时所得到的总效果 或总报酬，称为目标函数( 或称指标函数) 。它是定义在全过程和所有后部子过 程上的确定的数量函数，它要求满足递推关系和严格单调【4 8 】- i 5 2 1 。 若考虑的过程是从第k 段开始到过程终点的k 子过程，则目标函数可表示为： v 。= v k 。( s hs ，s ) = v h ( s hd bd 。山一。) = v 。( s 。，p ( 。，( s 。) )( 2 1 ) 不同的问题中，目标函数也不同，可能是距离、利润、成本、产品的产量或 资源的消耗等等。 如果目标函数是各段报酬函数之和； v ，。，( x ，) ) = v j c x , , ，西) ( 2 2 ) j = l i 则有v - 。( x n m ( x t ) ) = v y ( x j ，砌+ v j ( x j ，西) t ij - k + l = v 1 k ( x 【，pc ”( x ：) ) + v k n ( x k ，p ( h m ( x k ) ) ( 2 3 ) 湖北工业大学硕士学位论文 2 4 2 动态规划的基本思想 ( 1 ) 动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条 件( 简称为基本方程) 。要做到这一点，必须先将问题的过程分成几个相互联系 的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题 化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优 在每个子问题的求解中，均利用它的一个后部子问题的最优化结果，依次进行， 最后一个子问题所得的最优解，就是整个问题的最优解。 ( 2 ) 在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分丌， 又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选 取是从全局来考虑的，与该段的最优选择答案一般是不同的。 ( 3 ) 在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都 是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定 了最优路线。 2 4 3 动态规划的基本方程及数学模型 根据最优化原理，结合一个具体问题，把它表述为使过程状态序列转移，楣 应效益指标函数递推变化的递推方程( r e c u r s i v ee q u a t i o n ) ，就是动态规划的 基本方程。它的数学形式对于逆序鳃法如下： f 。+ ( ：。) = o p t v 。( s 。，d 。) + f 。+ ( s 。) ) ( 2 4 ) 出e d * 其中，k = n ，n - l ，2 ，l d 。为第k 阶段的决策变量； d k ( s 。) 为允许决策变量集合； s 。为第k 阶段的状态变量： f 。+ ( s 。) 为第k 阶段开始，初始状态为s 。时，子过程最优目标函数值； f k 0 ( s 。) 为第k + l 阶段开始，初始状态为s 。时，子过程最优目标函数值： v 。( s 。d 。) 为第k 阶段、状态为s 。，决策变量为d t 时的阶段报酬函数值： 从中可以看出： 湖北工业大学硕士学位论文 a ) 阶段变量k 经历过程的所有阶段，则这个方程变为组递推方程式。 b ) 方程中状念变量s 。的变化满足状态转移方程( 或称系统方程) ，即 s “= t k ( sk id k ) ； c ) 子过程的最优目标函数值f 。( s 。) ，当k = i 时，就是全过程的总效益最优值。 方程( 2 4 ) 的结构图如下： 望壁垄塑 始ai ! l ! l ! i l 鉴ii 丝：! l 蔓i b 终 l23kk + i nn + l 气g 】( 广1 可甄百厂- 系统方程：s k * l = t k ( s k ，d k ) 基本方程：p k ( s k ) = o p t v k ( s x ，d k ) + f * k + j ( s k ) ) 艘e d ( k = n ，n 一1 一，2 ，1 ) 图2 2 动态规划基本方程结构图 当一个实际问题归结为用动态规划方法来处理时，需根据题意，把它构造成 动态规划的数学模型。模型有三个主要组成成分，即： 系统的状态转移方程( 即系统方程) ； 衡量决策效益的标准目标函数； o 限制系统运筹的约束条件。 其中的决策效益若以收益( b e n e f i t ) 来衡量，目标函数则应取极大化。若以 成本和费用( c o s t ) 来衡量，则应取极小化。譬如，若令v 。( s 。一d ) 代表在k 阶段 时，系统状态为s 。使用决策为d 。时的收益，则此问题的动态规划数学模型可写为： 目标函数：使总收益极大化 m a x r = r * = f ( s 【，d ，d i ) = m a x ( ，矾) ) ( 2 5 ) ，l 约束条件： 湖北工业大学硕士学位论文 s k x d 。d 其中x 和d 为状态空间和决策空间。令f 。( s 。) 代表从第t 阶段兀始，初始状 态为s 。直到最后阶段n 过程中，用所有可行决策所能得到的最大收益。根掘动 态规划数学模型中目标函数的公式，( 2 5 ) 式可写为 m a x r t 一= f 。( s t ) = m a x ( ，反) ( 2 6 ) = l 再考虑模型的约束条件及系统方程，根据最优化原理将其推导如下； f ? j l ) ：m a x 羔吣矾) k i 文? n h t = m a x u ( 丑，4 ) + k ( & ，d 。) 。= 慨。n l k = t + l j r1 = m a x m a x v ，( s d ) + v ；( s 。d ) d t e d 。璺j d l k 。t + lo rn、 = m a x m，吐) + 叱( 墨，。) ( 2 7 ) “。篡a f 络x i f , ( s , m a x m t 篡a f o x ddied k - t + lj 根据最优化原理知，( 2 7 ) 式中第一项与d 。，d “无关，第二项中的s - 并不 明显的与d 。有关，但第t + 】阶段的状态变量s 。依d ，和s ：而变，它们的关系由系 统状态转移方程决定。因此( 2 5 ) 式变为 ，( s ) = n l a x h ( s 。4 ) + m a ) ( + 。陋( s ，d ，) = m a x v , ( s , ，一) + ：+ l + ( s ) ( 2 8 ) 则(