基于拉格朗日的高速铁路车站作业优化

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (4): 120-125.

基于拉格朗日的高速铁路车站作业优化

白紫熙，周磊山^*，王劲，郭彬

北京交通大学交通运输学院，北京100044

收稿日期:2013-11-25 修回日期:2014-03-11 出版日期:2014-08-25 发布日期:2014-09-16
作者简介:白紫熙（1988-），女，山西晋城人，博士生.
基金资助:
国家科技支撑计划(2009BAG12A10-7)；铁道部科技司项目（2012X011-C）；中央高校基本科研业务费专项资金资助（2013YJS046）.

A Lagrangian Relaxation Model for High-speed Railway Station Operation Optimization

BAI Zi-xi, ZHOU Lei-shan,WANG Jin, GUO Bin

School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044,China

Received:2013-11-25 Revised:2014-03-11 Online:2014-08-25 Published:2014-09-16

摘要/Abstract

摘要：

本文从Job-Shop 调度角度出发，以列车为待加工的“工件”，将车站接车进路、到发线和发车进路看作“加工机器”，列车在车站的走行与停站看做不同的“作业工序”，把高速铁路车站作业问题抽象成Job-Shop 车间调度优化，以设备能力、冲突进路、停站时间为空间和时间约束，以最小化到发线的占用时间为优化目标，建立高速铁路车站作业优化模型.采用拉格朗日方法松弛原模型的约束条件，建立车站技术作业问题的拉格朗日对偶松弛问题，设计了高速铁路车站作业优化模型算法.并以高速铁路的某一车站为实例进行验证，实例表明，该算法可以有效地化解车站作业进路冲突和实现到发线运用时间的最小化.

关键词: 铁路运输, 车站作业优化, Job-Shop, 拉格朗日松弛, 次梯度算法

Abstract:

This paper applies the Job- Shop scheduling theory to station operation optimization of highspeed railway. In this study, trains are regarded as workpieces, the arrival-departure tracks, inbound and outbound road are regarded as machines, trains’operations at a station are treated as different works. In this way, the station operation optimization problem can be transformed into a special kind of job-shop problem. The study takes the station equipment capacity, conflicts in inbound road and outbound road, station dwell time as the space and time constraints. The optimization goal is to minimize dwell time of trains., Then, the paper develops the high-speed railway station operation optimization model and the corresponding Lagrangian relaxation model of station operation. The optimization algorithm is also proposed for high-speed railway station technique operation. A real high-speed railway station case shows that the model and algorithm are able to generate the optimization plan for high-speed railway station operation and they can effectively eliminate the conflicts in inbound road and outbound road.

Key words: railway transportation, station operation optimization, Job-Shop, lagrangian relaxation, subgradient

中图分类号:

U292.1

白紫熙，周磊山，王劲，郭彬. 基于拉格朗日的高速铁路车站作业优化[J]. 交通运输系统工程与信息, 2014, 14(4): 120-125.

BAI Zi-xi, ZHOU Lei-shan,WANG Jin, GUO Bin. A Lagrangian Relaxation Model for High-speed Railway Station Operation Optimization[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(4): 120-125.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18826.shtml

http://www.tseit.org.cn/CN/Y2014/V14/I4/120

参考文献

[1] 徐杰, 杜文. 基于遗传算法的区段站到发线运用优化安排[J]. 中国铁道科学, 2003,24(2): 109-114.[XU J, DU W. The genetic based algorithms optimization plan of using the arrival and departure track at railway sec? tional station[J]. China Railway Science, 2003, 24(2): 109-114.]

[2] 陈彦, 史峰. 旅客列车过站径路优化模型与算法[J]. 中国铁道科学, 2010, 31(2): 101-106. [CHEN Y, SHI F.Optimization model and algorithm for routing passenger trains through a railway station[J]. China Railway Science,2010, 31(2): 101-106.]
[3] 张英贵, 雷定猷. 铁路客运站股道运用窗时排序模型与算法[J]. 铁道学报, 2011,33(1): 1-7.[ZHANG Y G,LEI D Y. Due windows scheduling model and algorithm of track utilization in railway passenger stations[J]. Journal of the China Railway Society, 2011,33(1): 1-7.]
[4] 谢楚农, 黎新华. 铁路客运站到发线运用优化研究[J].中国铁道科学, 2004,25(5): 130-133.[XIE C N, LI X H. Optimization research for utilization of arrival and departure tracks in railroad passenger station[J]. China Railway Science, 2004,25(5): 130-133.]
[5] Malachy Carey, Sinead Carville. Scheduling and platforming trains at busy complex stations[J].Transportation Research Part A,2003,37：195-224.
[6] Partha Chakroborty, Durgesh Vikram. Optimum assignment of trains to platforms under partial schedule compliance[J]. Transportation Science,2008,42:169-184.
[7] Joaqu?'n Rodriguez. A constraint programming model for real-time trains scheduling at junctions[J]. Transportation Science 37:213-222.
[8] Richard Freling, Ramon M Lentink, Leo G Kroon, et al. Shunting of passenger train unitsin a railway station[J].Transportation Science,2005,39(2):261-272.
[9] Kibardin V M. Decomposition into functions in the minimization problem[J]. Automation and Remote Control，1980，40(8)：1311-1323.
[10] Diaby M, Bahl H C, Karwan M H, et a1. A Lagrangean relaxation approach for very- large- scale capacitated lot-sizing[J]. Management Science, 1992，38(2): 1329-1340.

[1]	耿庆桥, 贾元华, 陈军团. 基于变权可拓物元的铁路“走出去”公私合营项目风险决策[J]. 交通运输系统工程与信息, 2022, 22(2): 64-71.
[2]	戚建国, 周厚盛, 杨立兴, 周亚茹, 张春田. 灵活编组条件下轨道交通客货协同运输方案优化[J]. 交通运输系统工程与信息, 2022, 22(2): 197-205.
[3]	张晓明, 徐芳, 江文辉, 蒋朝哲. 考虑资金约束的中欧班列运价与运量决策分析[J]. 交通运输系统工程与信息, 2022, 22(1): 30-36.
[4]	张春田, 戚建国, 杨立兴, 高原, 高自友. 基于不确定旅客需求的高速铁路鲁棒列车开行方案研究[J]. 交通运输系统工程与信息, 2022, 22(1): 115-123.
[5]	周勇, 张杰, 钟祾充, 李文锋, 王国栋. 铁路集装箱中心站多轨道吊柔性协同调度优化[J]. 交通运输系统工程与信息, 2022, 22(1): 133-141.
[6]	牛惠民. 轨道列车时刻表问题研究综述[J]. 交通运输系统工程与信息, 2021, 21(5): 114-124.
[7]	胡臣杰, 张军. 基于时空等待特征系数的大型活动出行规划研究[J]. 交通运输系统工程与信息, 2021, 21(4): 148-155.
[8]	刘葛辉，陈绍宽，刘爽，金华，王丹阳. 资源约束下城市轨道交通基础设施维修任务安排优化模型[J]. 交通运输系统工程与信息, 2021, 21(3): 163-169.
[9]	徐智勇. 铁路电分相布设及纵断面协同优化研究[J]. 交通运输系统工程与信息, 2021, 21(3): 170-175.
[10]	钟明轩，乐逸祥，周磊山. 高铁站列车和调车作业计划一体化编制方法[J]. 交通运输系统工程与信息, 2021, 21(3): 176-186.
[11]	吕敏，帅斌，周照玉，张士行，左静，李林卿. 考虑边境站延误风险的中欧班列运输路径决策[J]. 交通运输系统工程与信息, 2021, 21(3): 254-259.
[12]	张蒙蒙，许茂增. 考虑政府补贴决策的中欧班列竞合关系研究[J]. 交通运输系统工程与信息, 2021, 21(2): 16-21.
[13]	李岸隽，王典，彭其渊. 基于个体出行链的区域城际铁路规划方法研究[J]. 交通运输系统工程与信息, 2021, 21(2): 30-36.
[14]	刘晓伟，晏启鹏，倪少权，吕苗苗，吕红霞. 考虑空车调配协调的货物列车开行方案优化研究[J]. 交通运输系统工程与信息, 2021, 21(2): 180-188.
[15]	杨森炎，宁连举，商攀. 基于时空状态网络的电动物流车辆路径优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 196-204.