跨校選授課專車排程規劃模式暨演算法之研究

近年來各校間選授課行為日益頻繁，於是跨校選授課專車因應而生。然而，目前國內跨校進授課專車之班表及排程大多以人工的經驗來規劃，缺乏系統性分析，因此難以掌握排程的績效。緣此，本研究考量合作學校的立場，並在滿足實務之營運目標及相關限制下，構建一多對多起迄需求之跨校還授課專車排程模式，期能輔助合作學校有效地規劃專車排程及班表。本研究模式為一特殊之多重貨物網路流動問題，屬NP-hard問題。為有效地求解實務的大型問題，本研究利用問題分解及合併策略，且配合CPLEX軟體，發展一有效的啟發解法。最後，本研究以國內某一教學合作大學系統之跨校還授課專車營運為例，進行範例測試，結果良好，顯示本研究模式及演算法應可為實務界及學術界之參考。

關鍵字

跨校專車；選授課；時空網路；多重貨物網路流動問題；啟發解法

並列摘要

In recent years, the cooperation between colleges and the behavior of attending inter-school classes significantly strengthen. In order to service teachers and students for attending inter-school classes, inter-school buses for class attendance arise. However, the inter-school bus route/schedule is manually determined by planning personnel with experience, without optimization from a systemic perspective. Consequently, the effectiveness of the resulting route/schedule is unknown. Therefore, in this research, based on the perspective of the cooperated schools, we develop a bus scheduling model with many-to-many OD demand for inter-school class attendance, subject to the real operating objective and constraints. The model is expected to be an effective planning tool for cooperated schools to decide on a good bus route/schedule for inter-school class attendance. The model is formulated as a special multiple commodity network flow problem, which is characterized as NP-hard. To efficiently solve realistically large problems that occur in practice, we develop a heuristic algorithm by adopting a problem decomposition and collapsing strategy, couple with the use of CPLEX software. Finally, to evaluate how well the model and the solution algorithm could be applied in practice, a case study is performed using the bus operation data for inter-school class attendance from an allied university system in Taiwan. The test results are good, showing that the proposed model and solution algorithm could be useful reference for academics and practices.

並列關鍵字

Inter-school bus ； Class attendance ； Time-space network ； Multiple commodity network flow problem ； Heuristic

參考文獻

Bodin, L. D.,Berman, L.(1979).Routing and Scheduling of School Buses by Computer.Transportation Science.13(2),113-129.

Google Scholar

Bowerman, R.,Hall, B.,Calamai, P.(1995).A Multi-Objective Optimization Approach to Urban School Bus Routing: Formulation and Solution Method.Transportation Research Part A.29(2),107-123.

Google Scholar

Braca, J.,Bramel, J.,Posner, B.,Simchi-Levi, D.(1997).A Computerized Approach to the New York City School Bus Routing Problem.IIE Transactions.29,693-702.

Google Scholar

Corberan, A.,Fernandez, E.,Laguna, M.,Marti, R.(2002).Heuristic Solutions to the Problem of Routing School Buses with Multiple Objectives.Journal of the Operational Research Society.53(4),427-435.