方案系统优化

文章编号:100124098(2006)1120024207客运专线旅客列车开行方案优化系统设计Ξ史峰,邓连波,霍亮(中南大学交通运输工程学院,湖南长沙410075)摘要:分析中国旅客列车开行方案的现状,并结合客运专线建设的实际背景,提出旅客列车开行方案优化问题,指出开发客运专线旅客列车开行方案优化系统的必要性和迫切性.
对开行方案双层优化模型和优化框架进行概述.
系统分析设计要求、功能需求、数据组织等内容,为客运专线运营组织提供决策支持,为客运专线建设方案的评价提供理论支撑.
关键词:客运专线;开行方案;系统设计中图分类号:U29文献标识码:A旅客列车开行方案是在客流计划的基础上,确定开行旅客列车的开行数量、类别、运行区段和沿途停站,以充分利用铁路线路、机车车辆的设备能力,满足旅客出行数量和质量方面的合理需求,提高运输企业经济效益.
开行方案的确定要考虑因素众多,包括客流构成和分布、路网构成、线路条件、车站设置、机车车辆等,是铁路运输组织中越来越重要的系统工程问题,是铁路旅客运输组织和行车组织的重要内容.
目前中国开行方案编制是由编制人员根据实际经验对既有开行方案进行修改、增补,不仅无法保证方案的质量,而且也不适应铁路旅客运输市场的快速变随着旅客运输市场上各种交通方式日趋激烈的竞争,需要不断调整旅客列车开行方案以适应需求、提高服务,原有人工逐步修正旅客列车方案的方法无法适应科技进步、现代管理和经营理念的发展.
高速铁路和客运专线的即将推出,将形成新建高速铁路、客运专线、普速铁路、提速普速铁路构成的铁路运输网络,极大缓解铁路运输的紧张局面,同时也使客流构成和服务需求发生很大变化,使旅客列车开行方案更为复杂化.
在此背景下,本文对客运专线旅客列车开行方案优化系统设计相关问题进行探讨.
1国内外研究进展和研究基础国内外对旅客列车开行方案优化问题的探讨中,较为典型的有具有周期时刻表的开行方案优化问题[3],整数规划模型及其分支定界算法[4],高速列车开行方案的多目标0-1规划数学模型[5],直通旅客列车开行方案的二分图最大加权匹配问题[6],总运营成本和总旅行时间最少的多目标优化模型以及其采用模糊数学求解方法[7],考虑铁路和旅客双方利益的客运专线旅客列车开行方案的多目标模型[8],以及文献[8]基础上,以旅客客流分配为下层规划的双层规划模型[9]等.
文献[10]研究了城市轨道交通多个循环区段线路上列车最优开行方案的计算机自动编制问题,给出各种循环交路方式下车底运用数下界的计算公式,建立了使列车实载率达到最大的列车日班次运行计划的优化模型,实现了编制城轨列车班次计划的自动化.
文献[11]、文献[12]利用现有开行方案的客流数据对OD流数据进行估计,采用二部图模型优化开行方案,并构建了旅客列车开行方案决策支持系统,系统中可以对列车进行点到点的技术经济评价,并进行相应的调整.
本文基于文献[7]、文献[8]对旅客列车开行方案优化方法的研究基础上,对开行方案优化系统设计进行探讨.
文献[7]基于中国路网发展规划,特别是客运专线和高速铁路建设的建设规划,在详尽的社会经济分析的基础上,分析了旅客列车开行方案的相关费用和优化目标,均衡考虑企业利益和旅客需求,建立了开行方案优化的多目标模第24卷第11期(总第155期)系统工程Vol.
24,No.
112006年11月SystemsEngineeringNov.
,2006Ξ收稿日期:2006207215基金项目:国家自然科学基金资助项目(70471047)作者简介:史峰(19562),男,湖南芷江人,中南大学交通运输工程学院院长,教授,博士生导师,研究方向:交通运输规划与管理,交通运输系统优化理论;邓连波(19772),男,辽宁昌图人,中南大学交通运输工程学院博士研究生,研究方向:交通运输营运管理与信息系统,交通运输系统优化理论;霍亮(19812),男,山东禹城人,中南大学交通运输工程学院研究生,研究方向:交通运输营运管理,交通运输组织理论.
http://www.
paper.
edu.
cn中国科技论文在线型,并设计了启发式的求解方法.
文献[8]在此基础上,将列车开行方案与旅客换乘方案结合起来,建立了旅客列车开行方案的双层规划模型,揭示旅客列车开行方案的内在规律.
该模型和算法将开行方案优化与客运径路确定、旅客列车换乘网络设计、旅客换乘的客流分配问题、旅客列车停站优化、旅客列车开行方案的评价指标分析等一系列相关子问题结合起来,建立了系统的旅客列车开行方案的优化方法.
本文以这种算法作为核心,对客运专线相关路网上旅客列车开行方案优化系统(SpecialLinePassengerTrainPlanSystem,SLPTP)的开发设计相关问题进行探讨.
该系统利用优化理论和计算机技术,为铁路规划部门的路网发展规划的经营效果和运营评价、旅客运输部门的合理运输组织提供决策信息优化系统,以期降低使用者的劳动强度,提高运输能力的利用效率,提高铁路客运市场竞争能力,同时提升旅客运输组织和客运专线建设、路网规划等决策的科学性.
2旅客列车开行方案模型和优化思路[8]2.
1旅客列车开行方案优化的双层规划模型由于客运专线和既有铁路在旅客运输组织上分工、衔接、配合和协调关系,客运专线旅客列车开行方案优化的研究范围并不仅仅局限于客运专线,而是与客运专线相关的铁路客运网络.
旅客列车开行方案问题是在车辆、编组辆数、列车整备能力等的限制条件下,确定网络上旅客列车的对数、类别、运行区段和停站,满足旅客的出行需求,使铁路企业的运营效益最大化.
旅客运输系统包含两方面的决策,一方面决策来自于旅客运输企业,另一方面决策来自于旅客,相应地开行旅客列车的优化目标也包括两个方面,一方面为尽可能地扩大运输企业运营效益,另一方面为充分满足旅客出行需求.
确定旅客列车开行方案,首先需要分析旅客列车开行方案的相关收益与费用.
对于给定开行方案,研究旅客在此开行方案下的换乘方案选择,进行基于开行方案的客流分配.
在综合考虑各方面利益的条件下,建立换乘方案的客流分配作为下层规划、旅客列车开行方案的确定作为上层规划的双层优化模型.
给定铁路旅客运输网络N=(S,E),其中S={1,2,…,n}为车站集,E为路段集,路段e∈E的里程为d(e).
可开行l种类别的旅客列车,其中类别的列车在路段e上的旅行速度为V(u,e).
旅客列车开行方案包括列车的路线方案和装备方案.
其中列车T的路线方案由其停靠站序列Q表示;列车装备由列车类别u、列车编组辆数b和开行频率q(日开行对数)来表示.
因此可记列车开行方案为8={T=(Q,u,b,q)}.
考虑运输资源的限制,限制类别u的车辆小时总数不超过N(u),类别u的列车编组辆数上下限分别为bλ和b,列车整备能力为L(i).
旅客列车的开行费用划分为列车公里费用cL、车公里费用cK、车小时费用cH.
记列车T′经过停站s至列车T″的中转换乘时间为Σ(T′,s,T″).
旅客的旅行费用包括客票总金额P、乘车时间价值S、中转换乘时间价值Z.
同时由于列车载客能力的限制,引入列车T关于载客人数x的拥挤费用函数yT(x)=yT(gT(i′,i″)),其中gT(i′,i″)为列车运行区段T(i′,i″)上的客流量.
客流分为m个消费层次,车站i至j的客流量为f(i,j),f(i,j)按消费层次分为fw(i,j),w=1,2,…,m,再将其按换乘方案可分解为fwk(i,j),k=1,2,…,Ρ(i,j).
消费层次w的旅客平均时间价值为Β(w).
为了平衡铁路企业和旅客两方面的利益,引入平衡因子Α:0<Α<1,建立旅客列车开行方案优化的双层规划模型如下:max8Z=Α(PΑ)(P+S+Z)s.
t.
∑T∈8∑e∈T(bTqTd(e)V(uT,e))u(T)≤N(u),u=1,2,…,lbλ(uT)≤bT≤b(uT),T∈8∑T∈8Γi(T)≤L(i),i=1,2,…,n其中u(T)=1,uT=u0,uT≠uΓi(T)=1,i为T的起点站0,其它旅客负费用P+S+Z满足旅客换乘多类用户平衡条件,即满足下层规划:minf,tF=∑ni,j=1∑Ρ(i,j)k=1∑T(i′,i″)t.
∑Ρ(i,j)k=1∑mw=1fwk(i,j)=f(i,j),i,j=1,2,…,nfwk(i,j)≥0,i,j=1,2,…,n;k=1,2,…,Ρ(i,j);w=1,2,…,m2.
2旅客列车开行方案优化思路旅客列车开行方案优化问题较为复杂,而且其规模一般较大,需要根据问题的特点,设计优化求解算法.
优化模型的下层是客流量分配.
流量分配问题有很多比较成熟的求解算法,我们采用效率较高的GP路径配流算法.
为了求得旅客列车开行方案的双层规划问题全局范围内的较优解,我们采用模拟退火算法进行求解.
对上层的开行方案优化,希望通过构造恰当的邻域系,采用邻域搜索的方法来求解模型.
而文献[13]建立的旅客列车开行方案的评价指标体系,可以作为上层规划的优化方向.
近年来,研究小组依托铁路高速客运专线可行性研究,"生成方案——网络配流——方案评价——方案调整52第11期史峰,邓连波等:客运专线旅客列车开行方案优化系统设计——循环迭代"的旅客列车开行方案优化框架已经形成.
从2003年4月开始,研究小组提出了旅客列车开行方案的多目标规划模型及其启发式方法;提出了旅客换乘网络的概念和构造方法,并将其应用于列车方案的客流分配;构建了旅客列车开行方案的评价指标体系,并对评价方法进行了初步探讨.
将上述工作综合起来,设计了求解旅客列车开行方案问题的求解算法.
旅客列车开行方案生成策略中,借鉴了"按流开车"的思想,并将其系统化.
同时将旅客列车开行方案的配流问题、评价指标体系和评价方法、调整迭代策略纳入优化算法.
将开行方案的优化研究与客运径路确定、旅客列车换乘网络设计、旅客换乘的客流分配问题,旅客列车停站优化、旅客列车开行方案的评价指标分析等一系列相关子问题结合起来,形成了以模拟退火为基础的求解算法.
邻域系的构造是模拟退火算法的关键步骤之一.
旅客列车开行方案中列车的确定与客流换乘选择情况有关.
受这种思想启发,邻域搜索优化算法的具体邻域构造可以通过在列车方案中将部分客流释放,保留未释放客流的列车,并对这些客流重新开车,这些列车与所保留列车组成的开行方案作为原方案的一个邻近解.
采用开行方案评价指标体系的评价结果作为在方案中随机选取列车和客流的依据,选取一定比例的列车方案和客流换乘方案进行调整,构成原有列车方案的一个临域解.
开行方案优化问题的双层规划模型综合考虑了旅客和铁路企业的利益,客流分配反映了铁路开行方案的运营特征.
由于问题的NP完备性和特点,通过抽象归纳铁路企业制定开行方案的丰富经验和利用邻域搜索优化方法,设计了行之有效的模拟退火优化算法,可解决路网上大规图1开行方案优化流程图62系统工程2006年模的旅客列车开行方案优化问题.
以模拟退火求解算法为基础的求解算法,具有运算速度快、优化效率高的特点.
经过综合分析比较,优化理论较为全面反映了开行方案的本质特征,其优化理论较为全面反映了开行方案的本质特征,具有良好的适用性,因此本软件也采用这种方法.
算法的优化流程如图1所示.
3系统目标设计作为一个优化决策系统,客运专线旅客列车开行方案优化系统解决问题的合理性必须得到保证,运行效率也是不应忽视的因素.
系统的核心功能是提供合理的开行方案,因此应注意优化和改进软件系统的数据结构、程序流程和求解算法,特别是优化算法的设计,它是分配方案合理性的根本保证.
同时为了方便用户的操作,系统的人机交互方式应尽可能采用直观友好的图形交互界面,这样用户可以直观、便捷地处理数据的各种输入输出.
并注意系统能应对各种正常与非正常的情况,提高系统的可靠性与稳定性.
综上所述,系统的设计目标应该包括以下几个方面:(1)人机交换界面友好,具有灵活的人机交互能力铁路客运专线旅客列车开行方案优化系统的目标是优化客运专线背景下的开行方案,优化结果应注重减轻客运专线和高速铁路路网规划与客运组织、行车组织、运营管理人员的劳动强度,因此设计过程中要特别强调界面的友好性和操作的方便性.
铁路客运专线旅客列车开行方案优化系统的基础数据包括车站、线路、线站关系、地区、消费层次、地区消费层次分布、列车等级、线路种类、各类线路的列车费用、OD流信息等庞杂数据信息,为了方便有效地进行数据维护,利用数据窗对数据进行管理,大大减少了使用者的工作量.
对用户修改的数据,系统对其完整性和一致性进行检验,并尽可能排除无效的数据输入干扰.
系统采用标准的Windows设计风格,采用数据窗的处理、难以人工确定数据的图形化输入、录入数据的自动检测、基础数据的有效性检验、系统错误信息的自动追踪和定位,并提供了数据信息的全方位查询方式.
对路网数据,还提供图形化的交互控制,有效较少了错误率.
对径路的查询和生成都可以与图形交互,尽可能降低操作的难度,降低劳动强度.
并对开行方案提供灵活的查询功能,包括开行方案的区段列车选取和统计,并提供按照起点站、终到站、等级、停靠站等信息的查询功能,区段列车方案可以输出成Excel文件,对开行方案图提供AutoCAD图形化输出方式.
(2)优化算法具备实用性,优化过程支持人工干预铁路客运专线旅客列车开行方案问题涉及因素众多,是一个复杂的多目标的优化问题,迭代优化算法可将算法的时间控制在合理范围内.
根据问题特点系统采用了分阶段的迭代优化方法,包括初始方案生成、配流和停站优化、列车开行方案评价以及综合迭代优化几个步骤.
开行方案的各阶段优化过程向用户开放,用户可以在多阶段优化过程中根据需要进行灵活的控制.
问题求解算法的创新性大大降低了问题的复杂程度,增强了方案的合理性,可适用于大规模路网上的决策支持.
用户可以根据需要对优化过程进行通过修改各种算法参数,对优化过程进行干预和控制,也可以分解单步执行循环迭代操作的各个步骤,增强了系统灵活处理实际问题的能力.
通过优化得到的旅客列车开行方案,考虑一些特殊要求,在实际应用中可能需要进行调整.
系统支持对开行列车的修改、删除、添加、延长、分拆、增减停靠站等多样性的操作,可对开行方案进行灵活修改.
(3)可扩充性强目前中国铁路正面临一个大发展时期,客运专线和高速铁路不断推出,车站、线路等行车设备正在不断的进行改扩建,相关信息变化频繁,同时市场经济条件下客流变动频繁,旅客列车开行不断需要调整,迫使系统应具有通用性和可扩充性.
为此,系统必须能够适应路网和其他因素的变更,基础数据灵活而不固定,允许动态增加或者减少、变更基本数据信息.
考虑系统使用的数据来源的不同,以及在今后运输规划与管理中可能在其它MIS中的使用,因此预留了系统的数据扩充以及功能扩充的接口.
4系统功能设计根据用户需求的分析,系统设计的功能模块列于表1.
我们在Windows2000操作系统下,用VisualC++6.
0进行开发,系统采用MicrisoftAccess2000数据库,并提供文本输出、MicrosoftExcel2000的输入输出和AutoCAD2000的图形输出.
采用COM接口的技术,通过VC++的OLEAutomation机制实现在应用程序中调用并读写Excel,实现数据交换.
区段列车方案图要求采用AutoCAD的图形方式输出,以便于后续分析和修改.
本系统采用内部生成DXF文件的方法,与利用ObjectARX、AutoLisp等AutoCAD接口技术相比,具有较好的环境适应性,其运行可以脱离AutoCAD环境.
将DXF文件以节为单位分别保存为模板文件,对各种线条、标注文本、车站等特殊结构定义块,实体部分(ENTITIESSection)由系统利用模板自动生成,将生成的图形导出为DXF文件格式.
72第11期史峰,邓连波等:客运专线旅客列车开行方案优化系统设计表1系统设计的功能模块主模块子模块说明1.
基本数据维护和查询路网数据查询和维护维护车站、线站关系、线路等数据地区消费层次数据维护维护地区、消费层次、地区消费层次关系等数据费用基本数据的维护维护列车等级信息查询、线路基本信息查询、以及列车线路费用信息等数据客流数据的编辑维护通过数据窗生成、编辑和维护客流OD数据2.
列车方案优化列车方案的优化初始方案生成、配流优化、列车方案评价、开行方案迭代优化列车方案的导入导出包括开行方案的Access数据表、Excel数据表的导入导出3.
列车方案查询列车开行方案的图形化显示列车开行方案查询显示区段列车信息或按特殊要求查询列车区段列车方案图输出区段列车流图的显示、区段列车流图的图形化输出4.
区段列车方案图查询和编辑列车信息查询列车信息查询换乘信息查询按消费层次的客流换乘方案查询编辑列车方案列车方案的修改、变更和停站设置区段列车信息区段列车方案生成、统计5.
基本数据维护和查询路网数据查询和维护通过数据窗维护车站、线站关系、线路等数据地区消费层次数据综合维护通过数据窗维护地区、消费层次、地区消费层次关系等数据费用基本数据的维护通过数据窗维护列车等级信息查询、线路基本信息查询、以及列车线路费用信息等数据客流OD数据的编辑维护通过数据窗生成、编辑和维护客流OD数据6.
基本参数设置路网窗体视图的背景颜色设置、车站表示设置、线路显示设置7.
路网数据的图形化编辑车站、线路信息的图形化查询和修改8.
径路的查询和设定一般径路一般径路的查询和图形化显示指定径路指定径路的生成和显示分流径路分流径路的生成和显示5数据流设计和模块设计5.
1数据库设计系统的基础数据包括以下几部分:(1)路网结构数据.
它以数据表的形式存在,便于操作、维护以及移植,包括车站信息表、线路信息表、线站关系信息表.
系统自动将一些不太重要的中间站隐去,保留叉点站和重要的OD流的起讫点,形成的骨架网络,用于在计算机屏幕上绘制网络结构图、OD流的优化分配以及径路的查询.
(2)地区和消费层次信息.
包括消费层次的划分、地区的划分、每一地区客流的消费层次结构信息等.
(3)基本费用信息.
(4)列车信息.
(5)客流信息.
系统采用Access数据库存储这些数据信息.
为便于用户操作方便,数据表的命名方式约定为:信息名加相关数据表内容缩写,其结构如表2所示.
(6)系统的其他信息,系统设置和图形数据处理模板等,采用数据文件形式存储.
82系统工程2006年表2数据库表信息信息种类数据表名称路网信息车站词典线路词典线站关系词典地区和消费层次信息地区信息表消费层次信息表地区消费层次信息表基本费用信息列车基本信息表线路基本信息表列车线路费用基本信息表列车信息列车信息表列车停站信息表列车客流信息表客流信息OD运量表OD运量换乘信息表5.
2系统数据流程图和模块设计系统的数据流程和模块流程如图2所示.
图2系统数据流程和功能模块图6结论旅客列车开行方案的合理性直接影响到旅客利益和铁路企业效益.
客运专线旅客列车开行方案优化系统的开发是铁路客运专线旅客运输组织的需要,也是客运专线和高速铁路建设的需要,是在旅客运输组织与市场经济共同作用的必然结果.
92第11期史峰,邓连波等:客运专线旅客列车开行方案优化系统设计在既有优化模型和求解算法的基础上,用VC++开发了铁路旅客列车开行方案优化系统.
本文以客运专线旅客列车的双层规划模型及其求解算法为基础,对客运专线旅客列车开行方案优化系统设计的功能、数据设计、模块设计等进行了探讨.
系统功能包括路网数据生成与维护,OD流生成与维护,开行方案优化,优化参数调整,开行方案的综合查询,方案图输出,开行方案的交互式修改等模块,很好满足了开行方案优化相关的功能需求.
系统具备解决路网上实际规模的旅客列车开行方案的优化问题的能力,并可以通过系统提供的人机交互功能对开行方案根据要求进行修改.
利用系统提供的旅客列车开行方案的评价指标体系,可以对旅客列车开行方案的社会经济效益进行综合评价.
该系统在多条客运专线可行性研究的开行方案优化设计中得到了应用,结果表明,该系统具有良好的优化质量和运算效率,适合实际需求.
系统能够为客运专线(高速铁路)运营组织提供决策支持,为客运专线的建设评价提供理论支撑.
参考文献:[1]汤奇志,时颢.
沪宁高速铁路运输组织的探讨[J].
铁道运输与经济,1997,2:33~36.
[2]彭其渊,闫海峰,魏德勇.
武广客运专线运输组织模式研究[J].
西南交通大学学报,2004,36(6):703~707,711.
[3]BussieckMR,KreuzerP,ZimmermannUT.
Optimallinesforrailwaysystems[J].
EuropeanJournalofOperationalResearch,1996,96:54~63.
[4]ClaessensMT,etal.
Costoptimalallocationofrailpassengerlines[J].
EuropeanJournalofOperationalResearch,1998,(101):474~489.
[5]张拥军,任民,杜文.
高速列车开行方案研究[J].
西南交通大学学报,1998,(4):400~404.
[6]查伟雄,符卓.
直通旅客列车开行方案优化方法研究[J].
铁道学报,2000,22(5):1~5.
[7]ChangYH,YehCH,ShenCC.
Amultiobjectivemodelforpassengertrainservicesplanning:applicationtoTaiwan'shigh2speedrailline[J].
TransportationResearchPartB,2000,(34):91~106.
[8]史峰,邓连波等.
客运专线相关旅客列车开行方案研究[J].
铁道学报,2004,26(2):16~20.
[9]史峰,邓连波等.
旅客列车开行方案的双层规划模型和算法[J].
中国铁道科学(待发表).
[10]孙焰,施其洲,赵源,孔庆瑜.
城市轨道交通列车开行方案的确定[J].
同济大学学报(自然科学版),2004,32(8):1005~1008,1014.
[11]查伟雄,熊桂林,万国栋.
旅客列车开行方案决策支持系统研究[J].
系统工程,2004,22(6):78~82.
[12]胡辉.
旅客列车开行方案系统的开发研究[J].
铁道运输与经济,2004,26(20):58~60.
[13]邓连波,史峰.
旅客列车开行方案评价指标体系[J].
中国铁道科学,2006,27(3):106~110.
SystemDesignofPassengerTrainPlan-OptimalReferenceonPassengerSpecialLinesSHIFeng,DENGLian2bo,HUOLiang(SchoolofTrafficandTransportationEngineering,CentralSouthUniversity,Changsha410075,China)Abstract:Inthispaper,theactualityofChinesepassengertrainplanisanalyzed,combinedwiththepracticalbackgroundoftheconstructionofthepassengerspecialline,theoptimalproblemofthepassengertrainplanisputforward,thenthenecessityandtheimminenceispointedouttodeveloptheoptimalsystemofPassengerTrainPlanRelatedProblemsonPassengerSpecialLine.
Basedonthese,thebi2leveloptimalmodelandtheoptimizationframeworkaresummarized.
Thesystemanalysesthefollowingcontentsuchasthedesigndemand,requiredfunctionanddataorganizationwhichcanofferdecision2makingadvicefortheoperationofthepassengerspeciallineandprovidetheoreticsupportfortheevaluationoftheconstructionprojectofthepassengerspecialline.
Keywords:PassengerSpecialLine;PassengerTrainPlan;SystemDesign03系统工程2006年