• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

基于固定班制的地铁乘务计划一体化优化方法

金华 陈绍宽 刘爽 刘葛辉

金华, 陈绍宽, 刘爽, 刘葛辉. 基于固定班制的地铁乘务计划一体化优化方法[J]. 西南交通大学学报, 2020, 55(5): 955-962. doi: 10.3969/j.issn.0258-2724.20190952
引用本文: 金华, 陈绍宽, 刘爽, 刘葛辉. 基于固定班制的地铁乘务计划一体化优化方法[J]. 西南交通大学学报, 2020, 55(5): 955-962. doi: 10.3969/j.issn.0258-2724.20190952
JIN Hua, CHEN Shaokuan, LIU Shuang, LIU Gehui. Integrated Optimum Crew Planning in Fixed Shift System for Subways[J]. Journal of Southwest Jiaotong University, 2020, 55(5): 955-962. doi: 10.3969/j.issn.0258-2724.20190952
Citation: JIN Hua, CHEN Shaokuan, LIU Shuang, LIU Gehui. Integrated Optimum Crew Planning in Fixed Shift System for Subways[J]. Journal of Southwest Jiaotong University, 2020, 55(5): 955-962. doi: 10.3969/j.issn.0258-2724.20190952

基于固定班制的地铁乘务计划一体化优化方法

doi: 10.3969/j.issn.0258-2724.20190952
基金项目: 国家自然科学基金项目(71571015,71621001)
详细信息
    作者简介:

    金华(1993—),男,博士研究生,研究方向为交通运输规划与管理,E-mail:18114037@bjtu.edu.cn

    通讯作者:

    陈绍宽(1977—),男,教授,博士,研究方向为交通运输规划与管理,E-mail:shkchen@bjtu.edu.cn

  • 中图分类号: U292.6

Integrated Optimum Crew Planning in Fixed Shift System for Subways

  • 摘要: 针对运营中常用的固定班制轮班模式,通过加入班次数量比例和备班约束,构建排班和轮班计划一体化的乘务计划优化模型,进行乘务组数的全局优化;之后对传统列生成求解算法进行改进,在定价子问题中分别针对不同班次类型,各自生成班次以适应新的模型约束,并设计加速策略,以完成对一体化优化模型的求解;最后以轮乘站设置不同的两条地铁线路为例开展案例研究,研究了在四班三运转和六班五运转班制下的优化效果,分析了算法的求解效率. 研究结果表明:固定班制条件下,与分阶段优化方法相比,简化了轮班单元构成,乘务组数量减少了6.67%~14.29%,求解时间节约了44.2%~51.4%.

     

  • 图 1  四班三运转示意

    Figure 1.  Diagram of three shift in four groups

    图 2  双层网络图模型示意

    Figure 2.  Diagram of double-layer network

    图 3  一体化优化模型求解算法流程

    Figure 3.  Algorithm flow chart of integrated optimization

    表  1  不同班制对应的班次比例系数

    Table  1.   Proportional coefficient of shifts in different shift system

    班次 $j$ 的类型四班三运转六班五运转
    ${b_{1,j}}$${b_{2,j}}$${b_{3,j}}$ ${b_{1,j}}$${b_{2,j}}$${b_{3,j}}$
    早班100100
    白班−110−220
    夜班0−110−11
    休息00−100−2
    下载: 导出CSV

    表  2  网络图模型中点、弧定义

    Table  2.   Definitions of nodes and arcs in network model

    代表事件时间属性空间属性
    源点 所有班次的开始 网络图的开始时间
    汇点 所有班次的结束 网络图的结束时间
    任务开始点 连续值乘区段的开始 连续值乘区段的开始时间 连续值乘区段的开始地点
    任务结束点 连续值乘区段的结束 连续值乘区段的结束时间 连续值乘区段的结束地点
    代表活动 连式 连接条件
    单层网络图 多层网络图
    源点弧 班次开始前的准备 源点—开始点 任意任务开始点 第一层任意任务开始点
    汇点弧 班次结束后的整备 结束点—汇点 任意任务结束点 最后一层任意任务结束点
    就餐弧 连续值乘区段间的就餐 结束点—开始点 不存在 相邻层且满足就餐接续约束
    任务弧 连续值乘任务 开始点—结束点 同一层且属于同一连续值乘区段
    间休弧 连续值乘区段间的休息 结束点—开始点 同一层之间且满足间休接续约束
    下载: 导出CSV

    表  3  班次类型构成统计

    Table  3.   Numbers of different shift types

    班次类型线路 1 线路 2
    分阶段方案一体化方案 分阶段方案一体化方案
    四班三运转六班五运转四班三运转六班五运转
    早班数201924 151418
    白班数21191214149
    夜班数151924121418
    总数565760 414245
    下载: 导出CSV

    表  4  轮班单元与乘务组数统计

    Table  4.   Numbers of rosters and drivers

    线路四班三运转
    分阶段方案一体化方案
    白-夜-早-休数夜-早-休-休数白-休-休-休数乘务组数 白-夜-早-休数乘务组数
    线路 12001841976
    线路 21410601456
    线路 六班五运转
    分阶段方案一体化方案
    白-夜-早-休-白-休数白-夜-早-休-夜-早数白-夜-早-休-休-休数乘务组数白-夜-早-休-白-休数乘务组数
    线路 1671841272
    线路 245160954
    下载: 导出CSV

    表  5  算法求解效率对比分析

    Table  5.   Comparisons of solution efficiency among different solution methods

    线路模型算法线性松弛解整数解可行班次数/个LP 求解时间/sIP 求解时间/s总求解时间/s
    线路 1 四班三运转 原算法 54.55 57 572 552.8 2.2 555.0
    加速算法 54.55 57 446 43.5 1.4 45.0
    六班五运转 原算法 55.27 60 603 428.7 1.8 430.5
    加速算法 55.27 60 442 44.0 1.6 45.6
    分阶段方案 54.29 56 374 81.1 1.5 82.6
    线路 2 四班三运转 原算法 42.00 48 248 415.0 73.3 488.3
    加速算法 42.00 42 892 220.1 2.9 223.0
    六班五运转 原算法 40.39 45 856 647.3 2.5 649.8
    加速算法 40.39 45 883 219.7 7.7 227.5
    分阶段方案 38.90 41 717 422.0 36.5 458.6
    下载: 导出CSV
  • CAPRARA A, FISCHETTI M, TOTH P, et al. Algorithms for railway crew management[J]. Mathematical Programming, 1997, 79(1/2/3): 125-141. doi: 10.1007/BF02614314
    SOUAI N, TEGHEM J. Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem[J]. European Journal of Operational Research, 2009, 199(3): 674-683. doi: 10.1016/j.ejor.2007.10.065
    SADDOUNE M, DESAULNIERS G, ELHALLAOUI I, et al. Integrated airline crew pairing and crew assignment by dynamic constraint aggregation[J]. Transportation Science, 2012, 46(1): 39-55. doi: 10.1287/trsc.1110.0379
    SADDOUNE M, DESAULNIERS G, ELHALLAOUI I, et al. Integrated airline crew scheduling:a bi-dynamic constraint aggregation method using neighborhoods[J]. European Journal of Operational Research, 2011, 212(3): 445-454. doi: 10.1016/j.ejor.2011.02.009
    CHEN C H, LIU T K, CHOU J H. Integrated short-haul airline crew scheduling using multiobjective optimization genetic algorithms[J]. IEEE Transactions on Systems,Man,and Cybernetics:Systems, 2013, 43(5): 1077-1090.
    ŞAHIN G, YÜCEOĞLU B. Tactical crew planning in railways[J]. Transportation Research Part E: Logistics and Transportation Review, 2011, 47(6): 1221-1243. doi: 10.1016/j.tre.2011.05.013
    SUYABATMAZ A Ç, ŞAHIN G. Railway crew capacity planning problem with connectivity of schedules[J]. Transportation Research Part E: Logistics and Transportation Review, 2015(84): 88-100.
    赵鹏,姚凤金,张洪亮. 综合调度仿真系统中的机车乘务计划的编制[J]. 铁道运输与经济,2005,27(3): 74-76. doi: 10.3969/j.issn.1003-1421.2005.03.028

    ZHAO Peng, YAO Fengjin, ZHANG Hongliang. The establishment of locomotive crew working plan in comprehensive command & control simulation system[J]. Railway Transport and Economy, 2005, 27(3): 74-76. doi: 10.3969/j.issn.1003-1421.2005.03.028
    王莹,刘军,苗建瑞. 客运专线乘务交路计划编制的优化模型与算法[J]. 铁道学报,2009,31(1): 15-19.

    WANG Ying, LIU Jun, MIAO Jianrui. Modeling and solving the crew scheduling problem of passenger dedicated line[J]. Journal of the China Railway Society, 2009, 31(1): 15-19.
    CAPRARA A, MONACI M, TOTH P. A global method for crew planning in railway application[C]//Computer-Aided Scheduling of Public Transport. Berlin: Springer, 2001: 17-36.
    李献忠,徐瑞华. 基于时间耗费的城市轨道交通乘务排班优化[J]. 铁道学报,2007,29(1): 21-25. doi: 10.3321/j.issn:1001-8360.2007.01.004

    LI Xianzhong, XU Ruihua. Optimization of crew scheduling for urban rail transportation based on time costs[J]. Journal of the China Railway Society, 2007, 29(1): 21-25. doi: 10.3321/j.issn:1001-8360.2007.01.004
    李献忠,徐瑞华. 基于乘务广义费用的城市轨道交通排班[J]. 同济大学学报(自然科学版),2007,35(6): 750-754.

    LI Xianzhong, XU Ruihua. An optimal wide crew-related costs-based scheduling for crew of urban rail transportation[J]. Journal of Tongji University (Natural Science), 2007, 35(6): 750-754.
    丰富,陈绍宽,杜鹏. 考虑时间均衡度的城市轨道交通乘务排班计划优化方法[J]. 交通运输系统工程与信息,2014,14(6): 164-170. doi: 10.3969/j.issn.1009-6744.2014.06.026

    FENG Fu, CHEN Shaokuan, DU Peng. Time equitability-based crew scheduling optimization for mass transit rail[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(6): 164-170. doi: 10.3969/j.issn.1009-6744.2014.06.026
    张增勇,毛保华,杜鹏,等. 基于惩罚费用的城市轨道交通乘务排班优化模型与算法[J]. 交通运输系统工程与信息,2014,14(2): 113-120. doi: 10.3969/j.issn.1009-6744.2014.02.018

    ZHANG Zengyong, MAO Baohua, DU Peng, et al. 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. doi: 10.3969/j.issn.1009-6744.2014.02.018
    刘杰,代佳妮. 基于驾驶质量的城市轨道交通乘务排班优化研究[J]. 重庆交通大学学报(自然科学版),2019,38(4): 116-122. doi: 10.3969/j.issn.1674-0696.2019.04.18

    LIU Jie, DAI Jiani. Optimization of crew schedule of urban rail transit based on steering quality[J]. Journal of Chongqing Jiaotong University (Natural Science), 2019, 38(4): 116-122. doi: 10.3969/j.issn.1674-0696.2019.04.18
    贾明奔,李世伟. 苏州轨道交通一号线乘务运作研究[J]. 城市公共交通,2012(2): 20-22. doi: 10.3969/j.issn.1009-1467.2012.02.008

    JIA Mingben, LI Shiwei. Crew organization study of Suzhou rail transit line 1[J]. Urban Public Transport, 2012(2): 20-22. doi: 10.3969/j.issn.1009-1467.2012.02.008
  • 加载中
图(3) / 表(5)
计量
  • 文章访问数:  761
  • HTML全文浏览量:  429
  • PDF下载量:  28
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-10-08
  • 修回日期:  2020-03-06
  • 网络出版日期:  2020-03-09
  • 刊出日期:  2020-10-01

目录

    /

    返回文章
    返回