（交通运输规划与管理专业论文）计算机编制编组站阶段计划的模型和算法的研究.pdf

北京交通大学硕士研究生论文 y8 7 9 2 8 1 中文摘要 阶段计划是铁路编组站作业计划的核心部分 一个好的阶段计划 应该反映出本阶段的工作重点 并按照列车编组计划的要求 把车流 及时编成各种列车 保证本阶段的所有列车都正点发车 传统手工编 制方法的弊端日趋明显 随着我国铁路现代化建设步伐的加快 作为 铁路调度指挥自动化重要内容之一的编组站阶段计划自动化编制的 研究势在必行 本文在前人研究成果的基础上 针对编组站阶段计划编制的重点 和难点 从我国铁路编组站实际情况出发 利用人工智能的最新研究 成果 a g e n t 及多a g e n t 方法 结合启发式搜索及离散事件动态系统 对编组站阶段计划编制内容进行详细的分析 并对阶段计划编制系统 的进行了初步探讨 论文主要内容如下 1 对目前铁路编组站阶段计划编制的内容和流程进行了详细分 析 指定编组站阶段计划编制问题的难点 论述了编组站阶段计划编 制方法研究的紧迫性 并给出编组站阶段计划形式化描述 2 基于人工智能最新成果一a g e m 及多a g e n t 方法的编组站阶段 计划编制方法研究中 讨论了系统的基本结构 功能及实现方法 并 完成了各主要a g c n t 予系统的设计与实现 3 在完成编组站阶段计划编制系统构建的基础上 提出了阶段 计划主要问题的模型和求解算法 在基于前人研究成果上 重点研究 了 车流接续 的启发式搜索模型与算法 对原有的车流接续模型与 算法进行了改进 利用离散事件动态系统的j o b s h o d 生产调度方法 构建了到发线运用计划的模型与算法 并从空间和时间两个方面构建 了疏解冲突模型与算法 在调车机车运用计划的研究中 在求得以 调 北京交通大学硕士研究生论文 车机车作业时间最小 为目标的单目标较优解的基础上 结合 调车 机车走行距离最短 的且标 构建了双目标加权求和的目标函数 求 出满足权重约束的双目标最优解 4 结合实际科研项目 本文对编组站阶段计划编制系统进行了 研究开发 系统能够对简单的原始资料进行整理 分析和设计 并在 人工干预的条件下最终得到阶段计划表 技术作业图表及车流信息等 一系列重要资辩 关键词 编组站阶段计划 多a g e n t 方法 启发式搜索 j o b s h o p 调度问题 2 北京交通太堂填 研嚣生论文 曼掣k h k 型 p 1l ul l 下l 上 f 鬟h 塞摹葛t 器号i 瓠醒 址 囊i 1 刍强j d l s h 簧r l i n 皿 涟0 址1 1 n n 篓荇j 1 学1 ja g 葬篁墨蔷y 写醚j u d 鄹疆一爿罐h 蓑 1 1 一塾莲野 0 i 叫竿j p h i 譬 m 请书 峙x 0 譬小 x 北京交通大学硕士研究生论文 l 绪论 1 1 问题的提出 铁路系统是一个庞大而复杂的系统 铁路运输生产过程是在全 国纵横交错的铁路网上进行的 从路网的结构看 它是由 点 f 车 站 枢纽 和 线 线路 两个子系统组成 在进行运输生产时 必须协调好这两个子系统的关系 随着人工智能在各个领域的应 用 实现铁路系统自动化也已经逐步展开 以便使常规铁路系统 扩展功能 降低成本 提高安全性 最终实现铁路自动化 目前 采用计算机编制列车运行图已经在许多路局展开 大多数路局已 经能完全利用计算机编制运行图 摆脱了纸和笔 运用计算机辅 助编制运行图代替原始的手工画图 实现了 线 的自动化 而 点 的自动化还远远没有达到计算机辅助编制的程度 铁路调度工作在铁路运输组织中占有重要的地位 编组站是 铁路调度最为集中 在铁路运输各主要方面占有极其重要地位的 场所 编组站的作业计划是组织各车问 工种协调生产 充分发 挥技术设备能力的前提与保证 是指挥车站各项作业有序进行的 神经中枢 作业计划编制的好坏直接关系到铁路运输生产的效率 和编组站作业管理的质量 现行由人工编制的编组站作业计划包 括日班计划 阶段计划和调车作业计划三个组成部分 从管理层 次上看 铁路编组站同班计划是对次日 班 车站作业的总体轮廓安 排 它规定了车站一班的到发列车接续的各种作业指标 阶段计 划是车站作业计划的核心部分 它既是实现日班计划的分阶段部 署 又是编制调车作业计划的主要依据 对于车站意义重大 一 个高质量的阶段计划应该反映本阶段的工作重点 并按照编组计 北京交通大学硕士研究生论文 划的要求 把车流及时编成各种列车 保证本输段的所有出发列 车都能正点发车 并能合理的安排列车解体和编组顺序以及调车 机车的作业内容 阶段计划质量的高低对于车站设备综合有效利 用 对于全面高效地完成运输生产任务起着至关重要的作用 近年来铁路编组站已经逐步建立起了车站管理信息系统和全 路的预确报系统 现车系统 这在很大程度上方便了现场作业 提高了编组站运输作业的效率和现代化水平 不过 目前铁路上 已经建立起的确报系统 现车系统等只是管理信息系统 只能为 调度人员提供信息 自动化程度只停留在现车管理这样的数据处 理层次 缺乏辅助决策功能 并不能为调度人员编制计划时的决 策提供支持 而调度员在编制计划时 不仅要进行大量的繁琐 重复的数据处理工作 还要考虑众多的相关因素 劳动强度很大 加之 由于受到达车流经常变动的影响 站调的计划编制与调整 工作非常繁琐紧张 造成 计划跟不上变化 而由此引发的计划 编制不及时 计划质量不高 计划调整困难等长期困扰计划编制 的主要问题 问题如下 1 编制速度慢 技术图表需手工绘制 信息收集 实时决策 方面可靠性差 劳动强度大等 2 手工方式对车站阶段计划图表的调整工作只能在小范围内 进行 难以从全局保证 机动性差 3 站调尽管经验丰富 但是仍然存在疏忽和考虑不周 以及 个人之间的不同处理方式和专业技能差别 必然造成编出来的阶 段计划缺乏科学的保障 由此可见 通过计算机技术和人工智能方法的结合 形成立 足于现场作业实际的阶段计划计算机编制方法是提高目前铁路编 北京交通大学硕士研究生论文 组站阶段计划编制水平的重要途径 1 2 国内外研究现状 铁路编组站阶段计划是编组站某一阶段d 5 小时1 作业组织的 依据 它超前于现场的实际作业 同时又因现场的实际情况的变 动而必须调整 解决编组站在既定配置下的优化组织方式一直是 铁路工作者潜心研究的重要课题 从国外的情况来看 上世纪六 十年代初 美国 加拿大 日本等发达国家率先将计算机在铁路 上推广应用 陆续完成的运营管理自动化系统有 货车运用和管 理 空车分配和管理 机车车辆维修计划和管理 货物运输管理 集装箱运输管理 货物运输核算 行车调度指挥等系统 到六十 年代末 一些欧美国家把注意力由铁路运营单向管理自动化转移 到综合管理自动化 八十年代以来 以计算机为核心的调度指挥 自动化建设得到积极推进 这其中包括编组站阶段计划的计算机 辅助编制系统 但是 他们把精力都用到硬件设备的改造上 加 上多年来运输能力比较富裕 对于采取运输组织措旌挖潜革新 提高计划质量却没有给予充分重视 同时他们在日常工作中面临 的情况和国内的情况大相径庭 其作业量都比较少 作业方法单 一 考虑到国内编组站作业量比较大 作业比较复杂 各项作业 之间的协调要求强烈 对路网通过能力影响比较大 因而必须进 一步研究适合中国国情的自动化系统 在五十年代系统学习原苏联铁路行车组织方式的基础上 形 成了组织型的行车模式 但由于我国铁路日常运输工作的复杂性 和时变性 只是国外在运能富裕的条件下建立起来的 以基本计 划管理为主的 觌划型的行车调度自动化系统难以满足我国的实 际需要 编制计划工作一直靠手工操作 丽在编组站计算机编制 北京交通大学硕士研究生论文 阶段计划豹理论研究开始比较晚 应用计算机等工具和现代信息 处理理论的研究只是指从8 0 年代起开始有人涉及 阶段计划的编制主要解决三个相互联系的问题 即 本阶段 列车出发计划 调车机车运用计划和到发线运用计划 在做阶段 计划时 中心任务是尽可能保证出发列车的正点 在此基础上 再考虑其它目标 如设备 到发线 调车机车等 的合理利用 尽 量减少不应有的等待 但是阶段计划编制问题涉及因素众多 要 用一种实际可解的确定性模型进行整体优化是不可能的 即便建 立相应的数学模型 也往往由于参数选取的不确定性和现场作业 瞬息万变的不稳定性 使求出适用的最优解成为不可能 许多学 者都对阶段计划的某个关键问题进行了研究 文献f 7 运用组合数 学原理 针对如何确定出发列车的编组内容和车流来源 即 配 流 问题 构建方案树 采用最大可能剩余量作为方案控制树的 生长 利用回溯算法搜索有利方案 众多学者则采用分步优化的 思想 从研究编组站阶段计划的几个关键问题入手 分析其实际 问题的特点 提出对其优化的简单可行的模型及算法 从而实现 整个阶段计划编制工作自动化 文献f 1 0 把编组站配流问题看作是 一类特殊的资源分配问题 通过一定的技术处理 将配流问题转 化为求总代价最小的运输问题 用表上作业法求解编组站配流问 题 文献f 1 1 j 以压缩车辆在站停留时间为目标 给出了给定列车满 轴车数条件下 编组站出发列车运行线选择和出发车流确定的网 络流优化模型及算法 文献 1 2 把到发线运用看成固定工件排序问 题 通过分析列车占用到发线的特性 建立到发线运用阀题的排 序模型 并通过分析列车占用到发线时间区间集合的特点 运用 构造方法绘出到发线运用问题的实用算法 文献 1 6 考虑解编调机 4 北京交通大学硕士研究生论文 断调适的满意解才是实用的 计划的编翻灵活性很强 很多时候 都需要车站调度运用个人经验对实际情况作出决策 这些经验难 以用数学模型进行描述 3 算法求解的时间规模漆肄叠裂肄出巍掣氧箭j 赢m 掣 掣惦 裁并皎卵诮醌雏前 籼匿烈犁褂妒时i 酬驯耙可沥灌注停舞雨产轻 郏嘲般翻刚到翱翅幽竖 蠹耋杼甫酌船话堑素拦瘸弭 斤豫淀噶 们噬逡嗾彬腮甜则 同时阶段计划的编制始终是围绕按列车运行图发车这一中心 来进行的 考虑因素众多 涉及的部门及信息量大 在具体编制 时车站调度员与各车场值班员 调车区长以电话联系 并进行人 脑记忆 加工后进行会址 具体的处理过程如下 1 收集资料 1 班计划规定的各项任务 时间要求及本阶段重点工作 2 各到达列车的到达时间及编组内容 实绩 3 1 各车场现车情况 4 调机作业进度 实绩 5 其他情况 细 机车整备 扣修 站内施工等资料 2 推算本阶段开始时的现在车 并在工作中随时进行推算 3 填画到开列车运行线使用计划和到达列车编组内容 4 安排到发场各到发线运用计划 同时编制调机运用计划 5 书面下达阶段计划 6 交接班 推算填写交接班时各股道占用情况 并绘制技术 作业图表 阶段计划的下达是自上而下的 其下达过程及信息数据流图 如下 北京交通大学硕士研究生论文 法 3 编组站阶段计划自动化编制理论和方法及计算机编制系统 的实现 使调度人员在计划执行前就能从计算机系统中获得多个 编制方案 这一方面从根本上改变了目前调度人员劳动强度大 劳动生产率低的现状 另一方面可以提高计划编制的质量 提高 铁路运输能力的利用率 获得更大的社会效益和经济效益 4 编组站阶段计划计算机编制方法中的实时调整方法 顺应 了现场工作中车流变动频繁 信息不完备的实际情况 能够较好 地满足调度员实际工作的需要 体现铁路工作中的 超前 意识 1 5 论文的研究特点及结构安排 1 5 1 论文的研究特点 1 阶段计划编制的实质就是如何利用车站调车机车 到发线等 设备资源来完成阶段列车出发计划 计划的优化编制涉及到列车 车辆的多个作业环节 是个比较复杂的系统决策过程 本文首次 将多a g e n t 方法用于编组站阶段计划计算机编制系统的构建中 用 人工智能的方法来分析编组站阶段计划计算机编制的现状 考查 计划相关的各主要因素 从系统 整体的层次上把握计划编制问 题的本质 明确编组站阶段计划编制问题中的研究对象 并给出 计划的形式化表述 将人工智能中的知识表示与知识处理的思想 引入到系统中 弥补了单纯依靠模型技术与数据技术的缺陷 重 点解决算法的规模化问题和时效性问题 提高结果的实用性 2 铁路编组站作为一个生产单位 应该追求最好的经济效益和 社会效益 编组站阶段计划的编制是一个复杂的大系统 计划的 优化目标不应仅仅局限于单个目标 本文在分析前人成就豹基础 北京交通大学硕士研究生论文 2 编组站阶段计划编制理论分析 2 1 阶段计划编制内容和流程分析 2 1 1 阶段计划编制内容分析 阶段计划的内容为包括到达列车的车次 到达时分 占用殷道 编组内容和解体起止时间 出发列车的车次 出发时分 占用股 道 编组内容及车流来源 编组起止时间 各货物作业地点装卸 车的取送时间 取道辆数及挂运车次 检修车 加冰车等的取送 时间和车数等 不难看出 阶段计划是班计划的进一步具体化 是一个班各阶段工作的具体安排 由车站调度员根据该阶段工作 开始前的具体情况编制 编制阶段计划时所依据的原始资料有 1 本阶段到达列车的车次 时分及编组内容 确报 2 本阶段应编组的出发列车车次 时分及机车来源 3 本除段内货场和专用线能装卸完毕的车辆 重车分去向 空 车分车种 情况 4 调车场内现车情况 待解车列的现车情况 5 调车机车在本阶段内是否需进行整备作业以及上一阶段作 业结束时分等情况 6 本阶段开始时到发线占用情况 7 上级布置的重点事项 上述资料中 列车到发车次及时分可能与班计划中的不完全 相同 这是因为由于各种实际情况 调度所调整列车运行和调整 开车计划等因素所造成的 2 1 2 阶段计划的编制流程及方法分折 北京交通大学硕士研究生论文 尽管阶段计划的内容比较多 但总的来说 编制时主要解决 的是相互联系的三个问题 即确定出发列车的车流来源 调车机 车的运用以及到发线的运用 三者分别对应于作业执行阶段自勺作 业对象 作业主体和作业地点 但又通过作业时间这一因素贯穿 为一体 从实际内容上来说 阶段计划的车流来源的确定主要解 决两个问题 相关车辆的状态确定和具体作业时间的确定 所谓 相关车辆的状态 是指日班计划中根据列车到达计划 现在车推 算 中转和货物作业车总数等假定的车流接续中作为车流来源的 车辆在现阶段的实际情况 包括所在地点 是否正在作业 正在 进行什么作业 何时能够结束现有作业 进而确定这些车辆是否 依然满足原定的车流接续条件 为后续的作业时间的确定提供决 策依据 具体作业时间的确定就是指进一步缩小日班计划中对车 流接续相关作业的大致时间安排 制定更为精确的作业时间范围 作为后续调车作业计划的编制的依据 因而 阶段计划中的车流 接续问题不必另行设计一套模型和求解方法 而只需根据现阶段 掌握的车辆信息对日班计划已经得出的出发列车编组内容进行必 要的验证和调整 并列出编组 取送作业的起讫时间 即对原有 模型中的车流推算部分和求解算法中的接续时间约束部分进行修 正 调车机车是编组站的主要生产力 编组站各项技术作业的执 行归根到底都可以等同于一定约束条件下对调机资源的占用 调 机运用的好坏直接关系到作业计划的执行效果和车站的生产效 率 在阶段计划编制阶段对调机运用的研究主要是如何确定在阶 段计划的作用时间内各类技术作业对调机资源的占用优先级 从 而决定调机在作业过程中对它们韵响应次序 属于多约束条件下 北京交通大学硕士研究生论文 图2 1阶段计划下达过程 1 4 北京变通太望坝士研究生丽文 雾i 萋爨囊确摧苦鬟弱躺赣 北京交通大学硕士研究生论文 2 到达确报 3 站内存车情况 4 调机工作状态 编制调车作业计划既要统筹考虑 又要采用最有效的调车方 法 以便为以后的调车作业创造有利条件 做到最大限度地解体 照顾编组 以达到节省调车钩数 缩短调车行程 减轻调动重量 压缩调车时间 保证调车安全 2 2 2 调车作业计翅编制流程及方法分析 调车作业计划分为解体 编组 取送等调车作业计划 所谓 解体调车就是将解体列车中的车辆 按其去向分解到编组场各指 定线路的调车作业 在指定解体调车作业计划时 要注意安排好 股道分配方案 要根据现车 现场实际情况 按 死固定 活应 用 的原则去使用线路 解体时应尽最大可能照顾编组作业 为 编组作业创造方便条件 在解体作业遇到困难时 要依靠工作人 员根据现场实际情况结合自己的管理经验灵活掌握 妥善处理 编组调车就是按列车的种类 用途和运输性质 根据 技规 列 车编组计划和列车运行图所规定的编挂条件 车组重量 长度 将车辆或车组选编和连挂成车列的调车作业 在制定编组调车计 划时 要了解许编组列车的车流分布 内容组成 以及股道占用 情况 若没有足够的车流来源 要考虑如何选择编挂车流或解体 到达列车的顺序 以完成班计划 阶段计划规定的出发列车任务 所谓取送调车则是向装卸作业地点 取送货物作业车或整修地点 取送检修车的调车作业 取送调车作业计划耐较为灵活的 工作 人员根据班计划 阶段计划 取送车的分布 实际现场情况综合 考虑从哪儿来送到哪儿去 主要取决于人的指导和安排 北京交通大学硕士研究生论文 调车作业是一项比较复杂而涉及面又广的工作 它具有以下 特点 1 作业地点涉及面广 从编组场到出发场 从编组线到货物 线 专用线 从牵出线到驼峰 从站内到站外 调车工作几乎涉 及整个铁路线 2 作业对象多种多样 被调动的有机车 客车和货车 货车 中又有各种类型的车辆 3 作业人员工种多 参与调车作业的人员有车站调度员 车 站值班员 调车区长 调车长 连接员等工种 4 作业组织的比较复杂 全站由站调 调车区由调车区长或 驼峰区长 调车组由调车长等领导组织的调车工作 5 作业方法灵活多变 按作业目的有解体 编组 取送 调 车等 在牵出线上按操作技术有推送 溜放调车等 6 影响调车作业效率的因素比较多 调车人员的技术水平 思想情况 车场道岔曲线 坡度 气候情况 线路的干扰度等 它们对调车作业效率有不同程度的影响 调车作业计划时调车工作的执行依据 站调或调车区长组织 领导调车工作都是通过作业计划来实现的 调车作业计划编制的 原则是 1 最大可能的实现解体照顾编组 使各项作业密切配合 2 考虑是否需要分步作业 确定合理的 开口 位置 3 有预先的掌握车流动态 做好股道线路灵活安排 4 考虑设各条件 综合运用各种调车作业方法 5 根据列车到发情况 车流接续要求 确定合理的作业顺序 6 调车工作和调车作业人员豹安全条件 北京交通大学硕士研究生论文 调车作业计划制定与执行过程如下阉所示 图2 4 调车作业计划的甫 定与执行过程 2 3 阶段计划图表的主要组成部分和填记要求 阶段计划图表的形式 铁路有基本的规范形式 多年来各个 编组站依照本站情况 制定了适合本站的图表 所以各个站的技 术图表并不尽相同 但主体部分是一样的 阶段计划图表的基本 格式为 1 到达列车 出发列车栏 填萄到达列车及出发列车运行线 北京交通大学硕十研究生论文 2 到达场 出发场 交换场栏 填画列车占用到发线韵股道 顺序及起j e 时间 3 编组内容栏 1 1 去向分栏 填记各方向到达列车的编组内容及其顺序 空车分栏 填记本站空车的到达情况 3 1 作业车分栏 填记货场 专用线地去送车辆情况 4 到达分栏 填记到达车总数 4 驼峰调机 峰尾调机运用实际栏 填画调车机车运用情况 占用驼峰的顺序及起止时间 非生产时间等 5 各统计表栏 包括阶段中时 阶段停时 小站出车 作业 车取送 始发违编 欠轴列车 始发晚点 运休 加开列车 到 发列车 解编列车 调车机一班工作量 6 安全生产情况和站长审阅意见栏 记本阶段完了时 对本 阶段作业情况的评价 根据 调规 站细 的规定 对绘制作业图表的一些具体 要求如下 1 阶段计划用黑线铺画 实际完成情况用红 蓝线纪录 到 最后 计划将被实绩代替 2 阶段计划开始时的现在车数 应填写上阶段的结存数 各 到发场各股道等处的结存车应填写车数 3 到达列车 在列车到发栏内 填画列车到达运行线和到达 时刻 并注明车次 在到达时刻出用垂直线引入到发场栏的接车 股道 列车到发线的时间 用横线的长短表示 并注明列车技术 检查完了时间 解体列车 由解体作业开始时用垂直线将车列由 到发线栏引入驼峰栏 直到解体作业完了 并注明起止时分 表 2 0 北京交通大学硕士研究生论文 示该列车占用驻峰豹时间 车列解体完了 车辆即分解于调车场 各股道之内 用垂直线将其由驼峰栏引入调车场 并在垂线右侧 注明各股道豹累计结存车数 即解体列车甩入该股道的车数加该 股道原有车数 如解体列车未使该股道车辆有所增减 则将原有 车数重填一次 4 出发列车 中转出发列车 可用引线由到发线直接引至列 车出发栏 并填画出发列车运行线 注明车次和开车时间 自编 出发列车对集结够规定辆数 牵引定数 的调车场内的车辆 从编组 作业开始就将其圈定 并在圆圈右侧记明编组后剩余车数 编组 完了 引入列车出发线进行出发作业 5 车辆取送 按取送时间填记车辆的转移 2 4 阶段计划内容的形式化描述 计算机编制编组站阶段计划 首先要建立模型 所谓模型的 形式化表述 就是将模型中涉及的概念 约束等进行具体的符号 化说明 从而为后续的模型推导提供依据 阶段计划的主要内容是确定出发列车的车流来源 调车机车 的运用以及到发线的运用 调车作业计划主要是对车列进行解体 编组和取送作业 当在某一时刻t 进行某项作业时 我们用以下的 定义来描述此刻编组站内各种资源的状态 定义1 某时刻f 编组站的状态可以表示成为四元组s s7 r d p f 其中 r 表示 前预计到达的到达列车集合 r 7i r 的到达 北京交通大学硕士研究生论文 时间 r 墨 d 表示f 后预计离开车站的出发列车集合 d d i d 的 到达时间 2 p 表示股道 驼峰等一切供车辆停留的技术设备的状态 集合 一般的p k u h u g k 为各股道的状态集合 h 为孵 峰的状态集合 g 为货场状态集合 对于任何p p 可表示为三 元组 p n p w 其中n 表示车辆停留地点的技术设备名 p 表示设备被占用或空闲 p w 表示占用的车辆数 4 表示该时刻调机 技检组等作业者的状态集合 一般 的 爿一lue 为调机状态集合 e 为技检组状态集合 对于 任何4 4 可表示为二元组爿 4 爿 其中4 为名称 爿 为 空 忙状态 定义2 在编组站中的执行的任意一项技术作业j 可以四元 组描述 即 j 丁 p 4 d 其中 丁 表示该作业的执行时间 r r f 5 r f 6 分别表示 作业的起止时间 p 表示作业的地点 p p 口 表示作业的执行者 口 一 北京交通大学硕士研究生论文 o 表示作业的对象 即车辆或列车 同时 j 也可定义为集合s s 为车站状态集合 上的二元关系 乳 5 1 其中 5 0 表示技术作业执行前编组站的状态 5 表示技术作业执行后编组站的状态 于是有 5 t i 2 5 计算机编制编组站阶段计划实质的分析 2 5 1 计算机编制编组站阶段计划所面牺韵困难 编组站作业计划计算机编制的研究从2 0 世纪踟年代起开始 经过2 0 年众多学者的努力 研究成果已比较丰富 但对于阶段计 划研究的突破性成果不多 理论应用于实践方面的成功范例也很 少 这主要是因为该领域尚且存在下述的一些技术和理论难点尚 待解决 1 编组站阶段计划的数学描述及模型 研究编组站阶段计划 的编制问题 首先遇到的问题是如何清晰地描述该研究需要解决 的问题范围 初始条件 目标体系和约束条件等 很多学者都把 对阶段计划的研究分解成三个关键问题 到发线运用计划 调机 运用计划和出发列车来源 对每个问题建立相应的模型 进行局 部最优化 但由于编组站阶段计划编制本身涉及到的因素众多 各变量问的关联度和影响程度复杂难辨 例如 列车密集到达时 要与列检协商 当列车运载危险货物时要与货捡协商 列检有时 北京交通火学硕士研究生论文 为了完成检修任务进行新车的甩挂等 总之实际情况很难用精确 的数学模型来描述 实现阶段计划的完全自动化编制是困难的 在具体的研究过程中 会出现各学者根辗研究的出发点 研究的 理论背景 以及研究的意义的差异而见仁见智 2 问题的求解和问题的最优解 当定义了问题的模型及约束 条件后 接下来的问题就是求解与优化 而由于编组站阶段计划 编制输入多目标 多约束的问题 在问题的求解中某一个解实际 是一个与技术作业内容和顺序 对象自身属性有关的集合 因此 其解的优化是一个组合优化的问题 现有的研究模型在处理该问 题时一般都处理为n p 完全问题 于是如何设计可靠 有效的求解 算法 在时问准许的情况下寻找最优解就成为一个难题 3 动态多问题决策 铁路编组站阶段作业的规范以及编组站 阶段计划编制过程本身都决定了编组站阶段计划编制问题是一个 动态多阶段决策问题 每循环递进一次 都需要根据当时的情况 进行决策 进而调整系统内的运行状况和输出结果的内容 因此 这一动态决策过程中的每一次决策都是对最终目标的一次逼近或 修正 从计划作用的角度看 阶段计划是对列车的到解编发整体 的安排 使车机电辆的协调 不是单纯追求某一环节的最优 因 此在编制过程中 通过各种模型抓住关键工作 保证重点作业根 据现场情况 不断提出新的优化准则 逐步使系统在时间 资源 上达到综合优化 如何进行决策 才能使总体决策效果更优 进 而实现更大范围内的作业优化就成为了一个难点 4 编组站阶段计划编制领域的专业知识获取和知识表示比较 困难 从国内编组站阶段计划编制计算机研究的进程来看 研究 学者很早就认识到由传统的数学方法转向计算机技术和人工智能 北京交通大学硕士研究生论文 理论是解决婀题舶主要途径 而人工智能方法的应用瓶颈之一就 是知识的获取和表示 编组站经验丰富的站调往往具有大量的专 业知识 如柯使计算机理解和掌握这些专业知识 如何有效地表 示这些知识都是技术上的难点 这一点从研究初期 学者集中采 用不同的理论 方法进行该领域研究 而后由于缺乏知识实时更 新和对突发意外的灵活应变等固有缺陷导致研究陷入困境的情况 中可见一般 阶段计划的最终结果必然是建立连贯一致的各子模 型集成 同时纳入更多的人的因素 达到人机互相激发 优势互 补 共同寻求问题解 但是如何实现机器的自学习功能以及人机 结合是人工智能研究领域的难题 2 5 2 计算机编制编组站阶段计划的特点 1 编制人员必须熟悉并遵照 技规 站细 等各种技术指 标要求 同时需要实时掌握各种资源数据 灵活运用所掌握的经 验知识和调度模式 2 数据的实时性 编组站作业系统是个实时系统 车流资源 随时间变化 在某一时刻可能同时有到达车辆 检修完毕车辆及 装卸车辆等 计划应随着现场实际情况变动 调车机车在进行不 同作业时 技术规范对其有严格的时问限制 计划要考虑执行时 间 3 编制人员所处理的车流资源信息比较复杂 求解规模大 从全局的角度考虑来看 编制阶段计划所需数据很大 求解问题 规模大 大型编组站有时一个阶段有几十列有调中转列车 编组 方向有数十个 再考虑车种别等 在迸行车流推算的时候 除了 出发列车及车流资源要满足编组方向 满轴和时间上的要求外 北京交通犬学顼 研究生论文 翅辈亘些1 乍些笺穰楚鬟旺 荔鹫叁碡垡湔撩 虱誊隆却爵5 玎j f 幅嫡矗嚣羽 簇亳 谕磁垛萄灌毽瘟讶谖 焉冀l l 竽目m 粤夏掣再现笮 必打卧到窟墓累铲卿鋈露 搦打i 戮p 拍拥匕e 干蔓 壤乏遣愫麒臻羽勰 尉妻而型壶甬篓蹦蹦蹦凿瑙蚕套蜀酬咎盛鞍羹董 i 瓢弱 畦譬剐蚪囊翌l i 稍蚀弩 北京交通大学硕士研究生论文 功能强大的单a g e n t 系统 由多个结构和性能较为简单的姆m 组成 的一个多a g e m 系统 通过多个a g e n t 之问的协作 使整个系统具有 丰富的知识和强大的功能 所谓多a g c t 系统是指由多个a g c n t 组成的一个较为松散的多 a g 助t 联邦 这些a g 蛐t 成员之间相互协同 相互服务 共同完成一 个任务 各个a g e n t 成员的活动是自制的和独立的 其自身的目标和 行为不受其他a g e n t 成员的限制 它通过竞争或磋商等手段协调和解 决各个成员a g c n t 的目标和行为之间的矛盾和冲突 多a g c n t 系统的 数据和资源是分散的 每个a g 哪对于所要完成的任务拥有不全面的 信息或能力 无法全局地控制系统 任务的执行和计算是异步的 通过多a g c n t 的协商 实现一个多a g e n t 群体共同求解问题的高 层观点和相关信息 从而实现一个多a g e n t 群体共同求解问题的高层 观点和相关信息 并实现各个成员a 窘e n t 在开放动态的环境中更好地 协同工作 3 2 1 多a g e n t 系统的分类 3 2 1 1 集中式多a g e n t 系统简介 集中式多a g e n t 系统至少拥有一个管理服务机构 以某种方式负 责对该系统所有a g e n t 成员的行为 协作 任务分配以及共享资源等 提供统一的协调和管理服务 同时 管理服务机构或协调服务机构与 各个a g e n t 成员具有一定的管理与被管理或协调与被协调的关系 该结构与传统的过程或对象有本质的区别 首先 各个a g 锄l 成 员都是自制的 能够主动接受或者承担不很明确的任务或意图 协助 管理机构和其他a g e n t 成员实现各自的和整体的目标 其完成任务的 形式具有一定的灵活性和适应性 其次 管理服务机构与各个a g e n t 北京交通大学硕士研究生论文 成员的管理通常采用一种较为宽松的协商或协调的管理形式 丽不是 简单的行政命令方式 各个a g 哪成员在一定程度上 有权根据自身 的能力和所处的环境状态接受或拒绝接受管理服务机构委托的任务 而管理服务机构所下达的目标既可以是明确的任务或指示 也可以是 任务的轮廓或意图 而传统的过程 子程序和函数等只能被动地接受 主控程序在特定的时机所分配的明确的任务 是一种调用和被调用的 关系 主控程序对过程 子程序和函数拥有绝对的控制权 3 2 1 2 分布式多a g e t 系统简介 对于分布式多a g c n t 系统 其内部a g e t 成员之间是平等关系 彼此间相互提供服务 各个a 窘融t 成员问的任务的划分与分配 共享 资源的分配与管理 冲突的协调 行为的一致性等 在遵循可能的社 会规则和共享资源的管理策略的基础上 通过某种机制 由各个a g c t 通过彼此的相互作用与对于所处环境的感知 运用其自身的知识进行 合理地判断和推理 自己做出决策来实现 分布式多衄e n t 系统 并不排除存在某些衄c t 成员拥有对其他 成员的行为 意图进行监控 裁决与进行局部协调等 它与集中式结 构中的管理服务机构是有所区别的 对大范围的和拥有众多的a g e n t 成员的系统而言 通常是借助于中介服务机构保存和维护各a g e n t 成 员的能力 位置和状态等信息 各a 鐾e n t 成员可通过中介服务机构发布各自的能力 寻找适合的 合作伙伴等等 中介服务机构可以是该系统内部的一个特殊成员提供 专门服务 也可以是系统外部的公共中介服务机构为大范围众多的 a g e n t 成员共同提供服务 分布式结构中的中介服务机构不同于集中 式的管理服务机构 它对于a g e m 成员只提供服务 不提供管理 不 北京交通大学硕士研究生论文 对工件的假定包括 1 从列车至4 达占用进路开始起 列车 车捌 即可被加工 或者 也可假定为 对不同类型的工件j i 需要有一个固定的相应准备时间t i 经过准备时间后即可对列车 车列 开始加工 2 每一个操作限定为不能由多于一条到发线来进行加工 3 每一个操作一旦开始 直到完成为止 不会被另外的操作所中 断 4 每列列车 车列 按照加工工艺的规定 以指定的次序在到发 线上加工 5 每种列车 车列 之间不存在加工上的优先权 即对到发线而言 每类列车 车列珈工的重要程度被认为是等同的 6 对每个操作均容许等待 也就是说 如果前一个操作还未完成 即仍在进行 那么后续的操作将需要等待 7 对每种列车 车列 j i 都规定相应的一个计划完成时间d i 通 常称为交货期 一般而言 计划完成时间既可以直接按用户订单要求 来指定 也可由生产者为了合理调度生产而自行指定 通常把计划完 成时间d i 规定为 加工准备时间r i 加上 工件加工时间p i 的k 倍 即有 d i r i k 4 p i 3 1 对机器的假定包括 1 在从加工过程开始的计划时间内 所有m 条到发线均为有效 的 即所有到发线从一开始就处于可加工状态 且在计划时间内不会 出现损坏和需要修理的情况 北京交通大学硕士研究生论文 2 生产线中 只有一条同一类型的到发线 不同到发线之间彼此 独立 3 在同一时刻 每条到发线只能从事一个操作 对加工时间的假定包括 1 对每个操作 其作业时阀是事前给出的 且在整个计划时间内 保持为常数 2 加工时阔包括了设置时问 即包括了列车 车列 在到发线之间 的作业和等待时间 3 3 可舾h o p 调度问题的描述 1 图论形式 设图g v c ud 为生产线加工过程的一个描述 其中 v 为定点 集合 对应操作的集合 c 为有向弧集合 称为合取弧集合 对应表 示由工艺路线所规定的工件的各道工序的顺序关系 它反映了同一工 件的两个操作之间的次序约束 d 为无向弧集合 称为析取弧集合 对应表示操作共享同一台机器的互斥关系 从图论的角度而言 所谓 j o 卜s h o p 调度问题 就是对表征生产线加工过程的图g 代c ud 为各个无向弧选择 个相应的方向 以使规定的一个性能指标最优 在图论描述中 选择一个调度 就等同于 选择一个图 g v c u d 在此调度下 图g 中的弧集合d 就是对图 g c u d 中的无向弧分别取定为某个方向下所形成的一个有向弧 集合 实质上 对无向弧的这个有向化过程 对应于在加工过程中对 每台机器确定其操作问的先后顺序 如图 北京交通大学硕士研究生论文 图3 3 生产线的图描述 图3 4 对生产线调度后的图描述 其中 一 f 步7 表示对应于操作的顶点 每个顶点都用三个数字 i j l 来表 示其特性 i 表示操作所属于的列车 车列 为j i j 表示此操作在其所 属列车 车列 的所有操作中的编号 k 表示操作所需要利用的到发线 m k 从图中可以看出 图3 4 中的有向弧代替了图3 3 中的无向弧 等价于对同一条到发线上进行的两个操作规定了先后顺序 也就是确 定了相应的一个调度方案 即调度问题的一个解 北京交通大学硕士研究生论文 针对性能指标 先引入有关豹一些符号 0 i i 表示工件j 在机器m j 上的操作 咒表示工件j 在机器m j 上的加工作业时间 s t 表示第t 步的前一道工序执行时刻的所有未被执行的操作的 集合 o i i 表示s 1 中的操作q 对应的 工件j 到达机器j i f j 的时伺 0 i i 表示s t 中的操作o i j 可完成最早时间 且有 q q 岛 计算过程可按如下的步骤来进行 s t 印1 令q 1 哦 l m 为操作集合 s 1 为所有工作第 一道工序的集合 s t c p 2 令t 1 s t 印3 令o 为满足 o i i l i n c 0 i i 10 i i s t 的操作 m 为 进行操作0 4 的机器 从集合 o i s t l r o o 中确定一个 操作0 i s t e p 4 生成q t 1 iq t o 也即在q t 中除去 0 由s t 除去操作o i m 并添加工件j 的下道工序 来生成集合s t 1 s t 印5 令q t 1 q t s 1 1 s t s t e p 6 若q t 为非空集 则进入下一步 若q 1 为空集 则计算 停止 s t e p 7 令t t 1 并返回s t e p 3 3 4 启发式搜索 北京交通大学硕士研究生论文 当所给定的问题用状态空间表示时 问题求解过程可归结为状态 空间的搜索 即从当前待扩展的状态节点 扩展到下一个状态节点 下一个待扩展状态节点的选择有两种方式 一是不考虑给定问题所具 有的特定知识 系统根据事先确定好的某种固定的排序选择待扩展的 节点 宽度优先搜索和深度优先搜索都属于这种搜索方法 另一种是 考虑问题领域可应用的知识 动态地选择待扩展节点 这就是启发式 搜索方法 启发式搜索总是选择那些被认为是 最有希望 到达目标状态地 的节点作为待扩展的节点 为此 用评价函数 对节点n 的 有希望 程度进行评价 0 可表示为 o 一g 伽 o o 表示从初始状态s 经节点n 到某一目标节点t 的最佳路径的 费用 o g o 矗 o 的 一个估计 g o 是从s 到n 的最佳费用g o 的一个估计 占 的一个明显的选 择是取到目前状态节点已经搜索的从s 到n 的各条路径中的最佳费用 0 是对未搜索的路径的最佳费用 o 的一个估计 它的选取主要 依赖于具体问题领域的启发式知识 被称为是启发函数 如果g o 为目前状态节点已经搜索的从s 到n 的各条路径中的最 佳费用 且 0 对于所有节点都有 0 sj i l 用这样的启发式评价 函数构造的算法成为彳 算法 已经证明 爿 算法一定能够找到一条 到达目标状态的最佳路径 在求解复杂问题时 通常只追求满意解 4 0 北京交通大学硕士研究生论文 而不强调最优解 因为满足 n s o 的矗o 在复杂问题中往往是狠 难得到的 这也是越问题求解的一个特点 启发式知识的获得需要智慧和经验 在文献 4 6 中 通过分析已有 的一些实例中的启发式知识后指出 用简化的模型提供的信息作为启 发式信息是获得启发式信息的一种重要途径 4 1 北京交通大学硕士研究生论文 4 基于多a g e n t 的编组站阶段计划编制系统的研究 4 1 基于多a 岛e n t 的编组站阶段计划编制系统结构的提出 通过前面对人工智能方法的介绍 我们可以认识到任何问题的求 解能力不仅取决于它使用的形式化体系和搜索的模型 而且取决于它 所拥有的知识 包括知识的结构和这些知识如何获取 如何有效的表 示和使用等问题 作为人工智能方法之一的多a g e n t 理论本身并非某种 新型的特定专业问题的理论模型和求解方法 而是对计算机相关问题 研究方式本身的一次突破和革新 相对于传统的基于流程和对象的思 考方式 多a g e n t 技术的研究思路更加侧重于对人类社会组织模式和人 类思维方式本身的模拟和再现 正是a g e n t 理论更加贴近自然进化和人 类社会发展的特点 使其可以更为直接地满足人们在处理对自然界或 人类社会的计算机模拟问题时对理论工具的特性要求 从而使研究者 可以更加自然地完成对已有结构的复制 模拟 以及改造 在第二章中 我们分析了阶段计划编制作业内容及流程 阶段计划 的编制与车站作业动态 车站资源使用状态及站场设备状态息息相关 我们可以将阶段计划编制系统从车站的 硬件 和 软件 方面进行 研究 硬件方面包括车流 调机 信号系统 通讯系统 不同车场的 作业设备和辅助作业的设施等 软件方面包括车站作业内容 方式 流程以及车站人员组织结构 从软件方面来讲 通过对铁路现行的作 业体系和站场结构的观察 我们可以看到铁路编组站基本上是根据不 同作业群的分工来进行作业地点的划分 常见的是将编组站分为到达 场 驼峰 调车场 出发场四个主要的车场 外加与整个编组站分离 的货场 不同的编组站的差异仅在于上述车场的个数 空间排列关系 以及部分车场的有无 简繁等 北京交通大学硕士研究生论文 现阶段的a g t 理论研究可以说主要进行的是一个新兴理论体系 的各类原则 特征 规范 标准的制定工作 接踵而来的就将是在各 个不同的子领域内基于a g c n t 架构的应用系统的飞速发展 将a g c l l t 理论与铁路编组站的作业体系和站场结构放到一起分析 我们就会很 直观地感到以模拟有机体a g 衄l 结构和以模拟生命活动形态为初衷的 多a g 蛆t 结构与铁路编组站这样的组织是多么的暗合 本文就是从 a g e n t 理论的角度出发 重新分析阶段计划编制系统中所涉及的问题 进而依照多a g e n t 方法的系统构造模式 构建一个类似j 二 有机生命体 的具有自适应 自学习特点的计算机辅助决策系统 4 2 基于多囱蛩豳t 编组站阶段计划编制系统结构概述 编制阶段计划主要是确定到发线运用 出发车流来源 调车机车 运用计划等问题 这些问题的研究与车站作业是分离不开的 根据前 面对铁路编组站一般结构的分析 从a g e n t 功能设计的角度出发 我们 从 硬件 和 软件 两个方面进行阶段计划编制系统的构造 可以 构造 资源a g e t 和 作业姆n t 资源a g e n t 包括 车流螂 到发线a g e n t 调机a g e n t 和 信号a g e n t 车流a g e n t 主要 负责车流来源的确定和车流接续 到发线a g e n t 主要负责到发线 的使用 调机a g c n t 和 信号a g e n t 是两个反应式a g e n t 调机 a g e t 负责对其他a g e n t 状态对调机状态查询的回应 调机状态信息 的发布 调度调机运行命令的执行以及调机异常信息的报警 从而确 定调机运用计划 信号 a g e n t 负责对外部环境和内部各a g e n t 的信 号请求予以响应 并实时监控这个编组站的信号系统的运转 发布信 号信息的和报告信号异常状态 作业a g e n t 包括 到达a g e n t 解 体a g e n t 编组a g e n t 出发姆n t 和 货场a g e n t 它们分别 北京交通大学硕士研究生论文 图4 1 编组站阶段计划编制系统结构 4 3 作业知识库 对阶段计划编制系统进行过整体概述之后 下一步就要进行各个 部分的详细设计了 作业知识库介绍了是阶段计划编制系统的基础 与作业计划密切相关但又不归属于某个具体a g e n t 作业知识库的内容 存储在调度a g e t 的知识库内 可以由各个a g c n t 通过通信接口对其内 容进行查询和调用 4 3 1 编组站不同车辆 列车 作业种类库 4 j 1 l 技术站作业对象分析 技术站的技术作业内容取决于列车和车流的种类 一般而言 技术 站办理的货物列车种类有 北京交通大学硕十研究生论文 图4 2 货物列车种类 在技术站办理的货车有 1 无调中转车 随无改编中转列车或部分改编中转列车到达 在该站进行到发技 术作业后 又随原列车继续运行的货车 2 有调中转车 随到达解体列车或部分改编中转列车到达 在该技术站经过一系 列改编作业后 再随白编始发列车或另一列部分改编中转列车继续运 行的货车 3 货物作业车 或称本站作业车 随到达解体列车或部分改编中转列车到达 在车站进行货物作业 卸车或装车 的货车 4 3 1 2 编组站主要技术作业过程分析 编组站典型的技术作业内容主要体现在有调中转车和货物作业车 的技术作业过程中 卜面重点介绍它们的作业过程 北京交通大学硕士研究生论文 作鞋罐猕律生鼙缓耐闫 捌扶住量 i 悼作生 叶 囊嬉过程 砌扬砌翮 囊啦 l 一 出赛作韭 l 莲辏时分 一 f 图4 0 有调中转车技术作业过程图 有调中转车的一般作业过程如图7 所示 1 到达