基于列生成的城市轨道交通乘务计划优化编制方法研究
|
摘要
乘务日计划是乘务人员每日的工作计划,其编制结果直接影响运营部门的运营成本。提出一种基于列生成算法的城市轨道交通乘务计划优化编制方法,以集合划分模型为主规划,将子规划归结为以乘务作业段之间的衔接关系为基础的网络图上的最短路问题。网络图中权重的确定综合考虑了乘务任务数等多种影响因素,切合现场的实际情况。同时提出了一种基于影子价格的标号法以求解子规划,该方法利用主规划传递给子规划的影子价格,以贪婪的方式快速找到符合要求的乘务作业段的组合。案例分析表明,应用本文提出的方法生成的乘务日计划各项指标均优于现场日计划。进一步分析发现,随着工作效率的提高,通过压缩非必要劳动时间来提升工作效率的空间显著降低。
Crew schedule is the daily plan of crews, which has direct effect on the cost of rail transit operation. A column generation-based crew scheduling optimization method for urban rail transit is proposed, with set cutting model as the main-problem, and shortest path model as the sub-problem, which is based on a graph describing relations between tasks. The weights in the graph are considered comprehensively by factors including number of shifts that correspond to reality. Also it is proposed a labelling method based on shadow price to solve the sub-problem. This method takes advantage of simplex multipliers generated by main-problem, and keeps generating new feasible shifts quickly in a greedy way. Case study shows that indices of the crew schedule yielded by the method proposed in this paper are better than those used by the operation agency. Further analysis indicates that with the increasing of working efficiency, it is less significant to increase the efficiency by the way of reducing unnecessary labor time.
Crew schedule is the daily plan of crews, which has direct effect on the cost of rail transit operation. A column generation-based crew scheduling optimization method for urban rail transit is proposed, with set cutting model as the main-problem, and shortest path model as the sub-problem, which is based on a graph describing relations between tasks. The weights in the graph are considered comprehensively by factors including number of shifts that correspond to reality. Also it is proposed a labelling method based on shadow price to solve the sub-problem. This method takes advantage of simplex multipliers generated by main-problem, and keeps generating new feasible shifts quickly in a greedy way. Case study shows that indices of the crew schedule yielded by the method proposed in this paper are better than those used by the operation agency. Further analysis indicates that with the increasing of working efficiency, it is less significant to increase the efficiency by the way of reducing unnecessary labor time.
引文
[1] 褚飞跃, 田志强, 倪少权. 高速铁路单循环乘务排班计划编制模型与算法[J]. 铁道学报, 2012, 34(7):1-9.CHU Feiyue, TIAN Zhiqiang, NI Shaoquan. Model and Algorithm for Formulation of the Single Cycle Crew Rostering Plans of High-speed Railways[J]. Journal of the China Railway Society, 2012, 34(7):1-9.
[2] 杨国元, 史天运, 张秋亮. 铁路客运乘务排班计划编制模型及算法[J]. 交通运输系统工程与信息, 2016, 16(4):159-164.YANG Guoyuan, SHI Tianyun, ZHANG Qiuliang. Model and Algorithm for Railway Passenger Crew Rostering Plan[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(4):159-164.
[3] 夏平, 马建军. 乘务员运用计划编制模型与计算方法的研究[J]. 铁道运输与经济, 2007, 29(11):27-30.XIA Ping, MA Jianjun. Study on Model and Algorithm of Crew Working Plan[J]. Railway Transport and Economy, 2007, 29(11):27-30.
[4] 阎永光, 黄斌. 广深线城际列车乘务组排班计划编制方法探讨[J]. 交通运输工程与信息学报, 2010, 8(1):25-29.YAN Yongguang, HUANG Bin. Research on the Crew Schedule Programming Method of Guangzhou-Shenzhen Intercity Trains[J]. Journal of Transportation Systems Engineering and Information Technology, 2010, 8(1):25-29.
[5] 李耀华, 谭娜. 基于遗传算法的飞机一体化排班优化方法[J]. 控制工程, 2017, 24(2):435-440.LI Yaohua, TAN Na. Optimization Method of Aircraft Integrated Planning Based on Genetic Algorithm[J]. Control Engineering of China, 2017, 24(2):435-440.
[6] 吴东华, 夏洪山. 基于航空公司成本最小化的飞机排班问题模型与算法[J]. 交通运输系统工程与信息, 2014, 14(1):109-116.WU Donghua, XIA Hongshan. Model and Algorithm for Fleet Assignment Problem Based on Airlines Cost Minimization[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(1):109-116.
[7] 陈明明, 牛惠民. 多车场公交乘务排班问题优化[J]. 交通运输系统工程与信息, 2013, 13(5):159-166.CHEN Mingming, NIU Huimin. An Optimization Model for Bus Crew Scheduling with Multiple Depots[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(5):159-166.
[8] 陈明明, 牛惠民. 带时间窗的多车场公交乘务排班优化[J]. 兰州交通大学学报, 2015, 34(4):100-106.CHEN Mingming, NIU Huimin. An Optimization for Bus Crew Scheduling with Multiple Depots under Time Window Condition[J]. Journal of Lanzhou Jiaotong University, 2015, 34(4):100-106.
[9] 李献忠, 徐瑞华. 基于时间耗费的城市轨道交通乘务排班优化[J]. 铁道学报, 2007, 29(1):21-25.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.
[10] 张增勇, 毛保华, 杜鹏,等. 基于惩罚费用的城市轨道交通乘务排班优化模型与算法[J]. 交通运输系统工程与信息, 2014, 14(2):113-120.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.
[11] 丰富, 陈绍宽, 杜鹏. 考虑时间均衡度的城市轨道交通乘务排班计划优化方法[J]. 交通运输系统工程与信息, 2014,14(6):164-170.FENG Fu, CHEN Shaokuan, DU Peng. Time Equitability-based Crew Scheduling Optimization for Urban Rail Transit[J]. Journal of Transportation Systems Engineering and Information Technology, 2014,14(6):164-170.
[12] POTTHOFF D, HUISMAN D, DESAULNIERS G. Column Generation with Dynamic Duty Selection for Railway Crew Rescheduling[J]. Transportation Science, 2010, 44(4):493-505.
[13] JANACEK J, KOHANI M, KONIORCZYK M, et al. Optimization of Periodic Crew Schedules with Application of Column Generation Method[J]. Transportation Research Part C: Emerging Technologies,2017,83:165-178.
[14] 陈仕军, 沈吟东, 苏璇,等. 带中式用餐约束的乘务调度问题[J]. 交通运输系统工程与信息, 2013, 13(2):90-95.CHEN Shijun, SHEN Yindong, SU Xuan, et al. A Crew Scheduling with Chinese Meal Break Rules[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(2):90-95.
[15] 王莹, 刘军, 苗建瑞. 客运专线乘务交路计划编制的优化模型与算法[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.
[2] 杨国元, 史天运, 张秋亮. 铁路客运乘务排班计划编制模型及算法[J]. 交通运输系统工程与信息, 2016, 16(4):159-164.YANG Guoyuan, SHI Tianyun, ZHANG Qiuliang. Model and Algorithm for Railway Passenger Crew Rostering Plan[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(4):159-164.
[3] 夏平, 马建军. 乘务员运用计划编制模型与计算方法的研究[J]. 铁道运输与经济, 2007, 29(11):27-30.XIA Ping, MA Jianjun. Study on Model and Algorithm of Crew Working Plan[J]. Railway Transport and Economy, 2007, 29(11):27-30.
[4] 阎永光, 黄斌. 广深线城际列车乘务组排班计划编制方法探讨[J]. 交通运输工程与信息学报, 2010, 8(1):25-29.YAN Yongguang, HUANG Bin. Research on the Crew Schedule Programming Method of Guangzhou-Shenzhen Intercity Trains[J]. Journal of Transportation Systems Engineering and Information Technology, 2010, 8(1):25-29.
[5] 李耀华, 谭娜. 基于遗传算法的飞机一体化排班优化方法[J]. 控制工程, 2017, 24(2):435-440.LI Yaohua, TAN Na. Optimization Method of Aircraft Integrated Planning Based on Genetic Algorithm[J]. Control Engineering of China, 2017, 24(2):435-440.
[6] 吴东华, 夏洪山. 基于航空公司成本最小化的飞机排班问题模型与算法[J]. 交通运输系统工程与信息, 2014, 14(1):109-116.WU Donghua, XIA Hongshan. Model and Algorithm for Fleet Assignment Problem Based on Airlines Cost Minimization[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(1):109-116.
[7] 陈明明, 牛惠民. 多车场公交乘务排班问题优化[J]. 交通运输系统工程与信息, 2013, 13(5):159-166.CHEN Mingming, NIU Huimin. An Optimization Model for Bus Crew Scheduling with Multiple Depots[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(5):159-166.
[8] 陈明明, 牛惠民. 带时间窗的多车场公交乘务排班优化[J]. 兰州交通大学学报, 2015, 34(4):100-106.CHEN Mingming, NIU Huimin. An Optimization for Bus Crew Scheduling with Multiple Depots under Time Window Condition[J]. Journal of Lanzhou Jiaotong University, 2015, 34(4):100-106.
[9] 李献忠, 徐瑞华. 基于时间耗费的城市轨道交通乘务排班优化[J]. 铁道学报, 2007, 29(1):21-25.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.
[10] 张增勇, 毛保华, 杜鹏,等. 基于惩罚费用的城市轨道交通乘务排班优化模型与算法[J]. 交通运输系统工程与信息, 2014, 14(2):113-120.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.
[11] 丰富, 陈绍宽, 杜鹏. 考虑时间均衡度的城市轨道交通乘务排班计划优化方法[J]. 交通运输系统工程与信息, 2014,14(6):164-170.FENG Fu, CHEN Shaokuan, DU Peng. Time Equitability-based Crew Scheduling Optimization for Urban Rail Transit[J]. Journal of Transportation Systems Engineering and Information Technology, 2014,14(6):164-170.
[12] POTTHOFF D, HUISMAN D, DESAULNIERS G. Column Generation with Dynamic Duty Selection for Railway Crew Rescheduling[J]. Transportation Science, 2010, 44(4):493-505.
[13] JANACEK J, KOHANI M, KONIORCZYK M, et al. Optimization of Periodic Crew Schedules with Application of Column Generation Method[J]. Transportation Research Part C: Emerging Technologies,2017,83:165-178.
[14] 陈仕军, 沈吟东, 苏璇,等. 带中式用餐约束的乘务调度问题[J]. 交通运输系统工程与信息, 2013, 13(2):90-95.CHEN Shijun, SHEN Yindong, SU Xuan, et al. A Crew Scheduling with Chinese Meal Break Rules[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(2):90-95.
[15] 王莹, 刘军, 苗建瑞. 客运专线乘务交路计划编制的优化模型与算法[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.