週期性乘務員輪班問題(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.

中文參考文獻
張育彰，應用基因演算法於台鐵列車駕駛員排班與輪班整合問題之研究，交通管理科學研究所碩士論文，國立成功大學，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.