（交通运输规划与管理专业论文）分局调度系统列车运行调整优化模型与算法.pdf

西南交通大学硕士学位论文第1 1 页 a b s t r a o t r a i l w a ya u t o c o n t r o ls y s t e m ( r a c s ) i so n eo fm o s ti m p o r t a n tp r o b l e mo fm o d e m r a i l w a yt r a f f i cm a n a g e m e n t ，i tc o n s i s t so ft w op a r t s ，c o m p u t e rc e n t r a l i z e dt r a f f i cc o n t r o l s y s t e ma n dc o m p u t e ra s s i s t a n td e c i s i o ns y s t e mo ft r a i no p e r a t i o na d j u s t m e n t ，t h ef o r m e ri s t h ef o u n d a t i o no fr a i l w a ya u t o c o n t r o l s y s t e m ，t h el a t t e ri s t h em e a n so fr a c st r a i n o p e r a t i o na d j u s t m e n ti s r e s u m et r a i n s o r d e rb ya d j u s t i n gt h es t a g ep l a nw h e nt h ea c t u a l s i t u a t i o no ft r a i n sr u n n i n gi s n ta c c o r dw i t ht h et r a i nd i a g r a m t h e ni n c r e a s et h ec a r r y i n g c a p a c i t yo f r a i l w a y s a n da s s u r em o s to f t r a i n s r u n n i n g o ns c h e d u l e i nt h i sp a p e rt h ep r o b l e m so fa u t o m a t i c a l l ya d j u s t i n gt h es t a g ep l a ni n s u b b u r e a u d i s p a t c hm a n a g e m e n ti n f o r m a t i o ns y s t e ma r es t u d i e df r o mt h ev i e w p o i n tc o m b i n a t o r i a l o p t i m i z a t i o n t h em a i nc o n t e x t s a r ea sf o l l o w s ： 1 a n a l y z e dt h ef a c t o r sa n dd i f f i c u l t i e si nt r a i no p e r a t i o na d j u s t m e n ts y s t e m ，d r e ww o r k f l o w d i a g r a ma n d d a t af l o w d i a g r a mo f t r a i no p e r a t i o na d j u s t m e n t 2 a i m i n ga td e c r e a s i n gt h es p e c i f i cg r a v i t yo ft a r d yt r a i n s ，a n dam a t h e m a t i c a lm o d e l o ns i n g l e t r a c ka n dd o u b l e t r a c ki ss e tu pu n d e rt h ec o n s t r a i n t so ft h es t a t i o na r r i v a l d e p a r t t r a c kc a p a c i t ya n da d j u s t m e n to f t h et r a i n sc r o s s i n go ro v e r t a k em o d e 3 s i n c ea d j u s t i n gt h es t a g ep l a ni sal a r g es c a l eo f c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ， i so n ek i n do f n p - h a r d p r o b l e m s t h eb a c k g r o u n d o f t h e p r o b l e m sd e c i d e st h a ta l g o r i t h mt o t h ep r o b l e m sm u s to u t p u tt h er e s u l ti nr a t h e rs h o r tt i m e t h e r ea r es om a n yf a c t o r si n f l u e n c e t r a i n sr u n n i n gt h a ti ti sd i f f i c u l tt os o l v et h ep r o b l e m sb ym e a n so ft r a d i t i o n a lm a t h e m a t i c a l p r o g r a m m i n g i n t h i sp a p e r , b a s e do nt h ed i s p a t c h e r s w o r ke x p e r i e n c eo n s t a g ep l a n ，w eu s e t a b u s e a r c ha l g o r i t h mt os e a r c ht h eb e s to r d e ro fd e a lw i t ht h er u n n i n gt r a i n s ，s o l v et h e p r o b l e m so fo p t i m i z a t i o ns t a g ep l a na d j u s t m e n to ns i n g l e t r a c ka n dd o u b l e t r a c k l i n ea n da r r i v a l - d e p a r tt r a c ki m p r o p r i a t et a b l em o d e lo ns i n g l e t r a c k ，d o u b l e - t r a c ko r m u l t i * t r a c ki ss e tu p t h em o d e li si m p l e m e n t e db yt h ed a t as t r u c t u r eo fl i n k e dl i s t ，s oi ti s c o n v e n i e n tt op r o g r a mu n d e ra l lk i n d so fc o n s t r a i n tc o n d i t i o n ，i nt h es a m et i m ec o m b i n et h e c o n s t r a i n t so f t h es t a t i o na r r i v a l - d e p a r tt r a c kc a p a c i t yw i t hs t a g e p l a n 5 o b j e c t o r i e n t e da n a l y s i s a n do b j e c t - o r i e n t e d d e s i g n i su s e dt o d e s i g n t r a i n sa u t o m a t i c a d j u s t m e n ts y s t e m ，a n dt h er e l a t i o n s h i p sb e t w e e no b j e c t sa n dt h ea t t r i b u t e so fo b j e c t sm a k et h es y s t e m e x p a n s i b l ea n dr e u s a b l e 6 t h ea u t o m a t i c a l l ya d j u s t i n gm o d u l ei nt r a i nd i s p a t c hs u b s y s t e mi s d e v e l o p e d ，t h es y s t e mi s p u t t e di np r a c t i c ei ns h i j i a z h u a n gs u b - b u r e a ua n dg u a n g z h o u b u r e a ua l o n gb e i j i n g - g u a n g z h o ur a i l w a y 西南交通大学硕士学位论文第m 页 l i n ea n db e i j i n g s h a n g h a i r a i l w a y t h ep r a c t i s ep 】r o v e t h em o d e la n t i a l g o r i t h mi nt h i sp a p e ri s c o r r e c t k e yw o r d s t r a i nr u n n i n ga d j u s t m e n t ；t a b us e a r c ha l g o r i t h m ；s u b b u r e a ud i s p a t c h ；s t a g e p l a n ； 西南交通大学硕士学位论文第1 页 1 1 问题的提出 第1 章绪论 对于铁路这样庞大的开放性动态时变系统，随着技术进步和社会发展，特 别是电子计算技术的发展，铁路运营管理自动化己成为铁路现代化的主要方向 和主要标志。铁路运营管理自动化主要包括两个相互联系和相互依存的方面： 信息处理自动化和过程控制自动化。过程控制自动化需要对大量复杂的实时信 息进行连续、快速、精确的判断处理，保证实时控制的实时性、准确性、安全 性和有效性。而信息处理，尤其是实时信息处理，也有赖于过程控制自动化动 态地感知并提供系统和环境的各种原始数据和信息，尽可能减少各种人工干预， 保证信息的准确性和实时性。在铁路运营管理自动化系统设计中，应使这两方 面有机结合，形成综合自动化管理系统。 铁路运输生产过程的最基本的表现形式，是活动设备( 机车、车辆) 在固 定设备( 区间、站场) 上的有序移动。因此，铁路运输生产过程控制自动化， 尤其是铁路行车调度指挥自动化，最主要的就是运用先进的科学技术，控制活 动设备在固定设备上的移动，实现安全、优质和高效的运输生产。铁路运输生 产过程控制自动化，要适应铁路运输高速和重载的发展方向，认真考虑和解决 以下问题： 运输系统的安全控制。 自动化系统的可靠性。 。 人机系统的优化设计。 系统的综合集成性。 随着计算机技术和网络的发展和应用，各国都致力于把铁路运输生产系统 的各个子系统用计算机统一管理起来，构成一个铁路运输综合自动化系统。在 这个系统中包括运输计划、行车指挥自动化、机车及车辆的技术管理、货车运 用及管理、集装箱运用管理、编组站、货运站、机务段、车辆段的管理、运输 设备管理、财务管理和统计报告等子系统。 实现用计算机辅助列车运行调整系统是我国铁路运输管理现代化的必然要 求。但是，由于我国铁路线路的衔接关系错综复杂，列车种类及运行要求纷繁 西南交通大学硕士学位论文第1 页 1 1 问题的提出 第1 章绪论 对于铁路这样庞大的开放性动态时变系统，随着技术进步和社会发展，特 别是电子计算技术的发展，铁路运营管理自动化己成为铁路现代化的主要方向 和主要标志。铁路运营管理自动化主要包括两个相互联系和相互依存的方面： 信息处理自动化和过程控制自动化。过程控制自动化需要对大量复杂的实时信 息进行连续、快速、精确的判断处理，保证实时控制的实时性、准确性、安全 性和有效性。而信息处理，尤其是实时信息处理，也有赖于过程控制自动化动 态地感知并提供系统和环境的各种原始数据和信息，尽可能减少各种人工干预， 保证信息的准确性和实时性。在铁路运营管理自动化系统设计中，应使这两方 面有机结合，形成综合自动化管理系统。 铁路运输生产过程的最基本的表现形式，是活动设备( 机车、车辆) 在固 定设备( 区间、站场) 上的有序移动。因此，铁路运输生产过程控制自动化， 尤其是铁路行车调度指挥自动化，最主要的就是运用先进的科学技术，控制活 动设备在固定设备上的移动，实现安全、优质和高效的运输生产。铁路运输生 产过程控制自动化，要适应铁路运输高速和重载的发展方向，认真考虑和解决 以下问题： 运输系统的安全控制。 自动化系统的可靠性。 。 人机系统的优化设计。 系统的综合集成性。 随着计算机技术和网络的发展和应用，各国都致力于把铁路运输生产系统 的各个子系统用计算机统一管理起来，构成一个铁路运输综合自动化系统。在 这个系统中包括运输计划、行车指挥自动化、机车及车辆的技术管理、货车运 用及管理、集装箱运用管理、编组站、货运站、机务段、车辆段的管理、运输 设备管理、财务管理和统计报告等子系统。 实现用计算机辅助列车运行调整系统是我国铁路运输管理现代化的必然要 求。但是，由于我国铁路线路的衔接关系错综复杂，列车种类及运行要求纷繁 西南交通大学硕士学位论文 第2 页 多变，随机扰动频繁，使得开发适合我国铁路特点的计算机辅助行车调度指挥 运行调整系统仍存在许多技术难点问题，这主要在于这个系统不仅要有很强的 实时处理能力，还必须要有一个表现丰富，操作灵活可靠、适应性强的人机交 互系统，它必须能直观、全面、准确、快速她表现列车运行调整的各个作业过 程，并具有通用性，以适应各种线路条件、各种车流结构、各种行车组织方法， 且可运行于多种操作平台。在这样的系统中，合理的数据结构是提高处理能力 和处理速度的基础，完美的图形处理方法是提高系统表现能力和速度的途径， 而编制列车运行调整计划的调度算法则是系统能否实用的关键所在，这三个方 面是调整系统的核心和难点，是开发调度系统首先应该解决的关键问题。 1 2 传统行车调度存在的问题 在我国线路能力紧张，运能与运量矛盾十分突出，靠加大行车密度缓解运 能不足矛盾，因而行车密度之高，堪称世界之最。行车密度大，列车关联性强， 运行点间相互牵制面广，交一点牵动全局，在我国列车运行调整的难度是相当 大的。由于线路能力紧张，因而在制订列车运行图时采用区间“撒点”的方法 增加列车的运行富裕时分是十分有限的。且区间“撤点”一般安排在区间运行 时分较小的区间，而较普遍采用的是车站停时“撒点”，该“撒点”方法在调整 时波及列车面广，往往需要通过较大范围列车会让方案的优选，增加了调度调 整的复杂性和难度。所以说我国现阶段列车运行图的抗干扰能力有限，而列车 运行图适应车流结构和强度变化能力有限，需要通过日常运输调整制订日班计 划来适应车流的变化。我国目前制订日班计划的原始数据不够准确，致使班计 划本身准确性不够，再受列车运行秩序和指挥水平影响，班计划的兑现率不高。 有时受客观条件( 设备条件、气候、灾害等) 影响，导致列车运行大面积紊乱。 因而必须制订3 4 小时列车运行调整计划( 即阶段计划) 。3 4 小时列车运行 调整计划是针对我国铁路特点丽设计的，是我国的首创。目前。我国铁路调度 指挥工作主要还是靠调度人员的个人技能和工作经验以及主观能动性的发挥来 完成的。调度设备、手段还比较落后调度人员使用的仍然是铅笔、橡皮、直 尺、电话和图表。由调度人员用铅笔，直尺逐个列车逐个区间推算，编制列车 运行调整计划，并必须随时记录列车运行实绩。通过电话获得有关信息，发布 有关调度命令和列车运行计划。在未采用计算机控制调度集中( 简称c t c ，即 c e n t k a l i z e dt r a f f i cc o n t r o l ) 系统的区间，无列车运行监控设备，对 西南交通大学硕士学位论文 第2 页 多变，随机扰动频繁，使得开发适合我国铁路特点的计算机辅助行车调度指挥 运行调整系统仍存在许多技术难点问题，这主要在于这个系统不仅要有很强的 实时处理能力，还必须要有一个表现丰富，操作灵活可靠、适应性强的人机交 互系统，它必须能直观、全面、准确、快速她表现列车运行调整的各个作业过 程，并具有通用性，以适应各种线路条件、各种车流结构、各种行车组织方法， 且可运行于多种操作平台。在这样的系统中，合理的数据结构是提高处理能力 和处理速度的基础，完美的图形处理方法是提高系统表现能力和速度的途径， 而编制列车运行调整计划的调度算法则是系统能否实用的关键所在，这三个方 面是调整系统的核心和难点，是开发调度系统首先应该解决的关键问题。 1 2 传统行车调度存在的问题 在我国线路能力紧张，运能与运量矛盾十分突出，靠加大行车密度缓解运 能不足矛盾，因而行车密度之高，堪称世界之最。行车密度大，列车关联性强， 运行点间相互牵制面广，交一点牵动全局，在我国列车运行调整的难度是相当 大的。由于线路能力紧张，因而在制订列车运行图时采用区间“撒点”的方法 增加列车的运行富裕时分是十分有限的。且区间“撤点”一般安排在区间运行 时分较小的区间，而较普遍采用的是车站停时“撒点”，该“撒点”方法在调整 时波及列车面广，往往需要通过较大范围列车会让方案的优选，增加了调度调 整的复杂性和难度。所以说我国现阶段列车运行图的抗干扰能力有限，而列车 运行图适应车流结构和强度变化能力有限，需要通过日常运输调整制订日班计 划来适应车流的变化。我国目前制订日班计划的原始数据不够准确，致使班计 划本身准确性不够，再受列车运行秩序和指挥水平影响，班计划的兑现率不高。 有时受客观条件( 设备条件、气候、灾害等) 影响，导致列车运行大面积紊乱。 因而必须制订3 4 小时列车运行调整计划( 即阶段计划) 。3 4 小时列车运行 调整计划是针对我国铁路特点丽设计的，是我国的首创。目前。我国铁路调度 指挥工作主要还是靠调度人员的个人技能和工作经验以及主观能动性的发挥来 完成的。调度设备、手段还比较落后调度人员使用的仍然是铅笔、橡皮、直 尺、电话和图表。由调度人员用铅笔，直尺逐个列车逐个区间推算，编制列车 运行调整计划，并必须随时记录列车运行实绩。通过电话获得有关信息，发布 有关调度命令和列车运行计划。在未采用计算机控制调度集中( 简称c t c ，即 c e n t k a l i z e dt r a f f i cc o n t r o l ) 系统的区间，无列车运行监控设备，对 西南交通大学硕士学位论文第3 页 列车运行状况能见度差，预见性差。通过电话获得的信息往往水分大，另外有 些调度员花费大量时间制订列车运行调整计划，而疏于对列车运行的监控、指 挥，致使编制的列车运行调整计划兑现率低，列车运计划变动频繁，调度人员 劳动强度大。同肘列车运行调整实时性强，调度人员在有限时间内制定一个经 过优化的调整方案是十分不容易的。一个调整方案质量好坏，在很大程度上取 决于调度人员的素质。有关资料表明，几乎三分之旅行速度的损失与列车调 度员没有很好地组织列车运行调整有关。这种状况严重影响了铁路运输能力的 充分发挥，同时也给行车安全带来隐患。开发自动编制列车运行阶段计划系统， 减少调度员花费在制订列车运行调整计划的时间，使调度员有更多的时间对列 车运行进行监控和指挥，实现铁路行车调度指挥系统的现代化势在必行。 1 3 国内外研究现状综述 1 3 1 国外列车调度指挥自动化系统发展概冽2 ，3 ，4 铁路调度工作是运营指挥工作的重要组成部分，借助于计算机可以更安全、 准时地指挥列车运行。6 0 年代中期，美国铁路在调度集中系统引入计算机，出 现了计算机辅助调度系统。8 0 年代各国铁路将微机引入调度集中系统，从而出 现了各具特色的微机化调度集中系统。进入9 0 年代各国均以计算机辅助调度系 统为核心，积极推进调度中心的建设。 只本国铁在1 9 6 4 年东京至新大阪东海道新干线开业时，建设了综合调度所， 集中指挥全线的列车。调度员工作负担加重。为了能自动排列进路，及时收集 运输信息和传达运输命令日本国铁于1 9 7 2 年3 月开始引入采用计算机的行车 指挥自动化系统c o m t r a c 。到1 9 8 1 年8 月，东北、上越新干线开业，c o m t r a c 系统已具备完善的功能。 同本的c o m t r a c 系统是功能较全的一个行车指挥系统，这与其特定条件 有关的。因为日本的新干线是客运专线，列车种类比较少，适于进行综合管理。 c o m t r a c 系统由信息处理和进路控制两部分组成，信息处理计算机( e d p ) 为2 台大型计算机，其中1 台为备用。进路控制计算机有3 台，1 台备用。 c o m t r a c 和s m i s 系统共用端机，端机设在车站、列车段和检修段等场所。 法国t g v 高速铁路的行车指挥系统也具有综合功能的性质，但仅限于行车 调度和电力调度。如巴黎东南线的调度中心设在巴黎，负责对全长3 9 0 公里的 西南交通大学硕士学位论文第3 页 列车运行状况能见度差，预见性差。通过电话获得的信息往往水分大，另外有 些调度员花费大量时间制订列车运行调整计划，而疏于对列车运行的监控、指 挥，致使编制的列车运行调整计划兑现率低，列车运计划变动频繁，调度人员 劳动强度大。同肘列车运行调整实时性强，调度人员在有限时间内制定一个经 过优化的调整方案是十分不容易的。一个调整方案质量好坏，在很大程度上取 决于调度人员的素质。有关资料表明，几乎三分之旅行速度的损失与列车调 度员没有很好地组织列车运行调整有关。这种状况严重影响了铁路运输能力的 充分发挥，同时也给行车安全带来隐患。开发自动编制列车运行阶段计划系统， 减少调度员花费在制订列车运行调整计划的时间，使调度员有更多的时间对列 车运行进行监控和指挥，实现铁路行车调度指挥系统的现代化势在必行。 1 3 国内外研究现状综述 1 3 1 国外列车调度指挥自动化系统发展概冽2 ，3 ，4 铁路调度工作是运营指挥工作的重要组成部分，借助于计算机可以更安全、 准时地指挥列车运行。6 0 年代中期，美国铁路在调度集中系统引入计算机，出 现了计算机辅助调度系统。8 0 年代各国铁路将微机引入调度集中系统，从而出 现了各具特色的微机化调度集中系统。进入9 0 年代各国均以计算机辅助调度系 统为核心，积极推进调度中心的建设。 只本国铁在1 9 6 4 年东京至新大阪东海道新干线开业时，建设了综合调度所， 集中指挥全线的列车。调度员工作负担加重。为了能自动排列进路，及时收集 运输信息和传达运输命令日本国铁于1 9 7 2 年3 月开始引入采用计算机的行车 指挥自动化系统c o m t r a c 。到1 9 8 1 年8 月，东北、上越新干线开业，c o m t r a c 系统已具备完善的功能。 同本的c o m t r a c 系统是功能较全的一个行车指挥系统，这与其特定条件 有关的。因为日本的新干线是客运专线，列车种类比较少，适于进行综合管理。 c o m t r a c 系统由信息处理和进路控制两部分组成，信息处理计算机( e d p ) 为2 台大型计算机，其中1 台为备用。进路控制计算机有3 台，1 台备用。 c o m t r a c 和s m i s 系统共用端机，端机设在车站、列车段和检修段等场所。 法国t g v 高速铁路的行车指挥系统也具有综合功能的性质，但仅限于行车 调度和电力调度。如巴黎东南线的调度中心设在巴黎，负责对全长3 9 0 公里的 西南交通大学硕士学位论文第3 页 列车运行状况能见度差，预见性差。通过电话获得的信息往往水分大，另外有 些调度员花费大量时间制订列车运行调整计划，而疏于对列车运行的监控、指 挥，致使编制的列车运行调整计划兑现率低，列车运计划变动频繁，调度人员 劳动强度大。同肘列车运行调整实时性强，调度人员在有限时间内制定一个经 过优化的调整方案是十分不容易的。一个调整方案质量好坏，在很大程度上取 决于调度人员的素质。有关资料表明，几乎三分之旅行速度的损失与列车调 度员没有很好地组织列车运行调整有关。这种状况严重影响了铁路运输能力的 充分发挥，同时也给行车安全带来隐患。开发自动编制列车运行阶段计划系统， 减少调度员花费在制订列车运行调整计划的时间，使调度员有更多的时间对列 车运行进行监控和指挥，实现铁路行车调度指挥系统的现代化势在必行。 1 3 国内外研究现状综述 1 3 1 国外列车调度指挥自动化系统发展概冽2 ，3 ，4 铁路调度工作是运营指挥工作的重要组成部分，借助于计算机可以更安全、 准时地指挥列车运行。6 0 年代中期，美国铁路在调度集中系统引入计算机，出 现了计算机辅助调度系统。8 0 年代各国铁路将微机引入调度集中系统，从而出 现了各具特色的微机化调度集中系统。进入9 0 年代各国均以计算机辅助调度系 统为核心，积极推进调度中心的建设。 只本国铁在1 9 6 4 年东京至新大阪东海道新干线开业时，建设了综合调度所， 集中指挥全线的列车。调度员工作负担加重。为了能自动排列进路，及时收集 运输信息和传达运输命令日本国铁于1 9 7 2 年3 月开始引入采用计算机的行车 指挥自动化系统c o m t r a c 。到1 9 8 1 年8 月，东北、上越新干线开业，c o m t r a c 系统已具备完善的功能。 同本的c o m t r a c 系统是功能较全的一个行车指挥系统，这与其特定条件 有关的。因为日本的新干线是客运专线，列车种类比较少，适于进行综合管理。 c o m t r a c 系统由信息处理和进路控制两部分组成，信息处理计算机( e d p ) 为2 台大型计算机，其中1 台为备用。进路控制计算机有3 台，1 台备用。 c o m t r a c 和s m i s 系统共用端机，端机设在车站、列车段和检修段等场所。 法国t g v 高速铁路的行车指挥系统也具有综合功能的性质，但仅限于行车 调度和电力调度。如巴黎东南线的调度中心设在巴黎，负责对全长3 9 0 公里的 西南交通大学硕士学位论文第4 页 铁路线进行管理，整个系统由三层结构的微机系统构成。 德国铁路在高速线采用计算机辅助行车调度系统( r z u ) ，该系统主要以信 息支持调度判断。指挥中心通过各站的微机实行列车追踪。各站通过数据总线 周期性地向指挥中心传送道岔和信号状态。歹u 车运行位置的信息，列车晚点时 分和原因由各站车站值班员通过微机终端输入。行车指挥中心的计算机辅助行 车调度系统通过运行图显示器、线路占用显示器和绘图仪，把上述信息的处理 结果提供和显示给调度员。 北美、西欧铁路为了提高运输安全、效率和和灵活性，研究开发了先迸列 车控制系统。根据各国的具体情况各有特点，如北美的先进列车控制系统 ( a t c s ) 和欧洲铁路运输管理系统( e r t m s ) 、法国的实时追踪自动化系统 ( a s t r e e ) 等。这些系统都是将微处理机和数据通信技术用于列车指挥、控 制和通信，将逐步推广应用。 1 3 2 国内外列车调整自动化理论研究现状综述 在铁路运输领域，多年来行车指挥自动化和列车运行调整问题的研究一直 备受关注，其研究热点主要集中在数学模型的建立和求解算法的研究两方面。 目前比较有代表性的实现这两方面的方法有以下几类：仿真方法、运筹学方法 ( o r ) 、人工智能方法( a i ) 。 一、仿真方法 尽管仿真不能进行复杂分析，但它可以灵活详尽地对系统进行建模，因此 在系统设计、使用、评价等方面成为种实用方法。自从1 9 6 1 年i b m 公司开 发g p s s ( 离散事件系统仿真语言) 以来，出现了许多仿真专用程序语言，用仿 真解决调度问题的方法得到了显著普及。特别是随着计算机技术的发展进步， 其实用性j 下在迅速提高。 6 0 年代，f r a n k 、p e a t 、m a r w i c k 、m i t c h e l l 、p e t e r s e n 、t a y l o r 等开始了用仿 真技术进行行车调度问题的研究。a b e & a r a y a f r a n k ( 1 9 8 6 ) 、p e t e r s e n & t a y l o r ( 1 9 8 2 ) 、驹谷( 1 9 8 1 ) 、安部& 荒谷( 1 9 8 6 ) 、c a r s o n & a t a l a 等人在基于事件的 仿真和基于网络的仿真等方面作了许多研究。 随着离散事件动态系统( d e d s ) 理论地发展，行车指挥仿真技术取得了许 多进步，基于d e d s 的行车指挥方法也应运而生。九十年代中期北方交通大学 周磊山、西安交通大学周伟等提出了用d e d s 解决列车运行调整问题的方法。 文献【5 和1 9 9 4 年周磊山博士应用离散事件动态系统理论，将列车运行调整 西南交通大学硕士学位论文第4 页 铁路线进行管理，整个系统由三层结构的微机系统构成。 德国铁路在高速线采用计算机辅助行车调度系统( r z u ) ，该系统主要以信 息支持调度判断。指挥中心通过各站的微机实行列车追踪。各站通过数据总线 周期性地向指挥中心传送道岔和信号状态。歹u 车运行位置的信息，列车晚点时 分和原因由各站车站值班员通过微机终端输入。行车指挥中心的计算机辅助行 车调度系统通过运行图显示器、线路占用显示器和绘图仪，把上述信息的处理 结果提供和显示给调度员。 北美、西欧铁路为了提高运输安全、效率和和灵活性，研究开发了先迸列 车控制系统。根据各国的具体情况各有特点，如北美的先进列车控制系统 ( a t c s ) 和欧洲铁路运输管理系统( e r t m s ) 、法国的实时追踪自动化系统 ( a s t r e e ) 等。这些系统都是将微处理机和数据通信技术用于列车指挥、控 制和通信，将逐步推广应用。 1 3 2 国内外列车调整自动化理论研究现状综述 在铁路运输领域，多年来行车指挥自动化和列车运行调整问题的研究一直 备受关注，其研究热点主要集中在数学模型的建立和求解算法的研究两方面。 目前比较有代表性的实现这两方面的方法有以下几类：仿真方法、运筹学方法 ( o r ) 、人工智能方法( a i ) 。 一、仿真方法 尽管仿真不能进行复杂分析，但它可以灵活详尽地对系统进行建模，因此 在系统设计、使用、评价等方面成为种实用方法。自从1 9 6 1 年i b m 公司开 发g p s s ( 离散事件系统仿真语言) 以来，出现了许多仿真专用程序语言，用仿 真解决调度问题的方法得到了显著普及。特别是随着计算机技术的发展进步， 其实用性j 下在迅速提高。 6 0 年代，f r a n k 、p e a t 、m a r w i c k 、m i t c h e l l 、p e t e r s e n 、t a y l o r 等开始了用仿 真技术进行行车调度问题的研究。a b e & a r a y a f r a n k ( 1 9 8 6 ) 、p e t e r s e n & t a y l o r ( 1 9 8 2 ) 、驹谷( 1 9 8 1 ) 、安部& 荒谷( 1 9 8 6 ) 、c a r s o n & a t a l a 等人在基于事件的 仿真和基于网络的仿真等方面作了许多研究。 随着离散事件动态系统( d e d s ) 理论地发展，行车指挥仿真技术取得了许 多进步，基于d e d s 的行车指挥方法也应运而生。九十年代中期北方交通大学 周磊山、西安交通大学周伟等提出了用d e d s 解决列车运行调整问题的方法。 文献【5 和1 9 9 4 年周磊山博士应用离散事件动态系统理论，将列车运行调整 西南交通大学硕士学位论文第5 页 系统描述为离散事件动态系统，在建模思路和方法上是对列车物理状态过程的 一种代数描述。采用的算法是按时间顺序设定列车。较以往时间顺序设定法所 不同的是提出了两个目标即正点率和旅行速度下的疏解两冲突事件的判定条 件，即 r ；一f ? 一f ? 0 l ：一纽； ；0 f ? 一蟛+ 埘一蟛0 其中f 0f ；：分别为冲突列车i ，j 的松弛时问：f ? ，f ? ：分别为冲突列 车疏解冲突时的待避时间；y f 厶罗f ? 分别为当前冲突列车在区段内其后运 行径路上与上层已设定列车冲突下的总待避时间。 该系统采用分层决策和滚动优化的方法设计了适合我国各种铁路区段列车 运行计划与调整的通用算法。该算法主要思路如下： 当列车运行状态偏离基本运行图，出现了不同列车在同一时间段内争夺同 一设备的现象时，必须重新合理规划列车占用设备的时机。调整的表现形式是 移动运行线。其焦点问题是合理安排运行线之间的间隔。如果将运行线定义为 事件，则调整的焦点问题是疏解事件之间的冲突问题。所谓两事件冲突，是指 同一空问上丽事件发生的时机不能满足必要的阿隔，即前事件尚未腾空设备， 后一事件便已出现。因此，设计计算机自动编制列车运行调整计划的算法关键 是要有一套确定和疏解事件冲突的方法。事件冲突类型何以归结为区间冲突和 车站冲突。区间冲突包括对向冲突、连发冲突和追踪冲突。车站冲突包括车站 问隔u , t f i j 冲突和站线冲突。对于各种冲突可按照事件的性质分别设计判别式。 列车运行调整就是要按照优化原则疏解事件之间的冲突，疏解冲突的一般方法 是采用错开冲突事件的发生时机，包括两个方面的含义：是根据冲突类型和 冲突性质，确定两冲突事件的放行顺序，二是根据放行顺序确定待避事件的滞 后量。 按上述方法构造的求解列车运行调整计划的算法模型，可以反映列车运行 调整的规律。设计求解算法时，结合列车运行调整的实际要求，按照列车等级。 区别轻重缓急，顺序求解，即采用分层决策的方法。所谓分层决策就是把问题 按各种因素的重要程度分成不同的层次，按层次的优先顺序，对各个层次的因 素分别决策，高层次的决策为低层次的决策规定轮廓，低层次的决策在高层次 决策的基础上，使问题的决策具体化。这样可以把一个复杂的大问题化为几个 简单的干问题，降低了问题的复杂性，提高求解效率。采用分层决策，可以比 西南交通大学硕士学位论文第6 页 较准确地预测出列车越行和交会地点，为组织列车赶点运行、提高列车正点率 提供了有利条件。” 由于调整计划的复杂性及因素的动态性，优化方法不宜采用数学规划方法， 而应采用滚动优化的方法。滚动优化与一般意义下的优化方法不同，它不是采 用一个不变的全局的最优目标，而是采用滚动式的有限时域内的优化策略；优 化过程不是一次完成的，而是在求解过程中不断滚动实旄、反复进行的。调整 系统的优化主要体现在冲突事件的放行顺序上，只有当两事件发生冲突时，才 需要根据当时的优化目标，配合事件的优先级、正晚点、机车交路等状况，确 定两事件的放行顺序。调整计划的优化寓于冲突的疏解过程中，这样，可以避 免构造大规模的优化模型和不必要的迭代计算。 由于d e d s 的研究刚刚兴起，尚缺乏统一的理论基础，d e d s 有可能发生 复杂性的组合爆炸，同时该方法还存在模型不够直观、难以验证状态方程的完 整性、正确性等不足，关于这方面的研究还有待深入。 二、运筹学方法( o r ) 七十年代初受到运筹学在车间调度问题上得到成功应用的鼓舞，很多学者 开始了用运筹学解决列车运行调整问题的研究。o r 方法以目标函数最优为中 心，其代表性的方法有分支限界法( b & b ) 整数规划法( p ) 。 b s z p i g e l 于1 9 7 3 年率先提出了“最优列车调度问题” 6 1 ，利用线性规划技 术和分支定界法解决单线铁路上列车的调度问题。其后k r a y a 等人又开发了考 虑不同速度和燃料消耗的更为完整的模型，进行了更为深入的研究。s a u d e r 等 于1 9 8 3 年提出了个优化的列车调度模型。并开发了一个用于单线铁路的全局 优化方法，该方法使用分支限界法部分列举出可能的交会、越行方案。j o v a n o v i c 于1 9 8 9 年提出了一个将启发式技术引入整数规划的行车调度方法，该方法显著 地减少了搜索节点的数目，从而大大提高了求解速度。a r a y a 等提出了一个在干 扰情况下产生优化调度的在线行车指挥方法。他们把调度问题视为0 1 混合整 数规划问题，并基于产生式系统方法得到一个次优解，然后以该解为初始上界， 利用b & b 法产生一个优化解。c u t y 等为s a op a u l o 地铁公司开发了一个时刻表 自动生成系统，对列车和乘客的运动建立了分析模型，并通过拉格朗只松弛法 把复杂问题分解为若干予问题，再通过分层方式求解各子问题。但当约束和环 境比较复杂时拉格朗日松弛技术将难以应用。 对于列车运行调整自动化理论，我国学者也做了深入的研究。程宇博士对 已有的理论研究方法和运行调整问题本身进行了深入研究后认为，列车运行调 西南交通大学硕士学位论文第7 页 整计划编制问题属于劣构问题( i u s t r u c t u r e dp r o b l e m ) ，即具有非数值性、不适 应性、离散性和信息开放性，依赖于有经验专家判断的情况较多、指出利用数 学模型方法解决是极其困难的。其原因主要是，在列车运行调整中，存在大量 非常规决策( 带有人的意志决定以及社会因素的决策) ，这些非常规决策往往起 着全面性、决定性的作用，在列车运行调整中占有重要地位，往往难于用数学 方法描述；对于常规决策部分，有一部分难以描述成数学模型，有的即使描述 成数学模型，可能也难于求解或求解时间难以满足实时性要求：另外对于运行 调整这一多目标问题，很难转化为单目标；数学模型的修改将花费大量的时间 和费用，数学模型建立后一般要求相对稳定，但随着人们对运行调整认识的不 断发展，若不经常修改和补充，在新的条件下仍使用旧的数学模型，就不能作 出适应新情况的最佳决策。 基于上述认识，1 9 8 8 年程宇博士提出了“组合界线法”编制列车运行调整 计划 】。该方法的思路是：先编制出客车运行调整计划。出其在运行图上的到 发时刻构成客车界线。所谓界线就是列车的到发时刻在运行图上对应点的连线。 然后，根据具体情况，确定虚拟客车界线。所谓虚拟是指该列车线并非由真i ：f 的客车到发时刻的连线构成，而是根据需要假定的。此外。还要参照运行调整 开始时刻进行取舍组合，构成组合界线，这样，可用组合界线将由时间、距离 构成的运行图平面分割成若干设定子区域，在子区域内设定货车的部分，当该 子区域的所有货车在此区域的部分都设定完之后，转入下个子区域。直至设 定到运行调整结束时刻，其主要内容为：旅客列车运行调整计划的编制、确定 组合界线和货物列车运行调整计划的编制。 尽管列车运行调整问题一直使用经典的数学方法解决，但由于问题的复杂 性和不确定性，结果并不令人满意，因为列车运行调整问题是一个大规模整数 问题，以可行的越行位置为例，设有n 个车站且列车只能在车站越行其余列车， 则将有2 ”种不同情况。虽然数学规划方法曾成功地应用于某些其它调度问 题，但它很难求解实时的列车运行调整闯题，原因如下： 形式化的数学模型本质上是一个大规模整数问题，对于中大规模的问题而 言该方法很难在可行的时间内求解。 列车运行调整问题要求大量的个人经验和专业技术处理调整中产生的大量 信息，但该方法难以处理大量的冲突准则和不确定性。 由于这类方法的搜索空间范围非常大，容易产生组合爆炸问题，在当前的 调整要求下难以解决列车运行调整的实时性要求。 西南交通大学硕士学位论文第8 页 近几年来，国内学者又开展了对列车运行图动态性能和列车晚点传播规律 的研究。 三、人工智能方法( a j ) 8 0 年代人工智能技术的兴起激发人们使用基于知识的技术解决调度问题， 与运筹学方法相比，人工智能方法主要有以下特征： 现实系统包含有许多复杂的约束条件，人们更希望找到满足这些约束条件 的可行解，而不定是最优解 j 。 利用专家掌握的知识可以解决难以形式化的约束及目标【9 】。 解决行车指挥问题的人工智能方法大致可分为专家系统方法、模糊决策方 法及把两者结合起来的模糊专家系统方法【1 ”。 l 、专家系统方法【1 1 , 1 2 , 1 3 专家系统本来是为医疗诊断和故障诊断而开发的，但它作为调度规划方法 却得到了广泛的应用。专家系统把专家知识用w - t h e n 形式的规则来表示并存 放在规则库中，推理机则基于规则库进行调度。 同本是最早将知识工程技术应用于行车指挥的国家，早在t 9 8 2 年三菱电气 公司就看手开发了e s t r a c 系统，并分别予1 9 8 3 、1 9 8 4 、1 9 8 8 年推出了三个 不同的版本e s t r a c i 、e s t r a c 一、e s t r a c 1 1 1 ，e s t r a c i ( a r a y a ，1 9 8 3 ) 采用启发式规则和分支定界法相结合的方法，尽管该版本只适用于小型简单的 路网且只能调整列车的顺序，但它的重要意义在于将知识工程这门新技术引入 到铁路行车指挥中。e s t r a c ( a y a r a ) 引入了调度员的知识获取机构，从而 可将有经验的调度员的“k n o w h o w ”知识用于列车运行的实时调整，尽管该版 本只能应用调度员的知识改变列车顺序及安排机车的使用，但它证明了知识工 程技术可以用于解决大规模、复杂路网的调整问题。e s t r a c i l i ( k o m a y a ，1 9 8 8 ) 在e s t r a c i i 的基础上开发了将基本仿真单元和