- 學位論文
應用優加劣減螞蟻系統於具時窗限制的取卸貨問題
Applying Added to the superior segments and subtracted from inferior segments Ant System for Pickup and Delivery Problem with Time Windows
摘要
優加劣減螞蟻系統(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%，與文獻比較差異不大，但仍有改善空間。
並列摘要
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.
參考文獻
延伸閱讀
- 李孟澤（2008）。結合平行基因演算法與蟻群最佳化應用於具時窗限制之車輛途程問題〔碩士論文，國立臺中科技大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0061-1811200915323686
- 盧步雲（2002）。應用塔布搜尋法於含軟性時窗限制之動態需求撿取配送途程規劃問題〔碩士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu200200332
- 吳建賢（2003）。應用蟻族尋優法於生產排程問題〔碩士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu200300381
- 林孟儒（2014）。A testing procedure for the lifetime performance index ofproducts with Weibull distribution underprogressive type I interval censoring〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2014.00905
- Valsala, S., & Nair, A. R. (2016). Requirement Prioritization and Scheduling in Software Release Planning Using Hybrid Enriched Genetic Revamped Integer Linear Programming Model. Research Journal of Applied Sciences, Engineering and Technology, 12(3), 347-354. https://doi.org/10.19026/rjaset.12.2342