臺灣博碩士論文加值系統

在公路公共運輸業者營運成本之中，公車駕駛員的人事成本所佔的比例相當高，因此公車駕駛員排班乃成為影響營運成本重要的影響因素。公車駕駛員排班問題必須考量公車營運特性與相關的限制條件，就複雜度理論而言，屬於困難求解的問題。
本研究採用基因演算法為求解架構的基礎，提出有別於傳統的染色體編碼以及交配程序，避免在模式求解時，於交配過程中產生不可行解。本研究採用中壢客運的實際的多條路線發車班表作為測試資料來源，進行模式的可用性測試。測試結果顯示本研究所提出的方法具體可行，並可在合理時間內產生符合實務需求的可行方案。

In view of reducing the operating cost while maintains the levels of service, a bus company always aims at obtaining a good driver schedules to fulfill all the required duties. The bus driver scheduling is a NP-Hard problem, which involves complex constraints related to regulations from bus company and authorities.
The purpose of this study is to solve the bus driver scheduling problem by adopting the genetic algorithm (GA). To effectively reduce the number of unfeasible solutions after crossover, we proposed a modified chromosome and gene coding scheme. The driver's work shift, rather each trip, has been encoded as a chromosome, and the trip has been encoded as a gene. We test the robustness of our algorithms by using the real data from a local bus operators. The testing results show that our algorithm is capable of producing feasible and practical sound results.

摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 vii
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 2
1.3研究範圍 2
1.4研究流程 2
第二章 文獻回顧 4
2.1 航空組員排班 4
2.2大眾運輸人員排班 5
2.3一般人員排班 8
2.4基因演算法 10
2.5小結 15
第三章 研究方法 20
3.1公車駕駛員排班問題 20
3.2求解基因演算法 23
3.3編碼方式 23
3.4產生起始解 25
3.5適應值之計算 28
3.6選擇親代及交配法 31
3.7突變 38
第四章 測試與分析 41
4.1實測資料 41
4.2參數設定 42
4.3實例測試 43
4.3.1單場站單路線排班 43
4.3.2單場站不同路線排班 45
第五章 結論與建議 51
5.1結論 51
5.2建議 51
參考文獻 53
 

1. 交通部運輸研究所（主編）（2012），運輸政策白皮書101年：綠運輸，交通部。
2. 黃瑛奇，「基因演算法在警察排班的應用」，國立屏東科技大學，工業管理系碩士論文，民國101年。
3. 張育彰，「應用基因演算法於台鐵列車駕駛員排班與輪班整合問題之研究」，國立成功大學，交通管理科學研究所碩士論文，民國92年。
4. 游文松，「公路客運人員與車輛排班之研究」，中華大學，科技管理研究所碩士論文，民國93年。
5. 臺北市政府交通局（2013），「臺北市聯營公車運價公式檢討方案」。
6. 交通部統計查詢網-中華民國交通部(2017年5月)‧機動車輛登記數‧2017年7月10日取自http://stat.motc.gov.tw/mocdb/stmain.jsp?sys=100&funid=a3301
7. Azadeh, A., Farahani, M. H., Eivazy, H., Nazari-Shirkouhi, S., and Asadipour, G. (2013), "A hybrid meta-heuristic algorithm for optimization of crew scheduling," Applied Soft Computing, Vol. 13, No. 1, pp. 158-164.
8. Beasley, J. E., and Cao, B. (1996), "A tree search algorithm for the crew scheduling problem," European Journal of Operational Research, Vol. 94, No. 3, pp.517-526.
9. Beasley, J. E. and Chu, P. C. (1996), "A genetic algorithm for the set covering problem," European Journal of Operational Research, Vol. 94, pp.392-404.
10. Do Ngoc, A. D., Lee, S. H., and Moon, I. (2014), "Hybrid genetic algorithm for test bed scheduling problems," International Journal of Production Research, Vol. 52, No.4,pp.1074-1089.
11. Elizondo, R., Parada, V., Pradenas, L., and Artigues, C. (2010), "An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport," Journal of Heuristics, Vol. 16, No. 4, pp. 575-591.
12. Han, A. F., and 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, Vol. 223, No. 1, pp. 173-193.
13. Holland, J. H. (1975/1992). Adaptation in Natural and Artificial Systems. Cambridge, MA:MIT Press. Second edition (1992). (First edition, University of Michigan Press, 1975).
14. Jeng, C. R., Liu, T. K., and Chang, Y. H. (2008), "Short-haul airline crew rostering by using inequality-based multiobjective genetic algorithm," Transportation Research Record, Vol. 2052, pp. 37-45.
15. Kim, S. J., Ko, Y. W., Uhmn, S., and Kim, J. (2014), "A strategy to improve performance of genetic algorithm for nurse scheduling problem," International Journal of Software Engineering and Its Applications, Vol.8, No.1, pp. 53-62.
16. Kwan, R. S. K., Wren, A. and Kwan, A. S. K. (2000), "Hybrid genetic algorithms for scheduling bus and train drivers," Evolutionary Computation, 2000, Proceedings of the 2000 Congress on 16-19 July 2000, pp.285-292. New York, IEEE.
17. Lin, D. Y. and Hsu, C. L. (2016), "A column generation algorithm for the bus driver scheduling problem," Journal of Advanced Transportation, Vol.50, No. 8, pp. 1598-1615.
18. Park, T., and Ryu, K. R. (2006), "Crew Pairing Optimization by a Genetic Algorithm with Unexpressed Genes," Journal of Intelligent Manufacturing, Vol. 17, No. 4, pp. 375-383.
19. Shen, Y., Peng, K., Chen, K., and Li, J. (2013), "Evolutionary crew scheduling with adaptive chromosomes," Transportation Research Part B: Methodological, Vol. 56, pp.174-185.
20. Wren, A., and Wren, D. O. (1995), "A genetic algorithm for public transport driver scheduling," Computers & Operation