臺灣博碩士論文加值系統

適當的車隊規模與準確的排程作業，對客運業者的經營績效有深切的影響，因為乘務重複覆蓋班次，或過多車輛在車站等待派班，而產生的資源浪費，以及車輛不足或乘務安排不周以致未覆蓋必要班次，而產生的服務品質瑕疵，都是亟待解決的實務課題。最適車輛數為中長期決策，它限定了系統可供服務資源的產能，應予排程作業整合探討，而客運排程係短期決策問題，求解工作有相當大的時效壓力，且遇到塞車、車輛故障等偶發狀況時，常常需要重排程，是複雜度很高的NP-hard問題。過去之相關研究，都著重在排程部分，主要解決途徑有二：一為啟發式解法，這類方法不僅限制住問題的發展性，且求解效果很難保證令人滿意。另一為最佳解法，其處理問題的時間大多過長，或受限於小型模式，無法考慮完整的限制條件，以致實用價值頗受質疑。
本文應用基因演算法求解最適車輛數及排班表，此法不受問題規模的限制，能夠快速的衍生更好的可行解，在短時間內獲致近似最佳解。為了驗證方法的有效性，我們以國道客運業者之現行班次表及相關資料，進行測試及探討，結果顯示整體改善比率高達22%，對實務作業很有幫助。

The quality of freeway bus scheduling and optimal number of bus influences transportation company performance deeply. Cost of the duty over-cover or uncover piece-of-work and bus waiting for dispatching in the station are the most important subject that need to be solved. The optimal number bus is a medium-term decision. It limited the system capacity that can serve customers, should be solved with bus scheduling. The freeway bus scheduling is a problem of short-term decision, and problem solving itself has very big pressure of the time limited. When there is a bus that met the occasional accidents: such as traffic jam and car breakdown, it usually needed to be re-scheduled immediately. Bus scheduling is a complex NP-hard problem. In previous researches about freeway bus scheduling problem, the scholars use heuristic or optimal algorithm to find the best solution. However, the solution of the former algorithm can’t guarantee to give satisfaction, due to into confinement in a contain condition, while the latter’s processing time is too long. This problem will suffer from the scale limit as unable to consider too many practical terms, with the result that its amplification the value suffers a query.
This study using genetic algorithm to solve the problem, takes number of bus and bus scheduling into consideration, it will produce solutions rapidly and make the approximate optimal solution in a short time. For checking the usefulness of the method, we use the bus timetable of the current transportation company to run tests. The results show that the various methods that this study suggests can resolve the freeway bus scheduling problems quickly and improve the performance of the freeway transportation company. They carried out a high improvement rate, about 22%.

目　錄
目錄 …………………………………………………………….. Ⅰ
圖目錄 …………………………………………………………….. Ⅱ
表目錄 …………………………………………………………….. Ⅲ
第壹章、 緒論……………………………………………………….. 1
一、 研究動機………………………………………………….. 1
二、 研究目的………………………………………………….. 4
三、 研究範圍………………………………………………….. 5
四、 研究流程………………………………………………….. 6
第貳章、 文獻探討………………………………………………….. 8
一、 基因演算法……………………………………………….. 9
二、 人員排班………………………………………………….. 21
三、 客運排程………………………………………………….. 23
四、 結語……………………………………………………….. 27
第參章、 最適車輛數與客運排程問題……….……………………. 28
一、 客運排班之現況調查…………………………………….. 28
二、 專有名詞定義…………………………………………….. 31
三、 最適車輛數之基因演算法設計………………………….. 32
四、 最佳化客運排程之基因演算法設計…………………….. 34
五、 結語……………………………………………………….. 43
第肆章、 實證資料測試…………………………………………….. 44
一、 問題描述………………………………………………….. 44
二、 時空網路圖之建立……………………………………….. 46
三、 實證結果分析…………………………………………….. 48
四、 敏感度分析……………………………………………….. 52
五、 結語……………………………………………………….. 53
第伍章、 結論與建議……………………………………………….. 54
一、 結論……………………………………………………….. 54
二、 建議…………………………..…………………………… 56
參考文獻 …………………………………………………………….. 57
附錄一 乘務列表………………………………………………….. 63
附錄二 基因演算法程式………………………………………….. 75
圖 目 錄
圖1-4-1 本研究之研究流程………………………………….. 6
圖2-1-1 基因演算法流程圖……………………………….…. 10
圖2-1-2 編碼後之基因示意圖…………………………….…. 11
圖2-1-3 編碼後之染色體示意圖………………………….…. 11
圖2-1-4 單點交配前之染色體…………………………….…. 15
圖2-1-5 單點交配後之染色體…………………………….…. 16
圖2-1-6 多點交配前之染色體…………………………….…. 16
圖2-1-7 多點交配後之染色體…………………………….…. 16
圖2-1-8 均勻交配前之染色體…………………………….…. 17
圖2-1-9 均勻交配後之染色體…………………………….…. 17
圖2-1-10 OM前之染色體…………………………….……….. 18
圖2-1-11 OM後之染色體…………………………….……….. 19
圖2-1-12 PM前之染色體…………………………….……….. 19
圖2-1-13 PM後之染色體…………………………….……….. 19
圖2-2-1 公車排班示意圖……………………...…….……….. 22
圖3-1-1 一車輛的運行示意圖…………………………….…. 30
圖3-3-1 最適車輛數求解流程圖………….…………………. 32
圖3-4-1 客運排程求解流程圖….……………………………. 36
圖3-4-2 時空網路示意圖……….……………………………. 37
圖3-4-3 染色體位置示意圖……….…………………………. 38
圖3-4-4 本研究交配前之染色體……….……………………. 41
圖3-4-5 本研究交配後之染色體…….………………………. 41
圖3-4-6 本研究突變前之染色體……….……………………. 42
圖3-4-7 本研究突變後之染色體…….………………………. 42
圖4-2-1 某國道客運公司六站之時空網路圖…….…………. 46
圖4-3-1 客運最適車輛數…….…………….………………… 49
圖4-3-2 客運排程演化圖…….…………….………………… 51
表 目 錄
表2-1-1 排序法運算過程表………………………………….. 14
表3-4-1 兩節點一節線變數…………..…………..………….. 37
表4-1-1 某國道客運公司班次時刻表(北上) ……..………… 45
表4-1-2 某國道客運公司班次時刻表(南下)…..………...….. 45
表4-3-1 最適車輛數之實證資料測試結果…….………...….. 49
表4-3-2 最佳客運排程之實證資料測試結果…………….…. 50
表4-4-1 本研究敏感度分析…………..…………..………….. 52

參考文獻
【國內文獻】
[1] 何信瑩, Solving Optimization Problems Using Genetic Algorithms, 逢甲大學資訊工程研究所, 1999。
[2] 黃昭平、張克章、侯永昌, 基因演算法, 中華管理評論, Vol.3, No.1, pp.173∼186, 2000。
[3] 楊長林, 基因演算法之研究現況探討, 2002。
[4] 邱元泰, 遺傳演算法在排課問題之應用, 國立中正大學數學研究所未出版碩士論文, 2002。
[5] 周永暉, 特殊尖峰需求下鐵路列車排程規劃之最佳化模式, 國立交通大學交通運輸研究所未出版博士論文, 2000。
[6] 連志平, 警察人員排班問題之研究, 國立交通大學運輸工程與管理學系未出版碩士論文, 1998。
[7] 廖學昌, 公車客運業人員排班問題之研究─以金門縣公車為例, 國立交通大學運輸工程與管理學系未出版碩士論文, 1996。
[8] 蔡文昉, 大眾運輸排班系統之研究, 國立交通大學運輸工程與管理系未出版碩士論文，2000。
[9] 蔡政峰，「求解有限資源專案排程問題最佳化之研究-以基因演算法求解」，國立成功大學工業管理學研究所碩士論文，2001。
[10] 蘇木村、張孝德，「機器學習：類神經網路、模糊系統以及基因演算法」，台北：全華科技圖書股份有限公司，2002。
[11] 謝欣宏, 台鐵司機員排班與輪班問題之研究-以基因演算法求解,國立成功大學交通管理科學研究所未出版碩士論文, 2002。
[12] 蕭義梅，遺傳演算法應用在零工式工廠生產排程之應用，元智大學工業工程研究所碩士論文，1999。
【國外文獻】
1. Abboud, N., Inuiguchi, M., Sakawa, M., and Uemura, Y., “Manpower allocation using genetic annealing,” European Journal of Operational Research, Vol. 111, 1998, pp. 405-420.
2. Ann S. K. Kwan, Raymond S. K. Kwan and Anthony Wren, “Driver scheduling using Genetic Algorithms with embedded combinatorial traits”, School of Computer Studies and Leeds, November 1999.
3. Bard, J. F., L. Huang, M. Dror, and P. Jaillet, “A branch and cut algorithm for the VRP with satellite facilities”, IIE Transaction, Vol 30 1998, pp.821-834.
4. Beasely J.E and Cao B., “A tree Search Algorithm for the Crew Scheduling Problem,” European Journal of Operational Research, Vol 94, No.3, 1996, pp.517-526.
5. Beasley, J.E. and Chu, P.C., “A genetic algorithm for the set covering problem,” European Journal Operational Research, vol.94, 1997, pp.392-404.
6. Bussieck, M., Kreuzer, pP., and Zimmermann, U., “Optimal lines for railway systems” European Journal of the Operational Research, Vo1.96, 1997, pp.54-63
7. Ching-Fang Liaw, “A hybrid genetic algorithm for the open shop scheduling problem,” European Journal of Operational Research, Vol 124, 2000, pp.28-42.
8. Desaulniers, Guy; Lavigne, June; Soumis, Francois, “Multi-depot vehicle scheduling problems with time windows and waiting costs”, European Journal of Operational Research, Vol 111, 1998, p: 479-494
9. Dias, T. G., Sousa, J. P., and Cunha, J. F., “Genetic algorithms for the bus driver scheduling problem: a case study”, Journal of the Operational Research Society, Vol. 53, 2002, pp. 324-335.
10. Goldberg, D. E., Genetic algorithm in search, optimization and machine learning., 1989.
11. Goldberg, D. E. and Lingle R., ”Alleles, loci, and the traveling salesman problem”, Proceedings of an Int. Conf, on genetic algorithms and their application, ,1985, pp. 154-159.
12. Hernandez, L. F. G. and Corne, D. W., “Evolutionary divide and conquer of the set covering problem,” Evolutionary Computing, Springer, pp. 198-208.
13. Holland, J. H., “Adaptation in Natural and Artificial Systems, ” University of Michigan Pres, Ann Arbor, 1975.
14. H. C. Lau, “On the Complexity of Manpower Shift Scheduling,” Computers Operations Research, Vol.23, No.1, 1996, pp. 93-102.
15. Klabjan, D., Johnson, E. L., Nemhauser, G. L., Gelman, E. and Ramaswamy, S., “Airline Grew Scheduling with Regularity,” Transportation Science, Vol 35, 2000, pp.359-374.
16. Lau, H. C., “On the Complexity of Manpower Shift Scheduling,” Computers Operations Research, Vol. 23, No.1, 1996, pp. 93-102.
17. Liaw, C. F., “A hybrid genetic algorithm for the open shop scheduling problem,” European Journal of Operational Research, Vol. 124, 2000, pp. 28-42.
18. Michalewicz, Z., “Genetic algorithms + data structures =evolution programs, second, extended edition,” 1994.
19. N. Abboud, M. Inuiguchi, M. Sakawa, and Y. Uemura, “Manpower allocation using genetic annealing,” European Journal of Operational Research, Vol. 111, 1998, pp.405-420.
20. Sakanashi, H., Suzuki, H. and Kakazu, Y., “Filtering-GA: The evolutionary TSP landscape”, Int. Conf. Evolutionary Computer, Vol. 1, 1995, pp. 390-395.
21. TG Dias, JP de Sousa and JF Cunha, “Genetic algorithms for the bus driver scheduling problem: a case study,” Journal of the Operational Research Society, Vol 53, 2002, pp.324-335
22. Wren, A. and Wren, D.O., “A genetic algorithm for public transport driver scheduling,” Computers Operations Research, Vol 22, 1995, pp.101-110