跨校選授課專車排程規劃之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：16

、訪客IP：18.191.200.60

姓名

謝潤曉(Jun-hsiao Hsieh) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

跨校選授課專車排程規劃之研究
(Inter-school Bus Schedule Planning)

相關論文

★ 橋梁檢測人力機具排班最佳化之研究	★ 勤業務專責分工下消防人員每日勤務排班最佳模式之研究
★ 司機員排班作業最佳化模式之研究	★ 科學園區廢水場實驗室檢驗員任務指派最佳化模式之研究
★ 倉儲地坪粉光工程之最佳化模式研究	★ 生下水道工程工作井佈設作業機組指派最佳化之研究
★ 急診室臨時性短期護理人力指派最佳化之探討	★ 專案監造人力調派最佳化模式研究
★ 地質鑽探工程人機作業管理最佳化研究	★ 職業棒球球隊球員組合最佳化之研究
★ 鑽堡於卵礫石層施作機具調派最佳化模式之研究	★ 職業安全衛生查核人員人力指派最佳化研究
★ 救災機具預置最佳化之探討	★ 水電工程出工數最佳化之研究
★ 石門水庫服務台及票站人員排班最佳化之研究	★ 空調附屬設備機組維護保養排程最佳化之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

近年來隨著台灣地區大專院校數量的增加，相對地學生人數與之劇增，各校間教學合作日益頻繁，校際間之選授課行為也因應而生，台灣聯合大學系統即為最佳範例。現行之跨校選授課專車，目的在於服務台灣聯合大學系統之教職員與學生，但跨校選授課專車之班表為人工經驗排班方式進行規劃，因缺乏系統性分析，故無法完善地服務搭乘需求。緣此，本研究針對跨校選授課專車之特性，以學校立場為考量，構建一系統最佳化模式，以期能提供學校方面作為有效規劃之輔助工具，並協助決策者有效地進行規劃。
本研究利用網路流動之技巧與數學規劃方法，建立一考量多對多起迄需求之跨校選授課專車排程模式，以最小車輛數及最小總加權營運時間為目標，於網路設計上，加上時窗限制以滿足實務之營運條件。本研究之模式為含額外限制之多目標整數網路流動問題，屬NP-hard問題，為有效率地求解大規模之問題，本研究利用問題分解策略，且配合CPLEX數學規劃套裝軟體，發展一有效之啟發式解法。最後評估本研究模式與啟發式解法之實用績效，以台灣聯合大學系統為範例測試，並針對不同之參數進行敏感度分析與方案分析，其測試結果良好，最後提出結論與建議。

摘要(英)

In recent years, with the increasing of universities in Taiwan, the number of students rises as a result. With this situation, the behavior of having inter-school classes appears. The University System of Taiwan is the best example. Nowadays, the inter-school bus is set up to service the teachers and students of The University System of Taiwan, but the schedule is manually performed by planning personnel with experience in current practice. Without a systematic analysis, it cannot satisfy the demands perfectly. Therefore, in this research, consider the properties of the inter-school bus problem and based on the perspective of school planner, we develop a system-optimized model. The model is expected to be an effective tool for the school, also, it can help planner to solve problems.
In this research, we employed network flow techniques and mathematical programming method, and build an inter-school bus scheduling model with many-to-many OD demand. The minimum number of vehicles and the minimum total weighted operating time is our target. In the network design, adds time window limit to meet the practical operating. Model is formulated as an integer multiple commodity network flow problem, which is characterized as NP-hard. To efficiently solve the problems whose sizes are expected to be huge in real practice, we developed a heuristic algorithm by use the problem decomposition strategy with CPLEX software. In addition, to evaluate the performance of inter-school bus model and solution algorithm practice, we take the University System of Taiwan as an example. Performing sensitive and scenario analysis for different parameters, and the result of the model test shows good. Finally, conclusions and suggestions are given.
Key words: Inter-school bus, Time-space network, Heuristic, Multiple commodity network flow problem.

關鍵字(中)

★ 跨校選授課專車
★ 含額外限制網路流動問題
★ 時空網路
★ 啟發解法

關鍵字(英)

★ Inter-school bus
★ Time-space network
★ Heuristic
★ Multiple commodity network flow problem

論文目次

摘要 I
ABSTRACT II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 VII
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 3
1.3 研究方法與程式架構 4
第二章文獻回顧 6
2.1校車排程與路線設計相關文獻 6
2.1.1國外校車規劃與排程 6
2.1.2國內校車規劃與排班 8
2.1.3國內外校車規劃小結 9
2.2 時窗限制之車輛派遣與排程問題 10
2.3 撥召共乘相關文獻 11
2.4 時空網路設計相關文獻 14
2.4.1海空運方面 14
2.4.2陸運方面 15
2.5大型含額外限制之整數網路流動問題啟發式演算法 16
2.6文獻評析 19
第三章模式構建 20
3.1跨校選授課專車排程模式 20
3.1.1基本假設與已知資訊 20
3.1.2時空網路設計 22
3.1.3符號說明 29
3.1.4數學定式 30
3.2 模式應用 31
3.3 小結 32
第四章求解演算法設計 33
4.1啟發式解法 33
4.2目標值下限解 37
4.3車輛定線與乘客配對演算法 38
4.4 小結 38
第五章範例測試 39
5.1資料分析 39
5.1.1 跨校選授課專車排程規劃所需之相關參數資料 39
5.1.2 搭乘需求之資料 40
5.1.3 跨校專車排程規劃之成本資料 42
5.2模式發展 43
5.2.1 問題規模 43
5.2.2 模式輸入資料 43
5.3電腦演算環境及設定 44
5.3.1 電腦演算環境 44
5.3.2 相關參數設定 45
5.3.3 模式輸出資料 46
5.4測試結果與分析 46
5.5敏感度分析 48
5.5.1總搭乘需求人數之敏感度分析 48
5.5.2 ODT種類之敏感度分析 53
5.5.3發車成本值之敏感度分析 57
5.5.4旅行成本值之敏感度分析 58
5.5.5人流未服務之懲罰成本值之敏感度分析 62
5.6 方案分析 63
5.6.1 不同問題規模之方案分析 63
5.6.2 發車地點固定與不固定之方案分析 66
5.6.3 現行班表之方案分析 68
5.7 小結 69
第六章結論與建議 70
6.1結論 70
6.2建議 71
6.3貢獻 72
參考文獻 73
附錄 81
附錄一 CPLEX Callable Library Code 81
附錄二 ODT種類輸入資料 82

參考文獻

1. 申生元，「多趟次車輛途程與排程問題」，行政院國家科學委員會，NSC90-2218-E155-010 (2002)。
2. 向美田，「公車動態資訊與撥召系統之研究與建立-以金門縣為例」，碩士論文，國立交通大學交通運輸研究所 (1997)。
3. 何依栖，「都會區計程車共乘制度實施及管理之探討」，運輸計畫季刊，第十八卷，第四期，507-518頁 (1989)。
4. 余秀梅，「多元商品模式應用在動態貨櫃調度問題之研究」，碩士論文，國立成功大學交通管理科學研究所 (1994)。
5. 吳志仁，(指導教授：韓復華)，「一般化卡車拖車路線問題」，碩士論文，國立交通大學運輸科技與管理學系 (2003)。
6. 周義華、林祥生，「都市公車路網設計方法之研究」，運輸計劃季刊，第十四卷，第四期，495-529頁 (1985)。
7. 邱明琦、陳春益、林佐鼎，「海運貨櫃排程模式之研究」，運輸計劃季刊，第三十一卷，第三期，第495-522頁 (2002)。
8. 卓裕仁，(指導教授：韓復華)，「以巨集啟發式解法求解多車種與週期性車輛路線問題之研究」，博士論文，國立交通大學運輸工程與管理學系 (2001)。
9. 夏文慶，(指導教授：王晉元)，「公車路線設計決策支援系統建立之研究-以新竹客運為例」，碩士論文，國立交通大學運輸科技與管理學系 (1998)。
10. 許采蘋，「計程車共乘與撥召計程車可行條件之研究」，碩士論文，國立交通大學交通運輸研究所 (2005)。
11. 陳建都，(指導教授：邴傑民、楊明璧)，「校車路線指派問題之研究」，碩士論文，大葉工學院事業經營研究所 (1996)。
12. 陳建緯，(指導教授：韓復華)，「大規模旅行推銷員問題之研究：鄰域搜尋法與巨集啟發式解法之應用」，碩士論文，國立交通大學運輸工程與管理學系 (2001)。
13. 陳文瑞，(指導教授：曹壽民)，「交通車之網路設計」，碩士論文，國立台灣大學土木工程研究所 (1989)。
14. 張容瑄，(指導教授：紀美秀)，「模擬退火法在校車路線問題上的應用」，碩士論文，國立中正大學數學研究所 (2001)。
15. 張靖、卓裕仁、莊子駿、王寶治、許惠淑，「地理資訊系統在校車路線與班次排程上之應用：以中華大學為例」，中華民國運輸學會第十六屆論文研討會論文集，台北，123-132頁 (2001)。
16. 張淑詩，「通勤交通車路線問題之研究」，碩士論文，國立交通大學運輸科技與管理學系 (2006)。
17. 黃勵君，(指導教授：周義華)，「捷運系統最適營運路線設計之研究」，碩士論文，國立台灣大學土木工程研究所 (2000)。
18. 韓復華、朱政威、張淑詩，「員工通勤車交通路線改善及規劃」，個人研究資料 (2005)。
19. 藍武王、施媺媺，「公車路線規劃與定線方法之研究」，運輸計劃季刊，第十二卷，第四期，411-432頁 (1983)。
20. 顏上堯、齊志仁、湯慶輝，「隨機需求下多目標長途客運排程模式之研究」，運輸計畫季刊，第34卷第1期，第93-118頁 (2005)。
21. Angel, R. D., Caudle, W. L., Noonan, R. and Whinston, A., “Computer-Assisted School Bus Scheduling,” Management Science, Vol. 18, No. 6, pp. 279-288(1972).
22. Aldaihani, M. and M. M., Dessouky, “Hybrid scheduling methods for paratransit operations,” Computers and Industrial Engineering, Vol. 45, pp. 75-96 (2003).
23. Azia, N., Gendreaua, M. and Potvin, J.Y., “An exact algorithm for a single-vehicle routing problem with time windows and multiple routes,”European Journal of Operational Research, 178(3), pp.755-766(2007).
24. Benders, J. F.. “Partitioning procedures for solving mixed-variables programming problems,” Numerische Mathematik, Vol. 4, pp. 238-252(1962).
25. Bodin, L. D. and Berman, L., “Routing and Scheduling of School Buses byComputer,” Transportation Science, Vol. 13, No. 2, pp. 113-129(1979).
26. Byren, B. F. and Vuchic, V. R., “Public Transportation Line Positions and Headways for Minimum Cost,” Traffic Flow and Transportation, pp. 347-360(1972).
27. Byrne, B. F., “Cost Minimizing Positions, Lengths and Headways for Parallel Public Transit Lines Having Different Speeds,” Transportation Research, Vol. 10, pp.209-214(1976).
28. Bodin, L., Golden, B. L., Assad A. and Ball, M., “Routing and Schedule of Vehicle and Crew: The State of Art,” Special Issue of Computers and Operations Research, Vol. 10, No. 2, pp. 63-211(1983).
29. Bodin, L. D. and Sexton, T., “The multi-vehicle subscriber dial-a-ride problem,”TIMS Studies in Management Science, Vol. 2, pp. 73-86 (1986).
30. Bowerman, R., Hall B. and Calamai, P., “A Multi-objective Optimization Approach to Urban School Bus Routing ： Formulation and Solution Method,”Transportation Research Part A：Policy and Practice, Vol. 29A, No. 2, pp. 107-123(1995).
31. Braca, J., Bramel, J., Posner B. and Simchi-Levi, D., “A Computerized Approach to the New York City School Bus Routing Problem,” IIE Transactions, Vol. 29, pp.693-702(1997).
32. Bent, R. W. and Hentenryck, P. V., “Scenario-based planning for partially dynamic vehicle routing with stochastic customers,” Operations Research, pp.52, 977-987(2003).
33. Christofides, N. and Eilon, S., “An Algorithm for Vehicle Dispatching Problem,”Operational Research Quarterly, Vol. 20, pp. 309-318(1969).
34. Chua, T. A., Silcodk, D. T., “The Practice of British Bus Operations in Planning Urban Bus Service,” Traffic Engineering and control, Vol. 23, pp. 66-70(1982).
35. Chua, T. A., “The Planning of Urban Bus Routes and Frequencies: A survey,”Transportation, Vol. 12, pp. 147-172(1984).
36. Chen, C. Y. and Kornhauser, A. L., “Decomposition of convex mulitcommodity network flow problem,” Report SOR-90-19, Dept. of Civil Engineering and Operations Research, Princeton University, Princeton, NJ(1990).
37. Corberan, A., Fernandez, E., Laguna M. and Marti, R., “Heuristic Solutions to the Problem of Routing School Buses with Multiple Objectives,” Journal of the Operational Research Society, Vol. 53, No. 4, pp. 427-435(2002).
38. Chakroborty, and P. and Dwivedi, T., “Optimal Route Network Design for Transit System Using Genetic Algorithms,” Engineering Optimization, Vol. 34, No. 1, pp.83-100(2002).
39. Cordeau, J. F. and Laporte, G., “A tabu search heuristic for the static multi-vehicle dial-a-ride problem,” Transportation Research Part B, Vol. 37, pp. 579-594 (2003).
40. Desrosiers, J., Dumas, Y., and Soumis, F., “A dynamic programming solution of the large-scale single vehicle dial-a-ride problem with time windows,”American Journal of Mathematical and Management Sciences, Vol. 6, pp.301-325 (1986).
41. Diana, M. and Dessouky, M.M., “A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows,” Transportation Research Part B, 38, pp.539–557(2004).
42. Equi, L., Gallo, G., Marziale, S. and Weintraub, A., “A combined transportation and scheduling problem,” European Journal of Operational Research, 97(1), pp.94-104(1997).
43. Fiedrich, F., Gehbauer, F. and Rickers, U., “Optimized Resource Allocation for Emergency Response after Earthquake Disasters,” Safety Science, Vol. 35, pp. 41-57 (2000).
44. Glover, F. and Laguna, M., Tabu search, Kluwer Academic Publishers, Norwell, MA (1997).
45. Hane, C. A., Barnhart, C., Johnson, E. L., Marsten, R., Nemhauser, G. L. and Sigismondi, G., “The Fleet Assignment Problem: Solving a Large-Scale Integer Program,” Mathematical Programming Study, Vol. 70, pp. 211-232 (1995).
46. Hart, S.M., “The modeling and solution of a class of dial-a-ride problems using sumulated annealing,” Control and Cybernetics, Vol. 25(1), pp. 1-27 (1996).
47. Hsu, C.I., Hung, S.F. and Li, H.C., “Vehicle routing problem with time-windows for perishable food delivery,” Journal of Food Engineering 80, pp.465–475(2007)
48. Ibaraki, T., Kubo, M., Masuda, T., Uno, T. and Yagiura, M., “Effective local search algorithms for the vehicle routing problem with general time windows constraint,” Transportaion Science, 39, pp.106-232(2005).
49. Jaw, J. J., Odoni, A. R., Psaraftis, H. N., and Wilson, N. H. M., “A heuristic algorithm for the multi-vehicle advance-request dial-a-ride problem with time windows,” Transportation Research Part B, Vol. 20, pp. 243-257 (1986).
50. J?rgensen, R. M., Larsen, J., and Bergvinsdottir, K. B., “Solving the dial-a-ride problem using genetic algorithms,” Journal of the Operational Research Society, Vol.58, pp.1321-1331 (2007).
51. Kennington, J. L. and Shalby, M., “An effective subgradient procedure for minimum cost multicommodity flow problem,” Management Science, Vol. 23, pp.994-1004(1977).
52. Levin, A., “Some fleet routing and scheduling problems for air transportation systems,” Flight Transportation Laboratory Report R68-5, Massachusetts Institute of Technology, MA(1969).
53. Levin, A., “Scheduling and fleet routing models for transportation systems,” Transportation Science, Vol. 5, pp. 232-255(1971).
54. Lee, B. C., “Routing problem with service choices, flight transportation laboratory,” Report R86-4, Massachusetts Institute of Technology, MA(1986).
55. Lamatsch, A., “An approach to vehicle scheduling with depot capacity constraints,” in Desrochers, M. and Rousseau, J. M.(eds.), Computer Aided Transit Scheduling, Lecture Notes in Economics and Mathematical System 386, Springer Verlag, Berlin, Heidelberg, pp. 181-195(1992).
56. Li, LYO and Z Fu, “The School Bus Routing Problem：A Case Study,” Journal of the Operational Research Society, Vol. 53, No. 5, pp. 552-558(2002).
57. Lai, M. F. and Lo, H. K., “Ferry service network design: Optimal fleet size, routing, and scheduling,” Transportation Research Part A, Vol. 38, pp. 305-328(2004).
58. Mesquita, M. and Paixao, J., “Multiple depot vehicle scheduling problem: a new heuristic based on quasi-assignment algorithm,” in Desrochers, M. and Rousseau, J. M.(eds.), Computer Aided Transit Scheduling, Lecture Notes in Economics and Mathematical System 386, Springer Verlag, Berlin, Heidelberg, pp. 181-195(1992).
59. Melachrinoudis, E., Ilhan, A. B., and Min, H., “A dial-a-ride problem for client transportation in a healthcare organization,” Computers and Operations Research, Vol. 34, pp. 742-759 (2007).
60. Psaraftis, H. N., “A dynamic programming approach to the single-vehicle, many-to-many immediate request dial-a-ride problem,” Transportation Science, Vol. 14, pp. 130-154 (1980).
61. Psaraftis, H. N., “An exact algorithm for the single-vehicle many-to-many dial-a-ride problem with time windows,” Transportation Science, Vol. 17, pp. 351-357 (1983).
62. Powell, W. B. and Ioannis, A. K., “Shipment routing algorithms with tree constraints,” Transportation Science, Vol. 26, pp. 230-245(1992).
63. Rego, C. and Roucairol, C., “Using tabu search for solving a dynamic multi-terminal truck dispatching problem,”European Journal of Operational Research, 83(2), pp.411- 429(1995).
64. Rekiek, B., Delchambre, A., and Saleh, H. A., “Handicapped person transportation: an application of the grouping genetic algorithm,”Engineering Application of Artificial Intelligence, Vol. 19, pp. 511-520 (2006).
65. Ropke, S., Cordeau, J. F., and Laporte, G., “Models and branch-and-cut algorithms for pickup and delivery problems with time windows,” Networks,Vol. 49, pp. 258-272 (2007).
66. Sexton, T., “The single vehicle many-to-many routing and scheduling problem,”Ph.D. dissertation, SUNY at Stony Brook (1979).
67. Solomon, M. M., “Vehicle routing and scheduling with time windows constraints: models and algorithms,” Ph.D. dissertation, Department of Decision Science, University of Pennsylvania, USA (1983).
68. Sato, T. and Ichii, K., “Optimization of post-earthquake restoration of lifeline networks using genetic algorithms,” Japan Society of Civil Engineers, No.537/I-35, pp.245-256 (1996).
69. Simpson, R.W., “A Review of Scheduling and Routing Model for Airline Scheduling,” IX AGIFORS Symposium, Broadway, England (1969).
70. Subramanian, R., Scheff, R. P., Quillinan, J. D., Wiper, D. S. and Marsten, R. E., “Coldstart: Fleet Assignment at Delta Air Lines,” Interface, Vol. 24, pp.104-120 (1994).
71. Teodorovic, D. and Guberinic, S., “Optimal dispatching strategy on an airline network after a schedule perturbation,” European Journal of Operational Research, Vol. 15, pp. 178-182(1984)
72. Teodorovic, D., Airline Operations Research, Gordon and Breach Science Publishers, New York(1988).
73. Tamura, T., Sugimoto, H. and Kamimae, T., “Application of Genetic Algorithms to Determining Priority of Urban Road Improvement,” Japan Society of Civil Engineers, No.482/IV-22, pp. 37-46 (in Japanese). (1994)
74. Toth, P. and Vigo, D., “Fast local search algorithms for the handicapped persons transportation problem,” In I. H. Osman and J. P. Kelly (Eds.), Meta-heuristics: Theory and Applications, Kluwer Academic Publishers, Boston, pp. 677-690 (1996).
75. Toth, P. and Vigo, D., “Heuristic algorithms for the handicapped persons transportation problem,” Transportation Science, Vol. 31, pp. 60-71 (1997).
76. Wong, K. I. and Bell, M. G. H., “Solution of the dial-a-ride problem with multi-dimensional capacity constraints,” International Transactions in Operational Research, Vol. 13, pp. 195-208 (2006).
77. Wang, D. Z. W. and Lo, H. K., “Multi-fleet ferry service network design with passenger preferences for differential services,” Transportation Research Part B, Vol. 42, pp. 798-822(2008).
78. Xiang, Z., Chu, C., and Chen, H., “A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints,” European Journal of Operational Research, Vol. 174, pp. 1117-1139 (2006).
79. Yan, S. and Young, H. F., “A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling,” Transportation Research, Vol. 30A, pp. 379-398 (1996).
80. Yan, S. and Chen, H. L., “A Scheduling Model and a Solution Algorithm for Inter-city Bus Carriers,” Transportation Research, Vol. 36A, pp. 805-825 (2002).
81. Yan, S., Chi, C. J. and Tang, C. H., “Inter-city Bus Routing and Timetable Setting under Stochastic Demands,” Transportation Research A 40, pp.572-586 (2006).
82. Yan, S. and Shih, Y. L., “A Time-Space Network Model for Work Team Scheduling after a Major Disaster,” Journal of the Chinese Institute of Engineers, Vol. 30, No. 1, pp. 63-75. (2006)
83. Yan, S. and Tang, C. H., “A heuristic approach for Airport Gate Assignments for Stochastic Flight Delays,” European Journal of Operational Research, Vol. 180, Iss. 2, pp. 547-567 (2007).
84. Yan, S. and Chen, C. H., “Coordinated flight scheduling models for allied airlines,” Transportation Research Part C, Vol. 15, pp. 246-264(2007).
85. Yan, S., Tang, C. H., and Fu, T.C., “An airline scheduling model and solution algorithms under stochastic demands,” European Journal of Operational Research, Vol. 190, pp. 22-39(2008).
86. Yan, S., Lai, W., and Chen, M., “Production scheduling and truck dispatching of ready mixed concrete,” Transportation Research, Part E, Vol. 44, Issue 1, pp. 164-179(2008).
87. Zhu, K., Tan, K.C. and Lee, L.H., “Heuristic methods for vehicle routing problem with time windows,” Artificial Intelligence in Engineering, 15(3), pp. 281-295(2000).

指導教授

顏上堯(Shang-Yao Yan)

審核日期

2010-7-16

推文