Title

因應拌合廠臨時故障下即時性拌合車派遣規劃之研究

Translated Titles

Real Time RMC Truck Dispatching When RMC Mixer Is Breakdown Unexpectedly

Authors

劉映岑

Key Words

預拌混凝土 ; 即時性規劃 ; 時窗限制 ; 含額外限制式網路流動問題 ; 時空網路 ; 拌合車 ; 排程 ; Real-time dispatching ; Ready mixed concrete ; Network flow problem with side constraints ; Time window ; Time-space network ; RMC truck ; Scheduling

PublicationName

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

Volume or Term/Year and Month of Publication

2008年

Academic Degree Category

碩士

Advisor

顏上堯

Content Language

繁體中文

Chinese Abstract

近年來,預拌混凝土已成為公共建設或私人建築之主要建材之一,而其生產方式係於預拌混凝土廠經由電腦化作業後,利用預拌混凝土拌合車裝載運送到工地卸料與澆置。值得一提的是,當預拌混凝土廠發生機具臨時故障時,會因為無法出貨導致預拌混凝土廠無法有效供應預拌混凝土需求,對於預拌混凝土廠與工地雙方的成本有一定程度的影響,然而業者目前對於預拌混凝土廠故障時的因應方式,是以人工方式調整原先的拌合車派遣規劃,未以系統最佳化的觀點調整排班,容易導致資源浪費及降低服務水準的情形。緣此,本研究針對拌合廠臨時故障時的拌合車派遣規劃問題進行探討,利用該廠商在該地區的現有資源進行支援供應,基於預拌混凝土廠商的立場,考量拌合廠與工地之整體性營運成本,並將產業營運特性納入考量,系統最佳化的觀點建構二個即時性拌合車派遣規劃模式。本研究首先構建系統中使用單一車種之即時性單車種拌合車派遣規劃模式,再進一步以此模式為基礎,構建使用不同載運量拌合車之即時性多車種拌合車派遣規劃模式,以幫助業者在拌合廠發生臨時故障時,以更有效並且更具彈性的資源使用方式調整拌合車派遣規劃,以期降低損失並維持服務品質。 本研究利用時空網路流動技巧構建即時性單車種與多車種拌合車派遣規劃模式,以定式車輛在時空中的流動情況,此二模式可定式為含額外限制之混合整數規劃網路流動問題,係屬NP-hard問題。在求解方法上,利用C++程式語言配合數學規劃套裝軟體CPLEX求解模式,並且為求有效地求解,本研究發展一以問題分解策略為基礎之啟發解法。最後,為測試模式與啟發解法之實用性,本研究以國內北區一家預拌混凝土廠商之實際營運資料進行實例測試與分析,結果顯示本研究所發展之模式與啟發解法,可有效率地求解並得到良好的預拌混凝土生產與車輛派遣規劃。

English Abstract

In recent years, ready mixed concrete (RMC) has became one of the most primary construction material of buildings and other public infrastructures. It is produced by automatic process and computer controlled process, and then delivered by RMC trucks. However, when RMC mixer is breakdown unexpectedly, RMC batch might not satisfy the demand of construction sites. Consequently, the operation cost of both RMC batch and construction sides would be increased. To deal with this situation, the dispatcher would manually adjust the original production scheduling and truck dispatching by experienced staff. It might lead to a result of wasting resources and decreasing the quality of service. Therefore, in this research, we aimed at dealing with the situation when RMC mixer is breakdown unexpectedly. To support the supplying, RMC is supplied by using all the applicable resources of the company in the specific area. By angle of owners of RMC Companies, we considered the operation costs of both RMC batch and construction sides. Besides, we also considered the operation characteristics of this industry. In this research, we systematically constructed two models. We first constructed the real time RMC truck dispatching with single type of trucks. Further, based on the first model, we constructed the real time RMC truck dispatching with various types of trucks. These two models are expected to be useful planning tools for helping dispatchers adjust truck dispatching more effectively, and thus to minimize loss of system profits and to maintain their quality of service. We applied time-space network techniques with the system optimization perspective to construct two real-time truck dispatching models. These two models are formulated as mixed integer network flow problems with side constraints, which are characterized as NP-hard. To solve realistic problems efficiently, we developed a solution method, which incorporates a mathematical programming solver CPLEX. To solve the problems more efficiently, we used problem decomposition techniques to develop the heuristic to solve the problems. In order to test the models and solution algorithms in actual operations, we performed a case study based on the real operating data from an RMC firm in Taiwan. The test results show that the models and the solution algorithm would be better then actual operations.

Topic Category 工學院 > 土木工程學系
工程學 > 土木與建築工程
Reference
  1. 邱明琦,陳春益,林佐鼎,「海運貨櫃排程模式之研究」,運輸計劃季刊,第三十一卷,第三期,第495-522頁 (2002)。
    連結:
  2. 吳權哲,「都會區計程車共乘配對模式暨求解演算法之研究」,碩士論文,國立中央大學土木工程學系 (2007)。
    連結:
  3. 陳春益,邱明琦,「貨櫃航線網路設計模式之研究」,運輸計劃季刊,第三十一卷,第二期,第267-298頁(2002)。
    連結:
  4. 陳毓卿,「因應臨時事件航機停機修護排程調整最佳化之研究」,碩士論文,國立中央大學土木工程學系(2007)。
    連結:
  5. 曹智翔,「短期需求擾動下動態醫療物資輸配送之研究」,碩士論文,國立中央大學土木工程學系(2007)。
    連結:
  6. 廖建韋,「醫療物資訂購及配送排程規劃之研究」,碩士論文,國立中央大學土木工程學系(2007)。
    連結:
  7. 顏上堯、羅智騰,「因應預期性航具維修之系統性飛航排程」,中國土木水利工程學刊,第八卷,第三期,第447-456頁 (1996)。
    連結:
  8. 顏上堯、翁綵穗,「季節轉換間緩衝期飛航排程之研究」,運輸計劃季刊,第三十卷,第四期,第891-922頁 (2001)。
    連結:
  9. 顏上堯、杜宇平、陳怡妃,「因應臨時事件機場共用櫃檯即時指派之研究」,運輸計劃季刊,第三十三卷,第一期,頁59-頁81 (2004)。
    連結:
  10. 蘇志峰,「具時窗限制之多場站車輛路線問題之研究」,碩士論文,國立成功大學工業管理科學系 (2001)。
    連結:
  11. Abara, J., “Applying Integer Linear Programming to the Fleet Assignment Problem,” Interfaces, 19(4), 20-28 (1989).
    連結:
  12. Bent, R. W. and Hentenryck P. V., “ Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers,” Operations Research, 52(6), 977-987 (2003).
    連結:
  13. Clarke, L. W., Hane, C. A., Johnson, E. L. and Nemhauser, G. L., “Maintenance and Crew Considerations in Fleet Assignment, ” Transportation Science, 30(3), 249-260 (1996).
    連結:
  14. Cheng, T.M. and Feng, C.W., “An Effective Simulation Mechanism for Construction Operations,” Automation in Construction, 12(3), 227-244 (2003).
    連結:
  15. Deb, K. and Chakroborty. P., “Time Scheduling of Transit Systems with Transfer Considerations Using Genetic Algorithms,” Evolutionary Computing, 6(1), 1-24 (1998).
    連結:
  16. Feng, C.W. and Wu, H.T., “Integrating fmGA and CYCLONE to Optimize the Schedule of Dispatching RMC Trucks,” Automation in Construction, 15, 186-199 (2006).
    連結:
  17. 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, 70, 211-232 (1995).
    連結:
  18. Ibaraki, T., Kubo, M., Masuda, T., Uno, T. and Yagiura, M., “Effective Local Search Algorithms for the Vehicle Routing Problem with General Time Windows,” working paper, Department of Applied Mathematics and Physics, Kyoto University, Japan (2001).
    連結:
  19. Jarrah, A.I., Yu, G., Krishnamurthy, N. and Rakshit, A.,”A Decision Support Framework for Airline Flight Cancellations and Delays,” Transportation Science, 27(3), 266-280 (1993).
    連結:
  20. Kwon, O. K., Martland, C. D. and Sussman, J. M., “Routing and Scheduling Temporal and Heterogeneous Freight Car Traffic on Rail Networks,” Transportation Research, Part E , 34(2), 101-115 (1998).
    連結:
  21. Lu, M., Anson, M., Tang, S.L. and Ying, Y.C., “HKCONSIM: A Practical Simulation Solution to Planning Concrete Plant Operations in Hong Kong,” Journal of Construction Engineering and Management, 129(5), 547-554 (2003).
    連結:
  22. Matsatsinis, N.F., “Towards a Decision Support System for the Ready Concrete Distribution System: A Case of a Greek Company,” European Journal of Operational Research, 152(2), 487-499 (2004).
    連結:
  23. Rego, C. and Roucairol, C., “Using Tabu Search for Solving a Dynamic Multi-terminal Truck Dispatching Problem,” European Journal of Operational Research, 83(2), 411- 429, (1995).
    連結:
  24. Rochat, Y. and Taillard, E. D., “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing,” Journal of Heuristics, 1(1), 147-167 (1995).
    連結:
  25. Subramanian, R., Scheff, R. P., Quillinan, J. D., Wiper, D. S. and Marsten, R. E., “Coldstart: Fleet Assignment at Delta Air Lines,” Interface, 24(1), 104-120 (1994).
    連結:
  26. 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, 32(3), 181-193 (2000).
    連結:
  27. Thengvall, B.G., Yu, G. and Bard, J. F., “Multiple Fleet Aircraft Schedule Recovery Following Hub Closure,” Transportation Research, Part A, 35(4), 289-308 (2001).
    連結:
  28. Yan, S., Chen, S.C. and Chen, C.H., “Air Cargo Fleet Routing and Timetable Setting with Multiple On-Time Demands,” Transportation Research, Part E, 42(5), 409-430 (2006a).
    連結:
  29. Yan, S. and Chen, C.H., “Coordinated Flight Scheduling Models for Allied Airlines,” Transportation Research, Part C, 15(4), 246-264 (2007).
    連結:
  30. Yan, S. and Chen, H.L., “A Scheduling Model and a Solution Algorithm for Inter-city Bus Carriers,” Transportation Research, Part A, 36(9), 805-825 (2002).
    連結:
  31. Yan, S., Chi, C.J. and Tang, C.H. “Inter-city Bus Routing and Timetable Setting under Stochastic Demands,” Transportation Research, Part A, 40(7), 572-586 (2006b).
    連結:
  32. Yan, S., Lai, C.H. and Chen, C.H., “A Short-Term Flight Scheduling Model for International Express Package Delivery,” Journal of Air Transport Management, 11(6) , 368-374 (2005).
    連結:
  33. Yan, S. and Lai, W.S., “An Optimal Scheduling Model for Ready Mixed Concrete Supply with Overtime Considerations,” Automation in Construction, 16(6), 734-744 (2007).
    連結:
  34. Yan, S., Lai, W.S. and Chen, M.N., “Production Scheduling and Truck Dispatching of Ready Mixed Concrete,” Transportation Research, Part E, 44(1), 164-179 (2008).
    連結:
  35. Yan, S. and Lin, C.G., “Airline Scheduling for the Temporary Closure of Airports,” Transportation Science, 31(1), 72-82 (1997).
    連結:
  36. 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, 30(1), 63-55 (2007).
    連結:
  37. Yan, S. and Tseng, C.H., “A Passenger Demand Based Model for Airline Flight Scheduling and Fleet Routing,” Computers and Operations Research, 29(11), 1559-1581 (2002).
    連結:
  38. Yan, S. and Tu, Y.P., “Multi-Fleet Routing and Multi-Stop Flight Scheduling for Schedule Perturbation,” European Journal of Operational Research, 103(1), 155-169 (1997).
    連結:
  39. Yan, S. and Yang, D.H., “A Decision Support Framework for Handling Schedule Perturbation,” Transportation Research, Part B, 30(6), 405-419 (1996).
    連結:
  40. Yan, S. and Young, H.F., “A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling,” Transportation Research, Part A, 30(5), 379-398 (1996).
    連結:
  41. Zayed, T. M. and Minkarah, I., “Resource Allocation for Concrete Batch Plant Operation: Case Study,” Journal of Construction Engineering and Management, 130(4), 560-569 (2004).
    連結:
  42. Zhu, K., Tan, K.C. and Lee, L.H., “Heuristics for Vehicle Routing Problem with Time Windows,” Proceedings of 6th AI and Math Symposium, Florida, U.S.(2000).
    連結:
  43. 中國國家標準(Chinese National Standard,CNS),經濟部標準檢驗局,CNS3090。http://www.cnsonline.com.tw/
  44. 申生元,「時窗限制車輛途程問題」,博士論文,國立交通大學工業工程與管理學系 (1998)。
  45. 申生元,「多趟次車輛途程與排程問題」,行政院國家科學委員會,NSC90-2218-E155-010 (2002)。
  46. 江靜芳,「精簡營建於預拌混凝土供應鏈應用之研究」,碩士論文,國立中央大學土木工程學系 (2000)。
  47. 呂英志,「即時資訊下車輛路線問題之研究」,碩士論文,逢甲大學交通工程與管理學系 (2002)。
  48. 吳宗憲,「結合模擬技術與專家系統應用於公車之排班作業」,碩士論文,國立台灣大學土木工程學系 (1994)。
  49. 邱志洲,「用基因工程來解決時窗限制下車輛途程問題之研究」,行政院國家科學委員會,NSC87-2213-E030-007 (1998)。
  50. 洪轟嘉,「結合限制理論與SmartLink電腦模擬之開發以輔助預拌混凝土供應鏈之規劃」,碩士論文,國立中興大學土木工程學系 (2001)。
  51. 苑鳳萍,「客運車輛擾動下調度系統之研究」,碩士論文,國立交通大學運輸工程與管理學系 (2001)。
  52. 陳妙珍、顏上堯、張珮璇,「航空公司資產與負債管理模式之建立」,第四屆海峽兩岸會計與管理學術研討會論文集,武漢 (2000)。
  53. 陳振明,「共同配送環境下發展一整合倉儲區位、存貨補充及配銷路徑規劃模式」,行政院國家科學委員會,NSC89-2213-E008-015 (2000)。
  54. 道路交通安全規則,交通部,第38條。http://law.moj.gov.tw/Scripts/NewsDetail.asp?no=1K0040013
  55. 劉方旗,「市區公車排班與即時機動調度之研究--以新竹客運為例」,碩士論文,國立交通大學運輸科技與管理學系 (1998)。
  56. 顏上堯、何淑萍,「飛航排程暨班次表之建立」,運輸計劃季刊,第二十三卷,第一期,第73-90頁 (1994)。
  57. Agin, N. and Cullen, D., “An Algorithm for Transportation Routing and Vehicle Loading,” in Geisler, M. (Ed.), Logistics, 1-20, North Holland, Amsterdam (1975).
  58. Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M.M. and Soumis, F., “Daily Aircraft Routing and Scheduling,” Management Science, 43(6), 841-855 (1997).
  59. Equi, L., Gallo, G., Marziale, S. and Weintraub, A., “A Combined Transportation and Scheduling Problem,” European Journal of Operational Research, 97(1), 94-104 (1997).
  60. Freling, R., Paixão, J. M. P. and Wagelmans, A. P. M., “Models and Algorithms for Vehicle Scheduling,” report 9562/A, Econometric Institute, Erasmus University Rotterdam, the Netherlands (1999).
  61. Healy, P., “A Tool for Adjusting the Flight Schedule During High Volume Irregular Operations,” Proceedings of the AGIFORS 32nd Annul Symposium, 53-64 (1992).
  62. Naso, D., Surico, M., Turchiano, B., and Kaymak, U., “Genetic Algorithms in Supply Chain Scheduling of Ready Mixed Concrete,” ERIM report series research in management, ERS-2004-096-LIS, Erasmus Research Institute of Management (2004).
  63. Simpson, R. W., “A Review of Scheduling and Routing Model for Airline Scheduling,” IX AGIFORS Symposium, Broadway, England (1969).
  64. Thangiah, S. R., “Vehicle Routing with Time Windows Using Genetic Algorithms,” Application Handbook of Genetic Algorithms: New Frontiers, Volume II. Lance Chambers (Ed.), CRC Press, 253-277 (1995).
  65. Wang, S. Q., Teo, C. L. and Ofori, G.., “Scheduling the Truckmixer Arrival for a Ready Mixed Concrete Pour via Simulation with @Risk,” Journal of Construction Research, 2(2), 169-179 (2001).
  66. Zayed, T. M. and Halpin, D. W., “Simulation of Concrete Batch Plant Production,” Journal of Construction Engineering and Management, 127(2), 132-141 (2001).
Times Cited
  1. 王惟志(2011)。廢棄機車回收廠區位選址之研究。中央大學土木工程學系學位論文。2011。1-102。