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

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

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