铁路客运网络列车开行方案优化模型的列生成算法

《铁路客运网络列车开行方案优化模型的列生成算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第21卷第l期2012年2月运0PERATIONS筹与管理RESEARCHANDMANAGEMENTSCIENCEV01．21，No．1Feb．2012铁路客运网络列车开行方案优化模型的列生成算法蓝伯雄，吴李知(清华大学经济管理学院，北京100084)摘要：列车开行方案的设计是铁路旅客运输组织规划中的一个重要环节。本文首先给出了一个综合考虑铁路旅客运输的经济效益和公共服务性的优化模型，以铁路旅客运输的公共效益最大化为目标，对整个铁路客运网络上不同始发一终到和不同停站方式的列车开行方案进行优化。然后提出了一个求解此模型的启发式

2、列生成算法，该算法与标准列生成算法相比，可以减少迭代次数并缩短收敛时间。最后给出一组利用随机生成的网络和需求进行求解的算例，验证本算法可以在较短时间内求解较大规模的铁路网络列车开行方案优化问题，并能有效缩小问题规模。关键词：管理科学与运营管理；列生成算法；优化模型；铁路旅客运输；开行方案中图分类号：U292．4文章标识码：A文章编号：1007．3221(2012)01—0001·10AColumn—generationApproachtoLinePlanninginRailPassengerTransportLANBo—xi

3、ong．WU4Li—zhi(SchoolofEconomicsandManagement，TsinghuaUnivemi钞，Beijing100084，China)Abstract：Thelineplanningproblemisoneofthefundamentalelementsinstrategicplanningofpublicrailtrans—port．Itconsistsinfindinglinesandcorrespondingfrequenciesintransportnetworksuchthatagiv

4、endemandcanbesatisfied．Sofar，mostofthemodelsintheliteratureaimtominimizethecostsortomaximizethenumberofdirecttravelers．Inthispaperwepresentanewapproachmaximizingtheoperator’Sprofit，whileensuringthenatureofitspublicservices．ThisnewMIP(mixedintegerprogramming)modelta

5、kesintoaccountoftheoperat—ingcost，thenumberofdirecttravelers，andthetotalnumberoftransportedtravelers．Inaddition，weintroduceaheuristiccolumngenerationalgorithmtosolvethebasemodel．Ourcolumngenerationalgorithmcaneffectivelyreducetheproblemsize．Numericalresultsofrandom

6、lygenerateddataarepresented．Keywords：managementscienceandoperationsmanagement；columngenerationalgorithm；optimizationmodel；railpassengertransport；lineplanning0引言旅客列车的开行方案由旅客列车的运行区段、列车种类及开行对数三者构成⋯。其中运行区段是指旅客列车的始发站、终到站及经由的路线和停靠站，列车种类区别出列车不同的等级或性质，开行对数的多少表示行车量的大小。列车开行方

7、案的设计是铁路旅客运输组织规划中的一个重要环节，是运行图设计、车辆运用计划、乘务员运用计划的基础。列车开行方案的设计通常是从一个包括很多可能的发车方案的大集合中选取一组最优的开行方案，以在满足各种运营约束的同时达到一定的优化目标。旅客列车开行方案总的目标是以收稿日期：2010·ll·18作者简介：蓝伯雄(1950．)，男，黑龙江人。教授，博士生导师，研究方向：大系统优化理论与算法、供应链优化模型、收苴管理优化模型；昊李知(1983一)，女(羌族)，四川人．博士生．研宽方向：大系统优化理论与算法、铁路旅客运输优化模型与算法。2

8、运筹与管理2012年第2l卷客运量为基础(即“按流开车”)，在相关条件允许的情况下，经济、合理、充分地使用客运机车车辆和各种客运技术设备，最大限度地满足旅客出行需求，方便旅客出行(尽可能地减少旅客换乘次数的旅行时间)，同时要尽量减少运营成本，使铁路运营商收益最大化。好的旅客列车开行方案能够