基于列车运行状态推导图的列车运行调整算法地研究.pdfVIP

基于列车运行状态推导图 的列车运行调整算法的研究 周学松朱钰胡思继 北方交通大学运输系 摘要本文通过构造列车运行状态推导图表示的状态空间结构及其启发式有哪些信誉好的足球投注网站算法，成 功地进行了列车运行调整问题过程性知识的表示．并通过引人“占用记录表”，使算法滑 用列车间隔约束判断操作的时间复杂度降至线性阶。 关键词状态空闻算法知识表示列车运行罚整 妻 列车运行调整问题属-7：--类完全Np问题。目前其求解算法主要有整数规划、条件判断 I 和人工智能Z：L-类算法。整数规划类算法时间复杂度难以满足列车运行指挥实时性的要求。 条件判断类算法对列车运行图铺画过程的描述往往缺乏规范性，因而难以进一步拓展、深化。 而人工智能类方法难以对过程性知识作完整描述，目前尚未形成较成熟的应用。 状态空间法是人工智能中用于过程性知识表示的常用方法。若直接将列车运行图作为 状态单元，存在目标状态难以确定、有哪些信誉好的足球投注网站算法过于复杂等缺点，因而算法实现困难，必须利 用列车运行调度领域内的专门知识对其状态空间表示形式进行改进。 1 列车运行状态推导图及有哪些信誉好的足球投注网站算法 列车运行调整方案可用列车运行图表示的，其矩阵形式描述为： P】】，／h2…．，_P1村 P21．P22,．．．，P2M X= =嘛hxM，其中i为列车序号，j为该列车所在列车路径上的车站 Pm．PN2，．，PNM 序号(以下所指的第j个车站均指该列车所在列车径路上的第j个车站，车站序号j也是指 。一l变量，表示列车i在第j个车站的车站运行状态，其取值为o、1时分别代表通过和停 车状态。 按照列车运行调整时必须遵守的列车等级次序，并在同一等级列车中辅之以“先到先 ● 其中，q}为列车调整优先序中的第k个列车在列车运行调整计划中的编号，1s“≤N， k=1．2，．．．，吼根据序列O，可依次将原问题分解为子问题序列。第％个列车的运行计匍阿表 示为盯qk={：Pqk,1，Pqk,2，…Pq≈，埘7。 ● 状态空间由状态、算符两大要素构成，首先给出车站运行状态及列车车站状态推导算 符的表示。引入二元组sO，J)描述列车i在第j个车站的车站运行状态，j=％，…，s。。 313 礤，，)取值为0或l，分别表示列车在车站运行中通过、停车两种状态属性。 引人五元组ot，．f，d，sj，，，5。p1)描述列车车站状态推导算符(以下简称为算符)，莸云列车 i在第j个车站上以推导初始时刻d由第：j个车站的状态‘，』推导至第j+1个车站的状态 屯川的变换过程。孟E里所指的推导初始时刻d即列车i在第j个车站的出站时刻。 0停节点 。遗节点 ● 豳1 刊车运行状态推卑圈 State 基于以上表示，构造列车运行状态推导图(TrainRunningDerivation(；raph， 以下简称为TSG)来描述列车运行计划对应的状态空间表示。TSG为三元组G∽，E，R)，其 中N为列车的车站状态节点集，E为车站状态推导算符对应的边集，R为状态推导算符到对 应调整约束集的映射。TSG的示意图如图1所示。 TSG有以下特点： 按车站分层，每屡包括该站停车、通过两个车站状态节点； 相邻两层节点之间一般有四条有向边，分别对应前停后停、前停后通、前通后停、前 通后通四种车站状态准导算符。 初始节点、终止节点分别对应列车在第S6、。，。．个车站的车站状态。设初始节点、终止 节点为yD、％。 2算符