請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64459
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 楊烽正 | |
dc.contributor.author | "Huan-Ping, Chang" | en |
dc.contributor.author | 張恒彬 | zh_TW |
dc.date.accessioned | 2021-06-16T17:48:26Z | - |
dc.date.available | 2020-08-12 | |
dc.date.copyright | 2012-08-17 | |
dc.date.issued | 2012 | |
dc.date.submitted | 2012-08-13 | |
dc.identifier.citation | 1.Baran B, Schaerer M. A multiobjective ant colony system for vehicle routing problem with time windows. 2003:97-102.
2.Bent R, Hentenryck PV. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Computers & Operations Research 2006;33:875-893. 3.Doerner K, Hartl RF, Reimann M. Ant colony optimization applied to the pickup and delivery problem. Vienna: SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, 2000. 4.Goel A, Gruhn V. A General Vehicle Routing Problem. European Journal of Operational Research 2008;191:650-660. 5.Hoong Chuin LAU, Zhe L. Pickup and Delivery with Time Windows: Algorithms and Test Case Generation. 2001. 6.Junger M, Reinelt G, Rinaldi G. Chapter 4 The traveling salesman problem. In: M.O. Ball TLMCLM, Nemhauser GL (eds). Handbooks in Operations Research and Management Science: Elsevier, 1995:225-330. 7.Lau HC, Liang Z. Pickup and delivery with time windows: algorithms and test case generation. Tools with Artificial Intelligence, Proceedings of the 13th International Conference on, 2001:333-340. 8.Li H, Lim A. A metaheuristic for the pickup and delivery problem with time windows. Tools with Artificial Intelligence, Proceedings of the 13th International Conference on, 2001:160-167. 9.Mitrović-Minić S, Laporte G. Waiting strategies for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological 2004;38:635-655. 10.Nanry WP, Wesley Barnes J. Solving the pickup and delivery problem with time windows using reactive tabu search. 1999. 11.Pankratz G. A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows. OR Spectrum 2005;27:21-41. 12.Parragh S, Doerner K, Hartl R. A survey on pickup and delivery problems: Part I: Transportation between customers and depot. Journal fur Betriebswirtschaft 2008;58:21-51. 13.Parragh S, Doerner K, Hartl R. A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations. Journal fur Betriebswirtschaft 2008;58:81-117. 14.Rizzoli AE, Oliverio F, Montemanni R, Gambardella LM. Ant Colony Optimisation for vehicle routing problems: from theory to applications. 2004. 15.Ropke S, Cordeau JF. Branch and cut and price for the pickup and delivery problem with time windows. Transportation Science 2009;43:267-286. 16.Solomon MM. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 1987;35:254-265. 17.李泰琳, 張靖. 調適型導引螞蟻演算法求解時窗收卸貨問題之研究. 運輸計 劃季刊 2010;39:99-132. 18.林典翰. 優加劣減螞蟻擇段系統應用於組合問題. 臺灣大學工業工程學研究 所學位論文: 臺灣大學, 2004. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64459 | - |
dc.description.abstract | 優加劣減螞蟻系統(Added to the superior segments and subtracted from inferior segments Ant System, ASDSAS)是Lin and Yang 所提出的ACO 技術改良。針對表現較佳之螞蟻群所建構出的解添加費洛蒙;而對表現較差之螞蟻群所建構出的解扣減費洛蒙,能有效利用每隻螞蟻所求得的資訊,幫助螞蟻尋找最佳解。且被證明在求解旅行推銷員問題、物件裝箱問題、及零工式生產問題上有不錯的表現。因此本研究使用優加劣減螞蟻系統來求解具時窗限制的取卸貨問題(Pickup and Delivery Problem with Time Windows, PDPTW),並提出考慮時間(TASDSAS)與考慮距離(ASDSAS)兩種優化模式來求解。為驗證本研究所提的演算機制,本研究將Solomon 國際標竿題庫中的VRPTW 問題轉換成符合PDPTW 問題限制之例題,產生出小、中、大例題進行測試,且另外針對時窗窄的狀況比較TASDSAS 與ASDSAS 的差異。結果顯示優加劣減螞蟻統表現優於典型ACO 技術,且中型例題平均求解誤差僅1.69%,與文獻比較差異不大,但仍有改善空間。 | zh_TW |
dc.description.abstract | Added to the superior segments and subtracted from inferior segments Ant System(ASDSAS) is the ACO technical improvements proposed by Lin and Yang. Pheromone is added to the superior segments and subtracted from the inferior segments. The effective use of information obtained by the ants help the ants finding the best solution. Having good performance for solving the traveling salesman problem(TSP), the bin packing problem(BPP), the job shop scheduling problem(JSP). In this study, use ASDSAS to solve the Pickup and Delivery Problem with Time Windows(PDPTW), and consider the time (TASDSAS) and consider the distance (ASDSAS) two optimization models to solve. In order to verify that the proposed calculation mechanism, the Solomon international benchmark in the VRPTW was converted to meet the PDPTW Problem restrictions, and produce small, medium and large examples, and another narrow time windows constrain comparison difference between TASDSAS and ASDSAS. The results show ASDSAS performance better than the typical ACO technology, and only 1.69% of the average solution error for
medium-sized example. There is no big difference between our results and literature, but still has room for improvement. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T17:48:26Z (GMT). No. of bitstreams: 1 ntu-101-R99546024-1.pdf: 1759568 bytes, checksum: d3e7bfe6ab1c7b2ab369d62f5dc64801 (MD5) Previous issue date: 2012 | en |
dc.description.tableofcontents | 中文摘要 .............................................. i
Abstract ............................................ ii 第一章 緒論 ........................................... 1 1.1 研究背景 .......................................... 1 1.2 研究動機與目的...................................... 2 1.3 研究範疇與架構...................................... 3 1.4 章節概要 .......................................... 5 第二章 文獻探討 ........................................ 6 2.1 一般化取卸貨問題 .................................... 6 2.2 PDP 與PDPTW 問題 .................................. 7 2.2.1 PDP 與PDPTW 問題定義 ............................. 7 2.3 PDPTW 求解方法回顧 ................................. 11 2.3.1 PDPTW 的最佳解法 ................................. 11 2.3.2 PDPTW 的啟發式解法 ............................... 12 2.4 蟻拓最佳化技術....................................... 13 2.4.1 螞蟻系統.......................................... 15 2.4.2 螞蟻屯拓系統 ...................................... 20 2.4.3 優加劣減螞蟻系統 ................................. 22 2.4.4 蟻拓最佳化技術應用於取卸貨問題 ...................... 30 2.4.5 蟻拓最佳化技術的其他應用 ........................... 30 2.5 文獻探討結語 ...................................... 31 第三章 應用優加劣減螞蟻系統於具時窗限制的取卸貨問題........... 32 3.1 具時窗限制的取卸貨問題 .............................. 33 3.1.1 取卸貨順序限制.................................... 34 3.1.2 時間窗限制....................................... 36 3.1.3 車容量限制 ...................................... 38 3.1.4 衡量指標........................................ 39 3.2 優加劣減螞蟻系統設計 ............................... 43 3.3 優加劣減螞蟻系統應用於具時窗限制的取卸貨問題 ........... 44 3.3.1 ASDSAS 求解PDPTW 問題的演算流程 .................. 44 3.4 建構途程解 ........................................ 47 3.4.1 取卸貨組合費洛蒙矩陣 .............................. 47 3.4.2 候選清單......................................... 48 3.4.3 取卸貨組合費洛蒙 ................................. 52 3.4.4 關聯啟發式運算值 ................................. 53 3.5 改善途程解 ........................................ 54 3.5.1 路徑間1-1 結點交換法 ............................. 55 3.5.2 路徑間1-0 結點交換法 ............................. 55 3.5.3 路徑內結點交換法 ................................. 56 3.5.4 區域搜尋演算流程 ................................. 56 3.6 紀錄資訊 .......................................... 56 3.7 小結 ............................................. 60 第四章 優加劣減螞蟻系統求解系統及範例驗證 ................... 61 4.1 優加劣減蟻拓求解系統實作 ............................. 61 4.1.1 系統人機界面 ..................................... 61 4.2 測試例題轉換 ....................................... 65 4.3 演算法穩健性測試 .................................... 66 4.4 演算成效分析 ....................................... 68 4.4.1 中型例題測試 ..................................... 69 4.4.2 大型例題測試 ..................................... 73 4.4.3 繞行時間評量的ASDSAS ............................. 74 4.5 小結 ............................................. 75 第五章 結論與未來研究建議 ................................ 76 5.1 結論 ..................................................... 76 5.2 未來研究建議 ...................................... 76 參考文獻 .............................................. 77 附錄 ................................................. 80 | |
dc.language.iso | zh-TW | |
dc.title | 應用優加劣減螞蟻系統於具時窗限制的取卸貨問題 | zh_TW |
dc.title | Applying Added to the superior segments and subtracted from
inferior segments Ant System for Pickup and Delivery Problem with Time Windows | en |
dc.type | Thesis | |
dc.date.schoolyear | 100-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 徐旭昇,吳政鴻 | |
dc.subject.keyword | 蟻拓最佳化技術,優加劣減螞蟻系統,具時窗限制的取卸貨問題, | zh_TW |
dc.subject.keyword | Ant Colony Optimization,Added to the superior segments and subtracted from inferior segments Ant System,Pickup and Delivery Problem with Time Windows, | en |
dc.relation.page | 87 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2012-08-14 | |
dc.contributor.author-college | 工學院 | zh_TW |
dc.contributor.author-dept | 工業工程學研究所 | zh_TW |
顯示於系所單位: | 工業工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-101-1.pdf 目前未授權公開取用 | 1.72 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。