Integrated Optimum Crew Planning in Fixed Shift System for Subways
-
摘要: 针对运营中常用的固定班制轮班模式，通过加入班次数量比例和备班约束，构建排班和轮班计划一体化的乘务计划优化模型，进行乘务组数的全局优化；之后对传统列生成求解算法进行改进，在定价子问题中分别针对不同班次类型，各自生成班次以适应新的模型约束，并设计加速策略，以完成对一体化优化模型的求解；最后以轮乘站设置不同的两条地铁线路为例开展案例研究，研究了在四班三运转和六班五运转班制下的优化效果，分析了算法的求解效率. 研究结果表明：固定班制条件下，与分阶段优化方法相比，简化了轮班单元构成，乘务组数量减少了6.67%～14.29%，求解时间节约了44.2%～51.4%.Abstract: In order to globally optimize crew members in commonly used fixed shift system, an integrated optimum scheduling that combines crew scheduling and rostering is proposed with the constraints of shift proportions and candidate shifts. Then, an improved column generation approach is developed for the proposed model in which the suitable shifts are generated according to the type of shifts in a pricing sub-problem. Meanwhile, acceleration techniques are used for solving the proposed model. Finally, the case studies with two metro lines connecting different home stations in Beijing is carried out, focusing on the optimization results under three shifts in four groups and five shifts in six groups and their algorithm efficiency. It is indicated that as for the fixed shift system, the proposed integrated optimum scheduling is able to reduce the number of drivers by 6.67%−14.29% in contrast to the separated optimization, and the computation time by 44.2%−51.4%.
-
Key words:
- subways /
- combinatorial optimization /
- integration optimization /
- column generation /
- crew scheduling
-
表 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}}$ 早班 1 0 0 1 0 0 白班 −1 1 0 −2 2 0 夜班 0 −1 1 0 −1 1 休息 0 0 −1 0 0 −2 
下载: 导出CSV
表 2 网络图模型中点、弧定义
Table 2. Definitions of nodes and arcs in network model
点 代表事件 时间属性 空间属性 源点 所有班次的开始 网络图的开始时间 汇点 所有班次的结束 网络图的结束时间 任务开始点 连续值乘区段的开始 连续值乘区段的开始时间 连续值乘区段的开始地点 任务结束点 连续值乘区段的结束 连续值乘区段的结束时间 连续值乘区段的结束地点 弧 代表活动 连式 连接条件 单层网络图 多层网络图 源点弧 班次开始前的准备 源点—开始点 任意任务开始点 第一层任意任务开始点 汇点弧 班次结束后的整备 结束点—汇点 任意任务结束点 最后一层任意任务结束点 就餐弧 连续值乘区段间的就餐 结束点—开始点 不存在 相邻层且满足就餐接续约束 任务弧 连续值乘任务 开始点—结束点 同一层且属于同一连续值乘区段 间休弧 连续值乘区段间的休息 结束点—开始点 同一层之间且满足间休接续约束
下载: 导出CSV
表 3 班次类型构成统计
Table 3. Numbers of different shift types
个 班次类型 线路 1 线路 2 分阶段方案 一体化方案 分阶段方案 一体化方案 四班三运转 六班五运转 四班三运转 六班五运转 早班数 20 19 24 15 14 18 白班数 21 19 12 14 14 9 夜班数 15 19 24 12 14 18 总数 56 57 60 41 42 45
下载: 导出CSV
表 4 轮班单元与乘务组数统计
Table 4. Numbers of rosters and drivers
个 线路 四班三运转 分阶段方案 一体化方案 白-夜-早-休数 夜-早-休-休数 白-休-休-休数 乘务组数 白-夜-早-休数 乘务组数 线路 1 20 0 1 84 19 76 线路 2 14 1 0 60 14 56 线路 六班五运转 分阶段方案 一体化方案 白-夜-早-休-白-休数 白-夜-早-休-夜-早数 白-夜-早-休-休-休数 乘务组数 白-夜-早-休-白-休数 乘务组数 线路 1 6 7 1 84 12 72 线路 2 4 5 1 60 9 54
下载: 导出CSV
表 5 算法求解效率对比分析
Table 5. Comparisons of solution efficiency among different solution methods
线路 模型算法 线性松弛解 整数解 可行班次数/个 LP 求解时间/s IP 求解时间/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.028ZHAO 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.004LI 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.026FENG 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.018ZHANG 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.18LIU 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.008JIA 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)
计量
- 文章访问数: 774
- HTML全文浏览量: 432
- PDF下载量: 29
- 被引次数: 0