變動鄰域搜尋法於多目標資源分配問題之研究

Variable Neighborhood Search for Multi-Objective Resource Allocation Problem

莊佳穎(Chia-Ying Chuang)

指導教授 ： 梁韵嘉

元智大學/工程學院/工業工程與管理學系/碩士(2009年)

摘要

在現實環境中，資源分配問題(Resource Allocation Problem, RAP)的應用相當廣泛，例如：工廠原物料分配、人力資源分配、醫療資源分配、專案預算分配、武器目標指派等問題，皆為針對有限的資源在滿足限制規範下進行分配，使期望的目標得到最佳化，而通常決策者對於資源分配問題所關心的目標不會只有一個，比如公司主管對於人力資源的指派除了期望能夠降低整體的人事成本外，也同時期望能夠獲得整體高額的工作效率，而此為所謂的多目標決策資源分配問題，此類問題在近幾年成為相當受重視的議題。
資源分配問題是屬於NP-hard的問題，當變數增加或問題規模很大時，利用精確方法來求解時會耗用很多時間，不符合實務上的效益，而啟發式演算法則是另外一種解決方法，可以在合理的時間內求得滿意的結果。本研究所應用的方法為變動鄰域搜尋法(Variable Neighborhood Search, VNS)，乃是一套近年來被廣為應用的啟發式演算法之一，過去研究顯示，VNS在求解組合性最佳化問題有很好的表現。
本研究的變動鄰域搜尋法根據不同的鄰域結構、基準解的選擇方式與擾動時機衍生出十二種不同的VNS，藉由文獻上測試範例及隨機產生的測試例題作實驗，應用柏拉圖最佳解(Pareto Optimal Solutions)的概念進行求解，將實驗結果與窮舉法所求的柏拉圖前緣作比較，並使用 、Hit Ratio、Accuracy Ratio當作演算法績效衡量指標，其實驗結果顯示，VNS-XII整體表現最好，此外，在依問題大小而改變鄰域結構數的設計，可以大幅減少搜尋時間且有效率的找到大部分柏拉圖最佳解，驗證了VNS求解多目標資源分配問題的可行性。

關鍵字

資源分配問題；變動鄰域搜尋法；柏拉圖最佳解

並列摘要

Resource Allocation Problems (RAP) have been widely applied to different real problem such as product allocation, resource distribution, project budgeting, weapon-target assignment, etc. The RAP aims at optimizing expected goals using limited resources. For example, an executive officer may expect not only to decrease personnel expenses but also promote higher efficiency simultaneously. It can be considered as the Multi-Objective Resource Allocation Problem that has received highly attention in recent years.
RAP falls in the category of NP-Hard problems. When the number of variables increases the computational time of the exact methods grows exponentially. Therefore, metaheuristic algorithms which are able to find satisfying results within reasonable time have attracted more attention. Variable Neighborhood Search (VNS), one of the extensively used metaheuristic algorithms, has shown its performance in solving combinatorial optimization, and therefore is chosen as the research method in this study.
According to different neighborhood structures, base solution selection strategy and the timing of perturbation, twelve variations of VNS algorithms are proposed. Several sets of test instances obtained from the literatures and generated by the author, are used to compare the performance of algorithms. The Pareto front obtained from the competing algorithms are compared with the reference Pareto front by the exhaustive enumeration method, and three performance measures - Hit Ratio, Accuracy Ratio are employed. The results revealed that VNS-XII performs the best in general. In addition, the attempt of using different size of neighborhoods based on the number of workers is also implemented. This design further improves the efficiency of the proposed algorithm. This study has successfully shown the feasibility and promising of VNS on solving multi-objective resource allocation problems.

並列關鍵字

Resource allocation problem；Variable Neighborhood Search；Pareto Optimal Solutions

參考文獻

3. 田佳芸，2007，「變動鄰域搜尋法於雙目標平行機台排程問題之研究」，元智大學，碩士論文

8. 郭男極，2008，「變動鄰域搜尋法於多目標專案投資組合問題之研究」，元智大學，碩士論文。

9. 高淑娟，2008，「應用變動鄰域搜尋法於資源分配問題之研究」，元智大學，碩士論文。

25. Hou, Y. C. and Y. H. Chang, “A New Efficient Encoding Mode of Genetic Algorithms for the Generalized Plant Allocation Problem,” Journal of Information Science Engineering, vol.20, pp.1019-1034, 2004.

13. 陳怡靜，2005，「變動鄰域搜尋法於串並聯系統複置配置問題之研究」，元智大學，碩士論文。