公車運輸系統是屬於勞力密集的產業，需要許多司機員依照頒訂的路線時刻表以提供大眾完整的公共運輸服務。因此，人力成本佔公車業者整體經營成本很大部分。司機員班表是依據公車各路線班次之時刻表進行規劃，良好規劃的班表可使公車業者運用較少的人力資源完成給定的任務，以減少營運成本的支出。此外，安全駕駛亦是司機員管理之重要議題，公車司機員疲勞駕駛容易造成嚴重的交通意外危害大眾安全，而超時工作與休息時間不足是造成疲勞駕駛的主要因素。為確保公車司機員能在合理的工作環境中提供大眾運輸服務，政府部門訂定相關的工作法規，以限制最大工作時數與確保足夠的休息時間，然而這些法規使得公車司機員排班變得更加複雜。因此，發展一有效率的方法以求解考量舒適度與公平性提升之司機員班表規劃問題，將能改善公車運輸業司機員管理之效能。
在運輸業中，組員管理通常分為人員排班與人員輪班兩部分，兩問題皆是相當複雜且不易求解的問題，因此多數文獻皆針對單一問題進行演算法開發，或是以兩階段的方式進行求解。然而，將問題分為兩部分，使得求解時無法同時考量所有限制與資源調配，相較於整合問題，分解方法容易產生次佳解的結果。本研究之目的在於發展一公車司機員班表整合模型，同時考量人員排班與輪班問題，以及提升司機員工作舒適性與公平性之限制。此外，針對此數學模型提出一基於分支定價演算法、切割技術與多目標最佳化方法，發展之整合解決方案架構，以求解實際公車司機員班表之複雜問題，並將數學模型與整合解決方案架構之求解結果進行比較，以驗證此研究所發展之整合解決方案架構求解效益與效率。
本論文之主要學術貢獻，為提出一整合解決方案架構，以求解考量舒適性與公平性提升之整合司機員排班與輪班問題。此整合解決方案架構結合，分支定價演算法、切割技術與多目標最佳化方法。分支定價演算法藉由定價程序，有效產生有利於受限主程序的工作班。切割技術為基於受限主程序所開發之策略，以加快整合解決方案架構之求解效率。多目標最佳化方法用以權衡整合問題中，人員成本與舒適性和公平性之決策。根據相關文獻回顧，尚未有研究提出一整合解決方案架構，以求解考量舒適性與公平性之整合排班與輪班問題，並探討營運成本與求解品質間的權衡。
數值實驗測試於不同問題規模的實例，測試資料由台南一公車運輸業者提供。實驗結果顯示本研究所提出之整合解決方案架構，能提供與最佳化商業軟體相同之求解品質，在大型問題規模之實例，亦能有效率的求解此複雜之整合問題。此外，本研究所提出之整合方法與兩階段求解架構相比，能夠獲得較好的結果，班表之營運成本降低13.1%，從而顯示整合性之優勢。而針對舒適性與公平性之實驗測試，顯示以整合架構求解考量軟限制之司機員排班與輪班問題，其班表之公平性和舒適性水平提高30.7%。本研究所提出之整合性方案架構，為公車運輸業者提供一有效方案，提升公車司機員班表管理效率，並提供大眾更加安全之運輸服務。

Bus transportation is a labor-intensive industry that requires a lot of drivers to provide transport services. Therefore, the cost of employees accounts for a significant portion of the operating costs of bus companies. The drivers’ schedules are determined based on a published timetable, and well-managed schedules can reduce the number of drivers needed to complete all the given tasks. Also, the safety and interests of the crew is another significant factor that should be considered in crew management. The related labor laws and the contractual rules are legislated to ensure basic reasonable working conditions for bus drivers to avoid their working overtime and having inadequate rest time, as well as to ensure crew health. In addition, this research investigates issues related to comfortableness and fairness for bus drivers to further improve the quality of the schedule results. However, taking these issues into consideration makes it more difficult for bus companies to manage driver scheduling. Therefore, it is essential to develop an efficient approach for driver scheduling considering the comfortableness of drivers and how fairly they are treated.
Crew management in the transportation sector is typically decomposed into crew scheduling and crew rostering. Both are complex problems, and most studies do not simultaneously consider both. However, the decomposed approach cannot consider all constraints at the same time, which will lead to inferior solutions. The purpose of this paper is to develop an integrated model that considers crew scheduling and crew rostering simultaneously as well as the comfort of drivers. To tackle this problem, an integrated solution framework is devised to solve problem instances of a realistic size. The solutions obtained from the mathematical model and the proposed solution framework are compared with optimal solutions from a commercial optimization package to validate the effectiveness and efficiency of the solution framework.
The contribution of this research is to develop an integrated framework for the scheduling and rostering problem of bus drivers considering fairness and comfortableness. The proposed integrated framework involves the branch-and-price algorithm, the cut techniques, and the multi-objective optimization approach. The branch-and-price algorithm enhances the solution efficiency by generating a valuable subset of duties during the problem solving procedure. To accelerate the search procedure, cut techniques are developed to fathom the infeasible branches of the branch-and-bound tree. Furthermore, a multi-objective optimization approach is applied to make a trade-off between cost-efficiency and solution quality. To the best of our knowledge, the related literature has not proposed an integrated solution framework to investigate the driver scheduling and rostering problem considering the issues of comfortableness and fairness and explore the trade-off between operating costs and solution quality.
The numerical results are examined in real-world cases with various problem sizes based on the data from the H bus company in Tainan City, Taiwan. The results demonstrate that the proposed integrated solution framework can find solutions that are of the same quality as the optimal solutions obtained from the commercial optimization solver. In addition, the proposed solution framework can efficiently solve the complex integrated problem and provide solutions for large-scale instances within a reasonable computational time. In addition, the experimental results indicate that the integrated solution framework can provide a better solution in which the operation cost decreases by 13.1% compared to the conventional two-phase method, which shows the benefit of integration. Furthermore, compared to the model in cost minimization, the drivers’ fairness and comfortableness level increase by 30.7% in the model considering both the hard and soft constraints. The proposed integrated solution framework provides bus companies with an effective method by which to make driver planning more efficient and safer.

References
Abbink, E., Fischetti, M., Kroon, L., Timmer, G., & Vromans, M. (2005). Reinventing crew scheduling at Netherlands railways. Interfaces, 35(5), 393-401. https://doi.org/10.1287/inte.1050.0158
Abbink, E., Huisman, D., & Kroon, L. (2018). Railway crew management. Springer International Publishing, 243-264. https://doi.org/10.1007/978- 3- 319- 72153- 8- 11 .
Amberg, B., Amberg, B., & Kliewer, N. (2019). Robust Efficiency in Urban Public Transportation: Minimizing Delay Propagation in Cost-Efficient Bus Driver Schedules. Transportation Science, 53(1), 89-112. https://doi.org/10.1287/trsc.2017.0757
Axelsson, J. (2005). Long shifts, short rests and vulnerability to shift work, Ph.D., Stockholm Unversity.
Békési, J., Brodnik, A., Krész, M., & Pash, D. (2009). An Integrated Framework for Bus Logistics Management: Case Studies. Logistik Management, Physica-Verlag HD, 389-411. https://doi.org/10.1007/978-3-7908-2362-2_20
Bailey, J. (1985). Integrated Days Off and Shift Personnel Scheduling. Computers & Industrial Engineering, 9(4), 395-404. https://doi.org/Doi 10.1016/0360-8352(85)90027-0
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316-329. https://doi.org/DOI 10.1287/opre.46.3.316
Beasley, J. E., & Cao, B. (1996). A tree search algorithm for the crew scheduling problem. European Journal of Operational Research, 94(3), 517-526. https://doi.org/Doi 10.1016/0377-2217(95)00093-3
Borndorfer, R., Schulz, C., Seidl, S., & Weider, S. (2017). Integration of duty scheduling and rostering to increase driver satisfaction. Public Transport, 9(1-2), 177-191. https://doi.org/10.1007/s12469-017-0153-3
Boschetti, M. A., Mingozzi, A., & Ricciardelli, S. (2004). An exact algorithm for the simplified multiple depot crew scheduling problem. Annals of Operations Research, 127(1-4), 177-201. https://doi.org/Doi 10.1023/B:Anor.0000019089.86834.91
Brown, I. D. (1997). Prospects for technological countermeasures against driver fatigue. Accident Analysis and Prevention, 29(4), 525-531. https://doi.org/Doi 10.1016/S0001-4575(97)00032-8
Caprara, A., Fischetti, M., Guida, P. L., Toth, P., & Vigo, D. (1999). Solution of large-scale railway crew planning problems: the Italian experience. Computer-Aided Transit Scheduling, Proceedings, 471, 1-18.
Caprara, A., Fischetti, M., Toth, P., Vigo, D., & Guida, P. L. (1997). Algorithms for railway crew management. Mathematical Programming, 79(1-3), 125-141. https://doi.org/10.1007/bf02614314
Chen, M. M., & Niu, H. M. (2012). A Model for Bus Crew Scheduling Problem with Multiple Duty Types. Discrete Dynamics in Nature and Society. https://doi.org/Artn 649213 10.1155/2012/649213
Chu, H. D., Gelman, E., & Johnson, E. L. (1997). Solving large scale crew scheduling problems. European Journal of Operational Research, 97(2), 260-268. https://doi.org/Doi 10.1016/S0377-2217(96)00196-8
Dantzig, G. B. (1954). A Comment on Edie's "Traffic Delays at Toll Booths". Journal of the Operations Research Society of America, 2(3), 339-341. http://www.jstor.org/stable/166648
De Leone, R., Festa, P., & Marchitto, E. (2011). A Bus Driver Scheduling Problem: a new mathematical model and a GRASP approximate solution. Journal of Heuristics, 17(4), 441-466. https://doi.org/10.1007/s10732-010-9141-3
Di Milia, L., Smolensky, M. H., Costa, G., Howarth, H. D., Ohayon, M. M., & Philip, P. (2011). Demographic factors, fatigue, and driving accidents: An examination of the published literature. Accident Analysis and Prevention, 43(2), 516-532. https://doi.org/10.1016/j.aap.2009.12.018
Dial, R., Glover, F., Karney, D., & Klingman, D. (1980). Shortest-Path Forest with Topological Ordering - an Algorithm Description in Sdl. Transportation Research Part B-Methodological, 14(4), 343-347. https://doi.org/Doi 10.1016/0191-2615(80)90014-4
Ehrgott, M. (2005). Multicriteria Optimization. Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/3-540-27659-9
Ernst, A. T., Jiang, H., Krishnamoorthy, M., Nott, H., & Sier, D. (2001). An Integrated Optimization Model for Train Crew Management. Annals of Operations Research, 108(1), 211-224. https://doi.org/10.1023/a:1016019314196
Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3-27. https://doi.org/10.1016/s0377-2217(03)00095-x
Fatigue (2018). European Commission, Directorate General for Transport. Retrieved from https://ec.europa.eu/transport/road_safety/sites/roadsafety/files/pdf/
ersosynthesis2018-fatigue.pdf
Folkard, S. (1997). Black times: Temporal determinants of transport safety. Accident Analysis and Prevention, 29(4), 417-430. https://doi.org/Doi 10.1016/S0001-4575(97)00021-3
Freling, R., Lentink, R. M., & Wagelmans, A. P. M. (2004). A Decision Support System for Crew Planning in Passenger Transportation Using a Flexible Branch-and-Price Algorithm. Annals of Operations Research, 127(1), 203-222. https://doi.org/10.1023/b:anor.0000019090.39650.32
Graves, G. W., Mcbride, R. D., Gershkoff, I., Anderson, D., & Mahidhara, D. (1993). Flight Crew Scheduling. Management Science, 39(6), 736-745. https://doi.org/DOI 10.1287/mnsc.39.6.736
Haase, K., Desaulniers, G., & Desrosiers, J. (2001). Simultaneous vehicle and crew scheduling in urban mass transit systems. Transportation Science, 35(3), 286-303. https://doi.org/DOI 10.1287/trsc.35.3.286.10153
Hartley, L., Horberry, T., Mabbott, N., & Krueger, G. (2000). Review of fatigue detection and prediction technologies. National Road Transport Commission.
Heil, J., Hoffmann, K., & Buscher, U. (2020). Railway crew scheduling: Models, methods and applications. European Journal of Operational Research, 283(2), 405-425. https://doi.org/https://doi.org/10.1016/j.ejor.2019.06.016
Hooker, J. N. (2007). Planning and scheduling by logic-based benders decomposition. Operations Research, 55(3), 588-602. https://doi.org/10.1287/opre.1060.0371
Jutte, S., Muller, D., & Thonemann, U. W. (2017). Optimizing railway crew schedules with fairness preferences. Journal of Scheduling, 20(1), 43-55. https://doi.org/10.1007/s10951-016-0499-4
Khmeleva, E., Hopgood, A. A., Tipi, L., & Shahidan, M. (2018). Fuzzy-Logic Controlled Genetic Algorithm for the Rail-Freight Crew-Scheduling Problem. KI - Künstliche Intelligenz, 32(1), 61-75. https://doi.org/10.1007/s13218-017-0516-6
Kroon, L., & Fischetti, M. (2001). Crew Scheduling for Netherlands Railways “Destination: Customer”. Springer, 505, 181-201. https://doi.org/https://doi.org/10.1007/978-3-642-56423-9_11
Lavoie, S., Minoux, M., & Odier, E. (1988). A New Approach for Crew Pairing Problems by Column Generation with an Application to Air Transportation. European Journal of Operational Research, 35(1), 45-58. https://doi.org/Doi 10.1016/0377-2217(88)90377-3
Lin, D. Y. (2014). A Dantzig-Wolfe decomposition algorithm for the constrained minimum cost flow problem. Journal of the Chinese Institute of Engineers, 37(5), 659-669. https://doi.org/10.1080/02533839.2013.815010
Lin, D. Y., & Hsu, C. L. (2016). A column generation algorithm for the bus driver scheduling problem. Journal of Advanced Transportation, 50(8), 1598-1615. https://doi.org/10.1002/atr.1417
Lin, D. Y., Juan, C. J., & Chang, C. C. (2020). A Branch-and-Price-and-Cut Algorithm for the Integrated Scheduling and Rostering Problem of Bus Drivers. Journal of Advanced Transportation. https://doi.org/Artn315320110.1155/2020/3153201
Lin, D. Y., & Tsai, M. R. (2019). Integrated Crew Scheduling and Roster Problem for Trainmasters of Passenger Railway Transportation. Ieee Access, 7, 27362-27375. https://doi.org/10.1109/Access.2019.2900028
Lourenco, H. R., Paixao, J. P., & Portugal, R. (2001). Multiobjective metaheuristics for the bus-driver scheduling problem. Transportation Science, 35(3), 331-343. https://doi.org/DOI 10.1287/trsc.35.3.331.10147
Lusby, R. M., Larsen, J., & Bull, S. (2018). A survey on robustness in railway planning. European Journal of Operational Research, 266(1), 1-15. https://doi.org/10.1016/j.ejor.2017.07.044
Ma, J., Ceder, A., Yang, Y., Liu, T., & Guan, W. (2016). A case study of Beijing bus crew scheduling: a variable neighborhood-based approach. Journal of Advanced Transportation, 50(4), 434-445. https://doi.org/doi:10.1002/atr.1333
Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation, 213(2), 455-465. https://doi.org/10.1016/j.amc.2009.03.037
Mesquita, M., Moz, M., Paias, A., Paixao, J., Pato, M., & Respicio, A. (2011). A new model for the integrated vehicle-crew-rostering problem and a computational study on rosters. Journal of Scheduling, 14(4), 319-334. https://doi.org/10.1007/s10951-010-0195-8
Mesquita, M., Moz, M., Paias, A., & Pato, M. (2013). A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern. European Journal of Operational Research, 229(2), 318-331. https://doi.org/10.1016/j.ejor.2013.02.055
Nishi, T., Hiranaka, Y., & Grossmann, I. E. (2011). A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles. Computers & Operations Research, 38(5), 876-888. https://doi.org/10.1016/j.cor.2010.08.012
Rudin-Brown, C. M., Harris, S., & Rosberg, A. (2019). How shift scheduling practices contribute to fatigue amongst freight rail operating employees: Findings from Canadian accident investigations. Accident Analysis and Prevention, 126, 64-69. https://doi.org/10.1016/j.aap.2018.01.027
Sargut, F. Z., Altuntas, C., & Tulazoglu, D. C. (2017). Multi-objective integrated acyclic crew rostering and vehicle assignment problem in public bus transportation. Or Spectrum, 39(4), 1071-1096. https://doi.org/10.1007/s00291-017-0485-z
Shen, Y. D., & Chen, S. J. (2014). A Column Generation Algorithm for Crew Scheduling with Multiple Additional Constraints. Pacific Journal of Optimization, 10(1), 113-136.
Steinzen, I., Suhl, L., & Kliewer, N. (2009). Branching strategies to improve regularity of crew schedules in ex-urban public transit. Or Spectrum, 31(4), 727-743. https://doi.org/10.1007/s00291-008-0136-5
Suzie Edrington, Jonathan Brooks, Linda Cherrington, Paul Hamilton, Todd Hansen, Chris Pourteau, & Sandidge, M. (2014). Guidebook: Managing Operating Costs for Rural and Small Urban Public Transit Systems. Texas A&M Transportation Institute.
https://static.tti.tamu.edu/tti.tamu.edu/documents/0-6694-P3.pdf
Tien, J. M., & Kamiyama, A. (1982). On Manpower Scheduling Algorithms. Siam Review, 24(3), 275-287. https://doi.org/Doi 10.1137/1024063
Toth, A., & Kresz, M. (2013). An efficient solution approach for real-world driver scheduling problems in urban bus transportation. Central European Journal of Operations Research, 21, S75-S94.
https://doi.org/10.1007/s10100-012-0274-3
Xie, L., Merschformann, M., Kliewer, N., & Suhl, L. (2017). Metaheuristics approach for solving personalized crew rostering problem in public bus transit. Journal of Heuristics, 23(5), 321-347. https://doi.org/10.1007/s10732-017-9348-7
Yunes, T. H., Moura, A. V., & de Souza, C. C. (2005). Hybrid column generation approaches for urban transit crew management problems. Transportation Science, 39(2), 273-288. https://doi.org/10.1287/trsc.1030.0078
Zhang, W. H., & Reimann, M. (2014). A simple augmented epsilon-constraint method for multi-objective mathematical integer programming problems. European Journal of Operational Research, 234(1), 15-24. https://doi.org/10.1016/j.ejor.2013.09.001