（系统工程专业论文）面向网络列车运行计划调整的分层递阶智能混杂优化技术研究.pdf

北京交通大学硕士学位论文中文摘要 中文摘要 摘要：高速铁路客运专线容量大、速度快、行程时间短、可靠性高，己成为改善 铁路运输繁忙状况的重要战略举措，它在服务定位、车站设置以及运营特征上与 传统铁路存在着一定差别，因此客运专线运行计划调整方法设计应具备独有理念 和思路。 本文分析了我国高速铁路客运专线的运营特征，从指导思想、调整原则、调 整方法三个方面总结了我国客运专线运行计划调整的策略；以传统运行计划调整 模型为基础，提出了基于大系统分层递阶结构的改进模型，以列车群权重系数为 控制参数，把复杂的多变量非线性模型分成四层，从下往上分别为列车层、列车 群层、区段层、路网层，其中列车层和列车群层为控制层，区段层和路网层为协 调层；在优化过程中，引入了模式识别机制，加快了算法的寻优速度。在控制参 数的选取上，结合客运专线运行计划调整策略，引入人机交互机制。 基于以上理论研究进行了算例设计和模拟系统开发，采用基于整数编码的遗 传算法，对客运专线运行计划调整优化模型进行了求解，算例结果表明，基于大 系统分层递阶结构的改进模型不仅切实可行，而且求解速度快，具有良好的实时 性。 关键词：客运专线运行调整；大系统理论；分层递阶结构；智能混杂优化；模式 匹配；遗传算法 分类号：【u 4 9 1 ；u 4 9 1 1 + 2 ；u 4 9 1 1 + 3 ；u 4 9 1 1 + 7 】 北京交通大学硕十学位论文 a b s t r a c t a b s t r a c t ：h i g h - s p e e dr a i l w a yp a s s e n g e rd e d i c a t e dl i n ew h o s eh a sl a r g ec a p a c i t y 、 h i 曲s p e e d 、s h o r tt r a v e lt i m ea n dh i g hr e l i a b i l i t yh a sb e c o m ea l li m p o r t a n ts t r a t e g i ct o c h a n g et h eb u s ys i t u a t i o no fr a i l w a yt r a n s p o r t a t i o n ，i ti sd i f f e r e n tf r o mt r a d i t i o n a l r a i l w a yo nt h es e r v i c el o c a t i o n 、s t a t i o ns e t t i n ga n do p e r a t i n gc h a r a c t e r i s t i c s ，s od e s i g no f p a s s e n g e rd e d i c a t e dl i n eo p e r a t i o na d j u s t m e n tm e t h o dn e e du n i q u ec o n c e p t sa n d i d e a s i nt h i sd i s s e r t a t i o n ，w ei n v e s t i g a t e di n t ot h eo p e r a t i n gc h a r a c t e r i s t i c so fc h i n e s e l l i g h s p e e dr a i l w a yp a s s e n g e rd e d i c a t e dl i n e ，s u m m a r ya d j u s t m e n ts t r a t e g i co f c h i n e s e h i g h - s p e e dr a i l w a yp a s s e n g e rd e d i c a t e dl i n ef r o mg u i d i n gi d e o l o g y 、a d j u s t m e n t d i s c i p l i n ea n da d j u s t m e n tm e t h o d b a s e do nt h et r a d i t i o n a la d j u s t m e n tm o d e lo ft r a i n o p e r a t i o np l a n ，w ep r o p o s et h em o d e lb a s e do nt h eh i e r a r c h i c a ll a r g es c a l es y s t e m t h e o r y , m a k et h ei n d e xw e i g h to ft r a i ng r o u pt ob et h ec o n t r o lp a r a m e t e r , t h ec o m p l e x m u l t i v a r i a b l en o n l i n e a rm o d e li sd i v i d e di n t of o u rl a y e rw h i c ha r et r a i nl a y e r 、t r a i n g r o u pl a y e r ，s e c t i o nl a y e ra n dn e t w o r kl a y e r , o fw h i c ht r a i nl a y e r 、t r a i ng r o u pl a y e r b e l o n gt ot h ec o n t r o ll a y e ra n ds e c t i o nl a y e ra n dn e t w o r kl a y e rb e l o n gt oc o o r d i n a t i o n l a y e r ；i nt h ep r o c e s so fo p t i m i z a t i o n , w ea d o p tt h ep a t t e r nr e c o g n i t i o nm e c h a n i s mt o a c c e l e r a t et h eo p t i m i z a t i o na l g o r i t h m i nt h ep r o c e s so fc o n t r o lp a r a m e t e rs e l e c t i o n ，w e a d o p tm e c h a n i s mo fh u m a n - c o m p u t e ri n t e r a c t i o nc o m b i n ew i mt h es t r a t e g i co f p a s s e n g e rd e d i c a t e dl i n eo p e r a t i o na d j u s t m e n t an u m e r i c a le x a m p l ef o l l o w st o t e s tt h ea l g o r i t h mw ed e s i g n e da n db a s e do nt h e a b o v et h e o r e t i c a ls t u d yas i m u l a t i o ns y s t e mw a sd e v e l o p e dt ot e s tt h em o d e l sa n dt h e a l g o r i t h m sw ep r o p o s e d u s i n gt h ei n t e g e rc o d i n gg e n e t i ca l g o r i t h mt os o l v et h e p a s s e n g e rd e d i c a t e dl i n eo p e r a t i o na d j u s t m e n to p t i m i z em o d e l t h er e s u l ti n d i c a t en l a t t h em o d e lb a s e do nh i e r a r c h i c a ll a r g es c a l es y s t e mt h e o r yi sf e a s i b l ea n dt h es o l u t i o n a l g o r i t h mi sf a s ta n dg o o da tr e a l t i m e k e y w o r d s ：p a s s e n g e rd e d i c a t e dr a i l w a yl i n eo p e r a t i o na d j u s t m e n t ；t h e o r yo f l a r g es c a l es y s t e m ：h i e r a r c h i c a ls t r u c t u r e ；i n t e l l i g e n th y b r i do p t i m i z a t i o n ；s c h e m a m a t c h i n g ：p a t t e r nm a t c h i n g ：g e n e t i ca l g o r i t h m c l a s sn o ： u 4 9 1 ；u 4 9 1 1 + 2 ；u 4 9 1 1 + 3 ；u 4 9 1 1 + 7 】 北京交通大学硕士学位论文图表目录 图表目录 图1 全文技术路线图1 3 图2 大系统分层递阶结构图2 6 图3 整数编码遗传算法编码格式图3 0 图4 遗传算法交叉算子示意图3 l 图5 基于遗传算法的调整优化算法流程图3 3 图6 模式匹配法寻算法初值流程图3 5 图7 优化模型求解流程图3 6 图8 模拟系统界面3 9 表1 模拟系统车站属性表3 9 表2 模拟系统车辆速度属性表3 9 图9 模拟系统调整前列车运行计划4 0 图1 0 模拟系统调整前列车运行图4 1 图n 模拟系统调整后列车运行计划4 1 图1 2 模拟系统调整后列车运行图4 2 表3 模拟系统调整结果对照表4 2 北京交通大学硕士学位论文 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果、除了文中特别加以标注和致谢之处外、论文中不包含其他人已经发表或 撰写过的研究成果、也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 虢f 虱岛期：址p 夕年7 剃日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 同 签字日期：讼嗣年易月2 ，日 导师签名：交勇 签字日期：印降月 致谢 本论文是在我的导师秦勇教授( 北京交通大学交通运输学院交通信息工程系) 的悉心指导下完成的。这两年中，秦老师在科研、工作、学习和生活中，给予了 我无私的帮助，秦老师治学严谨、学识渊博、勇于探索、诲人不倦的学者风范， 为我在学习、科研和生活中树立了良好的榜样；课题组徐杰老师( 北京交通大学 交通运输学院交通信息工程系) 严把质量关，对本论文的研究思路、研究方法提 出了宝贵的意见和建议。在此，我向两位老师表示衷心感谢。 在论文撰写期间，课题组孟学雷博士、王莉博士对该论文的研究思路和技术 路线进行了指导，谢正媛、陈彩霞、孙彩虹硕士在论文的方法研究、资料收集等 方面给予了我积极帮助，在此向他们表达我真挚的感激。 感谢轨道交通控制与安全国家重点实验室的董宏辉、蔡国强、王艳辉、王卓 等诸位老师在实验室学习工作期间的关心；感谢实验室的周慧娟博士、张尊栋博 士在生活和学习上给予我无私的支持和帮助。 另外感谢我的父母多年来为我的求学生涯所做出的巨大牺牲，他们的理解和 支持使我能够在学校专心完成学业；感谢北京交通大学交通运输学院系统科学研 究所的张敖木翰博士在生活上给予我的照顾和支持。 最后衷心感谢在百忙之中抽出宝贵时间对本论文进行评审，并提出宝贵意见 的专家和学者们。 北京交通大学硕士学位论文绪论 1 绪论 1 1研究背景 客运专线的运输组织将采取由“高、中速混跑”向“全高速 过渡的模式， 因而在高速铁路运营初期将有如下特点： 1 ) 客流量大，行车密度高。以津沪线为例，预计近期京沪高速铁路区段开行的 最大列车对数为1 4 0 对左右，其中高速列车约占8 0 ，中速列车约占2 0 。考虑 维修天窗设置的需要，高速线平均每小时双向开行8 对列车，同时考虑节假日增 开临时客车和运行调整的需要，则高速线单位时间内需要的开行列车对数进一步 增加，可达1 0 对以上。 2 ) 高、中速列车速差大。因近期跨线客流采用中速列车输送，且高、中速列车 速差高达1 0 0k m h 以上，线路能力受到限制，同时在行车过程中，会自然产生 中速列车待避高速列车的情况，加大了运营管理和运行调整的难度。 3 ) 跨线中速列车在与高速线衔接的既有线路上运行晚点概率较大。根据铁路部 门对既有线路旅客列车晚点的情况统计，京沪沿线五大车站旅客列车平均晚点概 率为3 6 5 ，平均晚点时间为1 9 3m i n ，这一现象虽然在高速铁路开通后会有所改 善，但仍会增大跨线中速列车上高速线前的晚点概率，从而影响高速线正常行车。 4 ) 高速铁路列车运行图无法构成闭合的运行图。由于高速铁路养护维修的特殊 需要，其维修天窗时间一般应设置在4h 以上，且维修天窗时间必须连续设置，从 而造成了高速铁路列车运行图拥有长时间断开的时间带，无法像既有铁路那样构 成闭合的运行图。 沿繁忙干线修建的高速铁路，除实现旅客运输现代化的目标外，还有为既有 线扩能的目的。要尽可能地分担既有线客流，使既有线腾出更多的能力完成r 益 增长的货运量。在保证高速列车准点、快速运行的前提下，可以充分利用客运专 线的剩余能力，安排中速列车上线，穿插运行。由高速线始发的跨线中速列车在 高速线上的运行，将会有较高的准时性，但是对由衔接线始发的跨线中速列车， 在进入高速线之前的正点率却不能有过于乐观的估计。当中速列车进入高速线晚 点时，在列车运行调整中一般应以高速列车为优先列车，组织中速列车进行避让 或者推迟上线时间，以保证高速列车的运行质量。但是这样极易造成中速列车增 加被越行次数、延长晚点时间的不良后果。中速列车在既有线上运行时，具有最 北京交通大学硕士学位论文绪论 高的列车等级，可以保证良好的列车旅行速度；当在客运专线上运行时成为了最 低等级的列车，调整时如果一味地避让、增晚，势必造成其旅行速度的大大降低， 给中速列车旅客的出行带来不便。从运营经验和行车组织的便利性分析，高速线 本线列车的运行正点相对易于保证，高速线路的行车秩序主要取决于跨高速线运 行的列车在既有路网的运行情况，这是实施运行调整的关键。 因此，在常规铁路运行计划调整技术的基础上，从整个路网的角度出发，开 展对高速客运专线运行计划调整方法的研究，具有较大的理论价值和广泛的应用 前景，对于建立高速客运专线运输组织体系，完善与深化铁路运输组织的基础理 论，提高运营质量，扩大运能，节约成本，改进铁路运输系统服务水平，增强铁 路旅客运输吸引力，实现铁路运输可持续发展均具有重要的理论和现实意义。 1 2列车运行调整方法研究综述 1 2 1 列车运行调整的必要性 日常运输组织工作中，由于受货流、车流发生变化、线路施工、气候影响、 自然灾害以及行车事故等影响，经常发生列车停运、加开、早点、晚点的情况。 而铁路行车部门是由多部门、多工种参加联合作业的，一个环节出问题，就会影 响列车的安全正点。影响列车正常运行的因素主要来自于以下方面：【1 1 1 2 1 1 3 】 1 ) 自然方面：包括自然灾害以及天气异常等因素，比如洪水，山崩等不可抗拒 的自然灾害，以及大风、大雾等对司机了望信号造成影响时而需要列车放慢速度 运行。 2 ) 运输设备状态和能力方面：主要有线路故障、机车和车辆故障等原因。有些 车站、区间或者分界口能力紧张，必须适当调整列车运行计划才能完成任务。 3 ) 铁路自身作业组织方面：列车在车站作业时间延长，既有作业方面的原因， 也可能有司乘人员作业时问的原因。 4 ) 列车运行计划方面：制订列车运行计划时如果来源信息不准确，就会造成实 际指挥中无法再按原计划执行。 5 ) 领导的临时要求和变更等方面。 若发生上述情况，常常会影响列车的正常运行，这些影响主要体现在： 1 ) 引起部分列车晚点，包括始发晚点和运行晚点，这是最经常发生的情况。 2 北京交通大学硕士学位论文绪论 2 ) 部分列车机车交路或乘务组换班时间接续不上。 3 ) 该列车所包含车流和前方站的编组车流接续不上。 4 ) 旅客列车的晚点引起在前方站换乘其它列车时间连接不上，从而侵害旅客的 利益。 其中影响1 ) 是造成列车调整的主要原因，而后三种情况往往都伴随着列车晚 点情况的发生。如果晚点列车数少且晚点幅度小，晚点列车并不影响其它列车的 正常运行，则可以通过预留在基本运行图中的“撒点时间加快晚点列车运行， 并加快在车站作业进度来尽可能让晚点列车恢复正点。但如果列车运行计划衔接 比较紧密，晚点列车就会影响到后行列车的正常运行，形成晚点传播。此时需要 重新制订列车运行调整计划，使这种晚点所造成的损失最小。 1 2 2 列车调整的措施 目前，对列车运行状况调整的主要措施有：【1 】【3 】 4 】 1 ) 增加列车的停车站。 2 ) 延长列车在停车站的停车时分。 如果列车运行晚点，制订调整计划时所采取的主要措施有： 1 ) 选择合理的会让站、越行站，加速放行列车。 2 ) 组织列车进行快速、平行作业，缩短列车在站作业时间。 3 ) 充分利用列车运行的最大允许速度，缩短列车区间运行时分。 4 ) 合理组织摘挂列车，加速摘挂列车的运行。 5 ) 其它方法：如组织反方向行车，组织列车合并运行等。这些方法现在已经很 少采用 1 2 3 列车运行调整模型 1 ) 基于时间的调整模型 a 正点率高的目标函数模型。如文献【5 】【6 】 b 总停站时间、总晚点时间最少的目标函数模型。如文献【7 】【8 】 北京交通大学硕士学位论文绪论 c 总乘客候车时间、换乘时间最少。如文献 9 】 2 ) 基于乘客的调整模型 a 乘客满意度的目标模型 b 晚点惩罚、换乘失败惩罚、列车晚点惩罚最少的目标模型。如文献 1 0 】 3 _ ) 基于车站的运行调整模型 此种模型主要是以最佳会让站和越行站的选择为调整目标。 1 2 4 列车运行调整问题分类 国外研究的列车运行调整问题可分为两大类：一是列车在各区间内运行时分 不变的列车运行调整问题；二是列车在区间内运行时分可以改变的列车运行调整 问题。列车在区间可改变运行时分，就是列车在区间的运行速度是可以根据需要 变化的自变量，通过调整速度可以减少列车的停站次数和停站时分，以达到节约 列车运行所消耗能源的目的。 1 2 5 列车运行调整的研究方法 1 2 5 1 数学最优化方法 最优化方法是能产生一个精确最优解的方法，其求解的特点是首先构建一个 数学模型，然后利用优化理论进行求解、最优化理论方法中的分枝定界法是最早 用于求解列车运行调整问题的方法，也是使用最多的方法。分枝定晃法是求解组 合优化问题的一个有效的解决方法，由两个基本步骤组成，分别是分枝和定界。 分枝是将一个大问题分成两个或者更多的子问题，然后，再用相同的方法将子问 题分成子问题的子问题等。而定界则是计算每个分枝上子问题的最优值，以此作 为问题的下界。在每次分枝后，对凡是下界超出己知可行解值的结点便不再进一 步分枝，从而不断缩小搜索范围，这个过程一直进行到找出最优解为止。 最优化方法可以分为以下几种算法： 1 ) 分枝定界法。如b s z p i g l 对列车运行调整问题建立了线性规划模型，运用分 枝定界算法来求解问题的最优解，得到最佳的越行和会让地点 1 l 】。又如在文献 1 6 】 中，研究了在干扰情况下产生优化调度的实时列车运行调整方法，把调度问题视 为o 1 混合整数规划问题，首先采用基于产生式系统的方法得到一个次优解，然后 北京交通大学硕士学位论文绪论 以此解为初始上界，利用分枝定界法求出一个优化解。文献【1 2 】研究了以晚点时间 加权总和最小为目标的列车运行调整问题，并采用分枝定界法来解决列车间的冲 突。在文献【1 2 】研究的基础上，文献【1 8 】研究了时刻表评价系统s c a n 1 ，在该系 统中评价算法中也使用分枝定界法来评价时刻表的可行性。文献【1 9 】研究了单线列 车运行调整计划、车站到发线利用与机车交路调整综合协调的优化模型，同样也 使用分枝定界方法来求解列车运行调整计划的优化问题，在计算时采用固定搜索 深度的方法来避免搜索空间过于庞大。 分枝定界法的优点是搜索比较全面，缺点是分枝定界时的下界难以确定。分 枝定界算法在下界精确的情况下是一种精确最优算法，而当下界不十分精确时， 它就是近似算法。己经证明，分枝定界法的计算复杂性是指数型【1 7 】的。列车运行 调整问题属于一类大规模的组合优化问题，其本身的复杂性使其不具有多项式界 的求解算法。虽然对原问题进行化简后可能会找到更为简单的求解算法，但用这 种方法求解实时的列车调整问题仍然显得力不从心。为减少计算时间，必须有选 择地搜索解空间来获得问题的优化解，这就需要使用启发式搜索方法。 2 ) 穷举法。穷举法就是在进行列车运行调整时，将所有可能的调度可能方案全 部列出来，逐一进行评价。如：文献【7 】建立了铁路行车调度决策支持系统，该系 统列举出所有可行的交会、越行方案，然后选择一个让列车总晚点时分最小的方 案。 穷举法虽然能得到最优解，但由于列车调度问题的规模和其组合特性，必须 大量减少搜索空间才可能应用到实际中去。为此又产生了很多缩小搜索空间的算 法。 3 ) 拉各朗日松弛法。文献【2 0 】提出一个自动生成优化运行方案的方法，该方法 是用拉格朗日松弛法( l a g r a n g i a nr e l a x a t i o n ) 将原问题进行分解，然后利用分层方法 求解每个子问题。文献【4 8 】构建了解决铁路双线区段列车运行调整模型，该模型具 有线性目标函数和非线性的约束条件，并使用l a g r a n g e - n e w t o n 方法来求解。 拉格朗日松弛法虽然能够求出最优解，但是，构造符合此算法的模型很困难。 因为实际问题中会考虑很多因素，拉格朗日松弛法很难加以描述。 4 ) 对偶算法。文献【2 l 】研究了单线铁路上列车运行调整的优化问题，对原问题 进行化简后构造了一个变量数上限为( m 1 ) n 的“约束可选择的 线性规划模型， 并借用线性规划中对偶算法的思路来求解。接着文献 2 2 】又为双线铁路区段构建了 优化模型并使用同样的方法求解。 北京交通大学硕士学位论文绪论 对偶算法仍属于线性规划算法，不足之处就是问题的规模较大时，算法复杂 度增加，有一定的局限性。 5 ) 引入启发式算法的整数规划法。文献 9 】研究了将启发式技术引入混合整数 规划的行车调度方法。它是以总体延误费用为目标函数，引入启发式搜索函数形 成的一种加速算法，该方法显著地减少搜索节点的数目，从而大大提高了求解速 度。 此算法结合了整数规划与启发式算法，创造性地将启发式算法中搜索函数引 入到整数规划问题中来，对解决调整问题有一定的理论意义和现实意义。但是启 发式算法中搜索函数的确定工作难度较大。 基于数学规划方法的调度算法的最大优势是，有大量的现有研究成果可以借 鉴，其主要的缺陷有以下四个： 1 ) 系统的实时性难以满足。 2 ) 算法的灵活性较差，这主要体现在数学模型的灵活性和目标函数的灵活性两 个方面。 3 ) 交互性差，作为核心的调度员无法参与求解过程。 4 ) 优秀的调度员经长期实践所得到的十分宝贵的调度知识难于有效运用。 1 2 5 2 人工智能方法 2 0 世纪8 0 年代出现的人工智能( a d 在调度研究中占据重要地位。人工智能适 合于解决有很大搜索空间、专家可以很快找到满意解的那类问题。人工智能方法 的优点在于： 1 ) 可以有效地利用调度员丰富的经验性知识。 2 ) 可以通过人工智能的启发式方法克服列车调度优化中的组合爆炸问题。 3 ) 调度决策从根本上是多目标决策，且有许多目标相互矛盾，有些人工智能方 法并不追求一定目标函数下的最优。 人工智能的方法有如下两种： 1 ) 专家系统。专家系统是人工智能的重要组成部分，也是当前人工智能应用中 最成功的一个领域。专家系统以它产生的巨大经济和社会效益，已扩展到数学、 物理、化学、医学、地质、气象、农业、法律、教育、交通运输等领域，甚至渗 北京交通大学硕士学位论文绪论 透到经济、政治、军事等领域。专家系统是从人工智能、知识工程领域发展起来 的计算机辅助管理系统。它的实质是模拟人类专家解决问题的方式与方法，利用 专家知识解决一般人无法解决的问题。可以说，专家系统是一个( 或一组) 能在某特 定领域内，以人类专家水平去解决该领域中的困难或问题的计算机程序。专家系 统把专家知识用i f t h e n 形式的规则来表示并存放在规则库中，推理机则基于规 则库进行调度。目前大多数专家系统都采用产生式系统的结构来构建产生式系统 ( p r o d u c t i o ns y s t e m ) 是使用类似于文法的规则，对符号串做替换运算。它使用一定 的算法计算由多个简单条件连接起来构成的复合条件，再利用规则库中的知识做 出判断。 日本首次将人工智能技术应用到列车运行调整问题中，并在1 9 8 2 年后年陆续 推出三个不同版本的运行调整专家系统，分别为e s t r a c i 1 6 】， e s t r a c i i 2 3 】，e s t r a c i i i 【2 4 】e s t r a c i 采用启发式规则和分枝定界法相结合 的方法，该版本系统首次在行车指挥中引入知识工程，但是只适应于小型的简单 的路网且只能调整列车运行的顺序。e s t r a c i i 在第一版的基础上加入了调度员 的知识获取功能，系统可以应用有经验调度员的知识改变列车运行顺序或者安排 机车使用。e s t r a c h i 在e s t r a c i i 基础上研究了由四部分构成的问题解决层次 结构，并将基本模拟单元和基于“如果一那么 ( i f - t h e n ) 规则的规则库结合在一 起。问题解决层次结构的四部分分别是局部模拟( p a r t i a ls i m u l a t i o n ) 、基本命令( b a s i c c o n u n a n d ) 、战术知识( t a c t i c a lk n o w l e d g e ) 和战略知识( s t r a t e g i ck n o w l e d g e ) 。局部模 拟和基本命令主要用来在子系统中模拟列车运行，战术知识( t a c t i c a lk n o w l e d g e ) 用 来局部调整，而战略知识用来仿效专家的推理过程。e s t r a c i i i 可以在计算机上 重现有经验调度员的问题求解过程，从而可产生与优秀调度员相类似的调度结果。 文献【2 5 】在编制列车时刻表问题时构建了一种“尝试和错误( t r i a l 一a n d e r r o r ) 过程， 这同样是一种启发式方法，该方法只适合用于双线铁路，并且要求所有的约束都 被严格的定义。继日本之后，许多国家将专家系统技术应用于铁路行车指挥的研 究中。 文献 2 6 2 8 也延续了这种专家系统的方法构建了解决铁路双线区段列车运行 调整问题的专家系统。 此外文献【2 9 】利用计算机模拟的方法构建了具有三级控制结构的动态多级产 生式专家调整系统。最近的研究有文献【3 0 】 31 】。 文献【3 0 】是结合了模糊数学、p e t r i 网的知识构建了专家系统的推理机，取得了 很好的效果。专家系统不仅在列车运行调整中得到应用，在文献 3 2 】中提到的局部 北京交通大学硕士学位论文绪论 调度程序包( 1 0 c a ls c h e d u l e r ) 也是采用启发式的方法疏解列车之间存在的冲突。应用 人工智能的方法，特别是专家系统技术，为调度问题开辟了一条通向应用的途径。 但是，专家系统也有自身许多缺点。首先，由于专家系统的性能水平取决于 其拥有的知识的数量以及函数的质量，所以专家系统需要不断地扩展知识库，但 是这样势必降低其推理效率。其次，现阶段专家系统的针对性太强，规则及知识 不具备普遍性，可维护性和可抑制性也比较差。另外专家系统对新环境的适应性 较差，并且开发的周期比较长，开发的费用较高。 2 ) 多智能体技术。李先进与杨肇夏老师发表的论文基于m a s 的列车运行调整 方法针对列车运行调整问题，运用多智能体系统( m a s ) 技术，将列车运行调整 方案的制定过程抽象为多用户( 列车) 对车站股道和区间线路等共享资源的占用 预约过程，在此基础上建立智能体模型。车站和区间被抽象为资源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 之间的分布式自主决策和相 互协作产生。协作过程中的数据通信采用k q m l 标准设计，并增加消息等级，以 提高通信和系统的效率。仿真实验表明，采用基于m a s 的列车运行调整方法是可 行的。 1 2 5 3 计算机模拟方法 计算机模拟是基于对现实系统的模仿，构建一个对使用者非常透明的模型， 同时它能对不同系统方案进行对比并能预测将来的系统行为。计算机模拟技术有 巨大的优越性，利用它可以求解许多复杂而无法用数学手段解析求解的问题。它 可以预演或再现系统的运动规律及过程，还可以对无法直接进行实验的系统进行 模拟实验研究，从而可节省大量的资源和费用。由于列车运行调整问题具有动 态性和复杂性的特征，计算机模拟方法就成为评价列车运行调整方案和策略有效 性和适用性的常用方法。 近年来，一些学者将模拟分析方法用于列车运行调整计划的优化，取得较好 的效果。为了解决列车运行调整问题，日本国铁技术研究所于1 9 7 7 年专门开发了 新干线列车运行模拟系统s t r a t s 3 4 ( s h i n k a n s e nt r a i nt r a f f i cs i m u l a t i o ns y s t e m ) 用于模拟在发生多种方式的列车运行扰动时各种调整策略的调整效果，实际的调 整过程靠人机对话完成。 文献 3 5 1 将计算机模拟方法引入优化领域，通过模拟方法计算最优方案。 文献 3 6 】将人工智能引入到模拟技术中，建立了一个基于规则的模拟实验系 北京交通大学硕士学位论文绪论 统。随后，同一作者在文献1 3 7 又提出了将知识工程和计划评审技术p e r t ( p r o g r a m e v a l u a t i o na n dr e v i e wt e c h n i q u e ) 技术相结合的调整方法。该方法引进一个运行秩 序可变节点集合，利用一个知识库来推理列车运行秩序改变，在测知运行线之间 出现冲突的同时进行消解。但该方法对调整知识的表示有些简单，只有3 0 条启发 式规则，而且难以处理多个冲突点存在的情况。 文献 3 8 】将现代的p e r t 图模拟和传统的事件驱动模拟这两种方法结合起来， 提出了一个混合模拟方法，这种模拟方法吸收了二者的长处，能更有效也更容易 处理列车间发生的冲突。 文献【3 9 】设计了基于列车冲突解决( i n t e r - t r a i nc o n f l i c t ) 的调整算法，该算法通过 向后看( 1 0 0 k a h e a dm e t h o d ) 的计算机模拟方法来评价列车冲突解决后的情况。 在很多决策支持系统中，离散事件模拟是一个经常使用的方法。离散事件模 拟能有效对复杂、动态、半结构化的问题进行建模和分析，而这些问题是传统运 筹学方法所难以解决的随着离散事件动态系统( d e d s ) 【4 叫4 】理论的发展和应用 领域的扩大，基于d e d s 的行车指挥方法也应运而生，并取得了显著进展。 文献 6 】将列车运行调整过程视为一个离散事件动态过程，将列车运行调整系 统描述为d e d s 系统，这是对列车运行物理状态过程的一种代数描述，由此建立 系统变化的状态转移方程来解决列车运行调整问题。求解时是在系统状态空间递 推模型的基础上，以列车等级为基本依据，采用分层决策的滚动优化方法完成列 车运行调整过程。在优化过程中，提出了分别满足提高正点率和提高列车旅行速 度目标的状态转移方法。 文献【4 】聂磊，张星臣，赵鹏，杨浩，胡安洲。高速列车运行调整策略的研究。 铁道学报，2 0 0 1 年8 月。文献介绍综合评价不同调整策略的关键技术，并利用列 车运行组织模拟实验系统，对多种运营条件下的列车运行调整策略进行模拟分析， 为优化高速列车运行调整提供了方法和决策依据。 文献 2 2 】把列车运行的连续过程，例如列车由车站出发、进入区间，再由区间 进入下一个车站等，考虑成由一系列离散事件组成的事件序列，调度的过程就是 控制这些事件的发生，并利用p e t r i 网理论对列车运行系统建模分析。利用d e d s 理论对实际问题优化的研究还刚刚起步，尚缺乏统一的理论基础，同时使用d e d s 还存在模型不够直观，难以验证状态方程的完整性、正确性，并有可能发生组合 爆炸等不足，关于这方面的问题还有待于进一步研究。 计算机模拟系统主要用来辅助人们决策。比如德国西门子公司开发的运营模 北京交通大学硕士学位论文 绪论 拟工具t r a n s i t 【4 2 】( t r a i na n a l y s i sa n ds i m u l a t i o nt 0 0 1 ) 可以用来研究在既有设备 升级改造，或者在运量控制、系统控制以及信号和安全系统装设新设备时产生的 各种各样问题，从功能上说，t r a n s i t 可以作为实验系统，承担超前综合实验的 任务。该系统中也涉及了自动调整功能，但是调整方法比较简单，主要是把某列 车的延误分散到其前行或后行列车的停站时间上。文献【4 7 】建立了京沪高速铁路仿 真实验系统，对各种运营模拟参数设置作了模拟，借助此系统也研究了高速铁路 运输组织方法。文献【2 】研制了高速列车运行组织从计划到执行的全过程计算机模 拟实验系统，并运用模拟分析法对高速铁路列车运行调整策略进行了研究与探讨。 计算机模拟是一项实验技术，其实验结果取决于所采用的模型和数据。如果 模型和数据都能准确反映系统实际，则模拟实验输出的结果是有效的。反之，如 果模型要反映的细节太多，则模拟的花费也会很大。当需要对不同的调度方案进 行选择时，模拟可以作为决策支持工具。如果在线调度中使用计算机模拟的方法， 系统响应时间应是需要考虑的一个关键因素。计算机模拟方法的不足之处主要 有：( 1 ) 模拟本身并不是优化技术，它只能通过反复实验逼近最优而不能保证一定获 得最优；( 2 ) 模拟本身不能产生决策，它具有实验的特点，很难从特定的实验中提炼 出一般的规律性；( 3 ) 模拟的准确性受程序员判断能力和技能的限制，并且模拟结果 的可信度严重依赖于模拟模型、模拟方法和输入数据。 1 2 5 4 软计算方法 软计算( s o f tc o m p u t i n g ) 又称为智能计算，这个概念是由l a z a d e h ( 19 9 4 ) 首先 提出的。它综合了近2 0 年来研究最为活跃的神经元网络算法o 埘) 、模糊逻辑( f u z z y l o g i c ，e l ) 、遗传算法( g e n e t i ea l g o r i t h m ，g a ) 。( s i m u l a t e da n n e a l i n g , s a ) 、学习推 理、混沌等领域的间接优化求解方法。模拟退火与传统的“硬计算 不同，软计 算的指定思想是在容忍不精确及不精确因素的影响下，实现可行、鲁棒、低成本 的求解方案。软计算方法的特点是给定优化目标后就可以进行全局搜索，不是直 接用模型求解。与人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 相区别的是，计算智能依赖于 数值而不是知识l a z a d e h 认为，正是由于使用了计算智能技术才使得机器智商 ( m a c h i n ei n t e l l i g e n c eq u o t i e n t m i q ) 成为可能。 1 ) 遗传算法。在软计算技术的各种方法中，求解运行调整问题使用较多的是遗 传算法。许多优化方法是通过不断修正最优解的一个近似解来寻优的，遗传算法 与之相反，是在多点同时搜索逐渐通近最优解。遗传算法是一类借鉴生物界中自 然选择和自然遗传机制的随机搜索优化算法，它基于这样的理论，即生物性状是 其内在基因的体现，基因决定生物的主要性状。遗传算法的主要特点是群体搜索 北京交通大学硕士学位论文绪论 策略和群体中个体问的信息交换，搜索不依赖梯度等高阶信息，尤其适用于处理 传统搜索方法难于解决的复杂和非线性问题。还因其具有简单、通用、鲁棒性 ( r o b u s t n e s s ) 强等特点，以及适于并行分布处理的优点，在实际用取得了广泛的应 用。 文献【4 8 】使用遗传算法求解单线铁路的最佳会让越行地点问题，其优化目标是 最小化列车停车的代价，每个列车代价是根据其正点程度和对环境的影响程度两 个方面来评价。求解时将调整范围内的列车两两比较在各车站的运行顺序并分别 设置0 1 变量来表示，以0 一l 变量串直接构建基因串。并以优化目标作为适应度函 数求解。计算效果比较好，但非常耗时，进行1 0 0 0 0 次迭代运算时，需要大约3 5 个小时，因此并不能用于实时调整。文献 5 1 1 研究了使用遗传算解决以列车总晚点 时分最小为优化目标的列车运行调整问题。满意优化模型是将原列车运行调整问 题的约束条件依据其条件的严格性转化为的相应的优化目标函数，这样将原来有 约束的优化问题转化为只有自变量的无约束条件的满意优化问题，优化目标是使 由列车运行调整的约束条件和求解目标所构成的综合满意度函数取最大。但如果 将所有约束都转化为目标函数，在设计遗传算法的适应度函数是相当困难的。 虽然遗传算法具有全局搜索能力，但是其终止条件和满意优化函数却很难求 得，如果终止条件没有确定好，或者性能函数定义有偏差，同样难以求得最优解。 例如，文献【7 5 】就是采用限制进化代数以保证解的收敛。同时其运算时间也是无法 进行实时调整的主要影响因素。 文献【4 9 】定义了一种应用于铁路列车运行系统的模糊时间p e t r i 网，针对列车 运行时间的不确定性，该p e t r i 网引入了4 个模糊集理论函数：模糊时间片、模糊 使能时间、模糊发生时间和模糊延迟，来处理时间的不确定性问题，能够对列车 运行过程中的时间不确定性问题进行定量分析。可以有效应用于列车交会、列车 终到时间、列车运行调整的分析等，其相对于已有的方法具有精确分析、计算简 单、简化系统、便于系统集成的特点。 2 ) 粒子群算法。文献【5 0 】提出了改进的车辆调度模型，针对模型将粒子群算法 和模拟退火算法相结合，设计了混合粒子群算法求其有效近似解。文献 5 l 】依据我 国铁路行车组织体制的特点，建立了了相应的模型。在模型的求解过程中，先运 用大系统理论将列车进行分层次分级，从而将待解的问题分解为若干子问题，在 对分解后的问题求解时，设计了微粒群算法，运用算法可快速得到各子问题的近 似最优解。然后，利用系统原理对问题进行了还原，即可快速得到一个满意度高、 可用性强的列车运行方案。 北京交通大学硕士学位论文绪论 3 ) 蚁群算法。文献【5 2 】认为编组站调机运用计划为具有不同开工、完工时间窗 的单机调度问题，优化目标是最小化晚点列车的数量。文献中建立了调机运用计 划的数学模型，利用蚁群算法，求解到达列车的解体次序和出发列车的编组次序， 验证了该算法在编组站的改变能力无法满足车流配送情况下实现合理安排调机的 有效性。 文献【5 3 】认为有时间窗的车辆路径问题属于n p h a r d 问题，严格的时间约束使 此问题非常复杂。文献使用蚁群算法解决了此问题，并将计算结果与遗传算法以 及粒子群算法所得结果进行了对比，说明蚁群算法是一种行之有效的算法。 4 ) 粗糙集理论。文献 5 4 】这对铁路调度智慧的智能知识表达与决策问题，给出 行车调度智慧的列车相对优先度、列车相对正点度、列车相对旅程完成程度、列 车区间运行裕度、列车车站停车裕度、后继列车新增到达晚点等七个条件属性及 运行次序一个决策属性。论述基于粗糙集理论的知识表达和粗糙集决策规则的提 取过程，提出一种相应的行车指挥决策评价体系，证明列车运行次序决策属性能 完全作为列车运行调整的决策条件。 目前我国既有线列车运行调整主要是依靠值班员人工调整，对于高速铁路这种 落后的手工调整作业方式将严重影响铁路运输能力的充分发挥，也给行车安全带 来隐患。多年来，列车运行自动调整问题的研究一直备受关注，上述这些方法在 一定程度上解决了列车运行调整的数学描述和优化求解算法问题，但基本上考虑 的都是面向区段、确定变量、全局静态优化的情况，无法适应网络化运营、不确 定性、实时在线动态调整等实际生产环境。 1 3 研究的目标与技术路线 本研究的目标为： 1 ) 为高速客运专线的运行计划调整提供一套可行的、快速求解的方法。 2 ) 实现分层递阶智能混杂优化技术在运行计划调整中的应用，设计合适的分 层递阶模型，对求解问题降维、降阶以及并行处理，从而简