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

A Bus Scheduling Model and Solution Algorithm for Inter-School Class Attendance

10.6402/TPJ.201112.0034

顏上堯(Shang-Yao Yan)；蕭妃晏(Fei-Yen Hsiao)；謝潤曉(Jun-Hsiao Hsieh)

跨校專車 ； 選授課 ； 時空網路 ； 多重貨物網路流動問題 ； 啟發解法 ； Inter-school bus ； Class attendance ； Time-space network ； Multiple commodity network flow problem ； Heuristic

運輸計劃季刊

40卷4期（2011 / 12 / 30）

369 - 392

繁體中文

近年來各校間選授課行為日益頻繁，於是跨校選授課專車因應而生。然而，目前國內跨校進授課專車之班表及排程大多以人工的經驗來規劃，缺乏系統性分析，因此難以掌握排程的績效。緣此，本研究考量合作學校的立場，並在滿足實務之營運目標及相關限制下，構建一多對多起迄需求之跨校還授課專車排程模式，期能輔助合作學校有效地規劃專車排程及班表。本研究模式為一特殊之多重貨物網路流動問題，屬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.

1. Azia, N.,Gendreaua, M.,Potvin, J. Y.(2007).An Exact Algorithm for A Single-Vehicle Routing Problem with Time Windows and Multiple Routes.European Journal of Operational Research,178(3),755-766.
2. Bent, R. W.,Hentenryck, P. V.(2004).Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers.Operations Research,52(6),977-987.
3. Bodin, L. D.,Berman, L.(1979).Routing and Scheduling of School Buses by Computer.Transportation Science,13(2),113-129.
4. 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.
5. 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.
6. 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.
7. Cordeau, J. F.,Laporte, G.(2003).A Tabu Search Heuristic for the Static Multi-Vehicle Dial-a-Ride Problem.Transportation Research Part B,37,579-594.
8. Desrosiers, J.,Dumas, Y.,Soumis, F.(1986).A Dynamic Programming Solution of the Large-Scale Single Vehicle Dial-a-Ride Problem with Time Windows.American Journal of Mathematical and Management Sciences,6,301-325.
9. Diana, M,Dessouky, M. M.(2004).A New Regret Insertion Heuristic for Solving Large-Scale Dial-a-Ride Problems with Time Windows.Transportation Research Part B,38,539-557.
10. Equi, L.,Gallo, G.,Marziale, S.,Weintraub, A.(1997).A Combined Transportation and Scheduling Problem.European Journal of Operational Research,97,94-104.
11. Garey, M. R.,Johnson, D. S.(1979).Computers and Intractability: A Guide to the Theory of NP-Completeness.San Francisco, CA:WH Freeman.
12. Hsu, C. I.,Hung, S. F.,Li, H. C.(2007).Vehicle Routing Problem with Time-Windows for Perishable Food Delivery.Journal of Food Engineering,80,465-475.
13. Ibaraki, T.,Kubo, M.,Masuda, T.,Uno, T.,Yagiura, M.(2005).Effective Local Search Algorithms for the Vehicle Routing Problem with General Time Windows Constraint.Transportaion Science,39,106-232.
14. Li, L.,Fu, Z.(2002).The School Bus Routing Problem: A Case Study.Journal of the Operational Research Society,53(5),552-558.
15. Melachrinoudis, E.,Ilhan, A. B.,Min, H.(2007).A Dial-a-Ride Problem for Client Transportation in a Healthcare Organization.Computers and Operations Research,34,742-759.
16. Psaraftis, H. N.(1980).A Dynamic Programming Approach to the Single-Vehicle, Many-to-Many Immediate Request Dial-a-Ride Problem.Transportation Science,14,130-154.
17. Rekiek, B.,Delchambre, A.,Saleh, H. A.(2006).Handicapped Person Transportation: An Application of the Grouping Genetic Algoritham.Engineering Application of Artifical Intelligence,19,511-520.
18. Solomon, M. M.,(1983).USA,Department of Decision Science, University of Pennsylvania.
19. Yan, S.,Chen, C. H.(2007).Coordinated Flight Scheduling Models for Allied Airlines.Transportation Research Part C,15,246-264.
20. Yan, S.,Chen, H. L.(2002).A Scheduling Model and a Solution Algorithm for Inter-City Bus Carriers.Transportation Research Part A,36,805-825.
21. Yan, S.,Chen, S. C.,Chen, C. H.(2006).Air Cargo Fleet Routing and Timetable Setting with Multiple On-Time Demands.Transportation Research Part E,42(5),409-430.
22. 申生元(2011)。行政院國家科學委員會專題計畫報告行政院國家科學委員會專題計畫報告,行政院國家科學委員會。
23. 向美田(1997)。碩士論文(碩士論文)。交通大學交通運輸研究所。
24. 張容瑄(2001)。碩士論文(碩士論文)。中正大學數學研究所。
25. 陳文瑞(1990)。碩士論文(碩士論文)。臺灣大學土木工程研究所。
26. 陳建都(1997)。碩士論文(碩士論文)。大葉工學院事業經營研究所。
27. 黃台生、許采蘋(2006)。計程車共乘與撥召計程車可行條件之研究。第 14 屆海峽兩岸都市交通學術研討會