非支配排序遗传算法在智能公交调度中的应用研究_开题报告.docx

东北大学毕业设计（论文） 开题报告东北大学信息科学与工程学院毕业设计（论文）开题报告设计（论文）题目：非支配排序遗传算法在智能公交调度中的应用研究姓名： 卢 双 学号：20113564专业： 自动化 班级：1106班指导教师：马宏军 教授实习单位：控制理论与导航技术研究所开题日期： 2015年 3 月 25日1. 课题提出1.1 课题背景、目的与意义随着生产力水平的不但提高，社会的不断进步，全球城市化进程的不断发展，城市人口的不断增加，城市的公共交通运输已经成为国民生活重要的一部分，更是城市中不可或缺的基础设施。拥有一个好的公共交通运输系统对城市的各产业的发展都有着巨大的促进作用。现目前，伴随着工业水平的提高，机动车的数量大幅增长，城市道路交通流量几近饱和，交通事故频发，废气污染，噪声污染尤为突出，严重地制约了城市的发展，而公共交通工具具有运载量大，效率高，人均成本相对较低，相对占用资源较少，所造成的环境污染小的显著特点，因而公共交通运输系统成为解决交通拥挤的最佳策略。然而，各国现在所面临的主要问题是如何在有限的条件下最大化提高城市公共交通运输工具的承载能力，提高整个公共交通运输系统的运输效率，降低公交运营商的运营成本和乘客的出行成本。随着科学技术的不断发展，特别是信息技术的突飞猛进，城市公共运输系统已逐渐实现一定程度的信息化与智能化，智能交通系统（Intelligent Transportation System，简称ITS）逐渐建立。结合交通系统的信息化与智能化对公共运输系统进行优化成为一种有效的解决方案与措施。本文立足于目前各国智能交通系统发展状况，着眼于公交系统的未来发展，研究实用性较强的公交调度优化方案，降低公交公司运营成本，缓解城市客流拥挤，使公共交通系统更好的服务社会，致力于实现社会效益，经济效益的最大化。如今，各国各大城市均积极投资建设智能交通系统，并陆续投入使用，本文旨在为智能交通系统的应用提供一定的理论基础，助力于城市智能交通系统的实施水平达到国内先进水平。1.2 国内外现状智能交通方面的研究始于二十世纪五六十年代的欧美发达国家，伴随着工业技术的快速发展，不少国家机动车的保有量飞速增长，随之而来的是城市交通状况不断的恶化，各种交通问题日渐突出，因此很多国家将交通运输发展的重点放在了公共交通行业，众多学者将目光汇聚在智能交通的发展上。在上个世纪七八十年代，许多欧美国家开始将先进的信息技术应用于公交车辆的定位辅助上，采用了包括GPS，GIS在内的先进技术，使公交系统的调度水平迈上一个新的台阶。随后在九十年代初日本的东京都交通规划院开发设计了一套城市公交车综合运输控制系统，即 CTCS系统。与此同时，美国也建立了自己的城市交通信号控制系统 CTSCS，欧洲国家则大力应用卫星导航技术，对城市交通实施了全天候的监控和引导。不少国外学者也利用数学规划方法研究了发车频率。Furth和Wilson1建立了确定总成本，公交车辆运力，车辆载客率的情况的数学模型，该数学模型主要目的是减小乘客等待时间成本，最大化社会效益。Ceder2根据某时段某线路乘客周转量和某时段某站点乘客的到站率提出了四种不同发车频率的决策方案，并和Stern3建立了整数规划的数学模型。Lee-KK-T和Shoufeld.P.M4提出在起点站实行屯车策略，确定优化的行车间隔。Eberlein5提出了实时的公交滞站调度、放车调度、越站调度。Delgado6考虑了增加乘客上车限制的手段的滞站调度。基于信息技术对交通系统的整体化信息管理，有效缓解了城市交通压力，控制了城市交通流量，带来了良好的社会和经济效益，这些技术经验十分值得我国许多城市借鉴参考。与欧美等国相比，我国的智能交通系统的起步较晚，同时，我国还面临着人口密度较大，道路不完善，机动车与非机动车出行量大，距离交通基础设施的建设全面完成还需要相当长的时间等问题。自改革开放以来，我国各大城市在经济建设方面取得较大发展，但公共交通系统的落后极大制约着我国的城市化进程，但随着科学技术的发展和社会进步，智能交通系统的建设已得到国家相关部门的高度重视。1994年，部分学者专家参与了第一届世界智能交通系统大会。1995年中国国家技术监督局交通部门正式批准成立ISO/TC204中国委员会，该委员会把推进中国智能交通系统标准化作为主要任务。在二十世纪九十年代初，我国各大城市均已建立了交通信号控制系统和交通电视监视系统，主要功能就是对路口信号灯进行点、线、面相结合的控制，对路面的交通状况进行实时的监视，并辅之以人工干预。而在九十年代中期，GPS车辆定位系统，交通地理信息系统等技术同样被引入。同时，国内学者对于公交行车计划的编制问题也有不少成果。王顺凤7等人提出确定由发车班数，发车间隔，乘客等待时间，车辆总数组成模型决策变量，基于上述决策变量建立模型求解。张飞舟8提出利用遗传算法和混合遗传算法对车辆调度进行优化。陈鹏9基于BP神经网络建立了车辆运行时间预测模型。赵志军10在求解的过程中则是将蚁群算法和遗传算法相结合应用。1.3 研究（设计）内容本文主要基于智能交通系统的环境对公交车辆运营时刻表应用遗传算法进行优化，主要做了如下工作：（1）研究公交运营实际情况，建立了以公交车辆的发车时刻间隔作为决策变量的数学模型，模型引入多目标优化问题，目的在于使乘客的经济效益和公交公司运营的经济效益达到最优。（2）研究非支配排序遗传算法，结合多目标优化求解，应用改进后的算法，求得优化后的发车间隔。2. 设计方案论证（可行性研究）非支配排序遗传算法是一种优化效果较好的多目标优化遗传算法，相比于其他优化算法，非支配排序遗传算法不限制优化个数，非劣最优解分布均匀。方案如下：1）确定种群规模为n，随机产生n个可行解Xi1in组成初始群体；2）计算赋予个体适应度值fXi，作为个体评价标准；3）设a=1；4）对所有b=1,2,n且ab,比较个体Xa与Xb之间的支配与非支配关系；5）若不存在个体Xb支配Xa，则标记Xa为非支配个体；6）令a=a+1，转到2)，找到所有非支配个体后，算法结束。通过上述方案操作，将会得到种群的第一级非支配层，忽略第一级非支配层中的个体，再循环上述步骤，得到第二级非支配个体，依次循环，种群中所有个体将会分层，赋予同级个体相同虚拟适应度，同时非支配级别越低，其相对虚拟适应度越高，也就是说其个体越优，非支配级别越高，其相对虚拟适应度值越低，在接下来的操作中，相对较优的个体将会被以较高概率优先选入下一代，使得算法迅速收敛于最优区域。同时，为得到均匀分布的Pareto最优解集，引入基于拥挤策略的共享小生境技术。方案如下：1） 设l非支配层上有nl个个体，个体虚拟适应度值为fl，且令a,b=1,2,3nl；2） 对于同一非支配层的个体Xa，Xb，计算两者间欧几里得距离：da,b=l=1LDlXa-Dl(Xb)Dlu-Dld2其中，自变量个数为L，Dlu表示Dl的上界，Dld表示Dl的下界。3） 个体Xa和Xb通过共享函数sda,b表示个体之间的关系：sda,b=1-da,bshare 0 若da,bshare其它其中share为共享半径，其值越大，代表个体间密切度越大，为常数。4） 令b=b+1，如果bnl，转到2）；否则计算个体Xa的小生境数量为:ca=b=1nlsda,b5） 计算个体Xa共享适应度：flXa=flXaca令a=a+1，反复执行，计算每个个体的共享适应度值结合共享小生境技术，种群中的个体即使位于相同非支配集也会被赋予不同虚拟适应度，从而保证了种群多样性，避免优秀个体被淘汰，陷入局部最优的情况，也更好的得到均匀分布的最优解集。但非支配排序算法复杂度较高，缺少精英保留策略，并且共享半径需要根据大量实验和经验提前指定，因此，改进原有算法，增加拥挤度的概念，方案如下：1） 设每个个体拥挤度ai=0；2） 计算每个个体目标函数值并进行非支配排序，排序后，同一层个体计算拥挤度，假定每层中，处于边界的个体的拥挤度为无穷大，即0i=mi=；3） 对于非边界个体，计算公式如下 ：ai=j=1pfja+1-fja-1fja+1表示a+1点的第j个目标函数值。改进后的算法操作步骤如下：1） 设初始种群为G0，确定种群规模为n；2） 对种群进行非支配排序，进行选择，交叉，变异操作，得到子代种群G1,；3） 从G1开始，非支配排序前合并子代与父代种群，使种群规模变为2n，再进行非支配排序，计算非支配层个体拥挤度，并排序；4） 选择非支配序较小，同时拥挤度较大的个体组成子代种群；5） 对子代种群执行交叉；6） 根据子代非支配序ar，计算个体变异率k=e-1ar2，并执行变异操作；7） 判断是否满足结束条件，若不满足则继续执行3）；根据上述方案操作，种群可以通过迭代，较快收敛得到全局最优解，且最优解均匀分布，算法复杂度相对较低。3.开发环境及系统实现MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。MATLAB是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。功能强大的工具箱是MATLAB的一大特色。这些工具箱都是由该领域内学术水平很高的专家编写的，所以用户无需编写自己学科范围内的基础程序，而直接进行高，精，尖的研究。本课题采用matlab编写程序，验证算法的正确性与可行性。4.论文进度计划及预期效果 表4.1. 毕业设计进度表序号起止日期任务提交的阶段成果115.3.3-15.3.11调研、了解课题背景调研报告215.3.12-15.3.22确定具体的研究题目开题报告315.3.23-15.4.04课题分析及建模数学模型415.4.05-15.4.20算法应用算法方案515.4.21-15.4.30算法仿真设计仿真程序615.5.1-15.5.04调试及验证调整完整系统715.5.05-15.5.20撰写论文论文全文815.5.21-答辩准备答辩答辩材料5 参考文献 1 北京市公交总公司.运营调度管理M，北京：中国劳动出版社，1994,142-229.2 Ceder A. Bus Frequency Determination: Using Passenger Count DataJ, Transportation Research,1984,18(5):439-453.3 Ceder A. Stem H I. Optimal Transit Timetables for a Fixed Vehicle FleetC, Proceedings of the 10th International Symposium on Transportation and Traffic Theory, 1984, 331-355.4 Lee KK T, Shoufeld P M. Real-time dispatching control for coordinated operation in transit terminalsJ, Transportation Research, 1994, 14(33): 3-9. 5 Eberlein X.J. Real-time control strategies in transit operations: Models and analysisD. Civil Engineering, MIT, U.S.A.1995. 6 Delgado F, Munoz J C, Giesen R. How much can holding and/or limiting boarding improve transit performance?J. Transportation Research Part B: