铁路列车运行图编制系统

运行图编制的关键技术是怎样铺画运行线。整个运行图铺画过程是选择线路和列车，安排列车运行时间，并铺画运行线。其过程可以看作是在时空中的搜索过程。常用的搜索策略一种是深度优先搜索，另一个是宽度优先搜索。

深度优先搜索：

深度优先搜索是以列车为核心，将所有的列车按特征值（一般指列车等级）进行排队，特征值小的列车排在前面；特征值相同的列车比较客流和收入，客流大和收入高的排在前面。对每一列车，从始发站开始，为列车安排径路上通过区段和车站的时间，一直安排到到达终到站的时间，根据“区间、时间点”或“车站、时间点”可以画出本列车的运行线。每为一个区段或车站安排列车时间的同时，需要检查是否满足约束条件，也就是保证没有冲突。

宽度优先搜索：

宽度优先搜索是以区段为核心，通过径路计算，找出所有经过区段的列车，按优先级对每一列车，根据区段离列车始发站的位置和列车始发时间，安排通过区段的时间；同时，检查所有安排是否满足约束条件，保证不发生时间上的冲突。然后，滚动地安排下一区段，一直滚动安排所有的区段，形成列车运行图。