基于遗传算法动态路径优化.pdf

资助项目太原市20 12年科技项目计划大学生创新创业专题(1 20 164013) 太原市20 12年科学技术发展计划电子信息及物联网产业专题(1 11102) Supported by College Students’Innovative ’’· 。1几n nTai5 ScienceEntreoreneunal 1001C Ot 1alyuan clen andTechnology Development Planin20 12 (1 20164013) Electronic Informati—on and Inte,rnetof Things Industry Topic ofTaiyuan Science andTechnology Development Planin 2012 (11 1102) 太原理工大学硕士研究生学位论文基于遗传算法的动态路径优化摘要随着世界经济、社会进步以及城市化进程的加快,城市机动车的数量也迅速增长,交通拥挤甚至阻塞现象频繁发生,交通环境不断恶化,这己成为影响社会发展的消极因素。因此,如何提高城市道路的利用率,减少车辆的行程时间,降低交通拥挤的发生率以及其带来的消极影响已成为各大城市急需解决的交通问题。动态路径优化是目前解决以上交通问题的最佳方法,它的基础是对城市道路进行数学建模,核心思想为动态路径优化算法,宗旨是通过智能终端引导车辆按最优化路线行驶,提升道路的利用率,减少通行时问,缓解交通拥挤。本论文算法正是全面考虑动态路径优化的基础、核心和宗旨进行设计, 将动态路径优化的宗旨贯穿于建立模型和设计算法的整个过程中。文章内容主要包括以下三个部分:动态路网模型的建立、面向动态路网模型的改进遗传算法的研究以及该改进算法的收敛性分析和算例仿真。第一部分:动态路网模型是路径优化的依据,它的建立是整个优化过程的基础。本论文在详细介绍图论相关知识、交通流参数以及路权的标定方法的基础上,提出设计模糊控制器将间断交通流中交通流参数(平均行程速度和排队比)以及连续交通流中交通流参数(平均行程速度和流量)的实时值转化为取值区间为[O,1]的拥挤度,然后结合路段的实际长度计算得到路网中该边(路段)的动态路权,从而建立动态路网模型,为第二部分的动态路太原理工大学硕士研究生学位论文径优化作基础。第二部分:动态路径优化算法是动态路径优化的核心,算法的选择直接关系到动态路径优化的动态性、实时性和有效性。本论文对常用的最短路径算法进行比较分析后,选择遗传算法来进行路径优化,并对选择、交叉、变异算子进行改进,提出了面向动态路网模型的改进遗传算法。第三部分:查阅文献明确遗传算法收敛性的定义,根据该定义分析了本论文改进遗传算法的收敛性,并推理得到该改进算法收敛于全局最优解的充分条件。最后对某市部分地图构成的路网做实验,通过Matlab仿真验证了本论文算法的动态性、实时性和有效性。关键词:拥挤度,动态路网,模糊理论,遗传算法,动态路径优化太原理工大学硕士研究生学位论文 DYNAMIC PlATH OPTIMIZATl0N BASED ON THE IC ALGOIUTHM AB STRACT Witll the acceleration of the world economy,social progress,and the process ofurbanization,the number ofurban motor vehicle rapidly grow,and heavy traffic and even blocking phenomenon occurs e a negative factor affecting social development thattraffic environment is ,it e aD urgent need ofsolving thetraffic problems inmajor citieshow toimprove the utilization ofcityroads,and to reduce vehicle’S traveltime andthe incidence andthenegative impact oftraffic congestion. Dynamic path optimization isthe best way to solve the above traffic isbased onmathematical modeling oftheurban core isthe dynamic pathoptimization algor