應用二階段蟻群演算法求解P-中位問題之研究

Applying Two-Stage Ant Colony System to Solve the P-Median Problem

陳家和(Chia-Ho Chen) ； 丁慶榮(Ching-Jung Ting)

《運輸學刊》 19卷4期 (2007/12) Pp. 383-404

https://doi.org/10.6383/JCIT.200712.0383

摘要

P-中位問題是一個典型的設施區位問題，在實務上已有廣泛的應用，且亦有許多研究進行求解。因該問題屬於NP-hard的組合最佳化問題，故許多研究均採用啟發式演算法進行求解。本研究提出二階段蟻群演算法，以求解無容量限制與有容量限制的P-中位問題。接著，採用OR-Library中所提供的標竿測試例題來驗證TACS的求解績效。根據求解結果發現，針對無容量限制的P-中位問題，TACS在40題例題中可求得30題的文獻最佳解，且與文獻最佳解之平均誤差百分比只有0.02%；而在有容量限制的P-中位問題部分，TACS 則可求得所有例題之文獻最佳解。求解結果亦顯示，TACS在求解P-中位問題方面有不錯的求解績效與穩定性。

關鍵字

巨集啟發式演算法 ； P-中位問題 ； 二階段蟻群系統演算法

並列摘要

The P-median problem is a classical type of location problems. The P-median problem belongs to the class of NP-hard. Many heuristic approaches have been proposed to obtain optimal or near-optimal solutions. This paper aims to develop a Two-Stage Ant Colony System (TACS) to solve the Uncapacitated and Capacitated P-median problems. The performance of TACS is tested on benchmark instances from the OR-Library and compared with other methods in the literature. For the Uncapacitated P-median problem instances, the TACS can achieve best-known solutions in 30 out of 40 instances and the average deviation from the best-knownsolutions is only 0.02%. On the other hand, the TACS can obtain the best-known solutions in all Capacitated P-median problem instances. The results reveal that the TACS is effective to solve P-median problems.

並列關鍵字

Meta-heuristic ； P-median problem ； Two-stage ant colony system

參考文獻

陳家和、丁慶榮()。

陳家和、丁慶榮(2005)。應用螞蟻演算法於時窗限制車輛途程問題之研究。運輸學刊。17(3)，261-280。

蘇純繒、翁瑞聰(2004)。以螞蟻群聚最佳化整合基因演算法求解無資源限制單一指派中位轉接點問題。運輸學刊。16(2)，99-114。

Alp, O.,Erkut, E.,Drezner, Z.(2003).An Efficient Genetic Algorithm for the P-median Problem.Annals of Operations Research.122(1-4),21-42.

OR-Library