應用優加劣減螞蟻系統於具時窗限制的取卸貨問題

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%，與文獻比較差異不大，但仍有改善空間。

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.