以基因演算法求解公車駕駛員排班問題之研究

Abstract

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

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.