基于时空状态网络的高速铁路乘务交路计划优化研究  

Research on Optimization of Crew Scheduling of High-speed Railway Based on Time Space State Network

作　　者：张哲铭 王莹[2] 廖正文 曹文慧 ZHANG Zheming;WANG Ying;LIAO Zhengwen;CAO Wenhui(Hangzhou Pi-Solution Information Technology Co., Ltd., Hangzhou 311100, China;School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China;State Key Lab of Rail Traffic Control and Safety, Beijing Jiaotong University, Beijing 100044, China;Beijing State Postal Science & Technology Development Co., Ltd., Beijing 100032, China)

机构地区：[1]杭州派迩信息技术有限公司,浙江杭州311100 [2]北京交通大学交通运输学院,北京100044 [3]北京交通大学轨道交通控制与安全国家重点实验室,北京100044 [4]北京国邮科迅科技发展有限公司,北京100032

出　　处：《铁道学报》2019年第9期1-11,共11页Journal of the China Railway Society

基　　金：国家重点研发计划(2018YFB1201504);上海局集团有限公司科研计划(2019005)

摘　　要：乘务交路计划是同时考虑相对时间和绝对时间约束的混合时间问题,该类问题难以用时空网络描述。提出基于乘务规则的时空节点状态坐标递推原则和乘务任务可行转化判定条件,以此作为网络生成策略,构建融入乘务规则的时空状态网络,从而控制网络规模并简化数学模型复杂度。建立基于该网络的0-1整数规划模型,设计拉格朗日松弛算法,将多乘务交路组合优化问题分解为单乘务交路时空最短路径问题集合,提高求解效率。最后,以京津城际铁路和郑州东站高速铁路网为背景进行验算。结果表明:本方法不仅能有效解决高速铁路乘务交路计划问题,在求解大规模混合时间问题时也有一定效果。Crew Scheduling Problem(CSP) is a ‘mixing time’ problem considering the constraints of relative time and absolute time, which is difficult to solve by using the timespace network. This paper proposed recursion principle of time-space-state coordinates between adjacent two nodes and judgment method of feasible transformation between crew tasks as a network generation strategy which controlled the network scale and reduced the model complexity to construct a time space state network. A 0-1 integer programming model based on time space state network was established and Lagrangian relaxation algorithm was designed to divide the combinatorial optimization problem of multi-crew duties into a set of single-crew duty time-space shortest path problems to improve the solving efficiency.Finally, the model and algorithm were verified against the cases of Beijing-Tianjin Intercity Railway and the high-speed railway network centered on Zhengzhou East Station. The results show that this method not only solves the CSP of high-speed railway effectively, but also has a certain effect on solving large-scale ‘mixing time’ problem.

关 键 词：乘务交路计划 混合时间问题 时空状态网络 0-1整数规划 拉格朗日松弛 

分 类 号：U293.32[交通运输工程—交通运输规划与管理]