班次規劃(Transit Network Timetable Scheduling Problem, TNTSP)及司機排班 (Bus Driver Scheduling Problem, BDSP)一直以來都是兩大主要大眾運輸業的最佳 化問題。在過去的研究中，大多都是考慮司機只服務單一路線，並未對司機能服務多條路線的情況去做討論，因此在本研究將會著重在司機排班(BDSP)上，並且考慮司機服務多條路線做排班最佳化，由於此問題屬於NP-Hard問題，利用CPLEX最佳化軟體將會耗費相當多的計算時間，因此本研究將會利用混合啟發式演算法尋求最佳解，來提高民眾搭乘大眾交通運輸工具之意願。

本研究將藉由客運業者提供之票卡交易資料以及 8 條路線之發車班表進行乘客需求分析，並且針對班次規劃建立數學模型，以乘客等待時間最小為目標式，利用最佳化軟體CPLEX跑出最佳發車班表。再藉由班次規劃問題的最佳解作為司機排班問題的發車需求，並根據客運業者提出的需求與考量 70位司機的排班規定，建立出數學模型，以最小化司機的總上班時間為目標式。並提出兩種以基因演算法為基底的混合啟發式演算法，分別為模擬退火演算法與禁忌搜索演算法。將兩種混合啟發式演算法各別求出解後，再與基因演算法互相比較。

研究結果顯示，在班次規劃問題上，利用CPLEX跑出的最佳發車班表具有6%~59%的改善率。在司機排班問題上，本研究提出的兩種啟發式演算法皆優於傳統基因演算法。並且利用CPLEX最佳化軟體模擬，來證實混合啟發式演算法產出之解與最佳解相近，且計算時間較快，能夠實際應用到客運業中。提供民眾搭乘大眾運輸工具之意願與安全的乘車環境，以減緩交通堵塞與碳排放量的問題。

The Transit Network Timetable Scheduling Problem (TNTSP) and the Bus Driver Scheduling Problem (BDSP) have been main optimization problems in public transportation research for a long time. In the past, most research considered that drivers can serve only one route. Therefore, this paper will focus on the BDSP, especially considering that drivers can serve multiple routes. However, because these problems are NP-Hard problems, this paper will propose hybrid metaheuristics to find the optimal solution to increase the incentive that people take the public transportation.

This paper will analyze the demand of the passengers by the ticket transaction data and the bus timetable for eight bus routes at first, and formulate a mathematic model for the TNTSP to minimize the passenger waiting time, and use CPLEX which is an optimization software to make an optimal bus timetable. Next, the output of the TNTSP will be the demand of the BDSP, and formulate a mathematic model for the BDSP to minimize the seventy drivers’ difference between drive time and eight hours and the break time in a day. Then, this paper will propose two hybrid metaheuristics based on genetic algorithm, simulated annealing and tabu search respectively, and compare with each other to find the optimal solution

The research result shows that the optimal bus timetable by CPLEX is improved by 6%~59%. For the BDSP, two proposed hybrid metaheuristics are more effective than traditional genetic algorithm. To prove the effectiveness of the hybrid metaheuristics, this paper uses CPLEX to find the optimal solution and compare with the solution of the hybrid metaheuristics in a smaller scale problem

Hurdle, V. F. (1973). Minimum cost schedules for a public transportation route—I. Theory.
Transportation Science, 7(2), 109-137.
Sun, D. J., Xu, Y., & Peng, Z. R. (2015). Timetable optimization for single bus line based on hybrid
vehicle size model. Journal of Traffic and Transportation Engineering (English Edition), 2(3),
179-186.
Mesa, J. A., Ortega, F. A., & Pozo, M. A. (2014). Locating optimal timetables and vehicle schedules in
a transit line. Annals of Operations Research, 222(1), 439-455.
呂宏軒. (2014). 市區公車路線及排程最佳化模式. 中央大學土木工程學系學位論文, 1-95.
Huang, Shao-Hsuan. (2017). The Study of re-timetabling bus terminal trips based on dynamic bus system
data and bus smart card data, 1-41.
Kun-Hsiang Kuan. (2018). Study on the Integrated Planning Mode of City Bus Frequency. PhD Thesis.
National Central University.
Laporte, G., Ortega, F. A., Pozo, M. A., & Puerto, J. (2017). Multi-objective integration of timetables,
vehicle schedules and user routings in a transit network. Transportation Research Part B:
Methodological, 98, 94-112.
Wei-Shiang Yang. (2019). Application of Two-phase Genetic Algorithm for Bus Route Network
Scheduling Problem with Passenger Properties and Operating Expenses. 1-78
Wu, Y., Tang, J., Yu, Y., & Pan, Z. (2015). A stochastic optimization model for transit network timetable
design to mitigate the randomness of traveling time by adding slack time. Transportation Research
Part C: Emerging Technologies, 52, 15-31.
Tang, J., Yang, Y., & Qi, Y. (2018). A hybrid algorithm for urban transit schedule optimization. Physica
A: Statistical Mechanics and its Applications, 512, 745-755.
Manington, B., & Wren, A. (1975). A general computer method for bus crew scheduling. In Workshop
on Automated Techniques for Scheduling of Vehicle operators for Urban Public Transportation
Services”, Chicago.
Wren, A., & Wren, D. O. (1995). A genetic algorithm for public transport driver scheduling. Computers
& Operations Research, 22(1), 101-110.
De Leone, R., Festa, P., & Marchitto, E. (2011). A Bus Driver Scheduling Problem: a new mathematical
model and a GRASP approximate solution. Journal of Metaheuristics, 17(4), 441-466.
Constantino, A. A., de Mendonça Neto, C. F. X., de Araujo, S. A., Landa-Silva, D., Calvi, R., & dos
Santos, A. F. (2017). Solving a Large Real-world Bus Driver Scheduling Problem with a Multiassignment based Metaheuristic Algorithm. J. UCS, 23(5), 479-504.
Han, A. F., & Li, E. C. (2014). A constraint programming-based approach to the crew scheduling
problem of the Taipei mass rapid transit system. Annals of Operations Research, 223(1), 173-193.
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.
68
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.
Tóth, A., & Krész, M. (2013). An efficient solution approach for real-world driver scheduling problems
in urban bus transportation. Central European Journal of Operations Research, 21(1), 75-94.
Dias, T. G., de Sousa, J. P., & Cunha, J. F. (2002). Genetic algorithms for the bus driver scheduling
problem: a case study. Journal of the Operational Research Society, 53(3), 324-335.
蔡嘉妍. (2013). 公車駕駛長人力資源規劃與排班. 成功大學交通管理科學系學位論文, 1-66.
周怡均, & 王晉元. (2017). 以基因演算法求解公車駕駛員排班問題之研究 (Doctoral dissertation).
Shijun, C. H. E. N., Yindong, S. H. E. N., Xuan, S. U., & Heming, C. H. E. N. (2013). A crew scheduling
with Chinese meal break rules. Journal of Transportation Systems Engineering and Information
Technology, 13(2), 90-95.
Wang, S. Y., & Wu, K. F. (2018). Reducing traffic crash risk through driver rescheduling: a case study
on intercity bus drivers. In 18th International Conference Road Safety on Five Continents (RS5C
2018), Jeju Island, South Korea, May 16-18, 2018. Statens väg-och transportforskningsinstitut.
夏萬春. (2001) 禁制搜尋法於車輛排班之探討, 1-134.
Vanany, I., Rosyadi, R. S., Ciptomulyono, U. S., Hartanto, D., & Khoiri, M. (2016, July). Feeder bus
routing problem using a genetic algorithm: Surotram case study. In 2016 International Conference
on ICT For Smart Society (ICISS) (pp. 37-41). IEEE.
Jha, S. B., Jha, J. K., & Tiwari, M. K. (2019). A multi-objective meta-heuristic approach for transit
network design and frequency setting problem in a bus transit system. Computers & Industrial
Engineering, 130, 166-186.
Kletzander, L., & Musliu, N. (2020, June). Solving large real-life bus driver scheduling problems with
complex break constraints. In Proceedings of the International Conference on Automated
Planning and Scheduling (Vol. 30, pp. 421-429).
Kang, L., Chen, S., & Meng, Q. (2019). Bus and driver scheduling with mealtime windows for a single
public bus route. Transportation Research Part C: Emerging Technologies, 101, 145-160.
Yao, E., Liu, T., Lu, T., & Yang, Y. (2020). Optimization of electric vehicle scheduling with multiple
vehicle types in public transport. Sustainable Cities and Society, 52, 101862.