基于遗传算法的列车运行图编制优化研究博士论文罗瑜导师何大可教授.ppt

博 士 学 位 论 文 选 题 报 告报 告 人 罗 瑜 指导教师 何 大 可 教 授 专 业 交通信息工程及控制 研究方向 并行计算理论及其应用基于遗传算法的列车运行图编制优化研究1可编辑2024/5/8周三内容提要课题的研究意义、国内外现状分析课题研究目标、研究内容、拟解决的关键问题拟采取的研究方法、技术路线、及可行性研究课题的创新性计划安排、预期进展和预期成果完成论文所具备的条件2可编辑2024/5/8周三内容提要列车运行图是用来表示列车在铁路区间运行及在车站到发或通过时刻的技术文件，它规定各次列车占用区间的程序，列车在每个车站的到达和出发（或通过）时刻，列车在区间的运行时间，列车在车站的停站时间以及机车交路、列车重量和长度等，它是铁路运输工作中受多种因素制约、技术性强的综合性计划，是全路组织列车运行的基础。3可编辑2024/5/8周三课题的研究意义计算机编制列车运行图是铁路信息化的重要组成部分，国内外在该方面已进行大量的研究，取得了很大的成果，为本课题的研究提供了理论和实践基础。目前，计算机编制列车运行图在国内已取得一定进展，并得到大规模应用，但其智能化程度急需进一步提高，以提高编图效率和质量，为铁路适应市场提供强有力的技术支撑手段。这使得本课题的研究具有了实用意义。4可编辑2024/5/8周三国外研究现状国外研究利用计算机编制列车运行图，一般始于上个世纪五十年代后期。前苏联从上世纪五十年代后期开始，对计算机编制列车运行图进行了大量的研究工作。前苏联采用的基础算法是模拟人工方法，以实用为原则，不追求运行图最优，应用计算机代替人工繁琐的运算工作，在计算机给定方案的基础上进行人工调整直至满意。日本从1960年开始研究，日本主要采用人机对话的方式。近年来日本采用人工智能与专家系统相结合的方式。美国从上世纪五十年代后期对计算机编图进行研究，主要的技术路线是计算机模拟和逻辑判断。5可编辑2024/5/8周三国外研究现状与此同时，国外也开展了建立数学模型开发相应算法，实现运行图局部甚至全局优化的研究。目前比较典型的就是数学规划模型和人工智能。6可编辑2024/5/8周三国内研究现状我国研究计算机编图始于上世纪六十年代初期，主要是在研究所和大学中展开。铁路科学院运输所首先在1962年开始进行列车运行图的研究，此阶段主要是按照人工编图的过程和特点制定机器编图的规则和步骤，铺画单线非平行运行图。七十年代以后进行了全路直通客车方案的研究。哈尔滨铁路局、兰州铁道学院、北方交大等科研院所从上世纪七十年代初开始对计算机编图进行研究，取得了很大的成绩。西南交通大学从上世纪八十年代开始了计算机编图的研究。1993年投入实际运用的“复线列车运行图计算机系统”，在我国第一次实现了计算机编制枢纽列车运行图和复线干线上的方向列车运行图。7可编辑2024/5/8周三国内外研究现状国内外计算机编图方法数学规划沿用数学逻辑推断，对于结构明确、能定量描述的系统，可以求得最优解。而列车运行图编制由于定量、定性因素错综复杂，不能完全由数学模型描述清楚。并且由于所建的数学模型过于庞大，鉴于目前计算机速度、容量以及算法的局限，用纯数学模型解出满意实用的列车运行图还难以做到。人工智能（专家系统）总结了编图人员的实践工作经验，是人类逻辑思维的直接描述。这种方法接近实际，其结果明确了当，但由于专家系统过于局限于规则，对于列车运行图编制这样的大规模组合问题在建立知识库和搜索知识方面存在较大困难。模拟方法对人类逻辑思维与数学方法进行结合，可以同时考虑定量与定性因素。其质量与效果在很大程度上取决于判别规则和执行过程设计的合理性与全面性。8可编辑2024/5/8周三第二部分课题的研究意义、国内外现状分析课题研究目标、研究内容、拟解决的关键问题拟采取的研究方法、技术路线、及可行性研究课题的创新性计划安排、预期进展和预期成果完成论文所具备的条件9可编辑2024/5/8周三课题研究目标从列车运行的需求出发，系统化描述保证列车安全、快捷运行的各种必要条件，提出相应的数学模型，并在此基础上采用遗传算法对此模型展开优化研究，以达到实用目标。10可编辑2024/5/8周三课题研究内容列车运行图的数学模型列车运行图是全路与运输有关各单位的综合工作计划。因此，在编制运行图过程中，要从全局出发，统筹兼顾，正确处理列车运行与技术站作业之间的关系、列车运行与机车交路之间的关系、运输与施工之间的关系等等。根据对以上关系的研究制定列车运行图的编制原则。根据列车的运行规律和运行图的编制原则，对列车运行图进行数学建模。在本课题中，结合遗传算法的特点，构造利于遗传算法优化的数学模型。约束区间列车运行时间约束、列车停站时分约束、列车间隔时间约束、同向列车越行条件约束、车站间隔时间约束、列车单独占用联弧约束、列车禁停约束、敌对径路约束、机车乘务组工作时间约束、天窗时间约束、列车到发时刻特殊要求约束、车站到发线约束目标函数总旅行时间最小技术站列车接续时间最小机车总消耗时间最小11可编辑2024/5/8周三课题研究内容遗传算法构造染色体以及遗传算子（选择、杂交、变异）。针对编图中不同的优化问题，例如列车始发点分配、推线计算、运行图标准控制检查、越行会车点处理、列车接续、到发线安排、摘挂小运转方案等问题，要针对具体的问题设计染色体及遗传算子，以使优化结果、优化速度达到最佳。12可编辑2024/5/8周三课题研究内容(3)列车运行图计算机自动编制将运行图问题分解为若干个子问题，分步骤、分阶段求解。列车运行图初始布点列车初始布点就是计算线路交会点（基点）的列车始铺到发点方案，均衡合理的确定列车在基点站的到发点方案，是计算机编制列车运行图的重要的一环，直接影响着列车运行图的编制质量与实际使用价值，而且与机车交路、车站设备能力、车站作业进度和车流来源有关。确定列车初始布点处理直通列车接续始发列车车次分配132024/5/8 周三14可编辑2024/5/8周三课题研究内容(4)列车运行图计算机自动编制路网分解为子线路列车运行图的编制在通常情况下简化为旅行时间最小的单目标规划问题。由于目前尚未有较好的求解大规模时刻表规划的优化算法，因此本课题采取通过局部的多次优化来实现全局优化。而在铁路的不同线路上运行的列车，在线路交会点有间隔约束、进路约束、到发线约束以及接续时间约束等，在线路的其他地方则几乎不发生任何约束。因此，路网存在分解为子线路的可能性。选择基点(主要干线交会点、有大量列车产生或消失的编组站以及局间分界口等)将路网分解为相对独立的子线路。15可编辑2024/5/8周三课题研究内容(5)列车运行图计算机自动编制对子线路求解在生成列车始铺到发点方案以及路网分解的基础上，对相对独立的子线路分别建模，采用优化算法求解各个子线路。机车周转图编制由于机车应用质量的优劣直接影响到列车运行图的编制质量，需要同步编制机车周转图。最有代表性的是把机车周转图归结为二维分配问题，把到达机车看作资源，把出发机车看成活动。机车周转图的铺画，实质上是把资源分配给活动。目前的算法有采用解分配模型的特殊匈牙利算法，通过网络变换把二维分配问题模型转化为网络流模型，用求网络最小费用最大流方法求解。实际上，牵引机车的机车分配与应用方式，与列车的性质、种类和运行方向等因素有关。因此在建立机车周转图优化模型时，必须按牵引机车类型及运用方式等特点进行分类。寻求最优机车周转图，就是使机车不牵引列车时在站停留时间最短。16可编辑2024/5/8周三拟解决的关键问题提出满足列车运行图编制规则的数学模型。列车运行图编制的自动化。17可编辑2024/5/8周三第三部分课题的研究意义、国内外现状分析课题研究目标、研究内容、拟解决的关键问题拟采取的研究方法、技术路线、及可行性研究课题的创新性计划安排、预期进展和预期成果完成论文所具备的条件18可编辑2024/5/8周三拟采取的研究方法以列车行驶规律和运行图编制原则为基础，构造利于遗传算法优化的运行图模型，将运行图问题分解为若干个子问题分步骤、分阶段求解，实现列车运行图编制的自动化。19可编辑2024/5/8周三技术路线研究过程可以借鉴国内外在列车运行图计算机自动编制发展中的研究成果，同时对比其它方法，如数学规划；人工智能；吸取上述方法中的有益思想并结合遗传算法特点提出自己的见解。具体的技术路线为是对现有的编图技术加以改进或者扩展，改造数学模型，使之适合采用遗传算法进行优化20可编辑2024/5/8周三可行性研究可行性分析本课题从提高列车运行图自动编制的智能化出发，着眼于实用原则，得到了西南交通大学博士创新基金的支持；本课题工作将在西南交通大学交通信息技术研究所展开，该所具有多位计算机自动编图领域的专家，工作结果将在国家高性能计算中心(成都)验证，因此本项目研究有较强的核心技术支撑和实现手段。21可编辑2024/5/8周三课题的创新性在全面分析列车运行需求的基础上提出一种与优化方法相结合的数学模型；在列车运行图计算机自动编图中的关键问题中引入遗传算法，提出新的优化方案，提高列车运行图计算机编制的智能化。22可编辑2024/5/8周三第五部分课题的研究意义、国内外现状分析课题研究目标、研究内容、拟解决的关键问题拟采取的研究方法、技术路线、及可行性研究课题的创新性计划安排、预期进展和预期成果完成论文所具备的条件23可编辑2024/5/8周三计划进度与预期进展20032003年年1212月月 20042004年年3 3月月国内外资料的收集，了解最新动态20042004年年4 4月月 20042004年年6 6月月分析列车运行规律及运行图编制原则，建立运行图的数学模型20042004年年7 7月月 20042004年年1111月月将遗传算法应用于计算机编制列车运行图，编写相应算法，并由软件模拟20042004年年1212月月对采用遗传算法的编图进行性能分析20052005年年1 1月月 20052005年年3 3月月撰写毕业论文并答辩24可编辑2024/5/8周三预期成果在国内外高水平期刊杂志、会议上发表论文的目标是达到或争取超过学校要求的论文数量和质量。25可编辑2024/5/8周三谢谢各位专家莅临指导！262024/5/8 周三27