大型铁路客运站的进路分配问题及缓冲时间研究
|
摘要
衔接多个方向的大型客运站接发车作业密集,咽喉区交叉干扰多,通常构成行车组织的瓶颈,例如广州站、武汉站、郑州站、北京站及成都站等。这类大型客运站的能力既要能满足运行图中规定的接发车作业,又要实现一定的服务水平。在相同的时空范围内,随着接发车作业数量的增加,车站对列车作业的服务水平呈下降趋势；当车站能力不能满足运行图的需求时,一些列车就会产生到达或出发晚点。在车站平面图和列车运行图已知,以及车站能力满足图定列车作业的前提下,考虑到列车运行过程中的扰动,不同的接发车方案可能产生不同的效果,例如一个方案的抗干扰能力强于另外一个方案。在车站能力富余的前提下,研究如何获取抗干扰能力较好的接发车方案值得探讨,这将为分析车站能力与运行图抗干扰性的关系提供参考。因此,为获取高质量的列车接发车方案,需要研究车站接发车作业的进路分配问题。
铁路客运站的进路分配问题是编制旅客列车运行计划的一部分,目的是为运行图中的列车分配无冲突的进路和站台,同时满足车站作业和运输组织的要求。进路分配问题中包含由列车运行图和车站平面图引起的时间和空间约束,求解进路分配问题的一个基本要求是疏解列车作业之间的时空冲突,同时考虑车站设备利用以及列车服务水平,进路分配问题的解称为进路分配方案。既有方法中的目标函数包括列车等级总权重最大化、到发线运用效用最大化、分配进路总权重最大化以及列车晚点时间最小化等,部分研究提到进路分配方案与列车作业抗干扰性的关系问题,但未能充分考虑车站能力富余条件下以优化抗干扰性为目标的进路分配问题。
本文采用分层方法探讨进路分配问题与列车作业缓冲时间的关系,取得较好效果。首先以列车运行计算数据为基础,考虑列车接发车作业占用进路的详细时间,建立进路分配问题的约束满足模型。然后提出评价进路分配方案的定量指标,并利用仿真方法分析进路分配方案的抗干扰性,最后提出根据评价指标对进路分配方案进行局部优化的可行性。主要研究内容和结论包括以下五个方面。
(1)构造列车作业时间窗重叠图模型。利用列车运行计算获取列车接发车作业占用轨道区段的时间窗信息,通过判断列车作业时间窗之间的关系,构造列车作业时间窗重叠图。利用该模型可以将列车作业按照时间窗重叠关系分为若干个簇,在求解进路分配问题时以这些簇为单位疏解列车作业的空间冲突。因此,列车作业时间窗重叠图模型可以将大规模的进路分配问题进行分解。
(2)建立进路分配问题的约束满足模型,并利用求解约束规划(ConstraintProgramming, CP)问题的启发式搜索方法疏解列车作业的空间冲突。约束条件分为硬约束和软约束两类,硬约束表示不可违反的约束条件,包括股道作业间隔时间约束和进路冲突约束；软约束表示偏好,包括上下行约束、列车等级引起的约束、列车接续引起的约束、动车组运用计划引起的约束。求解过程分为约束识别、值排序以及回溯搜索(Backtracking)三个步骤。
(3)建立评价进路分配方案的定量指标体系。指标主要包括“使用站台的偏好”、“缓冲时间数”、“最小缓冲时间”、“车站设备利用率”以及瓶颈和晚点传播等内容。由于列车停留的股道表明了旅客乘降及技术作业的可用站台,因此“列车分配最优股道的总权重”反映了车站为列车提供的服务水平。两项作业之间不存在缓冲时间表示它们是完全的平行作业,存在缓冲时间则表示相反情况,即前一项作业受到的扰动大于缓冲时间时,后一项作业就会被延误,因此“缓冲时间数,,表示进路分配方案中存在的潜在冲突数。“最小缓冲时间”是指进路分配方案中所有缓冲时间的最小值,它表示方案中最脆弱的两项作业,也表示整个方案能容忍的不引起晚点传播的最大扰动。“车站设备利用率”反映了股道与咽喉区轨道区段的利用率,根据这些指标可以发现车站平面图中对接发车作业构成瓶颈的道岔组或轨道区段。
(4)利用有色时间Petri网技术建立进路分配方案的动态模型,并进行扰动分析。接发车作业的基本单元是列车占用和释放轨道区段的活动,在构造列车活动模型的基础上,建立单列车作业模型、两列车作业模型以及大规模进路分配方案的分层Petri网模型。模型可以描述列车运行图、车站轨道区段与进路以及进路分配方案,列车作业缓冲时间被隐式包含在模型中。通过对模型中的列车活动施加扰动,并收集模型中的列车实际到发时间信息,就可以获取扰动造成的晚点传播,从而识别方案中的瓶颈,并利用列车晚点时间等信息比较方案的抗干扰性。
(5)基于实际车站平面图的案例分析表明缓冲时间的分布及大小是影响进路分配方案抗干扰性的根源,这一发现为进路分配方案的局部最优化及制定调车作业方案提供数据支撑。以包含1045条进路的车站平面图和持续时间为1小时的列车运行图为案例,利用既有的WNPP方法和本文的约束规划方法求解相同规模的问题,两种方法所得方案的最小缓冲时间分别为17秒和188秒。分别对两个方案施加360秒的扰动,约束规划方法所得方案中列车的平均出发晚点时间比WNPP方法所得方案中的列车晚点少35.07%,因此约束规划方法能得到抗干扰性较好的方案。这进一步验证了约束规划方法求解进路分配问题的有效性。
The large-scale passenger rail stations are normally the bottlenecks of executing the scheduled train services, such as the Guangzhou station, Wuhan Station Zhengzhou station, Beijing station and Chengdu station. The infrastructure needed by the scheduled arrival and departure events must be available and some level of service should be achieved. The level of service tends to decrease when the scheduled trains increase and the arrival/departure delays occur when station capacity can not satisfy the trains demand. However, the delay-tolerances for two routing schemes might be different when there is surplus station capacity. Therefore, close attention should be paid to achieving delay-tolerable routing schemes.
Routing trains through rail stations is a sub-problem of scheduling passenger trains, and the aim of the Route Allocation Problem (RAP) is to allocate platforms and conflict-free inbound/outbound routes to trains while satisfying the specific train operation guidelines and ensure the station operation safety. The RAP is imposed on many temporal and spatial constraints which are caused by train timetable and station layout. The existing objectives include maximizing the total weight of train grade, maximizing the effectiveness of the platform tracks, maximizing the total weight of routes and minimizing the total delays. Some literatures mention that there is an internal delay-tolerable ability for each Route Allocation Solution (RAS). However, the problem of finding delay-tolerable RAS is rarely investigated. So, the overall objective of the RAP is to find one or some robust RAS taking consider of stochastic disturbances to trains in real-life operations.
A hierarchical approach is adopted to tackle the above RAP and the expected results are obtained. Firstly, the constraints satisfying model of the RAP is built and the blocking times of the arrival and departure events are embedded in the model by train movement calculation. Secondly, a group of quantitative indices are put forward to evaluate the obtained RAS from the above model and a RAS from other approaches can also be evaluated according to the proposed indices. Then, a simulation models is constructed to analyze the delay-tolerance of the above solutions. Finally, the feasibility of locally optimizing a RAS is discussed based on the evaluation of the RAS. The main contents of the thesis are summarized as follows.
(1) The time-windows overlapping model for arrival and departure events of trains is constructed. The blocking times of the events are achieved by the train movement calculation and the relation of the time-windows for two events can be made clear. The arrival and departure events of trains can be divided into some cliques and the essence of the RAP is to resolve the routes conflicts between any two events in a clique. Therefore, the RAP can be decomposed into small parts by means of the here proposed model.
(2) The constraints satisfying model of the RAP is constructed and the heuristic searching for constraints programming (CP) is exploited to resolve the temporal conflicts among arrival and departure events. The constraints are divided into hard and soft ones. The former states the minimum interval between two events accessing the same platform-track and the constraints on two events accessing the same track section in throat areas, while the latter indicates the preference, including the constraints form the up-down rule, trains grade, trains connection and locomotives plans. Three steps, detecting constraints, ordering values and backtracking are followed to resolve the model.
(3) A group of quantitative indices is proposed to evaluate the obtained RAS. The indices cover the platform-tracks preference, the number of buffer times, the minimum buffer time and the infrastructure utilization. The platform-tracks preference indicates the level of service of trains. Two events are totally parallel if there is no buffer time between them, while the buffer time means the maximal perturbation which the former event can bear and will not cause delay propagation, therefore the number of buffer times is the number of potential conflicts in a RAS. The minimum buffer time means the weakest part of a RAS. The bottleneck area in the station layout can be discovered by means of the infrastructure utilization.
(4) The dynamic model of RAS is developed by the colored timed Petri Nets (CTPN) technology to simulate dynamic behavior of RAS. The train activity model, the single and double train model, and the hierarchical model for large-scale station layout are established. The buffer times are embedded in the model, and the bottlenecks in a RAS can be detected and some indices about delay propagation are also achieved by performing disturbances analysis.
(5) The cases study indicates that the buffer times is the root determining the delay-tolerance of a RAS and the finding provide data support to optimize a RAS locally and to make shunting plans. The cases based on a practical station layout with 1045 routes and a one-hour timetable show that the minimum buffer times in two RAS obtained by WNPP and CP are 17 seconds and 188 seconds. The average departure delays for the RAS obtained by CP is 35.07% less than that for the RAS achieved by WNPP when they suffer an average disturbance of 360 seconds. So, CP is an effective approach to resolve the RAP and can obtain relatively robust solutions.
铁路客运站的进路分配问题是编制旅客列车运行计划的一部分,目的是为运行图中的列车分配无冲突的进路和站台,同时满足车站作业和运输组织的要求。进路分配问题中包含由列车运行图和车站平面图引起的时间和空间约束,求解进路分配问题的一个基本要求是疏解列车作业之间的时空冲突,同时考虑车站设备利用以及列车服务水平,进路分配问题的解称为进路分配方案。既有方法中的目标函数包括列车等级总权重最大化、到发线运用效用最大化、分配进路总权重最大化以及列车晚点时间最小化等,部分研究提到进路分配方案与列车作业抗干扰性的关系问题,但未能充分考虑车站能力富余条件下以优化抗干扰性为目标的进路分配问题。
本文采用分层方法探讨进路分配问题与列车作业缓冲时间的关系,取得较好效果。首先以列车运行计算数据为基础,考虑列车接发车作业占用进路的详细时间,建立进路分配问题的约束满足模型。然后提出评价进路分配方案的定量指标,并利用仿真方法分析进路分配方案的抗干扰性,最后提出根据评价指标对进路分配方案进行局部优化的可行性。主要研究内容和结论包括以下五个方面。
(1)构造列车作业时间窗重叠图模型。利用列车运行计算获取列车接发车作业占用轨道区段的时间窗信息,通过判断列车作业时间窗之间的关系,构造列车作业时间窗重叠图。利用该模型可以将列车作业按照时间窗重叠关系分为若干个簇,在求解进路分配问题时以这些簇为单位疏解列车作业的空间冲突。因此,列车作业时间窗重叠图模型可以将大规模的进路分配问题进行分解。
(2)建立进路分配问题的约束满足模型,并利用求解约束规划(ConstraintProgramming, CP)问题的启发式搜索方法疏解列车作业的空间冲突。约束条件分为硬约束和软约束两类,硬约束表示不可违反的约束条件,包括股道作业间隔时间约束和进路冲突约束；软约束表示偏好,包括上下行约束、列车等级引起的约束、列车接续引起的约束、动车组运用计划引起的约束。求解过程分为约束识别、值排序以及回溯搜索(Backtracking)三个步骤。
(3)建立评价进路分配方案的定量指标体系。指标主要包括“使用站台的偏好”、“缓冲时间数”、“最小缓冲时间”、“车站设备利用率”以及瓶颈和晚点传播等内容。由于列车停留的股道表明了旅客乘降及技术作业的可用站台,因此“列车分配最优股道的总权重”反映了车站为列车提供的服务水平。两项作业之间不存在缓冲时间表示它们是完全的平行作业,存在缓冲时间则表示相反情况,即前一项作业受到的扰动大于缓冲时间时,后一项作业就会被延误,因此“缓冲时间数,,表示进路分配方案中存在的潜在冲突数。“最小缓冲时间”是指进路分配方案中所有缓冲时间的最小值,它表示方案中最脆弱的两项作业,也表示整个方案能容忍的不引起晚点传播的最大扰动。“车站设备利用率”反映了股道与咽喉区轨道区段的利用率,根据这些指标可以发现车站平面图中对接发车作业构成瓶颈的道岔组或轨道区段。
(4)利用有色时间Petri网技术建立进路分配方案的动态模型,并进行扰动分析。接发车作业的基本单元是列车占用和释放轨道区段的活动,在构造列车活动模型的基础上,建立单列车作业模型、两列车作业模型以及大规模进路分配方案的分层Petri网模型。模型可以描述列车运行图、车站轨道区段与进路以及进路分配方案,列车作业缓冲时间被隐式包含在模型中。通过对模型中的列车活动施加扰动,并收集模型中的列车实际到发时间信息,就可以获取扰动造成的晚点传播,从而识别方案中的瓶颈,并利用列车晚点时间等信息比较方案的抗干扰性。
(5)基于实际车站平面图的案例分析表明缓冲时间的分布及大小是影响进路分配方案抗干扰性的根源,这一发现为进路分配方案的局部最优化及制定调车作业方案提供数据支撑。以包含1045条进路的车站平面图和持续时间为1小时的列车运行图为案例,利用既有的WNPP方法和本文的约束规划方法求解相同规模的问题,两种方法所得方案的最小缓冲时间分别为17秒和188秒。分别对两个方案施加360秒的扰动,约束规划方法所得方案中列车的平均出发晚点时间比WNPP方法所得方案中的列车晚点少35.07%,因此约束规划方法能得到抗干扰性较好的方案。这进一步验证了约束规划方法求解进路分配问题的有效性。
The large-scale passenger rail stations are normally the bottlenecks of executing the scheduled train services, such as the Guangzhou station, Wuhan Station Zhengzhou station, Beijing station and Chengdu station. The infrastructure needed by the scheduled arrival and departure events must be available and some level of service should be achieved. The level of service tends to decrease when the scheduled trains increase and the arrival/departure delays occur when station capacity can not satisfy the trains demand. However, the delay-tolerances for two routing schemes might be different when there is surplus station capacity. Therefore, close attention should be paid to achieving delay-tolerable routing schemes.
Routing trains through rail stations is a sub-problem of scheduling passenger trains, and the aim of the Route Allocation Problem (RAP) is to allocate platforms and conflict-free inbound/outbound routes to trains while satisfying the specific train operation guidelines and ensure the station operation safety. The RAP is imposed on many temporal and spatial constraints which are caused by train timetable and station layout. The existing objectives include maximizing the total weight of train grade, maximizing the effectiveness of the platform tracks, maximizing the total weight of routes and minimizing the total delays. Some literatures mention that there is an internal delay-tolerable ability for each Route Allocation Solution (RAS). However, the problem of finding delay-tolerable RAS is rarely investigated. So, the overall objective of the RAP is to find one or some robust RAS taking consider of stochastic disturbances to trains in real-life operations.
A hierarchical approach is adopted to tackle the above RAP and the expected results are obtained. Firstly, the constraints satisfying model of the RAP is built and the blocking times of the arrival and departure events are embedded in the model by train movement calculation. Secondly, a group of quantitative indices are put forward to evaluate the obtained RAS from the above model and a RAS from other approaches can also be evaluated according to the proposed indices. Then, a simulation models is constructed to analyze the delay-tolerance of the above solutions. Finally, the feasibility of locally optimizing a RAS is discussed based on the evaluation of the RAS. The main contents of the thesis are summarized as follows.
(1) The time-windows overlapping model for arrival and departure events of trains is constructed. The blocking times of the events are achieved by the train movement calculation and the relation of the time-windows for two events can be made clear. The arrival and departure events of trains can be divided into some cliques and the essence of the RAP is to resolve the routes conflicts between any two events in a clique. Therefore, the RAP can be decomposed into small parts by means of the here proposed model.
(2) The constraints satisfying model of the RAP is constructed and the heuristic searching for constraints programming (CP) is exploited to resolve the temporal conflicts among arrival and departure events. The constraints are divided into hard and soft ones. The former states the minimum interval between two events accessing the same platform-track and the constraints on two events accessing the same track section in throat areas, while the latter indicates the preference, including the constraints form the up-down rule, trains grade, trains connection and locomotives plans. Three steps, detecting constraints, ordering values and backtracking are followed to resolve the model.
(3) A group of quantitative indices is proposed to evaluate the obtained RAS. The indices cover the platform-tracks preference, the number of buffer times, the minimum buffer time and the infrastructure utilization. The platform-tracks preference indicates the level of service of trains. Two events are totally parallel if there is no buffer time between them, while the buffer time means the maximal perturbation which the former event can bear and will not cause delay propagation, therefore the number of buffer times is the number of potential conflicts in a RAS. The minimum buffer time means the weakest part of a RAS. The bottleneck area in the station layout can be discovered by means of the infrastructure utilization.
(4) The dynamic model of RAS is developed by the colored timed Petri Nets (CTPN) technology to simulate dynamic behavior of RAS. The train activity model, the single and double train model, and the hierarchical model for large-scale station layout are established. The buffer times are embedded in the model, and the bottlenecks in a RAS can be detected and some indices about delay propagation are also achieved by performing disturbances analysis.
(5) The cases study indicates that the buffer times is the root determining the delay-tolerance of a RAS and the finding provide data support to optimize a RAS locally and to make shunting plans. The cases based on a practical station layout with 1045 routes and a one-hour timetable show that the minimum buffer times in two RAS obtained by WNPP and CP are 17 seconds and 188 seconds. The average departure delays for the RAS obtained by CP is 35.07% less than that for the RAS achieved by WNPP when they suffer an average disturbance of 360 seconds. So, CP is an effective approach to resolve the RAP and can obtain relatively robust solutions.
引文
[1]Aarts, E.J.L. Local Search in Combinatorial Optimization [M]. Princeton University Press, 2003.
[2]Abbink, E., van den Berg, B., Kroon, L., and Salomon, M. Allocation of railway rolling stock for passenger trains [J]. Transportation Science,2004,38(1):33-41.
[3]Abril, M., Barber, F., and et al. An assessment of railway capacity [J]. Transportation Research Part E,2008,44(5):774-806.
[4]Ahuja, R. K., Liu, J., Orlin, J. B., Sharma, D., and Shughart, L. A. Solving real-life locomotive-scheduling problems [J]. Transportation Science,2005,39(4):503-517.
[5]Alavi, Y., Lick, D. R., and Liu, J. Survey of double vertex graphs [J]. Graphs and Combinatorics,2002,18(4):709-715.
[6]Albrecht, T. The influence of anticipating train driving on the dispatching process in railway conflict situations [J]. Networks and Spatial Economics,2009,9(1):85-101.
[7]Allen, J. F. An Interval-Based Representation of Temporal Knowledge [J]. International Joint Conferences on Artificial Intelligence, Vancouver, Canada,1981,221-226.
[8]Assad, A.A., Modeling of rail networks:toward a routing/makeup model [J]. Transportation Research Part B,1980,14(1-2):101-114.
[9]Baker, K. R. Introduction to Sequencing and Scheduling [M]. New York, Wiley,1974.
[10]Baker, K. R., and Trietsch, D. Principles of sequencing and scheduling [M]. John Wiley and Sons,2009.
[11]Bartak, R. Constraint-based scheduling:an introduction for newcomers [R],2002,69-74.
[12]Bartak, R. Modeling soft constraints:a survey [J]. Neural Network World,2002,12(5): 421-431.
[13]Bendfeldt, J.P., Mohr, U., Muller, L. RailSys, a system to plan future railway needs [J]. Computers in railways VII,2000,249-255.
[14]Billaut, J.C., Moukrim, A., Sanlaville, E. Flexibility and robustness in scheduling [M], John Wiley& Sons, London,2008.
[15]Billionnet, A. Using integer programming to solve the train-platforming problem [J]. Transportation Science,2003,37(2):213-222.
[16]Bowden, F. D. J. A brief survey and synthesis of the roles of time in Petri nets [J]. Mathematical and Computer Modeling,2000,31(10):55-68.
[17]Burdett, R., and Kozan, E. A sequencing approach for creating new train timetables [J]. OR Spectrum,2010,32(1):163-193.
[18]Caprara, A., Kroon, L., Monaci, M., Peeters, M., Toth, P., Cynthia, B., and Gilbert, L. Chapter 3 Passenger railway optimization [A]. Handbooks in operations research and management science [M], Elsevier,2007,129-187.
[19]Cardillo, D.L., Nicola, D.M., k L-list [lambda] coloring of graphs. European Journal of Operational Research,1998,106(1):160-164.
[20]Carey, M. A model and strategy for train pathing with choice of lines, platforms, and routes [J]. Transportation Research Part B-Methodological,1994,28(5):333-353.
[21]Carey, M., and Carville, S. Scheduling and platforming trains at busy complex stations [J]. Transportation Research Part A:Policy and Practice,2003,37(3):195-224.
[22]Carey, M., and Lockwood, D. A model, algorithms and strategy for train pathing [J]. Journal of the Operational Research Society,1995,46(8):988-1005.
[23]Chakroborty, P., and Vikram, D. Optimum assignment of trains to platforms under partial schedule compliance [J]. Transportation Research Part B:Methodological,2008,42(2): 169-184.
[24]Cheng, Y.-H., and Yang, L.-A. A Fuzzy Petri Nets approach for railway traffic control in case of abnormality:Evidence from Taiwan railway system [J]. Expert Systems with Applications,2009,36(4):8040-8048.
[25]Chunhua, G, Johnson, E., and Smith, B. Integrated airline fleet and crew robust planning[J]. Transportation Science,2009,43(1):2-16.
[26]Cordeau, J. F., Soumis, F., and Desrosiers, J. A benders decomposition approach for the locomotive and car assignment problem [J]. Transportation Science,2000,34(2):133-149.
[27]Cordeau, J. F., Toth, P., and Vigo, D. A survey of optimization models for train routing and scheduling [J]. Transportation Science,1998,32(4):380-404.
[28]D'Ariano, A., Corman, F., Pacciarelli, D., and Pranzo, M. Reordering and local rerouting strategies to manage train traffic in Real time [J]. Transportation Science,2008,42(4): 405-419.
[29]Du, D.-Z. The maximum clique problem [A], Handbook of combinatorial optimization [M], Kluwer Academic Boston,1998,1-74.
[30]Garcia, A.M., Manrique, D., Rodriguez-Paton, A., and Sosik, P. A P system and a constructive membrane-inspired DNA algorithm for solving the Maximum Clique Problem [J]. Biosystems,2007,90(3):687-697.
[31]Garey, M. R. Computers and intractability:a guide to the theory of NP-completeness [M]. W. H. Freeman, New York,1979..
[32]Golumbic, M. C. Algorithmic graph theory and perfect graphs [M]. Elsevier,2004.
[33]Goverde, R. M. P. optimal Scheduling of connections in railway systems [J]. The 8th World Conference on Transport Research, Belgium,1998.
[34]Goverde, R. M. P. Railway timetable stability analysis using max-plus system theory [J]. Transportation Research Part B,2007,41(2):179-201.
[35]Graham, R. L., Lawler, E. L., Lenstra, J. K., Kan, A. H. G R., P.L. Hammer, E. L. J., and Korte, B. H. Optimization and approximation in deterministic sequencing and scheduling:a survey [J].Annals of Discrete Mathematics,1979,287-326.
[36]Hagalisletto, A. M., Bjork, J., Yu, I. C., and Enger, P. Constructing and refining large-scale railway models represented by Petri nets [J]. IEEE Transactions on Systems Man and Cybernetics Part C-Applications and Reviews,2007,37(4):444-460.
[37]Hart, P. E., Nilsson, N. J., and Raphael, B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on Systems Science and Cybernetics,1968,4(2): 100-107.
[38]Hebrard, E., Hnich, B., and Walsh, T. Robust solutions for constraint satisfaction and optimization [A]. European Conference on Artificial Intelligence,2004,186-190.
[39]Hell, P., and Nesetril, J. Coloring, constraint satisfaction, and complexity [J]. Computer Science Review,2008,2(3):143-163.
[40]Herroelen, W., and Leus, R. On the merits and pitfalls of critical chain scheduling [J]. Journal of Operations Management,2001,19(5):559-577.
[41]Ho, T.K., Mao, B.H., Yuan Z.Z., Liu, H.D., Fung, Y. F. Computer simulation and modeling in railway applications [J]. Computer Physics Communications,2002,143(1):1-10.
[42]Isaai, M. T., and Cassaigne, N. P. Predictive and reactive approaches to the train-scheduling problem:A knowledge management perspective [J]. IEEE Transactions on Systems Man and Cybernetics Part C-Applications and Reviews,2001,31(4):476-484.
[43]Ishibuchi, H.T.M. Multi-objective genetic local search algorithm and its application to flow shop scheduling [J]. IEEE Transactions on Systems, Man, and Cybernetics,1998,28(33): 392-403.
[44]Jensen, K., Kristensen, L., and Wells, L. Colored Petri nets and CPN tools for modeling and validation of concurrent systems [J]. International Journal on Software Tools for Technology Transfer (STTT),2007,9(3):213-254.
[45]Jia Wenzheng, Chen Shaokuan, Ho Tinkin, Mao Baohua and Bai Yun. A heuristic algorithm for fixed train runtime [C], International Conference on Railway Engineering, Hong Kong, 2008,230-236.
[46]Jia Wenzheng, Ho Tinkin, Mao Baohua. A study of heuristic approach on station track allocation in mainline railways[C], International Conference on Natural Computation, Tianjin,2009,575-579.
[47]Jia Wenzheng, Mao Baohua, Ho Tin-kin, Liu Haidong. Bottlenecks detection of track allocation schemes at rail hubs by Petri nets [J]. Journal of Transportation Systems Engineering and Information Technology,2009,9(6):136-141.
[48]Jia Wenzheng, Mao Baohua, Liu Haidong, Chen Shaokuan, and Ding Yong. Service robustness analysis of trains by a simulation method [C]. Proceedings of the Sixth International Conference on Traffic and Transportation Studies, Xi'an,2008,752-762.
[49]Karp, R. M. Reducibility among combinatorial problems [A], Complexity of computer computations [M], New York,1972,85-103.
[50]Kasiwa, N., Wada, M., SasaKi, M. The expert system of drawing a track layout [J]. Computers in Railways, Washington DC.1992,307-316.
[51]Kondrak, G, and van Beek, P. A theoretical evaluation of selected backtracking algorithms [J]. Artificial Intelligence,1997,89(1-2):365-387.
[52]Kouvelis, P. Robust discrete optimization and its applications [M]. Kluwer Academic Publishers,1997.
[53]Kroon, L. G., Edwin Romeijn, H., and Zwaneveld, P. J. Routing trains through railway stations:complexity issues [J]. European Journal of Operational Research,1997,98(3): 485-498.
[54]Kroon, L., Huisman, D., Abbink, E., Fioole, P.-J., Fischetti, M., Maroti, G, Schrijver, A., Steenbeek, A., and Ybema, R. The new Dutch timetable:the OR revolution [J]. Interfaces, 2009,39(1):6-17.
[55]Kuznetsova, A., and Strekalovsky, A. On solving the maximum clique problem [J]. Journal of Global Optimization,2001,21(3):265-288.
[56]Lawler, E. L., and Wood, D. E. Branch-and-bound methods:a survey [J]. Operations Research,1966,14(4):699-719.
[57]Liu, S. Q., and Kozan, E. Scheduling trains as a blocking parallel-machine job shop scheduling problem [J]. Computers& Operations Research,2009,36(10):2840-2852.
[58]Lotfi, V., and Sarin, S. A graph coloring algorithm for large scale scheduling problems [J]. Computers& Operations Research,1986,13(1):27-32.
[59]Miguel, I., and Shen, Q. Solution techniques for constraint satisfaction problems:Advanced approaches [J]. Artificial Intelligence Review,2001,15(4):269-293.
[60]Miguel, I., and Shen, Q. Solution techniques for constraint satisfaction problems: Foundations [J]. Artificial Intelligence Review,2001,15(4):243-267.
[61]Monigel, M. Formal representation of track topologies by double vertex graphs [J]. Computers in Railways, Washington DC,1992,359-370.
[62]Nait, S.M.A., Manier, M. A., El Moudni, A., and Manter, H. Performance analysis of a bus network based on Petri Nets and (Max,+) algebra [J]. Systems Analysis Modeling Simulation,2003,43(5):639-669.
[63]Nash, D. H. Railroad simulation using OpenTrack [J]. Computers in Railways IX.2004, 45-54
[64]Nie Lei, and Hansen, I.A. System analysis of train operations and track occupancy at railway stations[J]. European Journal of Transport and Infrastructure Research,2005,5(1): 31-54.
[65]Odijk, M. A. A constraint generation algorithm for the construction of periodic railway timetables [J]. Transportation Research Part B-Methodological,1996,30(6):455-464.
[66]Pachl, J. Railway operation and control [M]. VTD Rail Publishing,2004.
[67]Pal, M., and Bhattacharjee, G P. A sequential algorithm for finding a maximum weight K-independent set on interval graphs [J]. International Journal of Computer Mathematics, 1996,60(3-4):205-214.
[68]Peterson, J. L. Petri net theory and the modeling of systems [M]. Prentice Hall PTR,1981.
[69]Pullan, W. Optimization of un-weighted/weighted maximum independent sets and minimum vertex covers [J]. Discrete Optimization,2009,6(2):214-219.
[70]Rodriguez, J. A constraint programming model for real-time train scheduling at junctions [J]. Transportation Research Part B-Methodological,2007,41(2):231-245.
[71]Sahin, I. Railway traffic control and train scheduling based on inter-train conflict management [J]. Transportation Research Part B:Methodological,1999,33(7):511-534.
[72]Szpigel, B. Optimal train scheduling on a single track railway [A]. The Sixth IFORS International Conference on Operational Research, Dublin, Ireland,1973,334-351.
[73]Tomita, E., and Kameda, T. An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments [J]. Journal of Global Optimization,2007, 37(1):95-111.
[74]Tyrrall, D. The UK railway privatization:failing to succeed? Economic Affairs,2004,24(3): 32-38.
[75]Vaidyanathan, B., Ahuja, R. K., and Orlin, J. B. The Locomotive Routing Problem [J]. Transportation Science,2008,42(4):492-507.
[76]Vaidyanathan, B., Ahuja, R. K., Liu, J., and Shughart, L. A. A real-life locomotive planning: new formulations and computational results [J]. Transportation Research Part B-Methodological,2008,42(2):147-168.
[77]Vanderaalst, W. M. P., Odijk, M. A. Analysis of railway stations by means of interval timed colored Petri nets [J]. Real-Time Systems,1995,9(3):241-263.
[78]Watson, R. The effect of railway privatization on train planning:a case study of the UK [J]. Transport Reviews,2001,21(2):181-193.
[79]Wood, D. C. A technique for coloring a graph applicable to large scale timetabling problems [J]. The Computer Journal,1969,12(4):317-319.
[80]Wright, M. B. Applying stochastic algorithms to a locomotive scheduling problem [J]. Journal of the Operational Research Society,1989,40(2):187-192.
[81]Zhang, H. H., and Gu, M. Modeling job shop scheduling with batches and setup times by timed Petri nets [J]. Mathematical and Computer Modeling,2009,49(1-2):286-294.
[82]Zhou, X., and Zhong, M. Single-track train timetabling with guaranteed optimality: Branch-and-bound algorithms with enhanced lower bounds [J]. Transportation Research PartB:Methodological,2007,41(3):320-341.
[83]Ziarati, K., Soumis, F., Desrosiers, J., and Solomon, M. M. A branch-first, cut-second approach for locomotive assignment [J]. Management Science,1999,45(8):1156-1168.
[84]Ziarati, K., Soumis, F., Desrosiers, J., Gelinas, S., and Saintonge, A. Locomotive assignment with heterogeneous consists at CN North America [J]. European Journal of Operational Research,1997,97(2):281-292.
[85]Zwaneveld, P. J., Kroon, L. G, and van Hoesel, S. P. M. Routing trains through a railway station based on a node packing model [J]. European Journal of Operational Research,2001, 128(1):14-33.
[86]Zwaneveld, P. J., Kroon, L. G, Romeijn, H. E., Solomon, M., and et al. Routing trains through railway stations:model formulation and algorithms [J]. Transportation Science, 1996,30(3):181-194.
[87]巴博.双线铁路列车运行图缓冲时间优化分配研究[D].西南交通大学博士学位论文,2008.
[88]柏赞,毛保华,周方明,丁勇,董成兵.基于功耗分析的货物列车节能运行控制方法研究[J].交通运输系统工程与信息,2009,9(3)：43-50.
[89]曹桂均.保证车站调车作业安全的研究[A].铁道科学新进展——铁道科学研究院五十五周年论文集[C],2005.
[90]陈建鑫.客运专线车站作业计划协同优化方法研究[D].北京交通大学硕士学位论文,2008.
[91]陈军华,张星臣,俞文锦.基于稳定性的列车运行计划编制模型与算法[J].物流技术2009,28(3)：70-72.
[92]、陈军华.基于稳定性的客运专线运行图编制与评价问题研究[D].北京交通大学博士学位论文,2009.
[93]陈韬,吕红霞,王艳艳.客运专线车站作业计划编制系统的研究[J].铁道运输与经济, 2009,31(8)：12-14.
[94]陈团生,毛保华,高利平,岳芳.客运专线旅客出行选择行为分析[J].铁道学报,2007,29(3)：8-12.
[95]陈团生,毛保华,何宇强.旅客列车发车时间域优化研究[J].铁道学报,2006,28(4)：12-16.
[96]邓连波：客运专线相关旅客列车开行方案优化研究[D].中南大学博士学位论文,2007.
[97]丁亮.关于对客运专线大型客站到发线数量的分析[J].铁道经济研究,2009,5:28-30.
[98]丁勇,毛保华,刘海东,王铁城,张鑫.定时约束条件下列车节能操纵的仿真算法研究[J].系统仿真学报,2004,16(10)：2241-2244.
[99]杜文,文东.客运专线客运站通过能力仿真研究[J].西南交通大学学报,2006,41(5)：549-553.
[100]高世蕊.客运专线车站通过能力计算方法的研究[J].铁道运输与经济,2005,27(10)：92-94.
[101]高四维,高雅.调车作业量发生规律研究及选编模型优化[J].中国铁道科学,2005,26(6)：107-112.
[102]耿敬春,肖荣国,倪少权,牛会想.客运专线动车组周期性运用计划编制的研究.铁道学报,2006,28(4)：17-21.
[103]郭莉,吕红霞,陈焕云.基于遗传算法的铁路车站到发线运用优化研究[J].西南民族大学学报自然科学版,2005,31(1):28-31.
[104]郭佑民,王志伟,武福,程瑞琪.列车操纵与运行仿真系统[J].兰州铁道学院学报,2002,21(6)：124-128.
[105]郝立光,张星臣.列车流到发车站的均衡性评价方法研究[J].铁道学报,2000,22(5)：13-16.
[106]何世伟,宋瑞,胡安洲.编组站阶段计划刚性与柔性优化的协调研究[J].铁道学报,1999,21(4)：1-8.
[107]胡思继.列车运行图编制理论[M].北京：中国铁道出版社,2007.
[108]黄鉴.客运专线旅客列车开行方案研究[D].西南交通大学硕士学位论文,2005.
[109]蒋亚磊,陈邦,李文慧.客运专线列车运行图质量的模糊综合评判研究[J].兰州交通大学学报,2008,27(3)：81-84.
[110]金炜东,王自力.列车节能操纵优化方法研究[J].铁道学报,1997,19(6)：58-62.
[111]雷定猷,王栋,刘明翔.客运站股道运用优化模型及算法[J].交通运输工程学报,2007,7(5)：84-87.
[1 12]李磊,崔炳谋.基于混合算法的编组站到发线模型算法研究[J].交通运输工程与信息学报,2008,6(1)：86-90.
[113]李文权,杜文.铁路技术站日工作计划优化模型及算法[M].成都：西南交通大学出版社,2003.
[114]李文权,王炜,程世辉.铁路编组站到发线运用的排序模型和算法[J].系统工程理论与实践,2000,20(6)：75-78.
[115]林志安,潘玲巧.基于Memetic算法的客运站到发线分配问题研究[J].兰州交通大学学报,2008,27(6)：80-82.
[116]刘海东,毛保华,丁勇,何天健.列车自动驾驶仿真系统算法及其实施研究[J].系统仿真学报,2005,17(3)：577-580.
[117]刘海东,毛保华,丁勇,贾文峥,赖树坤.城市轨道交通列车节能问题及方案研究[J].交通运输系统工程与信息,2007,7(5)：68-73.
[118]刘海东,毛保华,何天健,丁勇,王璇.不同闭塞方式下城轨列车追踪运行过程及其仿真系统的研究[J].铁道学报,2005,27(2)：120-125.
[119]刘澜,王南,杜文.车站咽喉通过能力网络优化模型及算法研究[J].铁道学报,2002,24(6)：1-5.
[120]龙建成,高自友,马建军,李克平.铁路车站进路选择优化模型及求解算法的研究[J].铁道学报,2007,29(5)：7-14.
[121]鲁工圆,彭其渊,贺东.铁路技术站作业系统的仿真策略研究[J].交通运输工程与信息学报,2009,7(2)：55-61.
[122]鲁工圆.客运专线车站作业仿真系统的研究及应用[D].西南交通大学硕士学位论文,2008.
[123]吕红霞,何大可,陈韬.基于蚁群算法的客运站到发线运用计划编制方法[J].西南交通大学学报,2008,43(2)：153-158.
[124]吕红霞,倪少权,纪洪业.技术站调度决策支持系统的研究——到发线的合理使用[J].西南交通大学学报,2000,35(3)：255-258.
[125]马大炜,康熊.关于列车牵引计算的研究[J].中国铁路,2001,9：15-20.
[126]马建军,胡思继,许红.基于京沪高速铁路运行图的高速路网理论研究[J].铁道学报,2002,24(3)：1-4.
[127]马建军,许红,胡思继,陈祖信.京沪高速铁路列车运行图指标评价体系的研究[J].北方交通大学学报,2003,27(5)：46-50.
[128]马建军,周磊山,胡思继.计算机编制网状线路列车运行图系统研究[J].铁道学报,2000,22(1)：7-11.
[129]毛保华,何天健等.通用列车运行模拟软件系统研究[J].铁道学报,2000,22(1)：1-6.
[130]毛保华,王保山等.我国铁路列车运行计划集成编制方法研究[J].交通运输系统工程与信息,2009,9(2)：27-37.
[131]倪少权,吕红霞,杨明伦.全路列车运行图编制系统设计的研究[J].西南交通大学学报,2003,38(3)：332-335.
[132]聂磊,赵鹏,杨浩,胡安洲.高速铁路动车组运用的研究[J].铁道学报,2001,23(3)：1-7.
[133]聂磊.提高我国铁路列车运行图编制质量的方法研究[A].快速提升铁路建设与装备现代化技术促进铁路跨越式发展论文集[C],2004.
[134]彭其渊.客运专线运输组织[M].北京：科学出版社,2007a.
[135]彭其渊,王慈光.铁路行车组织[M].北京：中国铁道出版社,2007b.
[136]彭其渊,王培.网络列车运行图的数学模型及算法研究[J].铁道学报,2001,23(1)：1-8.
[137]彭其渊,闫海峰,石子明.计算机编制列车运行图的理论与方法[M].成都：西南交通大学出版社,2004a.
[138]彭其渊,闫海峰,魏德勇.武广客运专线运输组织模式研究[J].西南交通大学学报,2004b,39(6)：703-707.
[139]彭其渊,张羽成,李孟.列车运行图均衡性评价方法研究[J].西南交通大学学报,1998,33(4)：372-377.
[140]青学江,马国忠.遗传算法在区段站到发线的应用研究[J].西南交通大学学报,1998, 33(4)：387-393.
[141]石道华,丁勇,毛保华.基于设备能力利用的铁路运输服务水平研究[J].交通运输系统工程与信息,2003,3(1)：45-50.
[142]时颢.我国高速铁路列车运行图采用模式的分析[J].铁道学报,2000,22(1)：92-97.
[143]史峰,陈彦,秦进,周文梁.铁路客运站到发线运用和接发车进路排列方案综合优化[J].中国铁道科学,2009,30(6)：108-113.
[144]史峰,邓连波,黎新华,方琪根.客运专线相关旅客列车开行方案研究[J].铁道学报,2004,26(2):16-20.
[145]史峰,胡安洲.机车周转图的线性配置算法[J].铁道学报,1996,18(4):18-24.
[146]史峰,谢楚农,于桂芳.铁路车站咽喉区进路排列优化方法[J].铁道学报,2004,26(4)：5-9.
[147]孙全欣.铁路客运专线运输组织理论与方法研究[D].北京交通大学博士学位论文,2007.
[148]田长海.双线自动闭塞区段列车运行模拟系统的研究[A].全国青年管理科学与系统科学论文集[C],1993.
[149]汪波,杨浩,牛丰,王保华.周期运行图编制模型与算法研究[J].铁道学报,2007,29(5)：1-6.
[150]王成国,马大炜.高速列车操纵运行的数值仿真[J].中国铁道科学,2001,22(2)：32-40.
[151]王正彬,杜文.铁路技术站到发线运用调整模型及算法[J].西南交通大学学报,2006,41(2)：202-205.
[152]王正彬,杜文.车站阶段计划计算机调整系统的实现[J].铁道运输与经济,2008,30(1)：47-49.
[153]文超,闫海峰,陈芋宏.城际铁路车站不设到发线组织列车越行的研究[J].铁道运输与经济,2009,31(2)：16-18.
[154]项源金,陈定.车站通过能力的模拟计算方法[J].铁道学报,1985,7(2)：64-71.
[155]谢楚农,黎新华.铁路客运站到发线运用优化研究[J].中国铁道科学,2004,25(5)：130-133.
[156]谢美全,聂磊.周期性列车运行图编制模型研究[J].铁道学报,2009,31(4)：7-13.
[157]’徐杰,杜文,常军乾,文军,梁志杰.基于遗传算法的区段站到发线运用优化安排[J].中国铁道科学,2003a,24(2)：109-114.
[158]徐杰,杜文,李冰.铁路区段站到发线运用计划安排的优化算法[J].系统工程理论方法应用,2003b,12(3)：253-256.
[159]徐杰,杜文,刘春煌.区段站阶段计划自动编制模型和算法研究[J].中国铁道科学,2004,25(6)：134-136.
[160]徐瑞华,杜世敏,陈百磊.城市铁路枢纽布局的调整优化研究[J].同济大学学报自然科学版,2005a,33(5)：631-635.
[161]徐瑞华,徐浩,宋键.城市交通列车共线运营的通过能力和延误[J].同济大学学报自然科学版,2005b,33(3)：301-305.
[162]徐瑞华,邹晓磊.客运专线列车开行方案的优化方法研究[J].同济大学学报自然科学版,2005c,33(5)：1608-1611.
[163]徐行方,徐瑞华.高速客运专线列车运行组织相关问题的研究[J].同济大学学报自然科学版,2003,31(5)：572-575.
[164]徐意,田长海,方琪根.以客运为主单线铁路通过能力计算方法[J].中国铁道科学,2003,24(4)：127-129.
[165]许诚,徐瑞华,程维生,陈宣,吴翔.胶济铁路干线调度集中系统的研究[J].铁道学报,2007,29(1)：7-15.
[166]闫海峰,彭其渊,包维民.单线铁路会让站到发线数量的研究[J].西南交通大学学报,2002,37(4)：434-438.
[167]杨浩.铁路运输组织学[M].北京：中国铁道出版社,2006.
[168]杨涛.基于约束推理的车站咽喉图型识别及优化设计模型[J].铁道学报,2006,28(2)：2-6.
[169]杨意坚,何宇强.基于Max-plus方法的列车运行图稳定性评价[J].铁道学报,2009,31(4)：14-19.
[170]叶怀珍.高速铁路与既有线的衔接及车站股道数量的确定[J].铁道运输与经济,1996,31(4)：65-67.
[171]袁庆达,杜文,黎青松.区段站阶段计划的优化模型和算法[J].西南交通大学学报,2000,35(3)：250-254.
[172]曾鸣凯,黄鉴,彭其渊.客运专线旅客列车开行方案的客流分配方法[J].西南交通大学学报,2006,41(5)：571-574.
[173]赵鹏,富井规雄.动车组运用计划及其编制算法[J].铁道学报,2003,25(3)：1-7.
[174]赵鹏,富井规雄.基于路段交换的多基地动车组运用计划的编制算法[J].铁道学报,2004,26(1)：7-11.
[175]赵强.列车运行方案车站到发线需求可行性模型及其算法[J].西南交通大学学报,2000,35(2)：196-200.
[176]周成晨,杜文,王媛媛.客运专线车站列车接发仿真进路排列算法研究[J].铁道运输与经济,2009,31(9)：9-12.
[177]周方明,毛保华,柏赞,丁勇.基于串口通信的列车实时数据通信的设计[J].交通运输系统工程与信息,2009,9(4)：53-58.
[178]周磊山,胡思继.计算机编制网状线路列车运行图方法研究[J].铁道学报,1998,20(5)：15-21.
[2]Abbink, E., van den Berg, B., Kroon, L., and Salomon, M. Allocation of railway rolling stock for passenger trains [J]. Transportation Science,2004,38(1):33-41.
[3]Abril, M., Barber, F., and et al. An assessment of railway capacity [J]. Transportation Research Part E,2008,44(5):774-806.
[4]Ahuja, R. K., Liu, J., Orlin, J. B., Sharma, D., and Shughart, L. A. Solving real-life locomotive-scheduling problems [J]. Transportation Science,2005,39(4):503-517.
[5]Alavi, Y., Lick, D. R., and Liu, J. Survey of double vertex graphs [J]. Graphs and Combinatorics,2002,18(4):709-715.
[6]Albrecht, T. The influence of anticipating train driving on the dispatching process in railway conflict situations [J]. Networks and Spatial Economics,2009,9(1):85-101.
[7]Allen, J. F. An Interval-Based Representation of Temporal Knowledge [J]. International Joint Conferences on Artificial Intelligence, Vancouver, Canada,1981,221-226.
[8]Assad, A.A., Modeling of rail networks:toward a routing/makeup model [J]. Transportation Research Part B,1980,14(1-2):101-114.
[9]Baker, K. R. Introduction to Sequencing and Scheduling [M]. New York, Wiley,1974.
[10]Baker, K. R., and Trietsch, D. Principles of sequencing and scheduling [M]. John Wiley and Sons,2009.
[11]Bartak, R. Constraint-based scheduling:an introduction for newcomers [R],2002,69-74.
[12]Bartak, R. Modeling soft constraints:a survey [J]. Neural Network World,2002,12(5): 421-431.
[13]Bendfeldt, J.P., Mohr, U., Muller, L. RailSys, a system to plan future railway needs [J]. Computers in railways VII,2000,249-255.
[14]Billaut, J.C., Moukrim, A., Sanlaville, E. Flexibility and robustness in scheduling [M], John Wiley& Sons, London,2008.
[15]Billionnet, A. Using integer programming to solve the train-platforming problem [J]. Transportation Science,2003,37(2):213-222.
[16]Bowden, F. D. J. A brief survey and synthesis of the roles of time in Petri nets [J]. Mathematical and Computer Modeling,2000,31(10):55-68.
[17]Burdett, R., and Kozan, E. A sequencing approach for creating new train timetables [J]. OR Spectrum,2010,32(1):163-193.
[18]Caprara, A., Kroon, L., Monaci, M., Peeters, M., Toth, P., Cynthia, B., and Gilbert, L. Chapter 3 Passenger railway optimization [A]. Handbooks in operations research and management science [M], Elsevier,2007,129-187.
[19]Cardillo, D.L., Nicola, D.M., k L-list [lambda] coloring of graphs. European Journal of Operational Research,1998,106(1):160-164.
[20]Carey, M. A model and strategy for train pathing with choice of lines, platforms, and routes [J]. Transportation Research Part B-Methodological,1994,28(5):333-353.
[21]Carey, M., and Carville, S. Scheduling and platforming trains at busy complex stations [J]. Transportation Research Part A:Policy and Practice,2003,37(3):195-224.
[22]Carey, M., and Lockwood, D. A model, algorithms and strategy for train pathing [J]. Journal of the Operational Research Society,1995,46(8):988-1005.
[23]Chakroborty, P., and Vikram, D. Optimum assignment of trains to platforms under partial schedule compliance [J]. Transportation Research Part B:Methodological,2008,42(2): 169-184.
[24]Cheng, Y.-H., and Yang, L.-A. A Fuzzy Petri Nets approach for railway traffic control in case of abnormality:Evidence from Taiwan railway system [J]. Expert Systems with Applications,2009,36(4):8040-8048.
[25]Chunhua, G, Johnson, E., and Smith, B. Integrated airline fleet and crew robust planning[J]. Transportation Science,2009,43(1):2-16.
[26]Cordeau, J. F., Soumis, F., and Desrosiers, J. A benders decomposition approach for the locomotive and car assignment problem [J]. Transportation Science,2000,34(2):133-149.
[27]Cordeau, J. F., Toth, P., and Vigo, D. A survey of optimization models for train routing and scheduling [J]. Transportation Science,1998,32(4):380-404.
[28]D'Ariano, A., Corman, F., Pacciarelli, D., and Pranzo, M. Reordering and local rerouting strategies to manage train traffic in Real time [J]. Transportation Science,2008,42(4): 405-419.
[29]Du, D.-Z. The maximum clique problem [A], Handbook of combinatorial optimization [M], Kluwer Academic Boston,1998,1-74.
[30]Garcia, A.M., Manrique, D., Rodriguez-Paton, A., and Sosik, P. A P system and a constructive membrane-inspired DNA algorithm for solving the Maximum Clique Problem [J]. Biosystems,2007,90(3):687-697.
[31]Garey, M. R. Computers and intractability:a guide to the theory of NP-completeness [M]. W. H. Freeman, New York,1979..
[32]Golumbic, M. C. Algorithmic graph theory and perfect graphs [M]. Elsevier,2004.
[33]Goverde, R. M. P. optimal Scheduling of connections in railway systems [J]. The 8th World Conference on Transport Research, Belgium,1998.
[34]Goverde, R. M. P. Railway timetable stability analysis using max-plus system theory [J]. Transportation Research Part B,2007,41(2):179-201.
[35]Graham, R. L., Lawler, E. L., Lenstra, J. K., Kan, A. H. G R., P.L. Hammer, E. L. J., and Korte, B. H. Optimization and approximation in deterministic sequencing and scheduling:a survey [J].Annals of Discrete Mathematics,1979,287-326.
[36]Hagalisletto, A. M., Bjork, J., Yu, I. C., and Enger, P. Constructing and refining large-scale railway models represented by Petri nets [J]. IEEE Transactions on Systems Man and Cybernetics Part C-Applications and Reviews,2007,37(4):444-460.
[37]Hart, P. E., Nilsson, N. J., and Raphael, B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on Systems Science and Cybernetics,1968,4(2): 100-107.
[38]Hebrard, E., Hnich, B., and Walsh, T. Robust solutions for constraint satisfaction and optimization [A]. European Conference on Artificial Intelligence,2004,186-190.
[39]Hell, P., and Nesetril, J. Coloring, constraint satisfaction, and complexity [J]. Computer Science Review,2008,2(3):143-163.
[40]Herroelen, W., and Leus, R. On the merits and pitfalls of critical chain scheduling [J]. Journal of Operations Management,2001,19(5):559-577.
[41]Ho, T.K., Mao, B.H., Yuan Z.Z., Liu, H.D., Fung, Y. F. Computer simulation and modeling in railway applications [J]. Computer Physics Communications,2002,143(1):1-10.
[42]Isaai, M. T., and Cassaigne, N. P. Predictive and reactive approaches to the train-scheduling problem:A knowledge management perspective [J]. IEEE Transactions on Systems Man and Cybernetics Part C-Applications and Reviews,2001,31(4):476-484.
[43]Ishibuchi, H.T.M. Multi-objective genetic local search algorithm and its application to flow shop scheduling [J]. IEEE Transactions on Systems, Man, and Cybernetics,1998,28(33): 392-403.
[44]Jensen, K., Kristensen, L., and Wells, L. Colored Petri nets and CPN tools for modeling and validation of concurrent systems [J]. International Journal on Software Tools for Technology Transfer (STTT),2007,9(3):213-254.
[45]Jia Wenzheng, Chen Shaokuan, Ho Tinkin, Mao Baohua and Bai Yun. A heuristic algorithm for fixed train runtime [C], International Conference on Railway Engineering, Hong Kong, 2008,230-236.
[46]Jia Wenzheng, Ho Tinkin, Mao Baohua. A study of heuristic approach on station track allocation in mainline railways[C], International Conference on Natural Computation, Tianjin,2009,575-579.
[47]Jia Wenzheng, Mao Baohua, Ho Tin-kin, Liu Haidong. Bottlenecks detection of track allocation schemes at rail hubs by Petri nets [J]. Journal of Transportation Systems Engineering and Information Technology,2009,9(6):136-141.
[48]Jia Wenzheng, Mao Baohua, Liu Haidong, Chen Shaokuan, and Ding Yong. Service robustness analysis of trains by a simulation method [C]. Proceedings of the Sixth International Conference on Traffic and Transportation Studies, Xi'an,2008,752-762.
[49]Karp, R. M. Reducibility among combinatorial problems [A], Complexity of computer computations [M], New York,1972,85-103.
[50]Kasiwa, N., Wada, M., SasaKi, M. The expert system of drawing a track layout [J]. Computers in Railways, Washington DC.1992,307-316.
[51]Kondrak, G, and van Beek, P. A theoretical evaluation of selected backtracking algorithms [J]. Artificial Intelligence,1997,89(1-2):365-387.
[52]Kouvelis, P. Robust discrete optimization and its applications [M]. Kluwer Academic Publishers,1997.
[53]Kroon, L. G., Edwin Romeijn, H., and Zwaneveld, P. J. Routing trains through railway stations:complexity issues [J]. European Journal of Operational Research,1997,98(3): 485-498.
[54]Kroon, L., Huisman, D., Abbink, E., Fioole, P.-J., Fischetti, M., Maroti, G, Schrijver, A., Steenbeek, A., and Ybema, R. The new Dutch timetable:the OR revolution [J]. Interfaces, 2009,39(1):6-17.
[55]Kuznetsova, A., and Strekalovsky, A. On solving the maximum clique problem [J]. Journal of Global Optimization,2001,21(3):265-288.
[56]Lawler, E. L., and Wood, D. E. Branch-and-bound methods:a survey [J]. Operations Research,1966,14(4):699-719.
[57]Liu, S. Q., and Kozan, E. Scheduling trains as a blocking parallel-machine job shop scheduling problem [J]. Computers& Operations Research,2009,36(10):2840-2852.
[58]Lotfi, V., and Sarin, S. A graph coloring algorithm for large scale scheduling problems [J]. Computers& Operations Research,1986,13(1):27-32.
[59]Miguel, I., and Shen, Q. Solution techniques for constraint satisfaction problems:Advanced approaches [J]. Artificial Intelligence Review,2001,15(4):269-293.
[60]Miguel, I., and Shen, Q. Solution techniques for constraint satisfaction problems: Foundations [J]. Artificial Intelligence Review,2001,15(4):243-267.
[61]Monigel, M. Formal representation of track topologies by double vertex graphs [J]. Computers in Railways, Washington DC,1992,359-370.
[62]Nait, S.M.A., Manier, M. A., El Moudni, A., and Manter, H. Performance analysis of a bus network based on Petri Nets and (Max,+) algebra [J]. Systems Analysis Modeling Simulation,2003,43(5):639-669.
[63]Nash, D. H. Railroad simulation using OpenTrack [J]. Computers in Railways IX.2004, 45-54
[64]Nie Lei, and Hansen, I.A. System analysis of train operations and track occupancy at railway stations[J]. European Journal of Transport and Infrastructure Research,2005,5(1): 31-54.
[65]Odijk, M. A. A constraint generation algorithm for the construction of periodic railway timetables [J]. Transportation Research Part B-Methodological,1996,30(6):455-464.
[66]Pachl, J. Railway operation and control [M]. VTD Rail Publishing,2004.
[67]Pal, M., and Bhattacharjee, G P. A sequential algorithm for finding a maximum weight K-independent set on interval graphs [J]. International Journal of Computer Mathematics, 1996,60(3-4):205-214.
[68]Peterson, J. L. Petri net theory and the modeling of systems [M]. Prentice Hall PTR,1981.
[69]Pullan, W. Optimization of un-weighted/weighted maximum independent sets and minimum vertex covers [J]. Discrete Optimization,2009,6(2):214-219.
[70]Rodriguez, J. A constraint programming model for real-time train scheduling at junctions [J]. Transportation Research Part B-Methodological,2007,41(2):231-245.
[71]Sahin, I. Railway traffic control and train scheduling based on inter-train conflict management [J]. Transportation Research Part B:Methodological,1999,33(7):511-534.
[72]Szpigel, B. Optimal train scheduling on a single track railway [A]. The Sixth IFORS International Conference on Operational Research, Dublin, Ireland,1973,334-351.
[73]Tomita, E., and Kameda, T. An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments [J]. Journal of Global Optimization,2007, 37(1):95-111.
[74]Tyrrall, D. The UK railway privatization:failing to succeed? Economic Affairs,2004,24(3): 32-38.
[75]Vaidyanathan, B., Ahuja, R. K., and Orlin, J. B. The Locomotive Routing Problem [J]. Transportation Science,2008,42(4):492-507.
[76]Vaidyanathan, B., Ahuja, R. K., Liu, J., and Shughart, L. A. A real-life locomotive planning: new formulations and computational results [J]. Transportation Research Part B-Methodological,2008,42(2):147-168.
[77]Vanderaalst, W. M. P., Odijk, M. A. Analysis of railway stations by means of interval timed colored Petri nets [J]. Real-Time Systems,1995,9(3):241-263.
[78]Watson, R. The effect of railway privatization on train planning:a case study of the UK [J]. Transport Reviews,2001,21(2):181-193.
[79]Wood, D. C. A technique for coloring a graph applicable to large scale timetabling problems [J]. The Computer Journal,1969,12(4):317-319.
[80]Wright, M. B. Applying stochastic algorithms to a locomotive scheduling problem [J]. Journal of the Operational Research Society,1989,40(2):187-192.
[81]Zhang, H. H., and Gu, M. Modeling job shop scheduling with batches and setup times by timed Petri nets [J]. Mathematical and Computer Modeling,2009,49(1-2):286-294.
[82]Zhou, X., and Zhong, M. Single-track train timetabling with guaranteed optimality: Branch-and-bound algorithms with enhanced lower bounds [J]. Transportation Research PartB:Methodological,2007,41(3):320-341.
[83]Ziarati, K., Soumis, F., Desrosiers, J., and Solomon, M. M. A branch-first, cut-second approach for locomotive assignment [J]. Management Science,1999,45(8):1156-1168.
[84]Ziarati, K., Soumis, F., Desrosiers, J., Gelinas, S., and Saintonge, A. Locomotive assignment with heterogeneous consists at CN North America [J]. European Journal of Operational Research,1997,97(2):281-292.
[85]Zwaneveld, P. J., Kroon, L. G, and van Hoesel, S. P. M. Routing trains through a railway station based on a node packing model [J]. European Journal of Operational Research,2001, 128(1):14-33.
[86]Zwaneveld, P. J., Kroon, L. G, Romeijn, H. E., Solomon, M., and et al. Routing trains through railway stations:model formulation and algorithms [J]. Transportation Science, 1996,30(3):181-194.
[87]巴博.双线铁路列车运行图缓冲时间优化分配研究[D].西南交通大学博士学位论文,2008.
[88]柏赞,毛保华,周方明,丁勇,董成兵.基于功耗分析的货物列车节能运行控制方法研究[J].交通运输系统工程与信息,2009,9(3)：43-50.
[89]曹桂均.保证车站调车作业安全的研究[A].铁道科学新进展——铁道科学研究院五十五周年论文集[C],2005.
[90]陈建鑫.客运专线车站作业计划协同优化方法研究[D].北京交通大学硕士学位论文,2008.
[91]陈军华,张星臣,俞文锦.基于稳定性的列车运行计划编制模型与算法[J].物流技术2009,28(3)：70-72.
[92]、陈军华.基于稳定性的客运专线运行图编制与评价问题研究[D].北京交通大学博士学位论文,2009.
[93]陈韬,吕红霞,王艳艳.客运专线车站作业计划编制系统的研究[J].铁道运输与经济, 2009,31(8)：12-14.
[94]陈团生,毛保华,高利平,岳芳.客运专线旅客出行选择行为分析[J].铁道学报,2007,29(3)：8-12.
[95]陈团生,毛保华,何宇强.旅客列车发车时间域优化研究[J].铁道学报,2006,28(4)：12-16.
[96]邓连波：客运专线相关旅客列车开行方案优化研究[D].中南大学博士学位论文,2007.
[97]丁亮.关于对客运专线大型客站到发线数量的分析[J].铁道经济研究,2009,5:28-30.
[98]丁勇,毛保华,刘海东,王铁城,张鑫.定时约束条件下列车节能操纵的仿真算法研究[J].系统仿真学报,2004,16(10)：2241-2244.
[99]杜文,文东.客运专线客运站通过能力仿真研究[J].西南交通大学学报,2006,41(5)：549-553.
[100]高世蕊.客运专线车站通过能力计算方法的研究[J].铁道运输与经济,2005,27(10)：92-94.
[101]高四维,高雅.调车作业量发生规律研究及选编模型优化[J].中国铁道科学,2005,26(6)：107-112.
[102]耿敬春,肖荣国,倪少权,牛会想.客运专线动车组周期性运用计划编制的研究.铁道学报,2006,28(4)：17-21.
[103]郭莉,吕红霞,陈焕云.基于遗传算法的铁路车站到发线运用优化研究[J].西南民族大学学报自然科学版,2005,31(1):28-31.
[104]郭佑民,王志伟,武福,程瑞琪.列车操纵与运行仿真系统[J].兰州铁道学院学报,2002,21(6)：124-128.
[105]郝立光,张星臣.列车流到发车站的均衡性评价方法研究[J].铁道学报,2000,22(5)：13-16.
[106]何世伟,宋瑞,胡安洲.编组站阶段计划刚性与柔性优化的协调研究[J].铁道学报,1999,21(4)：1-8.
[107]胡思继.列车运行图编制理论[M].北京：中国铁道出版社,2007.
[108]黄鉴.客运专线旅客列车开行方案研究[D].西南交通大学硕士学位论文,2005.
[109]蒋亚磊,陈邦,李文慧.客运专线列车运行图质量的模糊综合评判研究[J].兰州交通大学学报,2008,27(3)：81-84.
[110]金炜东,王自力.列车节能操纵优化方法研究[J].铁道学报,1997,19(6)：58-62.
[111]雷定猷,王栋,刘明翔.客运站股道运用优化模型及算法[J].交通运输工程学报,2007,7(5)：84-87.
[1 12]李磊,崔炳谋.基于混合算法的编组站到发线模型算法研究[J].交通运输工程与信息学报,2008,6(1)：86-90.
[113]李文权,杜文.铁路技术站日工作计划优化模型及算法[M].成都：西南交通大学出版社,2003.
[114]李文权,王炜,程世辉.铁路编组站到发线运用的排序模型和算法[J].系统工程理论与实践,2000,20(6)：75-78.
[115]林志安,潘玲巧.基于Memetic算法的客运站到发线分配问题研究[J].兰州交通大学学报,2008,27(6)：80-82.
[116]刘海东,毛保华,丁勇,何天健.列车自动驾驶仿真系统算法及其实施研究[J].系统仿真学报,2005,17(3)：577-580.
[117]刘海东,毛保华,丁勇,贾文峥,赖树坤.城市轨道交通列车节能问题及方案研究[J].交通运输系统工程与信息,2007,7(5)：68-73.
[118]刘海东,毛保华,何天健,丁勇,王璇.不同闭塞方式下城轨列车追踪运行过程及其仿真系统的研究[J].铁道学报,2005,27(2)：120-125.
[119]刘澜,王南,杜文.车站咽喉通过能力网络优化模型及算法研究[J].铁道学报,2002,24(6)：1-5.
[120]龙建成,高自友,马建军,李克平.铁路车站进路选择优化模型及求解算法的研究[J].铁道学报,2007,29(5)：7-14.
[121]鲁工圆,彭其渊,贺东.铁路技术站作业系统的仿真策略研究[J].交通运输工程与信息学报,2009,7(2)：55-61.
[122]鲁工圆.客运专线车站作业仿真系统的研究及应用[D].西南交通大学硕士学位论文,2008.
[123]吕红霞,何大可,陈韬.基于蚁群算法的客运站到发线运用计划编制方法[J].西南交通大学学报,2008,43(2)：153-158.
[124]吕红霞,倪少权,纪洪业.技术站调度决策支持系统的研究——到发线的合理使用[J].西南交通大学学报,2000,35(3)：255-258.
[125]马大炜,康熊.关于列车牵引计算的研究[J].中国铁路,2001,9：15-20.
[126]马建军,胡思继,许红.基于京沪高速铁路运行图的高速路网理论研究[J].铁道学报,2002,24(3)：1-4.
[127]马建军,许红,胡思继,陈祖信.京沪高速铁路列车运行图指标评价体系的研究[J].北方交通大学学报,2003,27(5)：46-50.
[128]马建军,周磊山,胡思继.计算机编制网状线路列车运行图系统研究[J].铁道学报,2000,22(1)：7-11.
[129]毛保华,何天健等.通用列车运行模拟软件系统研究[J].铁道学报,2000,22(1)：1-6.
[130]毛保华,王保山等.我国铁路列车运行计划集成编制方法研究[J].交通运输系统工程与信息,2009,9(2)：27-37.
[131]倪少权,吕红霞,杨明伦.全路列车运行图编制系统设计的研究[J].西南交通大学学报,2003,38(3)：332-335.
[132]聂磊,赵鹏,杨浩,胡安洲.高速铁路动车组运用的研究[J].铁道学报,2001,23(3)：1-7.
[133]聂磊.提高我国铁路列车运行图编制质量的方法研究[A].快速提升铁路建设与装备现代化技术促进铁路跨越式发展论文集[C],2004.
[134]彭其渊.客运专线运输组织[M].北京：科学出版社,2007a.
[135]彭其渊,王慈光.铁路行车组织[M].北京：中国铁道出版社,2007b.
[136]彭其渊,王培.网络列车运行图的数学模型及算法研究[J].铁道学报,2001,23(1)：1-8.
[137]彭其渊,闫海峰,石子明.计算机编制列车运行图的理论与方法[M].成都：西南交通大学出版社,2004a.
[138]彭其渊,闫海峰,魏德勇.武广客运专线运输组织模式研究[J].西南交通大学学报,2004b,39(6)：703-707.
[139]彭其渊,张羽成,李孟.列车运行图均衡性评价方法研究[J].西南交通大学学报,1998,33(4)：372-377.
[140]青学江,马国忠.遗传算法在区段站到发线的应用研究[J].西南交通大学学报,1998, 33(4)：387-393.
[141]石道华,丁勇,毛保华.基于设备能力利用的铁路运输服务水平研究[J].交通运输系统工程与信息,2003,3(1)：45-50.
[142]时颢.我国高速铁路列车运行图采用模式的分析[J].铁道学报,2000,22(1)：92-97.
[143]史峰,陈彦,秦进,周文梁.铁路客运站到发线运用和接发车进路排列方案综合优化[J].中国铁道科学,2009,30(6)：108-113.
[144]史峰,邓连波,黎新华,方琪根.客运专线相关旅客列车开行方案研究[J].铁道学报,2004,26(2):16-20.
[145]史峰,胡安洲.机车周转图的线性配置算法[J].铁道学报,1996,18(4):18-24.
[146]史峰,谢楚农,于桂芳.铁路车站咽喉区进路排列优化方法[J].铁道学报,2004,26(4)：5-9.
[147]孙全欣.铁路客运专线运输组织理论与方法研究[D].北京交通大学博士学位论文,2007.
[148]田长海.双线自动闭塞区段列车运行模拟系统的研究[A].全国青年管理科学与系统科学论文集[C],1993.
[149]汪波,杨浩,牛丰,王保华.周期运行图编制模型与算法研究[J].铁道学报,2007,29(5)：1-6.
[150]王成国,马大炜.高速列车操纵运行的数值仿真[J].中国铁道科学,2001,22(2)：32-40.
[151]王正彬,杜文.铁路技术站到发线运用调整模型及算法[J].西南交通大学学报,2006,41(2)：202-205.
[152]王正彬,杜文.车站阶段计划计算机调整系统的实现[J].铁道运输与经济,2008,30(1)：47-49.
[153]文超,闫海峰,陈芋宏.城际铁路车站不设到发线组织列车越行的研究[J].铁道运输与经济,2009,31(2)：16-18.
[154]项源金,陈定.车站通过能力的模拟计算方法[J].铁道学报,1985,7(2)：64-71.
[155]谢楚农,黎新华.铁路客运站到发线运用优化研究[J].中国铁道科学,2004,25(5)：130-133.
[156]谢美全,聂磊.周期性列车运行图编制模型研究[J].铁道学报,2009,31(4)：7-13.
[157]’徐杰,杜文,常军乾,文军,梁志杰.基于遗传算法的区段站到发线运用优化安排[J].中国铁道科学,2003a,24(2)：109-114.
[158]徐杰,杜文,李冰.铁路区段站到发线运用计划安排的优化算法[J].系统工程理论方法应用,2003b,12(3)：253-256.
[159]徐杰,杜文,刘春煌.区段站阶段计划自动编制模型和算法研究[J].中国铁道科学,2004,25(6)：134-136.
[160]徐瑞华,杜世敏,陈百磊.城市铁路枢纽布局的调整优化研究[J].同济大学学报自然科学版,2005a,33(5)：631-635.
[161]徐瑞华,徐浩,宋键.城市交通列车共线运营的通过能力和延误[J].同济大学学报自然科学版,2005b,33(3)：301-305.
[162]徐瑞华,邹晓磊.客运专线列车开行方案的优化方法研究[J].同济大学学报自然科学版,2005c,33(5)：1608-1611.
[163]徐行方,徐瑞华.高速客运专线列车运行组织相关问题的研究[J].同济大学学报自然科学版,2003,31(5)：572-575.
[164]徐意,田长海,方琪根.以客运为主单线铁路通过能力计算方法[J].中国铁道科学,2003,24(4)：127-129.
[165]许诚,徐瑞华,程维生,陈宣,吴翔.胶济铁路干线调度集中系统的研究[J].铁道学报,2007,29(1)：7-15.
[166]闫海峰,彭其渊,包维民.单线铁路会让站到发线数量的研究[J].西南交通大学学报,2002,37(4)：434-438.
[167]杨浩.铁路运输组织学[M].北京：中国铁道出版社,2006.
[168]杨涛.基于约束推理的车站咽喉图型识别及优化设计模型[J].铁道学报,2006,28(2)：2-6.
[169]杨意坚,何宇强.基于Max-plus方法的列车运行图稳定性评价[J].铁道学报,2009,31(4)：14-19.
[170]叶怀珍.高速铁路与既有线的衔接及车站股道数量的确定[J].铁道运输与经济,1996,31(4)：65-67.
[171]袁庆达,杜文,黎青松.区段站阶段计划的优化模型和算法[J].西南交通大学学报,2000,35(3)：250-254.
[172]曾鸣凯,黄鉴,彭其渊.客运专线旅客列车开行方案的客流分配方法[J].西南交通大学学报,2006,41(5)：571-574.
[173]赵鹏,富井规雄.动车组运用计划及其编制算法[J].铁道学报,2003,25(3)：1-7.
[174]赵鹏,富井规雄.基于路段交换的多基地动车组运用计划的编制算法[J].铁道学报,2004,26(1)：7-11.
[175]赵强.列车运行方案车站到发线需求可行性模型及其算法[J].西南交通大学学报,2000,35(2)：196-200.
[176]周成晨,杜文,王媛媛.客运专线车站列车接发仿真进路排列算法研究[J].铁道运输与经济,2009,31(9)：9-12.
[177]周方明,毛保华,柏赞,丁勇.基于串口通信的列车实时数据通信的设计[J].交通运输系统工程与信息,2009,9(4)：53-58.
[178]周磊山,胡思继.计算机编制网状线路列车运行图方法研究[J].铁道学报,1998,20(5)：15-21.