基于惩罚费用的城市轨道交通乘务排班优化 模型与算法

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

基于惩罚费用的城市轨道交通乘务排班优化模型与算法

张增勇，毛保华^*，杜鹏，许奇，吴珂琪

北京交通大学城市交通复杂系统理论与技术教育部重点实验室，北京100044

收稿日期:2013-09-17 修回日期:2013-12-05 出版日期:2014-04-25 发布日期:2014-07-07
作者简介:张增勇（1985-），男，山西运城人，博士生.
基金资助:
国家自然科学基金重点项目(71131001)；国家基础研究计划项目(2012CB725406).

Urban Rail Transit Crew Scheduling Model and Algorithm Based on Punishment Costs

ZHANG Zeng-yong, MAO Bao-hua, DU Peng, XU Qi, WU Ke-qi

Ministry of Education Key Laboratory of Complex System Theory and Technology of Urban Traffic， Beijing Jiaotong University，Beijing l00044，China

Received:2013-09-17 Revised:2013-12-05 Online:2014-04-25 Published:2014-07-07

摘要/Abstract

摘要：

乘务排班计划是城市轨道交通运营的核心问题之一.本文首先分析了乘务排班问题，接着基于惩罚费用构建了乘务排班优化模型,并提出了相应惩罚费用计算方法.根据乘务排班计划步骤可知，模型分为乘务作业段生成模型和乘务工作班生成模型，其中乘务作业段生成模型为乘务工作班生成模型的下层，乘务作业段生成模型的解为乘务工作班生成模型的输入条件. 随后针对建立的双层模型，分别设计了改进的Dijkstra算法和离散粒子群算法.最后，采用某地铁线路的运行数据对模型和算法进行了验证.结果表明，间休时间的均值为37分，工作时间的均值为6小时41分，并且所有的乘务工作班分布均匀，证明了模型与算法的有效性.

关键词: 城市轨道交通, 乘务排班计划, 作业段, 工作班, 离散粒子群算法

Abstract:

Crew scheduling is one of the core issues of urban rail transit operations. This paper develops an optimization model of crew scheduling based on punishment costs, and proposes corresponding punishment cost calculation method. From the process of crew scheduling, it is found that the models include a crew operating segment generation model and a crew work shift generation model. The crew operating segment generation model is the lower model, and its results are the inputs of crew work shift generation model. Then, for the double-layer model, the paper formulates the improved Dijkstra algorithm and discrete particle swarm optimization. Finally, a subway line’s operational data are used to validate the model and algorithms. The results show that the average rest time is37minutes, the average working time is6hours41minutes, and the crew work shifts are uniformly distributed. All of these demonstrate the effectiveness of the models and its algorithms.

Key words: urban rail transit, crew scheduling, operating segment, work shift, discrete particle swarm optimization

中图分类号:

U292.6

张增勇，毛保华*，杜鹏，许奇，吴珂琪. 基于惩罚费用的城市轨道交通乘务排班优化模型与算法[J]. 交通运输系统工程与信息, 2014, 14(2): 113-120.

ZHANG Zeng-yong, MAO Bao-hua, DU Peng, XU Qi, WU Ke-qi. Urban Rail Transit Crew Scheduling Model and Algorithm Based on Punishment Costs[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(2): 113-120.

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

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

http://www.tseit.org.cn/CN/Y2014/V14/I2/113

参考文献

［1］Dennis H. A column generation approach for the rail crew re-scheduling problem[J].European Journal of Op? erational Research,2007,180(1):163–173.

［2］Lucas P V, Daniel P, Dennis H, et al. Railway crew rescheduling with retiming[J].Transportation Research Part C.2012,20(1):95-110.
［3］Silke J, Ulrich W T. Divide- and- price: A decomposition algorithm for solving large railway crew scheduling problems [J]. European Journal of Operational Research,2012,219(2):214-223.
［4］赵鹏. 高速铁路动车组和乘务员运用的研究[D].北京交通大学,1998.
［5］王莹, 刘军, 苗建瑞. 客运专线乘务交路计划编制的优化模型与算法[J]. 铁道学报. 2009, 31(1): 15-19.[WANG Y, LIU J, MIAO J R. Modeling and solving the crew scheduling problem of passenger dedicated line[J].Journal of the China Railway Society, 2009, 31(1):15-19.]
［6］田志强. 高速铁路乘务计划编制优化理论与方法研究[D].西南交通大学, 2011. [TIAN Z Q. Study on theory and methods of crew planning problem of high-speed railway[D]. Chengdu: Southwest Jiaotong University,2011.]
［7］Chu S C K, Chan E C. Crew scheduling of light rail transit in Hong Kong: form modeling to implementation[J].Computers Ops Res.1998,25(11):887-894.
［8］李献忠, 徐瑞华. 基于时问耗费的城市轨道交通乘务排班优化[J].铁道学报. 2007, 29(1):21-25. [LI X Z,XU R H. Optimization of crew scheduling for urban rail transportation based on time costs[J]. Journal of the China Railway Society,2007,29(1):21-25.]

［9］陈仕军, 沈吟东, 苏璇, 等. 带中式用餐约束的乘务调度问题[J].交通运输系统工程与信息. 2013, 13(2):90-95. [CHEN S J, SHEN Y D, SU X, et al. A crew scheduling with Chinese meal break rules [J]. Journal of Transportation Systems Engineering and Information Technology,2013,13(2):90-95.]

[1]	许得杰, 巩亮, 朱宁, 王雪鑫. 城市轨道交通多交路共线运营客流分配方法[J]. 交通运输系统工程与信息, 2021, 21(5): 206-213.
[2]	张书婧, 许奇, 贾顺平, 廖婧仪. 城市轨道交通新建线路对沿线住宅价格增值的时空效应[J]. 交通运输系统工程与信息, 2021, 21(4): 54-62.
[3]	金华，陈绍宽，王志美，张翕然，许凤志. 基于地铁乘务资源共享的排班计划优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 126-132.
[4]	宿帅，刘旭，王学楷，唐涛，曹源. 北京地铁双超列车运行图编制方法[J]. 交通运输系统工程与信息, 2021, 21(1): 101-107.
[5]	刘爽，王慧文，兴妍，陈绍宽. 基于案例的城市轨道交通车站能耗定额标准研究[J]. 交通运输系统工程与信息, 2020, 20(4): 231-235.
[6]	邹庆茹，姚向明，赵鹏. 城市轨道交通峰前折扣定价方案编制模型[J]. 交通运输系统工程与信息, 2020, 20(2): 13-19.
[7]	禹丹丹，姚向明，徐会杰，赵鹏. 峰前折扣票价下轨道交通乘客出发时间弹性[J]. 交通运输系统工程与信息, 2019, 19(5): 156-162.
[8]	戎亚萍. 基于多编组的列车满载率均衡化方法研究[J]. 交通运输系统工程与信息, 2019, 19(4): 187-192.
[9]	贾文峥，宋晓敏，廖理明，冯旭杰. 基于情景分析的城市轨道交通应急指挥系统功能需求研究[J]. 交通运输系统工程与信息, 2019, 19(2): 46-51.
[10]	许得杰，巩亮，曾俊伟. 考虑客流时变需求的大小交路列车时刻表优化模型[J]. 交通运输系统工程与信息, 2019, 19(2): 122-129.
[11]	蒋熙，贾飞凡，冯佳平. 基于AFC数据的城轨路网客流OD在线动态估计[J]. 交通运输系统工程与信息, 2018, 18(5): 129-135.
[12]	毛保华，高自友. 城市轨道交通网络运营资源共享方法与技术进展[J]. 交通运输系统工程与信息, 2018, 18(3): 1-8.
[13]	孙元广，史海欧，王莹，陈绍宽. 城市轨道交通快慢车开行方案双层规划模型[J]. 交通运输系统工程与信息, 2018, 18(3): 160-167.
[14]	陈坚，唐炜，蔡晓禹，段力伟. 城市轨道交通乘客满意度多群组结构方程模型[J]. 交通运输系统工程与信息, 2018, 18(1): 173-178.
[15]	邹庆茹，赵鹏，姚向明. 基于售检票数据的城市轨道交通乘客分类[J]. 交通运输系统工程与信息, 2018, 18(1): 223-230.