跳到主要內容

臺灣博碩士論文加值系統

(3.237.38.244) 您好!臺灣時間:2021/07/24 17:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:孟欐潓
研究生(外文):Li-Hui Meng
論文名稱:應用門檻接受法於求解容量限制節線途程問題及家庭廢棄物清運規劃之研究
論文名稱(外文):A Threshold Accepting Algorithm for the Capacitated Arc Routing Problem and Application of Hosehold Waste Collection
指導教授:丁慶榮丁慶榮引用關係
學位類別:碩士
校院名稱:元智大學
系所名稱:工業工程與管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:102
中文關鍵詞:容量限制節線途程問題門檻接受法家庭廢棄物逆物流
外文關鍵詞:Capacity ConstrainArc Routing Problem (ARP)Threshold Accepting (TA)Household Refuse CollectionReverse Logistics
相關次數:
  • 被引用被引用:4
  • 點閱點閱:373
  • 評分評分:
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
  有容量限制的節線途程問題(Capacitated Arc Routing Problem, CARP)屬於節線途程問題(Arc Routing Problem, ARP),自提出後就常被應用在許多問題,如信件寄送、街道清掃規劃、校車路線與家庭廢棄物清運規劃。其問題定義為給定一個無方向之網路,網路中的節線有一路徑成本與需求量,當節線為有非負需求量稱之為需求節線。而服務車輛有容量限制,且為單一車種多台車。每台車從場站出發滿足車容量後再回至場站,每條需求節線僅被一台車輛服務,但可被經過數次。決定一最短的總旅行成本路徑,使得每條需求節線皆被服務。由於CARP為一NP-hard問題,本研究應用啟發式演算法中參數設定少、執行容易、求解時間快速與效果顯著的門檻接受法(Threshold Accepting, TA)求解之。本研究所發展之門檻接受法利用不同移步組合、動態搜尋與控制懲罰函數來調整搜尋的廣度與深度。測試部分使用三組CARP標竿測試例題,並設定相關參數進行測試。測試發現,參數的影響對於TA較不敏感,故選擇一組考量CPU時間與Gap績效較佳之參數組合。總結,本研究之門檻接受法可找到69%測試例題文獻最佳解,其中在小型例題可全部找到文獻最佳解,且求解時間優於其它演算法,表示TA應用於求解CARP上確實具有可行性。
 在實務應用方面,考慮實際道路有方向之限制,將家庭廢棄物清運規劃成有方向性有容量限制的節線途程問題(Directed Capacitated Arc Routing Problem, DCARP),並建構以DCARP為基礎之數學模式。實證分析以中壢市一收運責任區之家庭廢棄物清運為例,利用GoogleMap電子地圖並以Borland C++ 6.0繪製中壢市清運路線。本研究提出三種改善方案,僅以縮短路線總距離為目標,並未考慮到實際收運時之收運時間限制、各路線在不同時間車流量與紅綠燈狀況等。由於簡化收運狀況,且僅以縮短路線為目標,分析結果發現,目前討論之收運責任區,若不考慮各種收運限制,僅以收運行駛距離最小化為目標,經由更動現行規劃之收運路線運規劃,可縮短收運路線距離。未來研究中可將中壢市作整體考量規劃,並且將各種收運限制納入考量,以更能有效反映實務狀況。
The capacitated arc routing problem (CARP) is a special routing problem which has a variety of practical applications, such as urban waste collection, snow plowing, sweeping, gritting, etc. The CARP is defined on an undirected graph with a set of edges. Each edge has a routing cost and a demand. The edges with positive demand make up the subset of the required edges. A set of identical vehicles with capacity is available. Each required edge has to be served exactly by one vehicle. Each route must start and end at the same depot and the total demand served by a route cannot exceed vehicle capacity. The objective of CARP is to find a set of vehicle routes to minimize the total traveling cost.
Due to the CARP is a NP-hard problem, it is difficult to solve optimally within a reasonable computational time by exact solution approaches. Therefore, this research intends to present a threshold accepting (TA) meta-heuristic to solve the CARP. TA is tested on three groups of benchmark instances from the literature. Its performance is compared with other algorithms from the literature. The computational results show that TA is effective to solve the CARP and its performance is highly competitive. TA reaches 65 best known solutions in 81 instances.
In the practical application, we apply TA to solve the household refuse collection problem in Chung-Li city. The household refuse collection problem is formulated as a directed capacitated arc routing problem (DCARP). The road network is built by using GoogleMap and Borland C++ 6.0 and data were collected from Chung-Li city cleaning squad. The results show that the distance of waste collection can be reduced by arranging and planning the new routes under simplified situation. In the future research, we can consider the Chun-Li city for whole waste collection planning and take the real traffic situation into account.
目錄
摘要 i
Abstract ii
致謝 iii
目錄 iv
圖目錄 vi
表目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 4
1.3 研究流程 4
第二章 文獻探討 7
2.1 有容量限制的節線途程問題 7
2.2 垃圾清運規劃 11
2.3 廢棄物管理 13
2.4 門檻接受法 16
2.5 小結 19
第三章 研究方法 21
3.1 有方向性容量限制節線途程問題 21
3.1.1 問題描述 21
3.1.2 數學模式 22
3.2 門檻接受法 24
3.2.1 編碼與目標式 27
3.2.2 初始解建構模組 29
3.2.3 鄰近解搜尋模組 31
3.2.4 區域搜尋模組 35
3.2.5 TA搜尋機制 37
3.3 演算法測試 42
3.3.1 測試例題 43
3.3.2 測試與分析 46
3.3.3 參數測試與分析 58
3.3.4 演算結果比較 63
3.4 小結 65
第四章 實證研究 66
4.1 模式建立 66
4.1.1 問題描述與假設 66
4.1.2 數學模式 69
4.2 門檻接受法 72
4.3 實證案例分析 76
4.3.1 資料收集與分析 77
4.3.2 實證改善方案 82
4.4 小結 88
第五章 結論與建議 89
5.1 結論 89
5.2 建議 91
參考文獻 93
附錄一:預設參數測試結果 97
附錄二:最佳參數測試結果 100

圖目錄
圖 1.1 逆物流簡單示意圖 2
圖 1.2 台灣垃圾量與人口數趨勢圖 3
圖 1.3 台灣地區平均每人每日垃圾產生與清運量 3
圖 1.4 研究架構流程圖 6
圖 3.1 DCARP車輛收運狀況示意圖 22
圖 3.2 門檻接受法基本流程示意 26
圖 3.3 本研究門檻接受法求解架構 27
圖 3.4 TA演算法解編碼示意 28
圖 3.5 需求節線間最短距離成本陣列 28
圖 3.6最鄰近法 30
圖 3.7 產生初始解之路徑掃描法邏輯流程 31
圖 3.8 兩兩交換法路線間移步 32
圖 3.9 單節線插入法路線間移步 32
圖 3.10 雙節線插入法路線間移步 33
圖 3.11 2-Opt 交換法 33
圖 3.12 3-Opt交換後組合 34
圖 3.13途程內移步與途程間移步 35
圖 3.14 整體途程順序區域搜尋法 36
圖 3.15 完全改善之區域搜尋法 36
圖 3.16 等比遞減門檻數列示意圖 37
圖 3.17 本研究使用之TA搜尋法一 39
圖 3.18 本研究使用之TA搜尋法二 40
圖 3.19 本研究使用之TA搜尋法三 41
圖 3.20 演算法測試流程 47
圖 3.21 移步績效測試流程 48
圖 3.22 不同題組與不同移步T與Gap趨勢 49
圖 3.23懲罰函式法一流程 53
圖 3.24懲罰函式法二 54
圖 3.25 參數測試與分析流程 59
圖 4.1實際道路種類與方向示意 67
圖 4.2 模式使用之全有方向網路 67
圖 4.3 家庭廢棄物收運實際狀況示意圖 68
圖 4.4 應用於實務問題TA演算法解編碼 72
圖 4.5 最鄰近法流程(實務應用) 74
圖 4.6 路徑掃描法流程(實務應用) 75
圖 4.7 中壢市四個行政區域 76
圖 4.8 中壢市三大責任區清運路線 77
圖 4.9 中壢市各班次收運點數與時間對應趨勢圖 78
圖 4.10 收運路線圖手動編碼圖示 80
圖 4.11 中壢市收運路第一責任區收運路線區域分布圖 81
圖 4.12實證分析方案2各收運路線分布結果 85
圖 4.13 實證分析方案3各車收運分布結果 87

表目錄
表 3.1 CARP小型標竿測試例題gdb資訊 44
表 3.2 CARP中型標竿測試例題val資訊 45
表 3.3 CARP大型標竿測試例題egl資訊 46
表 3.4移步測試參數設定 48
表 3.5不同測試題組對應不同移步效果 49
表 3.6測試三參數設定 51
表 3.7 三種搜尋機制績效與是否接受不可行解測試結果一覽表 51
表 3.8 動態懲罰函數測試參數設定 52
表 3.9 動態懲罰函數測試結果 54
表 3.10 T、T1、|V|、|R|、|P|與W皮爾森相關係數分析 55
表 3.11 進行各項測試之預設參數 56
表 3.12 本研究發展之TA法預設參數測試結果 56
表 3.13 不同門檻數列更新方式測試結果 56
表 3.14 不同移步順序組合 57
表 3.15 不同移步組合測試結果 57
表 3.16 初始解對TA演算法之影響 58
表 3.17 gdb題組T0與α參數變動測試結果 60
表 3.18 val題組T0與α參數變動測試結果 60
表 3.19 egl題組T0與α參數變動測試結果 61
表 3.20 變動λ1*參數分析之相關參數設定 62
表 3.21 變動λ1*參數分析測試結果 62
表 3.22 各題組之最佳參數設定 63
表 3.23各組最佳搜尋結果 63
表 3.24 gdb測試題組文獻與本研究求解績效比較 64
表 3.25 val測試題組文獻與本研究求解績效比較 64
表 3.26 egl測試題組文獻與本研究求解績效比較 64
表 4.1 中壢市垃圾收運路線收運點與收運總時間 78
表 4.2 中壢市垃圾清運日報表資料型態 79
表 4.3 收運第一責任區各路線平均收運量 80
表 4.4 參數、決策變數與限制式個數 82
表 4.5 實證案例路線成本 83
表 4.6 實務改善參數設定 83
表 4.7 考慮原路線各車收運最大載量實證分析方案1 84
表 4.8 重新規劃收運路線之實證分析方案2 84
表 4.9 重新規劃收運路線之實證分析方案3 86
表 4.10 實證分析各方案結果比較 88
1.王生德(2004),「以巨集啟發式方法求解時窗限制回程取貨車輛路線問題之研究」,私立中華大學科技管理研究所碩士論文。
2.王聖斐(1995),「都會區廢棄物管理系統多目標規劃及決策支援系統之發展」,國立成功大學環境工程研究所碩士論文。
3.行政院環境保護署(2008),「中華民國環境保護統計年報」。2008年9月29日,取自「行政院環境保護署網站」:http://www.epa.gov.tw/ch/DocList.aspx?unit=24&clsone=501&clstwo=178&clsthree=172&busin=4177&path=9540
4.何家豪(2003),「有害廢棄物逆向物流聯合處理營運模式之研究」,國立交通大學交通運輸研究所碩士論文。
5.吳濟華與劉春初(1998),「應用DEA模型分析高雄市垃圾清運區對之生產效率」,中山管理評論,6(3),879-902。
6.中壢市公所全球資訊網,「中壢市行政區域圖」2008年12月30日取自網站http://www.junglicity.gov.tw/tw/library/street/list.asp
7.中壢市公所全球資訊網,「清運垃圾時刻表」,2009年1月10日取自網站
http://www.junglicity.gov.tw/tw/service/rubbish/list.asp
8.李慧梅、李公哲與陳永明(1986),「垃圾集運系統效率之評估」,中國土木水利工程學會第二屆廢棄物處裡技術研討會論文集,1-9。
9.卓裕仁與朱佑旌(2008),「兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究」,運輸計劃季刊,37(4),405-430。
10.周裕豐(1999),「事業廢棄物清除處理之分析:綠色國民所得帳與CGE 模型之應用」,國立央大學產業經濟研究所碩士論文。
11.林宗儀(2001),「垃圾公車清運系統之收集點位置規劃」,國立交通大學環境工程所碩士論文。
12.林冠宇(2006),「垃圾車收運範圍劃設之研究-以台中市南屯區為例」,私立朝陽科技大學建築及都市設計研究所碩士論文。
13.林志勳(2008),「連續補貨點接駁車路線問題之研究」,私立中華大學運輸科技與物流管理學系碩士論文。
14.林耕全(2005),「裝修工程廢棄物回收站與再利用廠設置最佳化區位評選之研究」,國立中央大學營建管研究所碩士論文。
15.林燦輝(2002),「有害事業廢棄物處理決定性因素探討與策略擬定─以高雄縣石化及化工業為例」,私立義守大學管理科學研究所碩士論文。
16.韋佩玲(1999),「垃圾產出量預估模式之研究」,國立台灣大學環境工程學研究所碩士論文。
17.夏大明、沈永堂、沈靜悅(2005),「都市鄰里公園區位分配之研究-以台中市西屯區為例」,台灣地理資訊學會年會暨學術研討會論文集。
18.張寶豐(2003),「以複合啟發式演算法求解時窗限制車輛途程問題」,私立中原大學工業工程學系碩士學位論文。
19.陳百傑(2002),「以啟發式演算法求解時窗限制車輛途程問題」,私立中原大學工業工程學系碩士學位論文。
20.陳哲寬(2002),「都市家戶垃圾清運頻率之研究-以高雄市為例」,國立高雄第一科技大學碩士論文。
21.陳隆熙(2002),「一個解決TSP 問題最佳解的穩定方法-以TA 演算法為例」,私立大葉大學工業工程學系碩士班碩士論文。
22.程耀輝(2006),「多路程車輛排程問題之門檻接受啟發式演算法」,私立義守大學工業工程與管理學系碩士論文。
23.黃承威(1997),「以工作負荷與轉彎合適性為基準之垃圾車巡迴路線規劃」,國立交通大學環境工程與科學系碩士論文。
24.黃仁杼(2004),「都垃圾轉運政策研擬及設置可行性研究-以桃園縣為例」,私立元智大學機械工程學系碩士論文。
25.黃文正(2007),「以垃圾不落地之原則規劃理論最佳清運路線之研究-以台南縣新營市為例」,國立高雄第一科技大學環境與安全衛生工程系碩士論文。
26.黃宥禔(2007),「廢棄物清運績效綜合指標」,國立交通大學環境工程研究所碩士論文。
27.楊文正(2005),「廢棄物物流系統規劃之研究」,國立成功大學工業與資訊管理研究所碩士論文。
28.劉珮伶(2004),「考量產品配送下之多廠區訂單分配問題應用門檻值接受法」,私立元智大學工業工程與管理研究所碩士論文。
29.盧啟文與程惠生(1996),「垃圾清運綜合性效率指標之研究」,第十一屆廢棄物處裡技術研討會論文集,51-59。
30.韓復與楊智凱(1996),「門檻接受法在TSP問題上之應用」,運輸計劃季刊,25(2),163-188。
31.韓復華、楊智凱、卓裕仁(1997),「應用門檻接受法求解車輛路線問題之研究」,運輸計劃季刊,26(2),253-280。
32.Amberg, A. and S. Voß. (2002). “A Hierarchical Relaxations Lower Bound for the Capacitated Arc Routing Problem”, Proceedings of the 35th Annual Hawaii International Conference on System Sciences, DTIST02. Piscataway: IEEE, 1–10.
33.Amponsah, S.K. and S. Salhi (2004), “The Investigation of a Class of Capacitated Arc Routing Problems: The Collection of Garbage in Developing Countries”, Waste Management, 24, 711–721.
34.Belenguer, J.M. and E. Benavent (2003),”A Cutting Plane Algorithm for the Capacitated Arc Routing Problem”, Computers & Operations Research, 30 (5), 705-728.
35.Brandao, J. and R.W. Eglese (2008), “A Deterministic Tabu Search Algorithm for the Capacitated Arc Routing Problem”, Computers & Operations Research, 35 (4), 1112 - 1126.
36.DeBrito, M.P., R. Dekker (2004), “A Framework for Reverse Logistics. Chapter 1 of Reverse Logistics. Quantitative Models for Closed-Loop Supply Chains”, Springer-Verlag, Germany.
37.Dijkstra, E. W. (1959), “A Note on Two Problems in Connection with Graphs”, Numerische Mathematik, 1, 269-271.
38.Dongarra, J. (2008), “Performance of Various Computers Using Standard Linear Equations Software”, Report CS-89-85, University of Tennessee, U.S.A.
39.Dror, M. (Ed.) (2000), Arc Routing: Theory, Solutions and Applications. Kluwer Academic Publishers, Dordrecht, the Netherlands.
40.Dror, M., H. Stern and P. Trudeau (1987), “Postman Tour on a Graph with Precedence Relation on Arcs”, Networks, 17 (3), 283-294.
41.Dueck, G. and T. Scheuer (1990), “Threshold Accepting: A General Purpose Optimization Algorithm Appeared Superior to Simulated Annealing”, Journal of Computational Physics, 90, 161-175.
42.Eiselt, H. A., M. Gendreau, and G. Laporte (1995), “Arc Routing Problems, Part I: The Chinese Postman Problem”, Operations Research, 43 (2), 231-242.
43.Eiselt, H. A., M. Gendreau, and G. Laporte (1995), “Arc Routing Problems, Part II: The Rural Postman Problem”, Operations Research, 43 (3), 399-414.
44.Greistorfer, P. (2003), “A tabu Scatter Search Metaheuristic for the Arc Routing Problem”, Computers & Industrial Engineering, 44 (2), 249-266.
45.Golden, B.L., J.S. DeArmon and E.K. Baker (1983), “Computational Experiments with Algorithms for a Class of Routing Problems”, Computers & Operations Research, 10 (1), 47-59.
46.Hertz, A., G. Laporte and M. Mittaz (2000), “A Tabu Search Heuristic for The Capacitated Arc Routing Problem”, Operations Research, 48 (1), 129-135.
47.Kulcar, T. (1996), “Optimizing Solid Waste Collection in Brussels”, European Journal of Operational Research, 90 (1), 71-77.
48.Lacomme, P., C. Prins, and A. Tanguy (2004), “First Competitive Ant Colony Scheme for the CARP”, Lecture Notes in Computer Science, 3172, 426-427.
49.Lacomme, P., C. Prins and W. Ramdane-Chérif (2001). “A Genetic Algorithm for the CARP and its Extensions.” Lecture Notes in Computer Science, 2037, 473–483.
50.Lacomme, P., C. Prins and W. Ramdane-Cherif (2004), "Competitive Memetic Algorithms for Arc Routing Problems”, Annals of Operations Research, 131, 159-185.
51.Lacomme, P., C. Prins and M. Sevaux (2006), “A Genetic Algorithm for a Bi-Objective Capacitated Arc Routing Problem”, Computers & Operations Research, 33 (12), 3473-3493.
52.Leea D. S., V. S. Vassiliadisb and J. M. Park (2004), “A Novel Threshold Accepting Meta-heuristic for the Job-shop Scheduling Problem”, Computers & Operations Research, 31 (13), 2199–2213.
53.Lenstra, J. K., and A. H. G. Rinnooy Kan (1976), “On General Routing Poblems”. Networks, 6, 273-280.
54.Lin, C. K. Y., K. B. Haley, and C. Sparks(1995), “A Comparative Study of Both Standard and Adaptive Versions of Threshold Accepting and Simulated Annealing Algorithms in Three Scheduling Problems”, European Journal of Operational Research, 83, 330-346.
55.Li, L.Y.O. and R.W. Eglese (1996). “An Interactive Algorithm for Vehicle Routeing for Winter-Gritting”, Journal of the Operational Research Society, 47, 217-228.
56.Maniezz, V. (2004), “Algorithms for Large Directed CARP Instances: Urban Solid Waste Collection Operational Support”, Technical Report UBLCS-2004-16.
57.Mourão, M.C. and M.T. Almeida (2000), “Lower-Bounding and Heuristic Methods for a Refuse Collection Vehicle Routing Problem”, European Journal of Operational Research, 121, 420-434.
58.Ong, T. N and Poh, K.L. (1990), “A Computerized Vehicle Routing System for Refuse Collection”, Advances in Engineering Software, 12 (2), 121-132.
59.Rogers D.S. and Tibben-Lembke R.S. (1998), Going Backwards: reverse logistics trends and practices, Reverse Logistics Executive Council, Pittsburgh.
60.Tarantilis C.D. and C.T. Kiranoudis (2002), “A List-Based Threshold Accepting Method for Job Shop Scheduling Problems”, International Journal of Production Economics, 77 (2), 159-171.
61.Tarantilis, C.D., C.T. Kiranoudis and V.S. Vassiliadis (2004), “A Threshold Accepting Metaheuristic for the Heterogeneous Fixed Fleet Vehicle Routing Problem”, European Journal of Operational Research, 152, 148-158.
62.Toussaint, K. J. and B. L. Golden (1994), “Exchange Heuristics to Improve the Clarity of Base/Time Plots”, Computers & Operations Research, 21 (5), 573-586.
63.Wøhlk, S. (2008), “A Decade of Capacitated Arc Routing”, Vehicle Routing Problem: Latest Advances and New Challenges, B.Golden, S. Raghavan and E. Wasil (eds.), Springer, 30-48.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top