旅客列车开行方案优化

旅客列车开行方案优化中南大学史峰2007年7月2报告内容一、旅客列车开行方案优化问题二、国内外研究现状三、开行方案问题的费用分析四、开行方案的多目标优化模型五、客流分配和旅客中转换乘问题六、旅客列车开行方案的双层规划模型七、算例分析3一、旅客列车开行方案优化问题旅客列车的开行方案，包括所开行的旅客列车的开行数量、类别、运行区段和沿途停站优化旅客开行方案涉及铁路运输企业和旅客两方面因素，以一定客流量为基础，在各种客运设备的限制下，满足旅客的服务需求，使铁路企业、旅客的利益最大化4一、旅客列车开行方案优化问题旅客运输组织优化面临的问题：网络规模大，客运专线使得网络更加复杂旅客的服务要求日益提高，包括中转衔接等优化方法不够完善，优化所需要的数据不完整铁路企业在服务社会的同时要求效益最大化5一、旅客列车开行方案优化问题旅客列车开行方案是旅客列车组织的重要技术文件合理的旅客列车开行方案能够综合利用铁路现有线路设施降低铁路运输组织费用满足旅客的出行需求提高铁路企业的收益6一、旅客列车开行方案优化问题（1）分析开行方案的相关收益与费用（2）建立旅客列车开行方案的多目标优化模型（3）研究旅客对给定开行方案的换乘方案选择（4）建立旅客列车开行方案的评价指标体系（5）双层规划优化模型和求解方法研究体系结构7二、国内外研究现状对旅客列车的组织模式、开行原则和经济分析单文浩,叶怀珍(2000)、贾俊芳(2002)、叶怀珍等(2000)、陶诗宇,查伟雄(2005)、周立新(2000)等。编制旅客列车开行方案具有一定的指导作用。网络或多起迄点开行方案的量化研究多目标0-1规划数学模型(张拥军,任民,杜文)二部图优化模型(查伟雄，符卓)客运专线开行方案多目标双层模型(何宇强,毛保华等)断面流量的城市轨道交通开行方案优化(孙焰等)城市公交“按流开车、逐条布线、优化成网”的优化方法(王炜等)。国内研究现状8二、国内外研究现状Anthony,R.N.(1965)给出了基本优化框架Hooghiemstra,J.S.(1996)论述了开行方案的地位和作用。几种典型的开行方案模型：M.T.Claessens等(荷兰)列车运行成本最小模型。CarlosMartins等支线公交网络设计的旅客和经营者的费用最小模型。MichaelR．等(1996)以直达旅客数量最大的混合整数规划模型。Yu-HernChang等以经营者的运营成本和旅客总旅行时间最少的模型。Higgins,A.等对航线优化问题的双层规划模型研究趋势：直线型-〉网络化，单目标-〉多目标，孤立优化-〉综合优化问题。国外研究现状9三、客运专线开行方案的费用分析给定铁路旅客运输网络(,)NSE，其中{1,2,,}Sn为车站集，E为路段集，路段eE的里程为()we。可开行l种类别的旅客列车，类别u的列车在路段e上的旅行速度为(,)vue方案及费用相关参数10三、客运专线开行方案的费用分析类别u的列车在类别的线路上行驶的每列车公里费用为(,)Lcu类别u的列车在类别的线路上行驶的每车辆公里费用为(,)Kcu类别u的列车的每车辆小时费用为()Hcu旅客乘坐类别u的列车在类别的线路上行驶的每人公里票价率为(,)ru方案及费用相关参数11三、客运专线开行方案的费用分析客流分为m个消费层次，车站i至j的客流量为(,)fij，nji,,1,，(,)fij按消费层次分为(,),hfij1,2,,hm。消费层次h的旅客平均时间价值为()h考虑有限的运输资源，限制类别u的车辆小时总数不超过()Nu，类别u的列车编组辆数上下限分别为()bu和()bu，车站i的等级为()Di，列车整备能力为()Li方案及费用相关参数12三、客运专线开行方案的费用分析旅客列车开行方案包括列车的路线方案和装备方案。其中列车T的路线方案由其停靠站序列Q表示；列车装备由列车类别u、列车编组辆数b和开行频率q（日开行对数）表示。因此可记列车开行方案为(,,,)TQubq对于列车T，分别用TQ，Tu，Tb，Tq,Tz，TP表示列车T的停靠站序列、类别、编组辆数、频率、载客总数和经路记(,)Tij和(,)Tij分别为列车运行区段(,)Tij的里程和旅行时间方案及费用相关参数13三、客运专线开行方案的费用分析铁路的收益主要为票价收入。旅客列车的开行费用主要包括列车公里费用、车公里费用、车小时费用，分别为：(,)()LLTeTTeTcuqdeC(,)()KKTeTTTeTcubqdeC()()(,)HHTTTTTeTcubqdevueC铁路费用14三、客运专线开行方案的费用分析将旅客的收益(即位移)记为0旅客的支出包括客票总金额、乘车时间价值、中转换乘时间价值，分别为：(,),111(,)(,)(,)(,)()kijnmwkTeijkweTiitijfijrudeP(,),111(,)(,)(,)()()(,)kijnmwkTijkweTiitijfijwdevueG(,),111(,,)(,)(,)()(,,)kijnmwkijkwTsTtijfijwTsTZ旅客费用15四、开行方案的多目标优化模型LKmaxTHZP-C-C-C（铁路收益）max0()KZPGZ（旅客收益）s.t.TPeTkjiPeTkzjif,),(),(,Ee（能力约束）()(,)()(),1,2,,TTTuTeTbqwevueTNuul（车辆）()(),()(),1,2,,TTTiTbubbuTTLiin（编组与始发）uuuuTTTu若若,0,1)(,其它的起点站为若,0,1)(TiTi16四、开行方案的多目标优化模型在多目标规划模型中，为了简化优化计算，引入参数10:（适当的值才能平衡铁路和旅客利益），得目标函数：))(1()(minTkzzz若开行I对列车，由单列列车载客容量B可知至少具有客流量1)1(BI，由载客量下限J可知至少具有客流量JI，所以至少具有客流量JIBI,1)1(max，所以车流),(jif足够开行I对列车的条件为JIBIjifJIBI)1(,1max),(,1)1(max剩余流量为BIjif),(,0max优化思路17四、开行方案的多目标优化模型为了使旅客列车尽可能满员、旅客尽可能减少中转次数，主要采用3个原则来确定开行方案：首先，大城市、中心城市之间等大流量客流优先开车其次，长距离客流优先开车最后，剩余客流降低载客量下限标准开车对于长距离客流，先按里程降序排列所有OD流，再依次处理：对并入本支客流全程的所有客流计算开行列车对数并修正剩余客流对于剩余客流，若总剩余流量不足够小，则降低载客量下限，重复长距离客流处理过程，直至总剩余流量足够小为止优化思路18四、开行方案的多目标优化模型通过吸流来提高上座率。吸流对象应注意两方面因素，其一为乘车里程较列车全程的比例较大，其二为乘车里程较客流全程比例较大，前者即“长票长卖”，以便有效提高列车上座率；后者尽可能减少旅客的换乘次数。我们可以对这两个比例值的乘积从大到小来控制吸流的先后顺序根据列车各消费层次客流人数比例，采用动态规划方法确定列车类别，若有必要可将列车分拆为在不同区段开行不同类别的列车，使得目标函数最优优化思路19五、客流分配和旅客中转换乘问题客流分配开行方案的多目标规划模型对流量的约束是限制路段上的流量不超过通过这条路段的列车载客量的总和，这是较粗的，更为准确的是分别对每一趟列车进行能力约束！它可以通过客流分配来获得。更准确地，应该按每一个列车约束，也就是旅客对换乘方案的选择应该满足多类用户平衡，要求我们开展下列工作（1）构造开行列车组成的换乘网络（2）在换乘网络上进行客流分配20五、客流分配和旅客中转换乘问题换乘网络设计换乘网络是在给定列车开行方案的基础上，反映列车之间换乘的网络。换乘网络的几种形式：乘降区间换乘网络最小区间换乘网络最小网络21五、客流分配和旅客中转换乘问题换乘网络设计无向换乘网络混合能力约束混合换乘网络上下车不分方向有向换乘网络上下车和上下行列车都分方向22五、客流分配和旅客中转换乘问题换乘网络综合比较分析n个停靠站列车特征种类车站节点虚拟节点数边或弧数重复弧列车能力约束描述换乘次数描述换乘时间描述乘降区间网络需要无2/)1(nn几乎都是多条弧流量之和径路上车站数径路上车站前后1条弧乘车区间网络需要无1n几乎都是区间弧容量径路上车站前后1条弧径路上车站前后1条弧无向网络需要22n232n无按对约束径路上车站数径路上车站前后2条弧混合网络需要2n32n无区间弧容量径路上车站数径路上车站前后2条弧有向网络需要2n53n无区间弧容量径路上车站数径路上车站前后1条弧23五、客流分配和旅客中转换乘问题对于给定的列车开行方案，旅客在列车能力的限制下按消费层次达到多类用户平衡，引入列车T关于载客人数x的拥挤费用函数()((,))TTTyxygii，客流),(jifwk的最小费用(,)wkpij为(,)(,)(,)(,,)(,)(,)((,))(,)()(,)()()(,,)kkwkTTTeTTiitijeTiiTsTtijpijygiiruwvuedewTsT其中),(iigT为列车区段),(iiT上的客流量，(,),111(,)(,)(,)(,),,1,2,,,kijnmwTkijkwTiitijgiifijiinT24五、客流分配和旅客中转换乘问题旅客换乘多类用户平衡问题可描述为以下数学规划：(,)(,)0,,11(,)(,)(,)11min()d(1)s.t.(,)(,),,1,2,,(,)0,,1,2TkijngiiTijkTiitijijmwkkwwkyxxfijfijijnfijijftPGZ,,,1,2,,(,),1,2,,nkijwmmw,,2,125五、客流分配和旅客中转换乘问题路径配流算法框架（AnthonyChen）初始化对每一客流OD对，生成初始路径.路径生成在当前路段阻抗下，生成OD对间的最短路经，如果该路径不在路径集中，则将其加入平衡配流在路径集内求解基于路径的交通分配问题收敛判断满足收敛条件时结束算法。26五、客流分配和旅客中转换乘问题收敛参数迭代次数客流分配迭代和收敛情况00.20.40.60.811.2123456727六、开行方案的双层规划模型旅客列车开行方案的优化模型可以用一个双层规划来描述：上层规划是前面的多目标规划模型，但流量约束条件除外，流量满足下层规划，它描述给定旅客列车开行方案条件下旅客对换乘方案的选择，下层规划是一个多类用户平衡的分配问题28六、开行方案的双层规划模型LKmaxTHZP-C-C-C（铁路收益）max0()KZPGZ（旅客收益）s.t.()(,)()(),1,2,,TTTuTeTbqwevueTNuul（车辆）()(),()(),1,2,,TTTiTbubbuTTLiin（编组与始发）uuuuTTTu若若,0,1)(，其它的起点站为若,0,1)(TiTi上层规划29(,)(,)0,,11(,)(,)(,)11min()d(1)s.t.(,)(,),,1,2,,(,)0,,1,2TkijngiiTijkTiitijijmwkkwwkyxxfijfijijnfijijftPGZ,,,1,2,,(,),1,2,,nkijwmmw,