土石方調派作業暨傾卸卡車派遣規劃之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：95

、訪客IP：18.188.205.249

姓名

陳冠霖(Kuan-lin Chen) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

土石方調派作業暨傾卸卡車派遣規劃之研究
(Soil and Rock Deploy and Dump Truck Dispatch Planning)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

營建工程中，土石方之運送方式以傾卸卡車為主，如何以快速、有效並節省成本的方法調派土石方及車輛資源，實為工程業者獲利之關鍵。但實務界於資源調派作業上仍以人工經驗的方式進行規劃，此方式缺乏系統最佳化分析，於小規模工程中尚可勝任，但於大規模工程如捷運興建工程中，則往往因缺乏整體車輛調度的考量，進而導致工程進度延宕或影響周邊道路交通順暢，實為資源的浪費，也直接降低營運績效。因此本研究以系統最佳化的觀點，針對傾卸卡車派遣規劃問題發展適合之模式及求解演算法，以提供決策者輔助工具，有效地規劃傾卸卡車的運送排程。
本研究利用時空網路流動技巧以定式傾卸卡車及其所載運之土石方在時空中的流動狀況，並根據問題特性加入額外限制，以期符合實務營運條件，並據以構建模式。本模式可定式為含額外限制之多目標整數網路流動問題，屬NP-hard問題，在面對實務大型的問題時，難以在有限的時間內求得最佳解。因此，為有效地求解實務大型問題，本研究利用問題分解策略，並配合使用數學規劃套裝軟體CPLEX，發展一有效的求解演算法。最後，為評估本模式與演算法之實際求解績效，本研究以台灣一大型營建工程之營運資料為範例進行測試與分析，結果甚佳，顯示本研究發展之模式與求解演算法可為實物業者之參考，以有效解決土石方調派及傾卸卡車排程規劃問題。

摘要(英)

In the construction projects, Dump truck is the main form of transporting soil and rock. How to fast, efficient and cost-saving resources deployed soil and rock and vehicles is a key project profit of the industry. But practitioners operating in the resources deployed are still manually determined with staff experience. In the Small-scale projects can still be qualified. However, in the large-scale projects such as the MRT construction project is often due to lack of integrated vehicle scheduling considerations. And this led to the progress of road traffic delay or affects the surrounding smooth. Consequently, the resulting solution, though feasible, could possibly be inferior. Therefore, in this research we focus on the soil and rock deployed operating and dump truck dispatch plan to develop a suitable model from the system optimization perspective. The model is expected to be useful planning tool for carriers to on their optimal soil and rock deploying and dump truck dispatching in their operations.
We employ time-space network flow techniques to formulate the dump truck flows and the soil and rock flows in the dimension of time and space, coupled with suitable side constaints comply real operating requirements, to develop the model. The model is formulated as an integer network flow problem with side constraints, which is characterized as NP-hard and is difficult to be optimally solved in a reasonable time for large-scale problem. In order to efficiently solve large-scale problems occurring in real world, we develop a solution algorithm. To evaluate the model and solution algorithm, we perform a case study using real operating data from a large construction project in Taiwan. The test results show that the model and the solution algorithm are good and could be useful references for carriers to handle soil and rock deploying and dump truck dispatching.

關鍵字(中)

★ 啟發解法
★ 時空網路
★ 營建剩餘土石方
★ 傾卸卡車排程
★ 含額外限制網路流動問題

關鍵字(英)

★ soil and rock
★ dump truck dispatching
★ network flow problem with side constraints
★ time-space network
★ heuristic algorithm

論文目次

摘要I
ABSTRACTII
誌謝III
目錄IV
圖目錄VII
表目錄VIII
第一章緒論1
1.1 研究背景與動機 1
1.2 研究目的與範圍 2
1.3 研究方法與流程 2
第二章文獻回顧4
2.1 土石方工程作業與傾卸卡車調派相關文獻4
2.2 時窗限制之車輛派遣/排程問題5
2.3 時空網路的相關文獻7
2.4 大型含額外限制之整數網路流動問題啟發式演算法 9
2.5 文獻評析11
第三章模式構建13
3.1 現況分析13
3.2 傾卸卡車派遣模式16
3.2.1 模式基本假設或給定資訊 16
3.2.2 車流時空網路 18
3.2.3 物流時空網路 22
3.2.4符號說明28
3.2.5 數學定式29
3.3 模式應用30
3.4 小結 31
第四章模式求解32
4.1 啟發解法架構32
4.2 單一車輛定線法 34
4.3 小結 34
第五章範例測試35
5.1資料輸入35
5.1.1 車輛任務時間資料35
5.1.2 土石方價格及營運成本資料35
5.2模式發展36
5.2.1問題規模36
5.2.2 模式輸入資料 37
5.3電腦演算環境及設定37
5.3.1 電腦演算環境 37
5.3.3 模式輸出資料 38
5.4測試結果與分析38
5.5 敏感度分析40
5.5.1傾卸卡車規模敏感度分析40
5.5.2 土石方供給與需求大小敏感度分析42
5.5.3土石方價格敏感度分析48
5.5.4土石方工地滯留成本大小敏感度分析 49
5.5.5 車輛任務成本大小敏感度分析51
5.6 情境分析54
5.6.1問題規模大小之情境分析54
5.6.2土石方供需比大小之敏感度分析56
5.7小結 57
第六章結論與建議 59
6.1 結論 59
6.2 建議 60
6.3 貢獻 61
參考文獻 63
附錄70
附錄一 CPLEX Callable Library Code70
附錄二任務時間資料 71
附錄三車輛流量分解 73
附錄四傾卸卡車作業排班表74
附錄五傾卸卡車規模敏感度分析 78

參考文獻

1.乃啟育，「策略聯盟環境下城際客運排程規劃模式之研究」，碩士論文，國立中央大學土木研究所 (2006)。
2.申生元，「多趟次車輛途程與排程問題」，行政院國家科學委員會，NSC90-2218-E155-010 (2002)。
3.李宇欣，「最佳化工程設計概念」，運輸工程專輯，土木水利工程學會，第二十九卷，第一期，第55-62頁 (2002)。
4.杜明星，「營建剩餘土資場申請設置審查、應有設施申報查核、營運管理及土石方再利用之研究~以桃園縣為例~」，碩士論文，國立中央大學土木工程學系 (2007)。
5.林士鈞，「定期貨櫃運輸船舶排程暨船期表建立之研究」，碩士論文，國立中央大學土木研究所 (2004)。
6.林益生，「隨機環境下多商品、多車種派車問題之研究」，碩士論文，中原大學工業工程學系 (1998)。
7.林憶田，「土方作業規劃同類資源考量之模擬研究」，碩士論文，國立中央大學土木工程學系 (1999)。
8.邱明琦、陳春益、林佐鼎，「海運貨櫃排程模式之研究」，運輸計劃季刊，第三十一卷，第三期，第495-522頁 (2002)。
9.張秀雲，「具時窗限制之車輛迴轉率與路線規劃問題之研究」，行政院國家科學委員會，NSC89-2416-H006-074 (2001)。
10.陳春益、邱明琦，「貨櫃航線網路設計模式之研究」，運輸計劃季刊，第三十一卷，第二期，第267-298頁 (2002)。
11.游俊雄、丁國樑，「需求反應旅次運載模擬模式應用於捷運營運班表之評估」，運輸計劃季刊，第二十七卷，第三期，第489-508頁 (1998)。
12.鄭明淵、陳惠民，「工程土方資源管理與指派載運監控系統」，中國土木水利工程學刊，第十卷，第二期，第251-262頁 (1998)。
13.鄭景鴻，「類神經模糊系統於公路土石方工程成本估價之應用」，碩士論文，中華大學營建管理研究所 (2002)。
14.賴怡君，「土方運輸卡車車隊安排模式之研究」，碩士論文，朝陽科技大學營建工程學系 (2006)。
15.顏上堯、何淑萍，「飛航排程暨班次表之建立」，運輸計劃季刊，第二十三卷，第一期，第73-90頁 (1994)。
16.顏上堯、羅智騰，「因應預期性航具維修之系統性飛航排程」，中國土木水利工程學刊，第八卷，第三期，第447-456頁 (1996)。
17.顏上堯、簡明智、施佑林，「營建工程人力調派最佳化決策模式之研究」，亞太工程科技學報，第四卷，第二期，第777-790頁 (2007)。
18.顏上堯、簡德和、陳俊穎，「開發區域內土方工程最佳調派決策模式之研究」，台灣公共工程學刊，第一期，第1-14頁 (2006)。
19.顏上堯、顧梓承、陳佳宏，「土石方工程調派最佳決策模式之研究」，技術學刊，第十八期，第503-508頁 (2002)。
20.簡君珊，「土方銀行營運最佳化管理模式」，碩士論文，國立成功大學土工程學系(1999)。
21.Abara, J., “Applying integer linear programming to the fleet assignment problem,” Interfaces, 19, pp. 20-28 (1989).
22.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).
23.Akkan, C. and Karabat, S., “The two-machine flowshop total completion time problem: Improved lower bounds and a branch-and-bound algorithm,” European Journal of Operational Research, 159, pp. 420-429 (2004).
24.Amirkhanian, S.N. and Baker, N.J., “Expert System for Equipment Selection for Earth-Moving Operations,” Journal of Construction Engineering and Management, Vol. 118, No. 2, pp. 318-331 (1992).
25.Arroyo, J.E.C. and Armentano, V.A., “Genetic local search for multi-objective flowshop scheduling problems,” European Journal of Operational Research, 167(3), pp. 717-738 (2005).
26.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).
27.Benders, J.F., “Partitioning procedures for solving mixed-variables programming problems,” Numerische Mathematik, 4, pp. 238-252 (1962).
28.Bierwirth, C. and Mattfeld, D.C., “Production scheduling and rescheduling with genetic algorithms,” Evolutionary Computation, 7(1), pp. 1-17 (1999).
29.Camerini, P.K., Fratta, L. and Maffioli, F., “On improving relaxation methods by modified gradient techniques,” Mathematical Programming Study, 3, pp. 6-25 (1975).
30.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).
31.Chih, K.C.K., “A real time dynamic optimal freight car management simulation model of multiple railroad, mulitcommodity temporal spatial flow problem,” Ph.D. Dissertation, Princeton University, Princeton, NJ (1986).
32.Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M.M. and Soumis, F., “Daily aircraft routing and scheduling,” Management Science, 43, pp. 841-855 (1997).
33.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).
34.Fisher, M. L., “The Lagrangian relaxation method for solving integer programming problem,” Management Science, 27, pp. 1-18 (1981).
35.Glover, F. and M. Laguna, Tabu search, Kluwer Academic Publishers, Norwell, MA (1997).
36.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, pp. 211-232 (1995).
37.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).
38.Hurink, J. and Knust, S., “Flow-shop problems with transportation times and a single robot,” Osnabrucker Schriften zur Mathematik, Reihe P, Nr. 201 (1998).
39.Husbands, P., “Genetic algorithms for scheduling,” AISB Quarterly, 89 (1994).
40.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).
41.Kenyon, A.S. and Morton, D.P., “Stochastic vehicle routing with random travel times,” Transportation Science, 37 (1), pp. 69-82 (2003).
42.Lai, M. F. and Lo, H. K., “Ferry service network design: Optimal fleet size, routing, and scheduling,” Transportation Research Part A, 38, pp. 305-328 (2004).
43.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).
44.Levin, A., “Scheduling and fleet routing models for transportation systems,” Transportation Science, 5, pp. 232-255 (1971).
45.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, 39, pp. 209-227 (2003).
46.Luh, P. B., Zhao, X., Wang, Y. and Thakur, L.S., “Lagrangian relaxation neural network for job shop scheduling,” Proc. of International Conference on Robotics and Automation, Leuven, Belgium, pp. 1799-1804 (1998).
47.Marzouk, M. and Moselhi, O.,“Object-oriented Simulation Model for Earthmoving Operations,”Journal of Construction Engineering and Management, Vol. 129, Issue 2, pp. 173-181 (2003).
48.Marzouk, M. and Moselhi, O., “Multiobjective Optimization of Earthmoving Operations,”Journal of Construction Engineering and Management, Vol. 130, Issue 1, pp. 105-115 (2004).
49.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).
50.Mulvery, J.M. and Ruszczynski, A., “A New scenario decomposition method for large-scale stochastic optimization,” Operations Research, 43(3), pp. 477-490 (1995).
51.Mulvery, J.M., Vanderbei, R.J. and Zenios, S.A., “Robust optimization of large-scale systems,” Operations Research, 43(2), pp. 254-281 (1995).
52.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).
53.Shan, Y.S., “A dynamic mulitcommodity network flow model for real time optimal real freight car management,” Ph.D. Dissertation, Princeton University, Princeton, NJ(1985).
54.Shmoys, D.B., Stein, C. and Wein, J., “Improved approximation algorithms for shop scheduling problems,” SIAM Journal on Computing, 23 (3), pp. 617-632 (1994).
55.Smith, S. D., Osborne, J.R., and Forde, M.C., “Analysis of Earth-Moving System Using Discrete-Event Simulation,” Journal of Construction Engineering and Management, Vol. 121, No.4, pp. 388-396 (1995).
56.Smith, S. D., “Earthmoving Productivity Estimation Using Linear Regression Techniques,” Journal of Construction Engineering and Management, Vol. 127, No.6, pp. 502-511 (2001).
57.Simpson, R. W., “A review of scheduling and routing model for airline scheduling,” IX AGIFORS Symposium, Broadway, England (1969).
58.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).
59.Stancu-Minasian, I.M., “Stochastic programming with multiple objective functions,” Editura Academiei, Bucharest (1984).
60.Teodorovic, D., Airline operations research, Gordon and Breach Science Publishers, New York (1988).
61.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), pp. 181-193 (2000).
62.Thengvall, B.G., Yu, G. and Bard, J. F., “Multiple fleet aircraft schedule recovery following hub closure,” Transportation Research, Part A, 35(4), pp. 289-308 (2001).
63.Varadharajan, T. K. and Rajendran, C., “A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs,” European Journal of Operational Research, 167, pp. 772-795 (2005).
64.Wang, D. Z. W. and Lo, H. K., “Multi-fleet ferry service network design with passenger preferences for differential services,” Transportation Research Part B, 42, pp. 798-822 (2008).
65.Wang, L. and Zheng, D. Z., “An effective optimization strategy for job shop scheduling problems,” Computers and Operations Research, 28, pp. 585-596 (2001).
66.Wang, L. and Zheng, D.Z., “A modified genetic algorithm for job shop scheduling,” International Journal of Advanced Manufacturing Technology, 20, pp. 72-76 (2002).
67.Yamada, T. and Nakano, R., “Job shop scheduling by simulated annealing combined with deterministic local search,” Metaheuristics International Conference, Hilton, Breckenridge, Colorado, USA, pp. 344-349 (1995).
68.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), pp. 409-430 (2006a).
69.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), pp. 572-586 (2006b).
70.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), pp. 368-374 (2005).
71.Yan, S., Shieh, C. W. and Chen, M., "A simulation framework for evaluating airport gate assignments,” Transportation Research, part A, 36(10), pp. 885-898 (2002).
72.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), pp. 63-55 (2007).
73.Yan, S. and Tu, Y.P., “Multi-fleet routing and multi-stop flight scheduling for schedule perturbation,” European Journal of Operational Research, 103(1), pp. 155-169 (1997).
74.Yan, S. and Yang, D.H., “A decision support framework for handling schedule perturbation,” Transportation Research, Part B, 30(6), pp. 405-419 (1996).
75.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), pp. 379-398 (1996).
76.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

推文