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