以位置搜尋方式求解集合涵蓋問題(SCP)之研究

Abstract

本研究針對集合涵蓋問題(Set Covering Problem, SCP) ，以韓復華、陳本立對零壹 整數規劃問題所提出的位置搜尋法(Location Search Algorithm) [35][44]為基礎， 提出一最佳解演算法(Exact Solution Algorithm, MPLSA) 與兩種啟發式演算法(Heu ristic Algorithm) 。各種解法均使用ANSI C語言寫成程式，並在SUN 4/330 電腦工 作站上進行測試。 MPLSA 仍然遵循與位置搜尋法相法的分枝定限(Branch & Bound)架構，但在決定0 或 1 可以出現的最大位置，則是利用SCP 的兩個特性：(1) 限制式係數矩陣元素為0 或 1 ，(2) 限制式不等號右手邊值為1 ，將其計算步驟簡化修正，以提高效率。以240 個乳數產生(Randomly Generated)之較高密度(15%-30%) 問題作測試 (限制式數目為 100 與200 二種，變數數目為1000、1500與2000三種) ，結果顯示MPLSA 之執行時間 為原位置搜尋法的1/4 ，且較高密度之問題其求解時間較少。並且發現MPLSA 的第一 個較佳可行解是Prime Cover 且是1/K Optimal Cover 。 第一類啟發式解法(C1PC 與C2PC) 是依MPLSA 之搜尋特性分析，以兩個相鄰較佳可行 解間所搜尋過的路徑數(No. of Fathomed Node)，作為停止搜尋的控制參數。第二類 啟發式解法(2/1 OPT、2/1 + 3/2 OPT 、2/1 + 3/1 OPT 與2/1 + 3/1 + 3/2 OPT)則 是以MPLSA 的第一個較佳可行解作為起始解，再合併λ/K Optimal Search[16] 對起 始解改善(Solution Improvement)。 以720 個乳數產生之演算例題 (密度5%-30%，限制式與變數數目同前) 測試結果顯示 ，第一類啟發式解法之誤差率隨密度之增加而明顯減小。第二類啟發式解法其誤差率 較穩定，平均而言最低誤差率約為4.5%(2/1 + 3/1 + 3/2 OPT) ，其求解時間在低密 度問題時較高。 本文並以中華航空公司部份航線班機上之人員排班為應用簡例[45]，依據台北－香港 、台北－東京與台北－洛杉磯三條航線一週內之68個航班，以及由此68個航班產生25 6 個可行航班組合(Pairing，由[45]產生) 所產生的SCP 問題(68 個限制式，256 個 零壹變數，密度11.6%)，以第二類啟發式解法求得最佳解。