Title

短期道路養護工作隊排程規劃之研究

Translated Titles

The Short-term Working Team Scheduling Models for Road Maintenance

Authors

張家維

Key Words

道路養護 ; 工作隊排程 ; 隨機性旅行時間 ; 隨機性修護時間 ; 模擬 ; simulation ; stochastic maintenance times ; stochastic travel times ; road maintenance ; work team scheduling

PublicationName

中央大學土木工程學系學位論文

Volume or Term/Year and Month of Publication

2006年

Academic Degree Category

碩士

Advisor

顏上堯

Content Language

繁體中文

Chinese Abstract

良好的道路養護工作隊排程規劃,可以提升養護效率,並降低成本。目前國內養護廠商大多依照以往經驗,估算平均的旅行時間與修護時間,以進行工作隊排程規劃。此作法忽略了實務營運上,旅行時間與修護時間之隨機特性,若隨機性擾動過大時,則可能使原規劃的結果失去其優越性,亦即最佳化工作隊排程結果可能不為實際最佳排程。此等最佳化道路養護工作隊排程在營運中受到隨機因素擾動的影響,在過去未曾發現有文獻進行探討。有鑑於此,為規劃較符合實務情況的工作隊排程,本研究考量實際營運時,旅行時間與修護時間之隨機變動狀況及實務營運的相關限制,以養護廠商總未養護時間最小化為目標,構建一確定性與一隨機性工作隊排程模式,幫助廠商在有限的養護資源下作出最佳的工作隊調派決策,並提高養護作業效率。 本研究參考國內實際的養護工程作業方式,利用時空網路流動技巧,以系統最佳化的觀點,構建一確定性道路養護工作隊排程模式。之後,進ㄧ步修正確定性模式中固定之旅行時間與修護時間為隨機變數,構建一隨機性道路養護工作隊排程模式。求解上,本研究以CPLEX數學規劃軟體直接求解模式。另外,為評估隨機狀況下的作業績效,本研究並將發展一模擬評估方法,以比較實務排程、確定性與隨機性排程規劃的結果於實際營運應用之差異。最後,為測試本研究模式與評估方法的實用績效,本研究以某縣市政府所負責之養護範圍為例,利用C程式語言結合數學規劃軟體CPLEX進行實例測試與分析,進而提出結論與建議。

English Abstract

A good work team schedule for road maintenance can help improve the effectiveness of the road maintenance and thus reduce the operating costs. In current practice the work team schedule is typically designed by the staff’s experience, in accordance with the projected (or average) fleet travel times and maintenance times, meaning that stochastic disturbances arising from variations in vehicle travel times and maintenance times in actual operations are neglected. In the worst case scenario, where vehicle travel times and maintenance times fluctuate wildly during daily operations, the planned work team schedule could be disturbed enough to lose its optimality. Since there has been no research on work team scheduling problems that can account for stochastic fleet travel times and maintenance times, in this research stochastic disturbances of daily vehicle travel times and maintenance times that occur in actual operations are considered from the basis of the carrier’s perspective. We try to develop a deterministic and a stochastic work team scheduling models, with the objective of minimizing the total operating time (including total vehicle travel time and total maintenance time). The models are expected to be useful planning tools for carriers to decide on their optimal work team schedules in their operations. We will employ network flow techniques, with a systemic optimization perspective, to construct a deterministic work team scheduling model. Then a stochastic work team scheduling model is developed by modifying the fixed vehicle travel time and maintenance time parameters in the deterministic work team scheduling model. We use the mathematical programming solver, CPLEX, to directly solve the scheduling model. To evaluate the models and the solution algorithms under stochastic vehicle travel times and maintenance times in actual operations, we will also develop a simulation-based evaluation method. Then, we will perform a case study on personal computers, using real data of a local government. Finally, conclusions and suggestions will be given.

Topic Category 工學院 > 土木工程學系
工程學 > 土木與建築工程
Reference
  1. 1.王中允、賀寶福,「災害緊急救難路網重建與設計之研究」,中華民國運輸學會第十八屆論文研討會論文集,新竹(2003)。
    連結:
  2. 6.邱明琦,陳春益,林佐鼎,「海運貨櫃排程模式之研究」,運輸計劃季刊,第三十一卷,第三期,第495-522頁(2002)。
    連結:
  3. 7.李志華,「基因演算法於震災路網搶修排程問題之研究」,碩士論文,國立成功大學交通管理研究所(2003)。
    連結:
  4. 19.陳春益,邱明琦,「貨櫃航線網路設計模式之研究」,運輸計劃季刊,第三十一卷,第二期,第267-298頁(2002)。
    連結:
  5. 21.陳俊豪,「因應臨時事件變動租用數機場共用櫃檯即時指派之研究」中央大學土木工程學研究所,(2005)。
    連結:
  6. 30.顏上堯、翁綵穗,「季節轉換間緩衝期飛航排程之研究」,運輸計劃季刊,第三十卷,第四期,第891- 922頁(2001)。
    連結:
  7. 32.顏上堯、杜宇平、陳怡妃,「因應臨時事件機場共用櫃檯即時指派之研究」,「民航學會/航太學會/燃燒學會」學術聯合會議研討會論文集(2002)。
    連結:
  8. 33.顏上堯、羅智騰,「因應預期性航具維修之系統性飛航排程」,中國土木水利工程學刊,第八卷,第三期,第447-456頁(1996)。
    連結:
  9. 34.顏上堯、齊志仁、湯慶輝 (2005),「隨機需求下多目標長途客運排程模式之研究」,運輸計畫季刊,第 34卷第 1 期,第93-118頁。
    連結:
  10. 36.Abara, J., “Applying Integer Linear Programming to the Fleet Assignment Problem,” Interfaces, Vol. 19, pp. 20-28 (1989).
    連結:
  11. 40.Clarke, L. W., Hane, C. A., Johnson, E. L. and Nemhauser, G. L., “Maintenance and Crew Considerations in Fleet Assignment, ” Transportation Science, Vol.30, pp. 249-260 (1996).
    連結:
  12. 42.Fiedrich, F., Gehbauer, F. and Rickers, U., “Optimized Resource Allocation for Emergency Response after Earthquake Disasters,” Safety Science, Vol. 35, pp. 41-57 (2000).
    連結:
  13. 43.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).
    連結:
  14. 44.Kenyou, A.S. and Morton, D.P., “Stochastic Vehicle Routing with Random Travel Times,” Transportation Science, Vol. 37, No. 1, pp. 69-82 (2003).
    連結:
  15. 45.Levin, A., “Some Fleet Routing and Scheduling Problems for Air Transportation Systems,” Flight Transportation Laboratory Report R68-5, Massachusetts Institute of Technology, MA (1969).
    連結:
  16. 47.Mulvey, J.M, Ruszczynski, A. (1995), “A New Scenario Decomposition Method for Large-Scale Stochastic Optimization,” Operations Research, Vol. 43, No. 3, pp. 477–490.
    連結:
  17. 48.Mulvery, J.M., Vanderbei, R.J., Zenios, S.A. (1995), “Robust Optimization of Large-Scale Systems,” Operations Research, Vol. 43, No. 2, pp. 254–281.
    連結:
  18. 49.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) (in Japanese).
    連結:
  19. 51.Stancu Minasian,I.M., “Stochastic Programming with Multiple Objective Functions,” Editura Academiei, Bucharest, (1984).
    連結:
  20. 52.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).
    連結:
  21. 53.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 (1994) (in Japanese).
    連結:
  22. 54.Thengvall, B.G., Bard, J.F. and Yu, G., “Balancing User Preferences for Aircraft Schedule Recovery During Airline Irregular Operations,” IIE Transactions on Operations Engineering, Vol. 32, pp.181-193 (2000).
    連結:
  23. 55.Thengvall, B.G., Yu, G. and Bard, J.F, “Multiple Fleet Aircraft Schedule Recovery Following Hub Closure,” Transportation Research, Vol.35A, pp.289-308 (2001).
    連結:
  24. 56.Yan, S. and Yang, D. H., “A Decision Support Framework for Handling Schedule Perturbation”, Transportation Research, Vol. 30B, pp. 405-419 (1996).
    連結:
  25. 57.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).
    連結:
  26. 58.Yan, S. and Lin,C., “Airline Scheduling for the Temporary Closure of Airports,” Transportation Science, Vol.31, pp. 72-82 (1997).
    連結:
  27. 59.Yan, S. and Tu, Y., “Multi-Fleet Routing and Multi-Stop Flight Scheduling for Schedule Perturbation,” European Journal of Operational Research, Vol.103, pp. 155-169 (1997).
    連結:
  28. 60.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).
    連結:
  29. 61.Yan, S. and Chang, J. C., “Airline Cockpit Crew Scheduling,” European Journal of Operational Research, Vol. 136, No. 3, pp. 501-511 (2002).
    連結:
  30. 62.Yan, Shangyao., Chin-Jen Chi, and Ching-Hui Tang, “Inter-city Bus Routing and Timetable Setting under Stochastic Demands,” Transportation Research A 40, pp.572-586(2006).
    連結:
  31. 63.Yan, S., D. H. Juang, C. R. Chen and W. S. Lai, “Global and Local Search Algorithms for Concave Cost Transshipment Problems,” Journal of Global Optimization, Vol. 33, No. 1, pp. 123 - 156 (2005).
    連結:
  32. 64.Yan, S., C. H. Tang and C. N. Shieh, “A Simulation Framework for Evaluating Airline Temporary Schedule Adjustments Following Incidents,” Transportation Planning and Technology, Vol. 28, No. 3, pp. 189-211 (2005).
    連結:
  33. 65.Yan, S. and Shih, Y. L. “A Time-Space Network Model for Work Team Scheduling after a Major Disaster”, submitted to Journal of the Chinese Institute of Engineers (accepted) (2006).
    連結:
  34. 66.Yan, S. and Chang, C.M. “A network model for gate assignment, Journal of Advanced Transportation 32,” pp. 176-189(1998).
    連結:
  35. 67.Yan, Shangyao and Ching-Hui Tang, “A integrated Framework for Airport Gate Assignments for Stochastic Flight Delays,” European Journal of Operational Research (accepted) (2006).
    連結:
  36. 2.王擴為,「公路搶修決策支援系統中指派模式之研究」,碩士論文,國立交通大學資訊管理研究所(1993)。
  37. 3.呂英志,「即時資訊下車輛路線問題之研究」,碩士論文,逢甲大學交通工程與管理研究所(2002)。
  38. 4.呂錦隆,「國內航空客運旅客選擇決策之實證研究」,博士論文,國立成功大學交通管理科學研究所 (1999)。
  39. 5.吳心琪,「震災後工程搶修作業排程之研究」,碩士論文,國立交通大學交通運輸研究所(1996)。
  40. 8.李銘杰,「變動需求下飛航排程暨班次表建立之研究」,碩士論文,國立中央大學土木工程研究所(2002)。
  41. 9.李綺容,「航空貨運網路於需求不確定下之規劃」,碩士論文,國立嘉義大學運輸與物流工程研究所(2004)。
  42. 10.林益生,「隨機環境下多商品、多車種派車問題之研究」,碩士論文,中原大學工業工程研究所(1998)。
  43. 11.施佑林,「災後工程搶修作業暨賑災物流排程之研究」,碩士論文,國立中央大學土木工程研究所(2004)。
  44. 12.苑鳳萍,「客運車輛擾動下調度系統之研究」,碩士論文,國立交通大學運輸工程與管理研究所(2001)。
  45. 13.唐存寬,「在顧客需求為隨機之假設下多種貨品儲運分配系統設計」,碩士論文,國防管理學院資源管理研究所(1999)。
  46. 14.陳文德,「台灣地區道路管理維護精進策略之研究」,碩士論文,國立中央大學土木工程研究所(2005)。
  47. 15.陳永林,「HDM-4 運用於國內高速公路養護管理之研究」,碩士論文,國立中央大學土木工程研究所(2003)。
  48. 16.陳妙珍、顏上堯、張珮璇(2000),「航空公司資產與負債管理模式之建立」,第四屆海峽兩岸會計與管理學術研討會論文集,武漢。
  49. 17.陳茂南,「啟動公路養護新紀元」,台灣地區運輸工程發展與管理研討會論文集,第1-13頁(2004)。
  50. 18.陳郁文,「模糊多目標組合規劃基因演算法應用於提升運輸系統災後應變效率之研究」,博士論文,國立交通大學交通運輸研究所(1999)。
  51. 20.陳軍凱,「隨機需求下航空貨物收貨人員人力供給暨班次表設計規劃之研究」中央大學土木工程學研究所,碩士論文(2005)。
  52. 22.張立偉,「災後工程緊急搶修作業排程之研究」,碩士論文,淡江大學運輸管理學系運輸科學碩士班(2001)。
  53. 23.游俊雄、丁國樑,「需求反應旅次運載模擬模式應用於捷運營運班表之評估」,運輸計劃季刊,第二十七卷,第三期,頁489-508 (1998)。
  54. 24.傅介元,「市區道路鋪面維護管理之研究(以台北市主次要道路為例)」,碩士論文,國立中央大學土木工程研究所(2003)。
  55. 25.傅曾志,「隨機性需求下飛航排程模式與評估方法之研究」,碩士論文,國立中央大學土木工程研究所(2003)。
  56. 26.劉方旗,「市區公車排班與即時機動調度之研究--以新竹客運為例」,碩士論文,國立交通大學運輸科技與管理研究所(1998)。
  57. 27.廖國行,「公路養護及管理績效(養路比賽)之研究」,碩士論文,國立中央大學土木工程研究所(2000)。
  58. 28.顏應明,「路網疏散時間敏感度分析及災後救援路線之研究」,碩士論文,國立交通大學交通運輸工程研究所(1987)。
  59. 29.顏上堯、何淑萍,「飛航排程暨班次表之建立」,運輸計劃季刊,第二十三卷,第一期,第73-90頁(1994)。
  60. 31.顏上堯、曾志煌,「單機種機隊排程與班次整合之研究」,運輸計劃季刊,第二十八卷,第四期,第635-658頁(1999)。
  61. 35.羅敏綺,「隨機需求下捷運系統營運模擬模式之構建-以台北市木柵線為例」,碩士論文,國立成功大學交通管理科學研究所(1998)。
  62. 37.Agin, N. and Cullen, D., “An Algorithm for Transportation Routing and Vehicle Loading,” in Geisler, M. (Ed.), Logistics, pp.1-20, North Holland, Amsterdam (1975).
  63. 38.Arimura, M., Tamura, T. and Saito. K. “Application of Genetic Algorithms model for Road Investment of Restoration Planning,” Proceedings of the Eastern Asia Society for Transportation Studies, Vol. 2, pp.55-69 (1999).
  64. 39.Birge, J.R., “Solution Methods for Stochastic Dynamic Linear Programs,” Technical Report SOL, pp. 29-80 (1980).
  65. 41.Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M.M. and Soumis, F., “Daily Aircraft Routing and Scheduling”, Management Science, Vol. 43, pp. 841-855 (1997).
  66. 46.List, G.F., Wood, B., Nozick, L.K., Turnquist, M.A., Jones, D.A., Kjeldgaard, E.A. and Lawton, C.R., “Robust Optimization for Fleet Planning under Uncertainty,” Transportation Research, part E, Vol. 39, pp. 209-227 (2003).
  67. 50.Simpson, R.W., “A Review of Scheduling and Routing Model for Airline Scheduling,” IX AGIFORS Symposium, Broadway, England (1969).
Times Cited
  1. 李德全(2009)。隨機作業時間之道路災害緊急搶修排程模式與演算法探討。中原大學土木工程研究所學位論文。2009。1-92。 
  2. 魏光譽(2008)。縣市政府提升道路挖掘埋設維生管線管理成效之研究-以桃園縣為例。中央大學土木工程學系碩士在職專班學位論文。2008。1-109。
  3. 洪羽佑(2008)。災後工程搶修物料補給排程之研究。中央大學土木工程學系學位論文。2008。1-75。
  4. 李子寧(2013)。道路管線施工品質管理機制之研究。臺北科技大學土木與防災研究所學位論文。2013。1-113。