集合涵蓋問題(SCP)啟發式解法之設計

Abstract

本研究針對集合涵蓋問題 (Set Covering Problem ，SCP) ，以韓復華、 黃銘崇對集合涵蓋問題所提出的 SCP位置搜尋法(Modified Positive Location Search Algorithm，MPLSA)[2][22] 與文獻上之貪心型解法( Greedy-Type Heuristic Method) [9][18][19]為基礎，利用混合解集( Hybrid Solution) 的概念，設計出一混合啟發式解法 HYBRID1 (Hybrid Heuristic of MPLSA & Greedy)；並且合併交換變數(λ/K Optimal Search)改善混合起始解，而成 HYOPT1(2/1 OPT)□HYOPT2(2/1+3/1 OPT) 、HYOPT3(2/1+3/2 OPT)與HYOPT4(2/1+3/1+3/2 OPT)等四種啟發式解法。 各種解法(包含文獻上的解法SCAMP與Greedy均使用ANSI C語言寫成程式， 針對 Vasko文獻[19]中之例題測試題庫 (共31題，100至200個限制式 ，400至2000個變數，密度5%至20%)，在 SUN 4/330 電腦工作站上進行測 試、比較。測試結果顯示本研究所設計的四種混合解法，針對密度為15% 及 20% 的15題高密度問題時，較Vasko 所提之SCAMP 解法，在平均精確 度比較上有較佳的結果；但對低密度(5% 及15%)的16個問題，平均而言則 略差於SCAMP 。值得一提的是，本研究所設計的HYOPT3及HYOPT4，平均只 須花費20秒至23秒，便可求解到全部八個高密度(20%) 問題的最佳解。針 對全部的31個問題，本研究所設計的混合解法HYOPT4，平均精確度 為1.75% ；而Vasko 所提之解法SCAMP ，平均精確度為1.77% ； HYOPT4 略優於SCAMP 。就整個結果而言，不論考慮到精確度或是求解效率，本研 究所設計的混合解法，在針對高密度的集合涵蓋問題時，可作為不錯的求 解工具。