:::

詳目顯示

回上一頁
題名:汽車客運多場站車輛排程問題之研究
作者:林至康
作者(外文):Lin, Chih-Kang
校院名稱:國立交通大學
系所名稱:運輸科技與管理學系
指導教授:王晉元
學位類別:博士
出版日期:2009
主題關鍵詞:多場站車輛排程問題變數固定法啟發式解法Multiple-Depot Vehicle Scheduling ProblemVariable Fixing AlgorithmHeuristic
原始連結:連回原系統網址new window
相關次數:
  • 被引用次數被引用次數:期刊(0) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:0
  • 共同引用共同引用:0
  • 點閱點閱:0
近年來臺灣地區受到私人運具過度成長與使用影響,大眾運輸之經營環境逐漸惡化,因此在外部環境開闢客源不易之情形下,規劃良好營運車輛排程以降低客運業者的內部成本支出,則被視為另一項可行辦法。但過去文獻中所提出多場站車輛排程問題(Multiple-Depot Vehicle Scheduling Problem, MDVSP)數學模式多存在不符實務之假設與限制,其相關假設與限制為:(1)各場站所配置營運車輛數目上限為已知;(2)相關營運成本被簡化為單一型式目標函數;(3)車輛空駛之處理並未提供足夠彈性;(4)勤務中車輛營運路線之轉換次數並未處理等四項假設與限制,上述假設與限制雖使得MDVSP於問題定式與模式求解較為容易,卻限制此類模式於臺灣地區汽車客運實務應用上之實用性,因此如何增加客運業者競爭力,並解決上述假設與限制對於處理實務問題時所造成之困難,產製出有效率之車輛排程勤務規劃,實為一大挑戰。
有鑑於此,本研究以具有多場站營運特性之汽車客運業者為研究對象,改善過去文獻中數學模式所建立假設與限制,構建符合臺灣地區汽車客運營運現況之多場站車輛排程模式,並依據所提出多場站車輛排程模式之特性,提出一啟發式解法—變數固定法(variable fixing heuristic)進行模式求解之工作。本研究並選取具有多場站多路線營運特性之金門縣公共車船管理處為測試對象,其測試結果顯示,本研究所構建之多場站車輛排程模式不僅可滿足臺灣地區汽車客運業者實際需求,而所提出之變數固定啟發式解法於處理較大型之車輛排程問題時,亦極具效率,顯示本研究之模式構建、參數特性證明、求解流程與測試結果等研究成果,具有提供國內汽車客運業者與學術界之參考價值。
The multiple-depot vehicle scheduling problem (MDVSP) address the work of assigning vehicle to serve a given set of time trips with the consideration of certain requirements representing the market rules. Extensive studies in the literature address the MDVSP, but because of the complexity of the problem, the findings made by those researches are still not enough to represent real world situations in Taiwan. Formulation for the MDVSP typically contains the following assumptions: (1) the size of fleet or maximum number of available vehicles at each depot is known already, (2) all trip serving costs are usually simplified as a single term in the objective function, which fails to reflect public transit operator concerns, (3) the applied deadheading strategy is static less flexibility, (4) without discussing of the difference of route change frequency in the problem. This study presents a new MDVSP model to address the above issues. A variable fixing heuristic algorithm based on the divide-and-conquer technique is also proposed to solve the MDVSP effectively. Computational tests are performed on the Kinmen Bus Administration (KBA) and results demonstrate that the proposed new model and the greedy heuristic algorithm for the MDVSP are effective in solving real world problems.
[1] Baita, F., Pesenti, R., Ukovich, W. and Favaretto, D., “A comparison of different solution approaches to the vehicle scheduling problem in a practical case”, Computer & Operations Research, Vol. 27, 2000, pp. 1249-1269.new window
[2] Ball, M., “A Comparison of Relaxations and Heuristic for Certain Crew and Vehicle Scheduling Problems”, Presented at National ORSA/TIMS Meeting, Washington, D. C., 1980.
[3] Ball, M. O., Magnanti, T. L., Monma, C. L. and Nemhauser, G. L., “Time Constrained Routing and Scheduling”, Handbooks in Operation Research and Management Sciences Volume 8 : Network Routing, 1995.
[4] Beasley, J. E. and Cao, B., “A Tree Search Algorithm for the Crew Scheduling Problem”, European Journal of Operational Research, Vol. 94, No. 3, 1996, pp. 517-526.
[5] Bertossi, A. A., Carraresi, P. and Gallo, G., “On Some Matching Problems Arising in Vehicle Scheduling Models”, Networks, Vol. 17, 1987, pp. 271-281.
[6] Bodin, L. and Golden, B. L., “Classification in Vehicle Routing and Scheduling”, Networks, Vol. 11, 1981, pp. 97-108.
[7] Bodin, L., Golden B., Assad A. and Gall, M., “Routing and Scheduling of Vehicles and Crews – the State of the Art”, Computers & Operations Research, Vol. 10, 1983, pp. 63-211.
[8] Carpaneto, G., Dell’Amico, M., Fischetti, M. and Toth, P., “A branch and bound algorithm for the multiple depot vehicle scheduling problem”, Network, Vol. 19, 1989, pp. 531-548.
[9] Carraresi, P. and Gallo, G., “Network Models for Vehicle and Crew Scheduling”, European Journal of Operational Research, Vol. 16, No. 3, 1983, pp. 139-151.
[10] Daduna, J. R. and Paixão, J., “Vehicle scheduling for public mass transit – an overview”, Computer-aided transit scheduling, Springer, Berlin Heidelberg New York, 1995, pp.76-90.
[11] Dantzig, G. B. and Fulkerson, D. R., “Minimizing the Number of Tankers to Meet a Fixed Schedule”, Naval Res. Log. Quart., Vol. 1, 1954, pp. 217-222.new window
[12] Forbes, M. A., Holt, J. N. and Watts, A. M., “An exact algorithm for multiple depot bus scheduling”, European Journal of Operational Research, Vol. 72, 1994, pp. 115-124.
[13] Ford, L. R. and Fulkerson, D. R., Flows in Networks, Princeton University Press, N. J., 1962.
[14] Freling, R., Huisman, D. and Wagelmans, A. P. M., “Models and algorithms for integration of vehicle and crew scheduling”, Journal of Scheduling 6, 2003, pp. 63-85.
[15] Gerard, S., Linear and Integer Programming - Theory and Practice, Second Edition, Marcel Dekker, Inc., 2002.
[16] Gintner, V., Kliewer, N. and Suhl, L., “Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice”, OR Spectrum 27, 2005, pp.507-523.
[17] Haghani, A. and Banihashemi, M., “Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints”, Transportation Research Part A 36, 2002, pp. 309-333.
[18] Haghani, A., Banihashemi, M. and Chiang, K. H., “A comparative analysis of bus transit vehicle scheduling models”, Transportation Research Part B 37, 2003, pp.301-322.
[19] Heurgon, H., “Preparing duty roster for bus routes by computer”, in Preprint Workshop on Automated Technique for Scheduling of Vehicle Operations for Urban Public Transportation Service, 1975.
[20] Hillier, F. S. and Lieberman, G. J., Introduction to Operation Research 8e, McGraw-Hill, New York, 2005.
[21] Hoffman, K. L. and Padberg, M., “Solving airline crew scheduling problem by branch-and-cut”, Management Science, Vol. 39, No. 6, 1993, pp. 657-682.
[22] Katta, G. M., Linear and Combinatorial Programming, Wiley, New York, 1976.
[23] Kliewer, N., Mellouli, T. and Suhl, L., “A time-space network based exact optimization model for multi-depot bus scheduling”, European Journal of Operational Research, Vol. 175, 2006, pp. 1616-1627.
[24] Lamatsch, A., “An approach to vehicle scheduling with depot capacity constraint”, In: Proceedings of the Fifth International Workshop on Computer-aided Scheduling of Public Transit, Montreal, Canada, 1990.
[25] Lenstra, J. K. and Rinnooy Kan, A.H.G., “Complexity of Vehicle Routing and Scheduling Problem”, Networks, Vol. 11, 1981, pp. 221-228.
[26] Mesquita, M. and Paixão, J., “Multiple depot vehicle scheduling problem: a new heuristic based on quasi-assignment algorithm”, In: Proceedings of the Fifth International Workshop on Computer-aided Scheduling of Public Transit, Montreal, Canada, 1990.
[27] Neapolitan, R., and Naimipour, K., 2004, Foundations of Algorithms-Using C++ Pseudocode, 3rd ed, Jones and Bartlett Publishers, Massachusetts, USA.
[28] Pepin, A., Desaulniers, G., Hertz, A., and Huisman, D., 2006, “Comparison of Heuristic Approaches for the Multiple Depot Vehicle Scheduling Problem”, Odysseus 2006, Altea, Spain (23-26 mai).
[29] Rayward-Smith, V. J., Osman, I. H., Reeves, C. R. and Smith, G. D., Modern Heuristic Search Methods, John Wiley and Sons, New York, 1996.
[30] Ribeiro, C. and Soumis, F., “A Column Generation Approach to the Multiple Depot Vehicle Scheduling Problem”, Operations Research, Vol. 42, 1994, pp. 41-52.
[31] Shepardson, F. and Marsten, R. E., “A lagrangean relaxation algorithm for the two duty period scheduling problem”, Management Science 26, 1980, pp. 274-281.
[32] Wang, J. Y. and Lin, C. K., “A Network Model for the Multiple Depot Vehicle Scheduling Problems of Public Transit”, In: Proceedings of 86th Transportation Research Board Annual Meeting, 2007.
[33] Yan, S., and Tu, Y.P., “A Network Model for Airline Cabin Crew Scheduling”, European Journal of Operational Research, Vol. 140, No. 3, 2002, pp. 531-540.
[34] 王晉元、林至康,「固定時刻表下之一般性車輛排程模式研究」,運輸計畫季刊,第三十五卷,第一期,頁107-130,民國95年。new window
[35] 王晉元、林至康等,大眾運輸車隊管理系統核心模組之規劃與建置,交通部運輸研究所,民國90年7月。
[36] 杜宇平,「空服員排班網路模式之研究」,國立中央大學土木工程學系博士論文,民國89年。
[37] 交通部運輸研究所,運輸經濟資料彙編第20期,民國95年。
[38] 交通部運輸研究所,運輸營運手冊,民國75年。
[39] 卓訓榮、王晉元、蘇昭銘、林至康,大眾運輸車隊管理系統核心模組之推廣應用,交通部科技顧問室,民國91年1月。
[40] 夏萬春,「禁制搜尋法於車輛排班之探討」,國立高雄第一科技大學機械與自動化工程學系碩士論文,民國90年。
[41] 游文松,「公路客運人員與車輛排班之研究」,中華大學科系管理研究所碩士論文,民國93年。new window
[42] 黃俐嘉,「公車路網績效評估模式之研究」,國立台灣大學土木工程學系碩士論文,民國86年。
[43] 蔡文昉,「大眾運輸排班系統之研究」,國立交通大學運輸工程與管理學系碩士論文,民國90年。
[44] 廖椿煜,「公路客運車輛排班調度制度之研究—以臺灣汽車客運公司為例」,國立交通大學交通運輸研究所碩士論文,民國74年。new window
[45] 盧宗成,「捷運司機員排班問題之研究—以台北捷運公司為例」, 國立交通大學運輸工程與管理學系碩士論文,民國88年。
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top
QR Code
QRCODE