查詢結果分析
來源資料
頁籤選單縮合
題名 | 調適型導引螞蟻演算法求解時窗收卸貨問題之研究=Solve Pick Up and Delivery Problem with Time Windows Via A Guided Adaptive Ant Colony System |
---|---|
作者 | 李泰琳; 張靖; | 書刊名 | 運輸計劃 |
卷期 | 39:1 2010.03[民99.03] |
頁次 | 頁99-132 |
分類號 | 557.445 |
關鍵詞 | 螞蟻演算法; 導引區域搜尋法; 時間窗收卸貨問題; Ant colony optimization; Guided local search; Pickup and delivery problem with time windows; |
語文 | 中文(Chinese) |
中文摘要 | 本研究主要結合導引區域搜尋技術 (guided local search, GLS) 與李泰琳等人提出的調適型螞蟻演算法 (adaptive ant colony system, AACS),設計調適型導引螞蟻演算法(guided adaptive ant colony system, GAACS) 求解時窗收卸貨問題(pickup and delivery problem with time windows , PDPTW)。首先,引用李泰琳等人所提出之問題規模精簡策略與關連式旅行成本網絡結構,將PDPTW 轉換為無時窗的近似收卸貨問題 (similar pickup and delivery problem, SPDP),其優點為在計算過程中不需要考慮時窗限制;其次,提出GAACS 演算法整合的觀念。演算法績效測試為應用國際標準題庫VRPTW 例題,配合Lau 與Liang (2002)方法進行修改,產生具有標竿解之PDPTW 例題18 題進行測試,問題規模皆為100 個作業,結果顯示GAACS 可以在25.9 分鐘平均時間,求得與標竿解平均差異僅1.8%之近似最佳解。 |
英文摘要 | The Pick Up and Delivery Problem with Time Windows (PDPTW) was solved via the proposed Guided Adaptive Ant Colony System (GAACS), which was integrated by the Guided Local Search (GLS) and Adaptive Ant Colony System (AACS) proposed by Lee Tai-Lin, etc. However, in order to solve the PDPTW more efficiently and effectively, a PDPTW was transferred to be a new similar PDP (SPDP) without time window via the Time Window Partitioning and Discretization Strategy. In order to show the contribution of the GAACS, 18 Solomon benchmark VRP problems were transferred to be PDPTW problems via the method developed by Lau and Liang. According to the computation results, we obtained the average percentages of errors of the best published solutions among18 PDPTW test instances, with 1.80% and an average computation time of 25.9 minutes. This shows that our proposed GAACS method can solve PDPTW accurately in a reasonable time. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。