《客运专线旅客列车开行方案优化研究课件》由会员分享，可在线阅读，更多相关《客运专线旅客列车开行方案优化研究课件（29页珍藏版）》请在金锄头文库上搜索。
1、客运专线旅客列车开行方案优化研究研究内容研究内容研究目的研究目的 从客运专线旅客列车开行方案形成的整个过程出发，从运量从客运专线旅客列车开行方案形成的整个过程出发，从运量预测、开行方案优化和运行图编制三个主要环节入手，对客运专预测、开行方案优化和运行图编制三个主要环节入手，对客运专线旅客列车开行方案进行整体协调优化，为客运专线的设计、建线旅客列车开行方案进行整体协调优化，为客运专线的设计、建设、运营提供更加科学可靠的理论依据。设、运营提供更加科学可靠的理论依据。研究内容研究内容研究进展和现状分析，总结存在的问题和不足研究进展和现状分析，总结存在的问题和不足研究问题总体描述；阐述运量预测与列车开
2、行方案制定之间研究问题总体描述；阐述运量预测与列车开行方案制定之间的联系。的联系。影响因素分析；旅客候车和中转换乘时间确定影响因素分析；旅客候车和中转换乘时间确定客车开行方案优化模型的建立和推广客车开行方案优化模型的建立和推广遗传算法设计遗传算法设计运行图编制的模型和算法设计运行图编制的模型和算法设计研究现状研究现状旅客列车开行方案优化的研究旅客列车开行方案优化的研究运量预测的研究运量预测的研究旅客列车方案图编制的研究旅客列车方案图编制的研究计算机辅助系统的研究计算机辅助系统的研究研究中存在的问题研究中存在的问题客车开行方案包括的内容较多，以往的研究工作多以某一客车开行方案包括的内容较多，以往
3、的研究工作多以某一方面作为研究对象，不够全面；方面作为研究对象，不够全面；很少用到优化的方法来解决实际工作中的问题，只停留在很少用到优化的方法来解决实际工作中的问题，只停留在理论研究阶段；理论研究阶段；认识到了开行方案与客流预测和运行图编制之间的关系，认识到了开行方案与客流预测和运行图编制之间的关系，但鉴于三者的复杂程度，并没有进行全面的深入研究；但鉴于三者的复杂程度，并没有进行全面的深入研究；不论在理论研究方面，还是实际应用中，都没有形成一套不论在理论研究方面，还是实际应用中，都没有形成一套完整的体系。完整的体系。研究问题的总体描述研究问题的总体描述 列车开行方案的内容列车开行方案的内容列车
4、运行特性列车运行特性起讫点、运行径路、途中停站方起讫点、运行径路、途中停站方案等；案等；列车性质列车性质列车等级、种类、数量等；列车等级、种类、数量等；设备利用情况设备利用情况列车编组内容、车底运用、客座列车编组内容、车底运用、客座利用等。利用等。列车开行方案的形成过程列车开行方案的形成过程客流客流OD的生成与分析的生成与分析前提和基础；前提和基础；列车开行方案的制定与优化；列车开行方案的制定与优化；旅客列车方案运行图编制旅客列车方案运行图编制方案的最终形成和具方案的最终形成和具体实施。体实施。开行方案形成过程的对应工作开行方案形成过程的对应工作 运量预测阶段需要的列车服务属性，是在客流输送方
5、案制定运量预测阶段需要的列车服务属性，是在客流输送方案制定后才产生的，而且是在运行图编制以后才被确定的；后才产生的，而且是在运行图编制以后才被确定的；客流输送方案制定阶段所需要的客流参数，是通过客流预测客流输送方案制定阶段所需要的客流参数，是通过客流预测得到的；得到的；运行图编制阶段所需要的列车参数，必须要在列车输送方案运行图编制阶段所需要的列车参数，必须要在列车输送方案优化后才能得到。优化后才能得到。 子过程子过程 需要相关参数需要相关参数 相关优化内容相关优化内容 相关优化结果相关优化结果 运量运量预测预测 服务属性（旅行时间、服务属性（旅行时间、候车时间、服务频率等）候车时间、服务频率等
6、） 客流预测客流预测路网配流路网配流 客流客流OD、客流密度、客流密度高峰客流分布等高峰客流分布等 客流输送客流输送方案制定方案制定客流参数、运行径路、列车能力客流参数、运行径路、列车能力利用参数、时间消耗参数等利用参数、时间消耗参数等 列车输送方案列车输送方案客流搭乘方案客流搭乘方案列车数量、起讫点列车数量、起讫点途中停站途中停站运行图运行图编制编制 列车参数等列车参数等 运行图铺画运行图铺画动车组周转动车组周转 列车旅行、停站、接续时间；列车旅行、停站、接续时间；服务频率；车组周转及数量服务频率；车组周转及数量 开行方案的优化方式开行方案的优化方式列车开行方案单独优化列车开行方案单独优化列
7、车开行方案与运行图编列车开行方案与运行图编制两个阶段的综合优化制两个阶段的综合优化列车开行方案与客流列车开行方案与客流OD生生成两个阶段的综合优化成两个阶段的综合优化三个阶段的整体综合优化三个阶段的整体综合优化采用统一的综合优化模型采用统一的综合优化模型和算法来实现和算法来实现任何一个都是复杂的优任何一个都是复杂的优化问题，统一后复杂程化问题，统一后复杂程度将大大提高度将大大提高三项工作由不同部门分三项工作由不同部门分别独立完成的，将其融别独立完成的，将其融为一体难度相当大为一体难度相当大采用各个阶段顺序优化、采用各个阶段顺序优化、循环迭代的形式循环迭代的形式 服务属性（旅行时间、候车时间、服
8、务频率等）运量预测客流OD、客流密度；高峰客流分布等客流输送方案制定运行径路、能力利用参数列车数量、起讫点、途中停站方案运行图编制列车旅行、停站、接续时间；服务频率车站参数、线路参数等初始参数客运专线旅客列车开行方案优化过程关系图客运专线旅客列车开行方案优化过程关系图时间消耗参数社会经济参数、成本参数、路网参数运量预测运量预测 用伯克森泰尔法估计LOGIT模型中效用函数的系数直接需求模型各OD中各种运输方式未来年度无客运专线条件下总运量预测运量分配模型诱发运量预测模型各OD中各种运输方式未来年度有客运专线条件下总运量预测各OD中各种运输方式未来年度市场份额的预测各OD中未来年度客运专线运量的预
9、测各OD点社会经济参数调查运量预测过程框图运量预测过程框图 模型结构中都包含有广义费用，客运专线运量预模型结构中都包含有广义费用，客运专线运量预测的结果取决于其服务属性。测的结果取决于其服务属性。（1）旅行时间）旅行时间（2）旅客进出站时间、费用）旅客进出站时间、费用（3）旅客在站等候时间）旅客在站等候时间（4）运价水平）运价水平从国民经济、生活水平、支付能力、比从国民经济、生活水平、支付能力、比价关系，以及客运专线技术经济特性和优势几个方面综合确价关系，以及客运专线技术经济特性和优势几个方面综合确定。定。（5）旅客时间价值）旅客时间价值通过统计数据运用效用函数模型标通过统计数据运用效用函数模
10、型标定基年旅客时间价值，预测年度时间价值增长率按客运专线定基年旅客时间价值，预测年度时间价值增长率按客运专线影响区影响区GDP的平均增长速度确定。的平均增长速度确定。 旅行时间、候车时间必须通过客运专线列车开行旅行时间、候车时间必须通过客运专线列车开行方案的制定才能精确得到。方案的制定才能精确得到。影响因素分析影响因素分析基本原则基本原则 以客流为依据，城市（车站）为基点，充分利用现有设备（线路和车辆），努力提高以客流为依据，城市（车站）为基点，充分利用现有设备（线路和车辆），努力提高客运专线旅客列车开行方案的经济效益和社会效益。客运专线旅客列车开行方案的经济效益和社会效益。影响因素分析影响因
11、素分析客流及列车径路客流及列车径路 客流客流OD客流径路客流径路列车径路列车径路列车编成及线路能力列车编成及线路能力区间最大通过能力：最小追踪间隔时间、列车种类区间最大通过能力：最小追踪间隔时间、列车种类列车编成：列车运行距离、运行径路上沿途车站到发线有效长、站台长度、牵出线长度、动车列车编成：列车运行距离、运行径路上沿途车站到发线有效长、站台长度、牵出线长度、动车组单元类型、牵引供电水平、追踪间隔时间、线路能力组单元类型、牵引供电水平、追踪间隔时间、线路能力公交化运营组织方式，保证较高的服务频率，采用相对固定、较小编组的形式公交化运营组织方式，保证较高的服务频率，采用相对固定、较小编组的形式
12、 确定：线路能力确定：线路能力最大客流密度区段高峰小时客流量最大客流密度区段高峰小时客流量列车编成列车编成定员定员经济效益经济效益经济效益主要来自于客票收入；旅客列车经济效益核算方法都要确定出客运总成本；总成本、经济效益主要来自于客票收入；旅客列车经济效益核算方法都要确定出客运总成本；总成本、票价和列车定员确定后，总利润与客座利用率之间存在关系：票价和列车定员确定后，总利润与客座利用率之间存在关系：总利润总利润=客票单价客票单价列车输送客座能力列车输送客座能力客座率客运总成本客座率客运总成本上座率提高上座率提高铁路收入增加铁路收入增加旅客服务水平下降旅客服务水平下降铁路收入下降铁路收入下降保证
13、铁路收入和旅客服务水平保证铁路收入和旅客服务水平确定合理的列车客座利用率确定合理的列车客座利用率旅行时间旅行时间社会效益的体现社会效益的体现旅客候车时间消耗旅客候车时间消耗候车集结到达过程候车集结到达过程列车停站时间消耗列车停站时间消耗列车停站方案；同等级车站的途中停站时间基本相同列车停站方案；同等级车站的途中停站时间基本相同列车运行时间消耗列车运行时间消耗列车技术速度，取决于列车等级列车技术速度，取决于列车等级旅客换乘时间消耗旅客换乘时间消耗列车服务频率及相互列车的接续时间列车服务频率及相互列车的接续时间始发客流候车集结过程分析始发客流候车集结过程分析始发客流候车集结过程的特点及其数学描述始
14、发客流候车集结过程的特点及其数学描述客流到达的随机过程描述客流到达的随机过程描述 客流到达客流到达简单计数过程简单计数过程齐次泊松过程齐次泊松过程到达间隔的随机描述到达间隔的随机描述 在客流的集结过程是具有强度在客流的集结过程是具有强度的齐次泊松过程时，则其到达间隔时间的齐次泊松过程时，则其到达间隔时间 是服从指数分布的随机变量序列。是服从指数分布的随机变量序列。到达数量的随机描述到达数量的随机描述 客流的集结到达过程客流的集结到达过程标值点过程标值点过程候车集结时间的确定候车集结时间的确定 ， ；假设；假设 的期望值收敛，记为的期望值收敛，记为 。结论结论 每个旅客所消耗的平均候车集结时间为
15、每个旅客所消耗的平均候车集结时间为 可用平均上座率来描述，可用平均上座率来描述，T 可用列车服务频率来描述。可用列车服务频率来描述。 门到站的时间消耗、购票等其他的额外消耗，暂不考虑。门到站的时间消耗、购票等其他的额外消耗，暂不考虑。时间消耗与列车服务频率的关系分析时间消耗与列车服务频率的关系分析候车时间消耗与列车服务频率的关系分析候车时间消耗与列车服务频率的关系分析旅客全天候候车旅客全天候候车 假定整个过程的持续时间从前日最后一列可服务于客流的列车出发时起，假定整个过程的持续时间从前日最后一列可服务于客流的列车出发时起，到今日最后一列可服务于客流的列车出发时止。候车集结时间消耗完全取决于到今
16、日最后一列可服务于客流的列车出发时止。候车集结时间消耗完全取决于列车的分布情况。在平均分布时有：列车的分布情况。在平均分布时有：旅客只在日间行车时间段内候车旅客只在日间行车时间段内候车旅客只在同类列车间隔时间内候车旅客只在同类列车间隔时间内候车 或或中转换乘时间消耗与列车服务频率的关系分析中转换乘时间消耗与列车服务频率的关系分析 在平均分布情况下，在平均分布情况下， 当到达列车数为当到达列车数为 nu ，出发列车数为，出发列车数为 nv 时，平均旅客时，平均旅客中转时间为中转时间为 td/2nv，它与到达的列车数量是无关的。，它与到达的列车数量是无关的。 列车开行方案优化模型构建列车开行方案优
17、化模型构建 最优的旅客列车开行方案（始发站、终到站、途中停站方案）总要对应最优最优的旅客列车开行方案（始发站、终到站、途中停站方案）总要对应最优客流输送方案（旅客出行方式选择问题）客流输送方案（旅客出行方式选择问题）相关边界假定相关边界假定单向性假设单向性假设直线型客运专线某一个方向的列车开行方案优化直线型客运专线某一个方向的列车开行方案优化确定性假设确定性假设客流客流OD、列车径路、列车定员、上座率是确定、列车径路、列车定员、上座率是确定相似性假设相似性假设列车区间运行时间、定员相同列车区间运行时间、定员相同能力假设能力假设区间通过能力已确定，车站能力不产生约束区间通过能力已确定，车站能力不
18、产生约束客流理性假设客流理性假设出行方式的选择只取决于开行方案出行方式的选择只取决于开行方案系统封闭性假设系统封闭性假设系统状态的变化只取决于内部影响因素系统状态的变化只取决于内部影响因素列车类型及组合输送方案的描述列车类型及组合输送方案的描述 车站的有序集合；列车种类集合；途中停站集合车站的有序集合；列车种类集合；途中停站集合 路段集合；路段集合； 列车接续方案；中转站集合列车接续方案；中转站集合 路段列车乘车方案关联矩阵；路段列车乘车方案关联矩阵； 客流输送方案中转站点关联矩阵客流输送方案中转站点关联矩阵 始发站点乘车方案关联矩阵始发站点乘车方案关联矩阵 ； 始发站点列车乘车方案矩阵始发站
19、点列车乘车方案矩阵 决策变量的定义决策变量的定义 Xijk以以i为为O点，点，j为为D点的选择乘车方案点的选择乘车方案Lk的旅客数量的旅客数量优化目标优化目标铁路部门经济效益：合理的上座率来保障铁路部门经济效益：合理的上座率来保障约束条件（目标约束法）；约束条件（目标约束法）；旅客出行成本：票价和时间成本旅客出行成本：票价和时间成本 所有旅客在途时间总和最短所有旅客在途时间总和最短优化目标优化目标运行时间消耗运行时间消耗停站时间消耗停站时间消耗始发候车集结时间消耗始发候车集结时间消耗中转时间消耗中转时间消耗 通过前述的各种集合和关联矩阵，通过前述的各种集合和关联矩阵， 可以描述出各种列车的数量
20、、旅客停站及次数、可以描述出各种列车的数量、旅客停站及次数、 旅客中转站及次数，进而得到各种时间消耗。旅客中转站及次数，进而得到各种时间消耗。约束条件约束条件客流约束、区间通过约束、列车服务能力约束客流约束、区间通过约束、列车服务能力约束方案可行性约束、变量取值约束方案可行性约束、变量取值约束模型特点模型特点模型为非线性整数规划问题，非线性都集中表现在目标函数模型为非线性整数规划问题，非线性都集中表现在目标函数模型存在如下组合优化的特点模型存在如下组合优化的特点列车由沿途经由站点的组合形式描述列车由沿途经由站点的组合形式描述接续方案由列车的组合描述接续方案由列车的组合描述旅客的出行由接续方案的
21、组合来描述旅客的出行由接续方案的组合来描述由于没有涉及到运行图的实际编制问题，很多参数都采用了假设或平均值由于没有涉及到运行图的实际编制问题，很多参数都采用了假设或平均值求解非常困难求解非常困难采用现代优化算法采用现代优化算法模型的进一步推广模型的进一步推广网状线路结构的推广网状线路结构的推广 分解算法：分解算法：直线型线路上单方向旅客列车开行方案的优化问题直线型线路上单方向旅客列车开行方案的优化问题各线路旅客列车开行方案在衔接站的协调优化问题各线路旅客列车开行方案在衔接站的协调优化问题 静态模型，不涉及连续性时间参数和变量，较计算机编静态模型，不涉及连续性时间参数和变量，较计算机编图更适合采
22、用。图更适合采用。 必须对列车集合在整个线路结构上统一确定，列车的运必须对列车集合在整个线路结构上统一确定，列车的运行方向不会对问题造成影响。行方向不会对问题造成影响。跨线列车和跨线客流的处理跨线列车和跨线客流的处理长途跨线客流，自然形成换乘，转化为衔接站上的本线长途跨线客流，自然形成换乘，转化为衔接站上的本线客流；客流；短途跨线客流，具备分离条件的（已确定了列车类型为短途跨线客流，具备分离条件的（已确定了列车类型为B类，由既有线的列车开行方案已确定了其输送方案的除类，由既有线的列车开行方案已确定了其输送方案的除外）可以与本线客流分开考虑，单独进行优化求解；外）可以与本线客流分开考虑，单独进行
23、优化求解；短途跨线客流，若不可分离，可按研究线路的拆分形式短途跨线客流，若不可分离，可按研究线路的拆分形式进行拆分，转化为接入站上的本线客流进行统一的优化进行拆分，转化为接入站上的本线客流进行统一的优化计算，而后与其他部分合并后确定列车形式。计算，而后与其他部分合并后确定列车形式。算法设计算法设计遗传算法介绍遗传算法介绍启发式随机搜索技术启发式随机搜索技术编码原则编码原则完备性、健全性、非冗余性完备性、健全性、非冗余性 收敛性收敛性全局最优算法全局最优算法时间复杂度时间复杂度O(O(f)nlnn) GA欺骗问题欺骗问题约束条件的处理约束条件的处理抛弃不可行解方法、基于智能编码的方法、抛弃不可行
24、解方法、基于智能编码的方法、改变遗传算子法、修补方法、罚函数法改变遗传算子法、修补方法、罚函数法DCPM法法保留部分不可行解保留部分不可行解方案优化模型转换方案优化模型转换求解思路：求解思路：用列车开行方案用列车开行方案Xi代替代替xijk构造构造Xi下的列车运行网络下的列车运行网络Gi(Vi,Ei,Ci,Hi,Pi)在在Gi上得到客流上得到客流N=nij的最优分配方案的最优分配方案 按上述求解思路，可将原模型描述为：按上述求解思路，可将原模型描述为： Z=minf(Fi)|Gi(Xi) 求解的主要工作：求解的主要工作：由由Xi构造构造GiGi中最小费用流中最小费用流fi的计算的计算个体编码处
25、理个体编码处理变量构造及个体编码含义变量构造及个体编码含义 Xkxijk为为0-1矩阵矩阵行行客运专线上车站客运专线上车站区区 间间车站的顺序结构；车站的顺序结构；行数行数mi是固定的由线路结构确定；是固定的由线路结构确定；列列列车在车站通过、停车、始发、终到或在区间运行的状列车在车站通过、停车、始发、终到或在区间运行的状态；态；列数列数mj由线路上所有区段中的最大列车数由线路上所有区段中的最大列车数maxminnq,cq| q确定确定个体冗余性处理个体冗余性处理车站取值冗余车站取值冗余车站取值约束车站取值约束 |xi+1,j-xi-1,j|xijxi+1,j+xi-1,j (i=2n, n
26、Z+,j=1,2.,mj) 列排序冗余列排序冗余字典排序字典排序车站限制处理：车站限制处理：车站不办理客运业务：取消该车站，将相邻区间合并车站不办理客运业务：取消该车站，将相邻区间合并车站不办理列车的始发和终到作业取值约束车站不办理列车的始发和终到作业取值约束 |xi+1,j-xi-1,j|xijxi+1,jxi-1,j (i=2n, n Z+) 弧产生始节点终节点费用位置始发弧列车始发站列车中间停站始发集结时间在弧上中间弧列车中间停站列车前方相邻停站停站时间、始发集结时间在始节点和弧上终到弧列车中间停站列车终到站停站时间、始发集结时间在始节点和弧上直达弧列车始发站列车终到站始发集结时间在弧上
27、中转弧旅客中转站V旅客中转站V中转时间消耗在弧上列车运行网络的构造列车运行网络的构造 初始网络构造初始网络构造网络参数确定网络参数确定弧的费用弧的费用弧的容量：满足一定上座率，弧的容量：满足一定上座率，容量限制为阶跃形式容量限制为阶跃形式cij 0,cu节点外部流量节点外部流量Wi：Wi+表示节点的发送量表示节点的发送量Wi-表示节点的到达量表示节点的到达量中转弧的构造中转弧的构造 中转方案的确定：列车在换乘中转方案的确定：列车在换乘节点前、后，具有不同的弧集；节点前、后，具有不同的弧集； 弧的容量为弧的容量为0 cij cu网络的统一化处理网络的统一化处理重复弧的处理：合并重复弧的处理：合并
28、 容量变为容量变为ncu或或ncu 节点费用的处理节点费用的处理始发集结消耗费用处理始发集结消耗费用处理节点外部流量处理节点外部流量处理 Pk Gk单源单汇给定流量的有向图单源单汇给定流量的有向图适应值函数的求解适应值函数的求解适应值函数适应值函数f就是求解就是求解G上给定流量上给定流量W的最小费用流。的最小费用流。网络的可行化处理网络的可行化处理不可行性产生的原因：不可行性产生的原因：列车在车站所提供服务能力小于该站始发客流量；列车在车站所提供服务能力小于该站始发客流量；列车在车站所提供服务能力小于该站终到客流量；列车在车站所提供服务能力小于该站终到客流量；列车在区间所提供服务能力小于该区段
29、旅客输送量（客流密度）；列车在区间所提供服务能力小于该区段旅客输送量（客流密度）；列车在列车在OD所表示两个车站提供服务能力的可达性关联。所表示两个车站提供服务能力的可达性关联。处理方法：增加虚拟扩容弧处理方法：增加虚拟扩容弧费用为费用为McHmax阶跃容量限制的转化阶跃容量限制的转化 根据对偶原理网络中弧的根据对偶原理网络中弧的 容量和费用可以互相转化。容量和费用可以互相转化。 转化为弧转化为弧eij： 容量限制容量限制cijcu； 费用为凹函数：费用为凹函数：hij (f)= hij (f)+Mh(cu-fij)fij； 为使得为使得fij 0且且fij cu的流值不发生在弧的流值不发生在
30、弧eij 上，要求上，要求Mh2NMc。 带有凹费用的网络求解带有凹费用的网络求解凸费用的处理凸费用的处理分段线性近似分段线性近似费用为凸时，总有费用为凸时，总有h1h2 出现固定费用出现固定费用把把eij的费用用一条直线的费用用一条直线近似，得到新的参数：近似，得到新的参数：有固定费用的最小费用流计算有固定费用的最小费用流计算隐枚举法隐枚举法有负费用的最小费用流求解有负费用的最小费用流求解在有容量限制的网络中，负费用的存在不会给最小费用流带来在有容量限制的网络中，负费用的存在不会给最小费用流带来更多的新问题，不需要进行特殊处理。更多的新问题，不需要进行特殊处理。网络网络G容量供给特性的分析容
31、量供给特性的分析能力过剩方案能力过剩方案能力过剩网络；能力过剩网络；能力紧缺方案能力紧缺方案能力紧缺网络；能力紧缺网络；能力平衡方案能力平衡方案供需平衡网络。供需平衡网络。 在非能力过剩网络中，去掉运行弧的容量阶跃约束而改为在非能力过剩网络中，去掉运行弧的容量阶跃约束而改为平凡的容量上限，不会出现违反阶跃容量限制的可行流，因平凡的容量上限，不会出现违反阶跃容量限制的可行流，因此不会影响最优解的性质。此不会影响最优解的性质。 保证个体不构成能力过剩网络，必须满足能力约束保证个体不构成能力过剩网络，必须满足能力约束实际工作与方案优化之间的比较分析实际工作与方案优化之间的比较分析实际新建客运专线列车
32、开行方案制定的通常做法。实际新建客运专线列车开行方案制定的通常做法。 【推论推论1】 把满足客流和技术条件的始发客流，以直达把满足客流和技术条件的始发客流，以直达列车的形式先输送至目的地而形成的开行方案不一定是最优列车的形式先输送至目的地而形成的开行方案不一定是最优的。的。 【推论推论2】 在运能短缺的情况下，当给定一个列车开行在运能短缺的情况下，当给定一个列车开行方案后，对于有条件的客流采用直达列车输送总是最优的。方案后，对于有条件的客流采用直达列车输送总是最优的。 推论推论1是对全局最优的叙述；推论是对全局最优的叙述；推论2是对局部最优的叙述，是对局部最优的叙述，两者并不矛盾。两者并不矛盾
33、。 现行的列车方案制定步骤和方法，可得出局部最优方案现行的列车方案制定步骤和方法，可得出局部最优方案遗传策略的选择和确定遗传策略的选择和确定遗传操作设计遗传操作设计个体冗余性处理个体冗余性处理非能力过剩网络的约束非能力过剩网络的约束处理处理协同对称群体交叉遗传协同对称群体交叉遗传操作操作不可行解的优不可行解的优化信息利用和处理化信息利用和处理其他辅助遗传操作：初其他辅助遗传操作：初始群体飘移、辅助终止始群体飘移、辅助终止条件判断条件判断算法步骤算法步骤城际客专旅客列车开行方案的制定城际客专旅客列车开行方案的制定列车始发、终到站均相同，为城际客专的起讫点；列车始发、终到站均相同，为城际客专的起讫
34、点；城际客运专线上每个区间内列车的开行数量都是相城际客运专线上每个区间内列车的开行数量都是相同的；同的；每列动车组类型相同，只有沿途停站方案不同；每列动车组类型相同，只有沿途停站方案不同；客流不产生换乘；客流不产生换乘；在客流密度较小的区段，上座率会小于限定值。在客流密度较小的区段，上座率会小于限定值。 城际客专列车开行方案优化问题城际客专列车开行方案优化问题确定一个确定一个在给定客流在给定客流OD情况下的最优列车停站组合方案。情况下的最优列车停站组合方案。 利用上述方法求解，可以得到该算法的整体复利用上述方法求解，可以得到该算法的整体复杂度为杂度为O(n4lnn)，(1,1)。列车运行图编制
35、模型及算法列车运行图编制模型及算法客运专线网描述客运专线网描述用节点、单向弧及其关系描述用节点、单向弧及其关系描述约束条件约束条件列车区间运行时间约束列车区间运行时间约束列车停站时分约束列车停站时分约束列车追踪间隔时间约束列车追踪间隔时间约束列车越行条件约束列车越行条件约束列车区间越行控制约束列车区间越行控制约束天窗时间约束天窗时间约束列车到发时刻特殊要求约束列车到发时刻特殊要求约束车站到发线数量约束车站到发线数量约束模型构造模型构造目标函数目标函数列车总旅行时间最小列车总旅行时间最小动车组总消耗时间最小动车组总消耗时间最小 把列车总旅行时间最小作把列车总旅行时间最小作为模型的优化目标。为模型
36、的优化目标。 动车组总消耗时间最小等动车组总消耗时间最小等价于动车组总停留接续时间最价于动车组总停留接续时间最小，它对应于动车组最优运用小，它对应于动车组最优运用计划。在求得总旅行时间最小计划。在求得总旅行时间最小的列车运行图后，再求解此基的列车运行图后，再求解此基础上的最优动车组运用计划础上的最优动车组运用计划。算法算法分解算法分解算法解决客运专线网的分解解决客运专线网的分解把客运专线网分解为相对独立的子线路分步建模求解。把客运专线网分解为相对独立的子线路分步建模求解。分解关键在于线路交会点的选择。分解关键在于线路交会点的选择。时空局域滚动算法时空局域滚动算法解决简单线路上模型的求解解决简单
37、线路上模型的求解在运行图时空局域内设置窗口，在窗口中进行运行线寻优，并通过滚动在运行图时空局域内设置窗口，在窗口中进行运行线寻优，并通过滚动“窗口窗口”动态地完成问题的求解，把原问题分解为规模较小的连续子问动态地完成问题的求解，把原问题分解为规模较小的连续子问题进行处理，逐步得到原问题的解。题进行处理，逐步得到原问题的解。列车初始布点方法列车初始布点方法解决初始解的构造解决初始解的构造特点分析特点分析布点的对象不同布点的对象不同列车种类少列车种类少布点的范围不同布点的范围不同布点车站不固定布点车站不固定布点的时段性要求不同布点的时段性要求不同客运专线列车开行密度的时段性差异客运专线列车开行密度
38、的时段性差异综合维修天窗的限制。综合维修天窗的限制。需要满足的条件需要满足的条件列车在始发站分阶段、分种类、分时段均衡发车列车在始发站分阶段、分种类、分时段均衡发车满足列车运行间隔时间要求满足列车运行间隔时间要求满足天窗时间要求满足天窗时间要求算法思路算法思路按照所排定的始发站顺序依次为进行布点；对于初始车站，相当于在一日营按照所排定的始发站顺序依次为进行布点；对于初始车站，相当于在一日营运时间范围内按照不同时段列车密度均匀布点，其后车站上的布点可以看作运时间范围内按照不同时段列车密度均匀布点，其后车站上的布点可以看作在已定列车运行线条件下的均匀布点。在已定列车运行线条件下的均匀布点。结论结论
39、客运专线旅客列车开行方案的形成过程要经历客流预测、开行方案优化客运专线旅客列车开行方案的形成过程要经历客流预测、开行方案优化与运行图编制三个阶段。包含的各项内容是在不同的环节过程中得到的，与运行图编制三个阶段。包含的各项内容是在不同的环节过程中得到的，三个阶段所需参数和优化结果互为因果。开行方案的整体优化可以通过三个阶段所需参数和优化结果互为因果。开行方案的整体优化可以通过三个子问题的单独顺序优化、循环迭代实现。三个子问题的单独顺序优化、循环迭代实现。始发客流到达集结过程可以描述为标值点过程。旅客平均候车集结时间始发客流到达集结过程可以描述为标值点过程。旅客平均候车集结时间和平均旅客中转时间可
40、以用列车服务频率描述。和平均旅客中转时间可以用列车服务频率描述。直线型客运专线旅客列车开行方案优化模型是一个具有列车和客流间的直线型客运专线旅客列车开行方案优化模型是一个具有列车和客流间的多种组合优化特性的非线性整数规划问题。采用分解的方法，对跨线客多种组合优化特性的非线性整数规划问题。采用分解的方法，对跨线客流处理后，模型可适用于网状线路结构。流处理后，模型可适用于网状线路结构。个体存在车站取值和列排序两方面的冗余性和不可行性，可描述为单源个体存在车站取值和列排序两方面的冗余性和不可行性，可描述为单源单汇的费用容量网络，适应值对应于网络的最小费用流。通过能力的单汇的费用容量网络，适应值对应于
41、网络的最小费用流。通过能力的控制，可以避免由于阶跃容量限制而产生的固定费用和负费用。控制，可以避免由于阶跃容量限制而产生的固定费用和负费用。为发挥不可行个体的优良遗传信息，采用协同对称群体交叉遗传操作。为发挥不可行个体的优良遗传信息，采用协同对称群体交叉遗传操作。得出关于直达列车输送客流的最优性判断。得出关于直达列车输送客流的最优性判断。城际客运专线的列车开行方案优化是一类比较简单的特定问题。采用上城际客运专线的列车开行方案优化是一类比较简单的特定问题。采用上述算法求解，整体时间复杂度为述算法求解，整体时间复杂度为O(n4lnn) 。分解算法可以解决网络运行图的求解问题；时空局域滚动算法可以实
42、现分解算法可以解决网络运行图的求解问题；时空局域滚动算法可以实现具体的运行图编制优化；初始布点算法解决了初始解的构造问题。具体的运行图编制优化；初始布点算法解决了初始解的构造问题。存在问题与进一步的工作存在问题与进一步的工作研究问题整体循环迭代过程收敛性的研研究问题整体循环迭代过程收敛性的研究和证明。究和证明。相邻各线旅客列车开行方案在衔接车站相邻各线旅客列车开行方案在衔接车站上的相互协调优化问题。上的相互协调优化问题。协同对称群体交叉遗传操作的算法测试协同对称群体交叉遗传操作的算法测试及验证。及验证。客运专线旅客列车开行方案决策支持系客运专线旅客列车开行方案决策支持系统应用软件的设计和开发。统应用软件的设计和开发。谢谢！谢谢！Questions and Comments are Welcome!
