調適型導引螞蟻演算法求解時窗收卸貨問題之研究

Solve Pick up and Delivery Problem with Time Windows via a Guided Adaptive Ant Colony System

李泰琳(Tai-Lin Li) ； 張靖(Ching Chang)

《運輸計劃季刊》 39卷1期 (2010/03) Pp. 99-132

https://doi.org/10.6402/TPJ.201003.0099

摘要

本研究主要結合導引區域搜尋技術(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.

並列關鍵字

Ant colony optimization ； Guided local search ； Pickup and delivery problem with time windows

參考文獻

Fabian, J.,Perez, L.(2005).A Meta-Heuristic Applied for a Topologic Pickup and Delivery Problem with Time Windows Constraints.Lecture Notes in Computer Science.3516,924-928.

李泰琳、張靖(2008)。應用時窗分割與整數化策略簡化時窗收卸貨問題之研究。運輸學刊。20(3)，313-350。

Dorigo, M.,Gambardella, L. M.(1997).Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.IEEE Transactions on Evolutionary Computation.1(1),53-66.

Dorigo, M.(1992).Optimization, Learning, and Natural Algorithms.Dipartimento diElettronica e Informatica, Politecnico di Milano.

李泰琳、張靖、卓裕仁(2007)。調適型螞蟻演算法應用於旅行推銷員問題之研究。運輸學刊。19(1)，89-120。