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