A Metaheuristic Algorithm for Multi-objective Transit Bus and Driver Scheduling Problems
-
摘要: 公交车辆与司机调度问题是智慧公交管理中的核心问题之一。针对我国人车固定作业模式下，相关研究中成本考虑不周全、算法通用性差和算法测试不充分等局限，设计了1个多目标公交车辆与司机调度问题元启发算法。算法支持电动车辆调度，适用于单线或跨线运营管理，满足人车固定或人车分离的调度模式，也支持灵活的车辆与司机相关参数设置。算法顾及车辆停车间隔、电池充电、司机休息与就餐等约束条件，优化目标包括车辆固定成本、车辆行驶成本、司机固定成本和司机津贴成本。算法首先生成初始解、再迭代使用班次链算子改进当前解，并通过群解、扰动和可变邻域下降等策略改进解的质量。使用62个单线案例和11个跨线案例进行算法测试，验证了算法的性能，并比较了不同运营模式下调度结果的差异。结果表明，使用续航里程150 km电动车辆取代燃油车辆，单线运营车辆数量增幅为0.8%，跨线运营增幅为1.6%；与单线运营相比，跨线运营所需车辆和司机数量分别减少4.6%和2.4%；与燃油车辆人车固定调度模式相比，人车分离能显著减少所需车辆，单线运营减少3.6%，跨线运营减少1.8%，所需司机数量基本保持不变，但司机需要换车驾驶，平均约为2次。Abstract: This article introduces a metaheuristic algorithm for multi-objective transit bus and driver scheduling problems, such as fuel or electronic vehicles, single route/multiple routes, and driving the same bus on the same day in most transit companies in China.The work aims to minimize the fixed bus cost, the bus travel cost, the fixed driver cost, and the allowance for drivers and to satisfy various operational rules on vehicles and drivers.The algorithm starts from an initial solution and iteratively improves the solution by local search and perturbation.It is also enhanced by two search strategies such as population-based search and variable neighborhood decent search.The performance of the proposed algorithm is tested on 62 single-route instances and 11 multi-route instances.There are three important findings for transit operations in China from the experimentation.Electronic vehicles may replace fuel buses by increasing 0.8% and 1.6% vehicles for single-route and multi-route instances, respectively.Compared with single-route scheduling, multi-route scheduling has the potentials to reduce 4.6% of vehicles and 2.4% of drivers.If the drivers are allowed to drive different buses in their daily works, the number of vehicles required can be reduced significantly, especially for the single-route instances.The general-purpose metaheuristic algorithm in the work is essential for developing intelligent public transit systems in China.
-
Key words:
- urban public transit /
- bus and driver scheduling /
- algorithm design /
- algorithm test
-
表 1 单线案例基本特征
Table 1. Main features of the single-route instances
案例 班次数量 线长/km 单程时间/min 案例 班次数量 线长/km 单程时间/min 案例 班次数量 线长/km 单程时间/min sh01 230 13.6 52.4 sza06 127 18.9 50.0 szb13 174 22.5 81.6 sh02 252 16.8 57.6 sza07 144 14.7 50.3 szb14 120 26.2 77.1 sh03 189 8.9 25.8 sza08 97 12.9 62.0 szc01 204 35.1 106.5 sh03 265 18.6 67.2 sza09 107 15.8 54.7 szc02 191 34.2 102.2 sh05 171 14.5 57.1 sza10 140 21.2 55.0 szc03 147 28.3 97.6 sh06 66 19.3 68.5 sza11 149 16.9 55.0 szc04 180 31.3 98.1 sh07 250 14.3 53.1 sza12 229 16.3 60.0 szc05 126 30.5 112.0 sg01 180 31.6 107.7 sza13 72 12.0 45.0 szc06 232 32.3 103.9 sg02 212 21.5 83.0 sza14 71 14.2 52.0 szd01 180 38.4 157.0 sg03 170 21.9 86.0 szb01 192 46.7 69.6 szd02 270 60.4 129.9 sg04 160 23.8 77.1 szb02 188 19.4 65.0 szd03 184 46.7 127.8 sg05 160 17.5 69.1 szb03 182 18.1 68.0 szd04 170 35.7 120.0 sg06 198 20.8 81.7 szb04 161 26.9 86.0 szd05 94 59.4 125.0 sg07 228 21.0 90.2 szb05 120 20.9 83.0 szd06 239 39.3 117.3 sg08 153 31.9 112.0 szb06 150 19.1 71.0 szd07 138 40.9 145.3 sg09 257 19.8 71.8 szb07 88 18.5 69.1 szd08 115 35.8 120.0 sza01 256 12.9 44.0 szb08 228 22.4 68.0 szd09 222 41.6 119.4 sza02 120 17.0 48.8 szb09 169 22.7 71.6 szd10 118 48.0 134.9 sza03 152 18.5 61.9 szb10 119 20.8 80.0 szd11 118 26.5 108.7 sza04 108 51.8 95.0 szb11 116 16.4 75.0 szd12 216 45.3 125.0 sza05 166 17.7 59.0 szb12 210 32.4 80.0 
下载: 导出CSV
表 2 跨线案例基本特征
Table 2. Main features of the multi-route instances
案例 线路 班次数量 运营里程/km 运营时间/min shmr01 sh05, sh06 237 3 753 14 285 shmr02 sh01, sh05 401 5 608 21 819 sgmr01 sg04, sg05 320 6 608 23 400 sgmr02 sg07, sg08 381 9 669 37 697 szmr01 sza01, sza02, sza03 528 8 154 26 525 szmr02 sza04, sza04, sza06 401 10 933 26 404 szmr03 sza07, sza08, sza09, sza10 488 8 027 26 810 szmr04 sza11, sza12, sza13, sza14 521 8 123 28 867 szmr05 szc01, sza05 346 9 840 38 055 szmr06 szc02, sza01 526 19 610 46 331 szmr07 szc03, sza12 413 12 326 37 252
下载: 导出CSV
表 3 单条线路作业计划统计
Table 3. Scheduling results from the single-route instances
案例分组 车辆类型 人车固定调度 人车分离调度 车辆数量 司机数量 轮班司机数量 空驶数量 车辆数量 司机数量 轮班司机数量 空驶数量 sh 燃油 127 193 280.2 27 127 194 282.1 19 sh 电动1 130 195 283.5 23 127 194 281.9 19 sh 电动2 130 193 283.3 19 127 195 283.5 19 sg 燃油 212 356 518.9 26 205 358 517.9 30 sg 电动1 214 359 519.5 28 205 355 513.4 30 sg 电动2 215 353 514.2 26 205 356 514.4 30 sza 燃油 189 292 432.2 26 181 291 429.6 18 sza 电动1 190 294 431.8 20 182 292 424.4 16 sza 电动2 189 293 432.6 22 184 292 427.8 18 szb 燃油 272 423 630.2 47 256 424 627.4 29 szb 电动1 274 426 631.8 39 258 423 626.3 31 szb 电动2 275 425 632.3 31 261 422 625.5 25 szc 燃油 186 257 395.7 2 180 257 393.7 2 szc 电动1 189 259 394.9 2 180 258 393.2 2 szc 电动2 188 259 396.8 2 180 261 393.9 2 szd 燃油 415 643 983.5 22 402 641 983.0 8 szd 电动1 415 644 984.8 22 403 641 980.2 14 szd 电动2 415 645 986.5 20 403 639 982.7 10
下载: 导出CSV
表 4 跨线调度结果及与单线调度比较
Table 4. Scheduling results from the multi-route instances
案例 车型 人车关系 跨线调度 单线调度 节约/% 车辆/辆 司机/人 空驶/次 车辆/辆 司机/人 空驶/次 车辆 司机 shmr01 燃油 固定 24 52.5 5 25 53.9 5 4.00 2.60 shmr02 燃油 固定 35 78.3 5 35 79.6 7 0.00 1.63 sgmr01 燃油 固定 31 80.9 8 33 82.6 8 6.06 2.06 sgmr02 燃油 固定 48 126.3 7 51 127.9 3 5.88 1.25 szmr01 燃油 固定 44 106.2 8 46 110.6 8 4.35 3.98 szmr02 燃油 固定 42 99.5 9 45 102.4 7 6.67 2.83 szmr03 燃油 固定 43 103.7 4 46 106.6 6 6.52 2.72 szmr04 燃油 固定 48 111.8 7 52 112.6 5 7.69 0.71 szmr05 燃油 固定 53 132.2 6 59 141.8 6 10.17 6.77 szmr06 燃油 固定 66 165.1 6 67 173.9 6 1.49 5.06 szmr07 燃油 固定 55 138.5 9 58 144.3 3 5.17 4.02 shmr01 电动 固定 24 51.1 5 25 55.0 3 4.00 7.09 shmr02 电动 固定 35 77.6 5 37 80.7 5 5.41 3.84 sgmr01 电动 固定 32 82.6 8 33 82.7 8 3.03 0.12 sgmr02 电动 固定 50 127.6 7 52 128.3 3 3.85 0.55 szmr01 电动 固定 46 104.0 10 46 108.8 6 0.00 4.41 szmr02 电动 固定 43 99.0 7 45 103.0 7 4.44 3.88 szmr03 电动 固定 43 104.8 4 47 105.5 2 8.51 0.66 szmr04 电动 固定 49 111.9 13 52 114.6 5 5.77 2.36 szmr05 电动 固定 53 132.3 6 59 142.6 8 10.17 7.22 szmr06 电动 固定 66 167.0 6 67 173.3 6 1.49 3.64 szmr07 电动 固定 56 140.5 7 58 144.5 3 3.45 2.77 shmr01 燃油 分离 24 51.8 5 25 54.2 3 4.00 4.43 shmr02 燃油 分离 33 79.9 9 35 78.6 3 5.71 -1.65 sgmr01 燃油 分离 31 81.9 8 32 82.6 8 3.13 0.85 sgmr02 燃油 分离 46 128.6 11 48 126.9 7 4.17 -1.34 szmr01 燃油 分离 44 104.3 6 46 108.7 6 4.35 4.05 szmr02 燃油 分离 41 99.8 5 43 102.9 5 4.65 3.01 szmr03 燃油 分离 42 103.7 4 44 105.1 2 4.55 1.33 szmr04 燃油 分离 48 113.3 3 48 112.9 5 0.00 -0.35 szmr05 燃油 分离 53 131.4 6 57 142.5 4 7.02 7.79 szmr06 燃油 分离 65 167.6 6 66 173 6 1.52 3.12 szmr07 燃油 分离 53 140.8 7 57 141.6 1 7.02 0.56 shmr01 电动 分离 24 51.8 5 25 54.2 3 4.00 4.43 shmr02 电动 分离 33 81.1 9 35 79.2 3 5.71 -2.40 sgmr01 电动 分离 31 82.8 8 32 82.4 8 3.13 -0.49 sgmr02 电动 分离 46 127.8 11 48 126.5 7 4.17 -1.03 szmr01 电动 分离 44 106.6 6 46 107.6 6 4.35 0.93 szmr02 电动 分离 41 100.8 5 43 101.0 5 4.65 0.20 szmr03 电动 分离 42 104.7 4 44 105.1 2 4.55 0.38 szmr04 电动 分离 48 112.7 3 49 110.7 3 2.04 -1.81 szmr05 电动 分离 53 131.7 6 57 140.2 12 7.02 6.06 szmr06 电动 分离 65 166.4 6 66 173.2 6 1.52 3.93 szmr07 电动 分离 53 138.5 7 57 141.8 1 7.02 2.33 平均 44.2 109.1 6.6 46.4 112.0 5.1 4.60 2.38
下载: 导出CSV
表 5 车辆中停时间（gap）对车辆调度的影响
Table 5. Effects of the waiting time (gap) for buses on scheduling results
gap/% 案例sh01 案例sg07 案例szb12 案例szmr04 车辆 司机 空驶 车辆 司机 空驶 车辆 司机 空驶 车辆 司机 空驶 5 18 28 2 28 46 4 26 40 2 46 69 7 7 19 28 2 29 46 4 27 40 6 46 71 9 9 19 28 2 28 47 6 28 39 2 47 72 7 10 19 28 2 29 47 6 28 39 2 48 71 11 11 20 28 2 30 46 4 28 39 4 49 74 9 13 20 29 2 30 47 4 29 38 0 50 72 9 15 20 29 2 30 48 6 29 37 4 50 72 9 20 21 29 2 32 48 4 28 38 6 52 74 9
下载: 导出CSV
表 6 司机班制设计对公交作业的影响
Table 6. Effects of the design of drivers' working shifts on scheduling results
案例 正常班tdn1/h 长班tdl1/h 高峰班 长班 车辆/辆 司机数量/人 轮班司机数量/人 空驶数量/次 sh01 8 10.7 允许 允许 19 28 41.7 2 sh01 8 10.5 允许 允许 19 28 41.1 2 sh01 8 10.7 不允许 允许 19 30 46.2 2 sh01 8 允许 不允许 20 30 42.4 2 sh01 8 不允许 不允许 19 37 51.8 2 sg07 8 10.7 允许 允许 29 47 69.0 6 sg07 8 10.5 允许 允许 29 47 69.2 6 sg07 8 10.7 不允许 允许 29 48 72.0 6 sg07 8 允许 不允许 29 53 74.4 6 sg07 8 不允许 不允许 29 54 75.6 6 szb12 8 10.7 允许 允许 26 33 54.2 0 szb12 8 10.5 允许 允许 27 40 56.7 0 szb12 8 10.7 不允许 允许 26 33 55.2 0 szb12 8 允许 不允许 28 39 55.4 0 szb12 8 不允许 不允许 26 47 65.8 0 szmr04 8 10.7 允许 允许 49 70 106.1 7 szmr04 8 10.5 允许 允许 48 72 110.5 11 szmr04 8 10.7 不允许 允许 48 75 115.8 7 szmr04 8 允许 不允许 49 83 117.5 9 szmr04 8 - 不允许 不允许 48 91 127.4 5
下载: 导出CSV
表 7 案例计算时间
Table 7. Statistics of computing times on cases
s 案例 人车固定 人车不固定 燃油 电动1 电动2 燃油 电动1 电动2 sh 157.3 203.3 252.0 186.8 250.1 329.3 sg 174.4 260.7 268.9 198.4 247.3 293.6 sza 67.9 118.0 103.4 74.5 114.6 118.0 szb 78.7 146.7 140.4 110.9 150.1 156.6 szc 89.7 192.2 193.7 159.2 173.2 153.0 szd 78.8 117.8 133.6 101.3 121.7 148.3 shmr01 376.3 430.8 346.8 285.6 843.1 512.5 shmr02 509.1 777.1 670.9 574.2 1 062.3 1 132.7 sgmr01 437.1 745.2 697.9 646.0 937.5 1 031.0 sgmr02 682.7 1056.4 715.3 792.8 1 292.7 1 227.3 szmr01 804.9 1 139.7 1 217.6 817.0 1 522.2 1 398.8 szmr02 528.4 927.1 1 038.9 947.0 1 240.6 1 116.4 szmr03 626.9 897.6 1 133.5 1 367.1 1 342.0 1 496.3 szmr04 670.7 1 121.7 1 168.7 1 250.4 1 509.8 1 600.5 szmr05 241.2 481.2 474.3 501.8 614.5 694.2 szmr06 728.5 1 015.6 1 071.7 1 467.6 1 659.8 1 681.6 szmr07 606.5 1 098.0 1 075.0 987.7 1 361.2 1 373.5
下载: 导出CSV
-
[1] CEDER A, WILSON N H M. Bus network design[J]. Transportation Research Part B: Methodological, 1986(20): 331-344. http://citec.repec.org/d/eee/transb/v_20_y_1986_i_4_p_331-344.html [2] KEPAPTSOGLOU K, KARLAFTIS M G. Transit Route network design problem: review[J]. Journal of Transportation Engineering, 2009, 135(8): 491-505. doi: 10.1061/(ASCE)0733-947X(2009)135:8(491) [3] PINE R. NIEMEYER J, CHISHOLM R. Transit scheduling: Basic and advanced manuals[R]. Washington, D. C. : World Transit Research, 1998. [4] National Academies of Sciences, Engineering, and Medicine. Controlling system costs: basic and advanced scheduling manuals and contemporary issues in transit scheduling[M]. Washington, D. C. : The National Academies Press, 2009. [5] LOURENCO H R, PAIXAO J M, PORTUGAL R, et al. Multiobjective metaheuristics for the bus driver scheduling problem[J]. Transportation Science, 2001, 35(3): 331-343. doi: 10.1287/trsc.35.3.331.10147 [6] DE LEONE R, FESTA P, MARCHITTO E, et al. A bus driver scheduling problem: a new mathematical model and a GRASP approximate solutionJ]. Journal of Heuristics, 2011, 17(4): 441-466. doi: 10.1007/s10732-010-9141-3 [7] LIN D, HSU C. A column generation algorithm for the bus driver scheduling problem[J]. Journal of Advanced Transportation, 2016, 50(8): 1598-1615. doi: 10.1002/atr.1417 [8] VALOUXIS C, HOUSOS E. Combined bus and driver scheduling[J]. Computers & Operations Research, 2002, 29(3): 243-259. http://www.sciencedirect.com/science/article/pii/S0305054800000678 [9] 魏明, 靳文舟, 孙博. 求解区域公交车辆调度问题的蚁群算法研究[J]. 公路交通科技, 2011, 28(6): 141-145. doi: 10.3969/j.issn.1002-0268.2011.06.023WEI Ming, JIN Wenzhou, SUN Bo. Ant colony algorithm for regional bus scheduling problem[J]. Journal of Highway and Transportation Research and Development, 2011, 28(6): 141-145. (in Chinese) doi: 10.3969/j.issn.1002-0268.2011.06.023 [10] 李一凡, 杨友磊. 基于整数规划的多车场多车型公交车辆调度问题研究[J]. 综合运输, 2019, 41(12): 61-66. https://www.cnki.com.cn/Article/CJFDTOTAL-YSZH201912013.htmLI Yifan, YANG Youlei. Multiple depots and types bus scheduling problems based on integer programming[J]. China Transportation Review, 2019, 41(12): 61-66. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSZH201912013.htm [11] 姚恩建, 卢沐阳, 刘宇环, 等. 考虑充电约束的电动公交区域行车计划编制[J]. 华南理工大学学报(自然科学版), 2019, 47(9): 68-73. https://www.cnki.com.cn/Article/CJFDTOTAL-HNLG201909011.htmYAO Enjian, LU Muyang, LIU Yuhuan, et al. Electric bus area driving plan preparation considering charging constraints[J]. Journal of South China University of Technology(Natural Science Edition), 2019, 47(9): 68-73. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-HNLG201909011.htm [12] 滕靖, 林琳, 陈童. 纯电动公交时刻表和车辆排班计划整体优化[J]. 同济大学学报(自然科学版), 2019, 47(12): 1748-1755. doi: 10.11908/j.issn.0253-374x.2019.12.009TENG Jing, LIN Lin, CHEN Tong. Optimizing the combination of timetable and vehicle scheduling for pure electric buses[J]. Journal of Tongji University(Natural Science), 2019, 47(12): 1748-1755. (in Chinese) doi: 10.11908/j.issn.0253-374x.2019.12.009 [13] 唐春艳, 杨凯强, 邬娜. 单线纯电动公交车辆柔性调度优化[J]. 交通运输系统工程与信息, 2020, 20(3): 156-162. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT202003025.htmTANG Chunyan, YANG Kaiqiang, WU Na. Optimizing flexible vehicle scheduling for single-line battery electric buses[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(3): 156-162. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT202003025.htm [14] 刘涛. 公交驾驶员排班与轮班问题的模型与算法研究[D]. 北京: 北京交通大学, 2013.LIUTao. Models and algorithms for bus driver run cutting and rostering[D]. Beijing: Beijing Jiaotong University, 2013. (in Chinese) [15] 陈明明, 牛惠民. 多车场公交乘务排班问题优化[J]. 交通运输系统工程与信息, 2013, 13(5): 159-166. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201305024.htmChen 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. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201305024.htm [16] 陈程. 基于多目标优化算法的公交车辆调度研究[D]. 北京: 北京邮电大学, 2014.CHENCheng. The research on vehicle scheduling problem based on multi-objective optimization algorithms[D]. Beijing: Beijing University of Posts and Telecommunications, 2014. (in Chinese) [17] 陈明明. 城市公共交通乘务调度优化理论和方法[D]. 兰州: 兰州交通大学, 2016.CHEN Mingming. Theory and method for crew scheduling problem of urban public Transport[D]. Lanzhou: Lanzhou Jiaotong University, 2016. (in Chinese) [18] 侯彦娥, 孔云峰, 朱艳芳等. 公交司机排班问题的混合元启发算法研究[J]. 交通运输系统工程与信息, 2018, 18(1): 133-138. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201801021.htmHOU Yane, KONG Yunfeng, ZHU Yanfang, et al. A hybrid metaheuristic algorithm for the transit bus and driver scheduling problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(1): 133-138. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201801021.htm -
点击查看大图
图(1) / 表(7)
计量
- 文章访问数: 581
- HTML全文浏览量: 275
- PDF下载量: 26
- 被引次数: 0