應用基因演算法及蟻群最佳化於台鐵乘務人員排班問題之研究

Applying Genetic Algorithms and Ant Colony Optimization to Resolve TRA's Conductor Scheduling Problem

徐志明(Chih-Ming Hsu) ； 黃廷合(Ting-Ho Huang) ； 劉雙火(Shuang-Huo Liu)

《明新學報》 34卷2期 (2008/08) Pp. 199-218

https://doi.org/10.29688/MHJ.200808.0014

摘要

本研究以台灣鐵路管理局列車乘務人員排班作業為研究對象。首先，在兼顧各車班組間工作負荷平衡率及總體工作負荷率的目標下，考量現有之車班人力數目及相關限制條件，利用基因演算法以獲得乘務分配的近似最佳解；接著，利用蟻群最佳化演算法尋找總工作時數最短的乘務串接，並以最少工作班總數為目標，進行乘務切割產生工作班；最後，在符合乘務人員排班限制條件下，完成輪班表之制訂。實例驗證結果顯示，乘務分配的結果較現行人工指派結果為佳，且工作負荷平衡率可以獲得大幅改善；透過乘務串接及切割則可減少10.2%的工作班總數；而在輪班表產生階段則可產生能實際運用的輪班表排班結果；此結果預期可替台鐵每年節省約2,820萬台幣的乘務人員薪資成本。由此，可證明本研究之構想為有效且實際可行。

關鍵字

基因演算法 ； 蟻群最佳化 ； 乘務人員排班

並列摘要

This study focuses on the conductor scheduling problem of Taiwan Railways Administration (TRA). First, genetic algorithms (GAs) are applied to obtain the near optimal solution to the trip assignment problem where the workload balance among subsections and the overall workload of all subsections are simultaneously optimized based on the current available manpower in each subsection and other constraints. Next, the ant colony optimization (ACO) algorithm is used to find the sequence of trips with the shortest working hours. The shifts are then generated by segmenting the sequence of trips with the objective of minimizing the total number of shifts. Finally, the crew rostering of conductors that conforms to the rules of crew scheduling can be set up. The demonstration through a real case reveals that the assignment of trips acquired by the proposed procedure is superior to the manual assignment. Furthermore, the workload balance among subsections can be improved dramatically. By optimizing and segmenting the sequence of trips, the total number of shifts is reduced by 10.2%. In the generation of rostering, the applicable crew rostering of conductors can be created. By applying these results, a saving of about NT$28.2 millions for the conductors' salaries can be expected for TRA. Hence, the proposed procedure can be considered to be effective and practicable.

並列關鍵字

Genetic Algorithms ； Ant Colony Optimization ； Conductor Scheduling

參考文獻

Beasley, J. E.,Cao, B.(1996).A tree search algorithm for the crew scheduling problem.European Journal of Operation Research.94,392-404.

Debora, A. A.,Roger, L. W.(1998).Applying genetic algorithms to the u-shaped assembly line balancing problem.(Proceedings of the 1998 IEEE World Congress on Computational Intelligence).

Dorigo, M.(1992).Optimization, learning and natural algorithms.Politecnico di Milano.

Dorigo, M.,Maniezzo, V.,Colorni, A.(1996).Ant system: optimization by a colony of cooperating agents.IEEE Transactions on Systems, Man, and Cybernetics-Part B.26,29-41.

Evans, S. P.(1976).Derivation and analysis of some model for combining trip distribution and assignment.Tranportation Research.10,37-57.