高速列车周期性开行方案优化模型与交叉熵算法

交通运输系统工程与信息 ›› 2020, Vol. 20 ›› Issue (1): 160-165.

高速列车周期性开行方案优化模型与交叉熵算法

付慧伶^*，胡怀宾，武鑫

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

收稿日期:2019-09-19 修回日期:2019-11-18 出版日期:2020-02-25 发布日期:2020-03-02
作者简介:付慧伶(1983-)，女，吉林蛟河人，副教授.
基金资助:
国家重点研发计划/National Key Research and Development Program of China(2018YFB1201402)；国家自然科学基金/ National Natural Science Foundation of China(61703030)；中国铁路总公司科技研究开发计划/ China Railway Corporation Science and Technology Research and Development Plan(P2018X001).

Model and Cross Entropy Algorithm for Periodic Line Planning Problem of High-speed Trains

FU Hui-ling, HU Huai-bin, WU Xin

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

Received:2019-09-19 Revised:2019-11-18 Online:2020-02-25 Published:2020-03-02

摘要/Abstract

摘要：

中国高速铁路不同车站之间，旅客对乘车时间、频次、直达与中转等列车服务要求的异质特征明显. 如何在一个周期内(如1 h 或2 h)用有限的列车起讫点和停站方式组合，满足多样化客流需求是制定周期性列车开行方案所面临的问题. 建立整数规划模型，确定一个周期内大站停、隔站停多个层级列车的起讫点、停站、开行频率和编组，保证站间直达率，满足旅客异质需求. 模型从按特定规则生成的备选列车集合中优选列车，同时决策其开行频率，实现列车开行成本最低. 针对问题特点设计交叉熵算法，与CPLEX软件的实例求解结果和计算效率进行对比.结果表明，所提算法能有效求解大规模实际问题，列车开行方案服务指标较优.

关键词: 铁路运输, 高速列车开行方案优化, 整数规划, 周期性列车开行方案, 交叉熵算法

Abstract:

Passengers between different stations in China's high- speed railway have obviously heterogeneous demand for trip time, frequency, direct or transfer service. A periodic line plan is required to use limited combination of train OD and stopping patterns in a short period (e.g. 1 h or 2 h) to meet diverse passenger demand. In this paper, an integer programming model is established. The train OD, stops, frequencies and compositions in a period are determined for classified trains which either stop at major stations or skip-stop a subset of stations. A high non-transfer rate is ensured, and heterogeneous passenger demand is satisfied. The model selects trains from a set of candidate lines generated according to specific rules, decides their frequencies, and minimizes the operation cost. A cross entropy algorithm is designed, the instance solutions and computation efficiency are compared with those of CPLEX software. Results show that the proposed algorithm is effective when the problem size is large, and service indicators of line plans perform well.

Key words: railway transportation, line plan optimization for high- speed trains, integer programming, periodic line plan, cross entropy algorithm

中图分类号:

U268.6

付慧伶，胡怀宾，武鑫. 高速列车周期性开行方案优化模型与交叉熵算法[J]. 交通运输系统工程与信息, 2020, 20(1): 160-165.

FU Hui-ling, HU Huai-bin, WU Xin. Model and Cross Entropy Algorithm for Periodic Line Planning Problem of High-speed Trains[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(1): 160-165.

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

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

http://www.tseit.org.cn/CN/Y2020/V20/I1/160

参考文献

[1] CLAESSENS M T, VAN DIJK N M, ZWANEVELD P J. Cost optimal allocation of passenger lines[J]. European Journal of Operational Research, 1998(110): 474-489.

[2] SCHOLL S. Customer-oriented line planning[D]. Germany: University of Kaiserslautern, 2005.

[3] GOERIGK M, SCHMIDT M. Line planning with useroptimal route choice[J]. European Journal of Operational Research, 2017, 259(2): 424-436.

[4] CHANG Y H, YEH C H, SHEN C C. A multiobjective model for passenger train services planning: Application to Taiwan's high-speed rail line[J]. Transportation Research Part B, 2000(34): 91-106.

[5] 汪波, 杨浩, 张志华. 基于周期运行图的京津城际铁路列车开行方案研究[J]. 铁道学报, 2007, 29(2): 8-13. [WANG B, YANG H, ZHANG Z H. The Research on the train operation plan of the Beijing-Tianjin inter-city railway based on periodic train diagrams[J]. Journal of the China Railway Society, 2007, 29(2): 8-13.]

[6] 颜颖, 韩宝明, 李华. 高速铁路周期化列车开行方案研究[J]. 铁道运输与经济, 2011, 33(11): 35-39. [YAN Y, HAN B M, LI H. Study on periodic line planning of high- speed rail[J]. Railway Transport and Economy, 2011, 33(11): 35-39.]

[7] 肖龙文, 史峰. 铁路公交化旅客列车开行方案优化[J]. 湖南大学学报, 2009, 36(1): 85-88. [XIAO L W, SHI F. Optimization of train of mass transit type plan[J]. Journal of Hunan University, 2009, 36(1): 85-88.]

[8] ZHOU W L, TIAN J, XUE L, et al. Multi-periodic train timetabling using a period- type- based Lagrangian relaxation decomposition[J]. Transportation Research Part B, 2017(105): 144-173.

[9] 李天琦, 聂磊, 谭宇燕. 基于换乘接续优化的高铁周期性列车运行图编制研究[J]. 铁道学报, 2019, 41(3): 10-19. [LI T Q, NIE L, TAN Y Y. Study on cyclic timetable generation of high-speed rail based on transfer connection optimization[J]. Journal of the China Railway Society, 2019, 41(3): 10-19.]

[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): 74-84.
[5]	张春田, 戚建国, 杨立兴, 高原, 高自友. 基于不确定旅客需求的高速铁路鲁棒列车开行方案研究[J]. 交通运输系统工程与信息, 2022, 22(1): 115-123.
[6]	周勇, 张杰, 钟祾充, 李文锋, 王国栋. 铁路集装箱中心站多轨道吊柔性协同调度优化[J]. 交通运输系统工程与信息, 2022, 22(1): 133-141.
[7]	郭彦茹, 罗志雄, 王家川, 何方. 数据驱动的共享单车停放区规划方法研究[J]. 交通运输系统工程与信息, 2021, 21(6): 9-16.
[8]	牛惠民. 轨道列车时刻表问题研究综述[J]. 交通运输系统工程与信息, 2021, 21(5): 114-124.
[9]	刘葛辉，陈绍宽，刘爽，金华，王丹阳. 资源约束下城市轨道交通基础设施维修任务安排优化模型[J]. 交通运输系统工程与信息, 2021, 21(3): 163-169.
[10]	徐智勇. 铁路电分相布设及纵断面协同优化研究[J]. 交通运输系统工程与信息, 2021, 21(3): 170-175.
[11]	钟明轩，乐逸祥，周磊山. 高铁站列车和调车作业计划一体化编制方法[J]. 交通运输系统工程与信息, 2021, 21(3): 176-186.
[12]	马晓磊，闫昊阳，缪然. 考虑财政补贴的电动公交车队置换优化模型[J]. 交通运输系统工程与信息, 2021, 21(3): 200-205.
[13]	吕敏，帅斌，周照玉，张士行，左静，李林卿. 考虑边境站延误风险的中欧班列运输路径决策[J]. 交通运输系统工程与信息, 2021, 21(3): 254-259.
[14]	张蒙蒙，许茂增. 考虑政府补贴决策的中欧班列竞合关系研究[J]. 交通运输系统工程与信息, 2021, 21(2): 16-21.
[15]	李岸隽，王典，彭其渊. 基于个体出行链的区域城际铁路规划方法研究[J]. 交通运输系统工程与信息, 2021, 21(2): 30-36.