臺灣博碩士論文加值系統

週期性乘務員?班問題(Cyclic Crew Rostering Problem, CCRP)旨在求得一可將所有工作班依序相?之最短週期?班表。過去文獻大多將?班問題轉化為特殊之??推銷員問題(Specific Travelling Salesman Problem, STSP)；然而此?轉化過後的模式通常無法處?每「?轉週」、或每「?轉月」內必須滿足之操作型規範；有鑑於此，本研究遵循台鐵現?之?班規範，以每工作班及?假為橫向階層，每日為縱向階層，並考?平均工時與次序型規範而發展出一個多階層?班網?圖(Multi-level Rostering Network, MRN)，以方?處??班問題之?轉式操作型規範。接著，我們以MRN 為基礎，將?班問題之剩餘規範轉換成一套整?規劃完整模式(Full Integer Programming, FIP)。由於FIP 難?甚高，即使使用專業最佳化
軟體亦無法快速求解，因此我們提出一套固定?假搜尋算法(Fix-and-Search Algorithm, FSA)」的分段求解方式，先將較??安排的?假日及部份工作班間以一套整?規劃部份模式(Partial Integer Programming, PIP)求解出?，再將這些關鍵節點之時間固定，以貪婪方式執?深?優先搜尋法(Depth First Search, DFS)以求得一可?之?班?徑。?值測試結果顯示，本研究提出之FIP 及FSA 的確可以計算出符合所有?班規範之?班表，其中FSA 之求解表現?是極為優?。
?遇到乘務員?時請假或缺席而無法執?其原始?職工作時，則需求解週
期性乘務員?班調整問題(Cyclic Cyclic Crew Rerostering Problem, CCRSP)，以設計出盡可能避免過多的人員重新調派之新工作?職表。由於鐵?管?相關文獻鮮少探討相關議題，本研究將以MRN為基礎，將?班調整問題轉化為一個多元商品網???問題(Multi-commodity Network Flow, MNF)，並提出其相對應之整?規劃模式(Integer Programming, IP)，以求得滿足規範下之最適工作調整?職表。

The Cyclic Crew Rostering Problem (CCRP) aims at ordering a set of duties to determine a roster of shortest cycle time. Previous solution methods usually treat CCRP as a Specific Travelling Salesman Problem (STSP). Although the STSP model can schedule all the duties, it cannot deal with some difficult operational regulations that restrict the schedules of off-duty periods in a rolling base. To this end, we design a Multi-level Rostering Network (MRN) to illustrate the CCRP and then solve it by a Full Integer Programming model (FIP). Since FIP usually consumes too much computational time to determine an optimal roster, we develop the Fix-and-Search Algorithm (FSA) that calculates a suitable roster in very short time. Starting with a lower bound on the length of a roster cycle, FSA tries to connect a feasible roster path by three major steps: First, it determines a feasible setting for two classes of duties by solving a subproblem of PIP so that the operational regulations can be easily satisfied; Second, the schedules for the key duties are fixed; Third, a modified Depth First
Search (DFS) algorithm is used to find a feasible roster path. If no feasible roster path can be connected, FSA then increases the lower bound by one and repeats the steps until a feasible roster path is connected. The results of our computational experiments indicate FSA usually gives an optimal roster and is much more efficient than the STSP model in literature.
If some crew members cannot be on duty, the Cyclic Crew Rerostering Problem (CCRSP) to rebuild a new roster starting from a given date (usually the first date of absence) has to be solved to the end of the current roster such that the interference is minimized. In a sense, CCRSP can be viewed as seeking another optimal roster to the original CCRP, and these two rosters should be identical before a given date of interference and as similar to each other as possible after that interference. To this end,we propose the Integer Programming (IP) model based on a Multi-commodity Network Flow (MNF) network.

摘要 I
Abstract II
誌謝 IV
表目? VIII
圖目? IX
第一章 緒? 1
1.1 研究背景與動機 ．．．．．．．．．．．．．．．．．．．．．．． 1
1.2 研究目的 ．．．．．．．．．．．．．．．．．．．．．．．．．． 2
1.3 研究範圍 ．．．．．．．．．．．．．．．．．．．．．．．．．． 3
1.4 研究假設 ．．．．．．．．．．．．．．．．．．．．．．．．．． 4
1.5 ?文架構 ．．．．．．．．．．．．．．．．．．．．．．．．．． 5
第二章 文獻回顧 6
2.1 鐵?客運運輸規劃問題之簡介．．．．．．．．．．．．．．．．． 6
2.2 乘務員排班與?班問題之簡介．．．．．．．．．．．．．．．．． 9
2.3 週期性乘務員?班問題．．．．．．．．．．．．．．．．．．．． 12
2.4 ?班調整問題．．．．．．．．．．．．．．．．．．．．．．．． 19
2.5 ?班規範之彙整．．．．．．．．．．．．．．．．．．．．．．． 22
2.6 小結．．．．．．．．．．．．．．．．．．．．．．．．．．．． 26
第三章 週期性?班問題之模式建構與發展 27
3.1 問題描述與解法架構．．．．．．．．．．．．．．．．．．．．． 27
3.1.1 問題描述．．．．．．．．．．．．．．．．．．．．．．．．． 27
3.1.2 解法架構．．．．．．．．．．．．．．．．．．．．．．．．． 30
3.2 ?班網?系統．．．．．．．．．．．．．．．．．．．．．．．．32
3.3 整?規劃完整模式(FIP)．．．．．．．．．．．．．．．．．．．．35
3.3.1 ?學模式．．．．．．．．．．．．．．．．．．．．．．．．．35
3.3.2 ?值範?．．．．．．．．．．．．．．．．．．．．．．．．．42
3.4 固定?假搜尋演算法(FSA)．．．．．．．．．．．．．．．．．． 45
3.4.1 整?規劃部份模式(PIP)．．．．．．．．．．．．．．．．．45
3.4.2 固定關鍵節點(FKD)．．．．．．．．．．．．．．．．．．．49
3.4.3 深?優先搜尋法(DFS)．．．．．．．．．．．．．．．．．．49
3.4.4 ?值範?．．．．．．．．．．．．．．．．．．．．．．．．53
3.5 ?值分析．．．．．．．．．．．．．．．．．．．．．．．．．．58
3.6 小結．．．．．．．．．．．．．．．．．．．．．．．．．．．．62
第四章 週期性?班調整問題之模式建構與發展 63
4.1 問題描述與解法架構．．．．．．．．．．．．．．．．．．．．． 63
4.2 多元商品網???圖(MNF)．．．．．．．．．．．．．．．．．．64
4.3 模擬乘員請假?況．．．．．．．．．．．．．．．．．．．．．．67
4.4 整?規劃模式(IP)．．．．．．．．．．．．．．．．．．．．．．69
4.5 ?值範?．．．．．．．．．．．．．．．．．．．．．．．．．．79
4.6 ?值分析．．．．．．．．．．．．．．．．．．．．．．．．．．85
4.7 小結．．．．．．．．．．．．．．．．．．．．．．．．．．．．86
第五章 結?與未?研究方向 87
5.1 結?．．．．．．．．．．．．．．．．．．．．．．．．．．．．87
5.2 研究成果與貢獻．．．．．．．．．．．．．．．．．．．．．．．88
5.3 未?研究方向．．．．．．．．．．．．．．．．．．．．．．．．89
?考文獻 90
附? 92
台灣鐵?管?局動??乘務員勤務時間排班須知．．．．．．．．．．． 92
機務段 機班運用表 ．．．．．．．．．．．．．．．．．．．．．．． 93
機務段 (柴電、DRC、EMU、調?) 機班運用表．．．．．．．．．．． 94

中文?考文獻
張育彰，應用基因演算法於台鐵??駕駛員排班與?班整合問題之研究，交通管?科學研究所碩士?文，國?成功大學，2003。
郭彥秀，鐵?駕駛員排班問題之研究，交通管?科學研究所碩士?文，國?成功大學，2000。
謝欣宏，台鐵司機員排班與?班問題之研究－以基因演算法求解，交通管?科學研究所碩士?文，國?成功大學，2002。

英文?考文獻
Bussieck, M. R., Winter, T. and Zimmermann, U.T. Discrete optimization in public rail transport. Mathematical Programming, 79, 415-444, 1997.
Caprara, A., Fischetti, M., Toth, P. and Vigo, D. Algorithms for railway crew management. Mathematical Programming, 79, 125-141, 1997.
Caprara, A., Fischetti, M., Toth, P. and Vigo, D. Modeling and solving the crew rostering problem. Operations Research, 46, 820-830, 1998.
Hartog, A., Huisman, D., Abbink, E. and Kroon, L. Decision support for crew rostering at NS. Proceedings of CASPT 2006, 2006.
Hartog, A., Huisman, D., Abbink, E. and Kroon, L. Decision support for crew rostering at NS. Public Transp, 1, 121-133,2009.
Huisman, D., Kroon, L. G., Lentink, R. M. and Vromans, M. J. C. M. Operations research in passenger railway transportation. Statistica Neerlandica, 59, 467–497,2005.
M?ller, J. Seminar on algorithms and models for railway optimization crew scheduling. University of Konstanz, ller-seminar, 2002.
Moz, M. and Pato, M. V. A genetic algorithm approach to a nurse rerostering problem. Computers and Operations Research, 34, 667-691, 2007.
Moz, M. and Pato, M. V. An integer multicommodity flow model applied to the rerostering of nurse schedules. Annals of Operations Research, 119, 285-301,2003.
Moz, M. and Pato, M. V. Solving a bi-objective nurse rerostering problem by using a utopic Pareto genetic heuristic. Journal of Heuristics, 14, 359-374, 2008.
Moz, M. and Pato, M. V. Solving the problem of rerostering nurse schedules with hard constraints: new multicommodity flow models. Annals of Operations Research,
128, 179-197, 2004.Konl, N. and Karisch, S. E. Airline Crew Rostering: Problem Types, Modeling and Optimization. Annals of Operations Research, 127, 223-257, 2004.
Sodhi, M. and Norris, S. A flexible, fast, and optimal modeling approach applied to crew rostering at London Underground. Annals of Operations Research, 127,259-281, 2004.