變動鄰域搜尋法於多目標專案投資組合問題之研究

Variable Neighborhood Search for Multiobjective Project Portfolio Problem

郭男極(Nan-Chi Kuo)

指導教授 ： 梁韵嘉

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

https://doi.org/10.6838/YZU.2008.00198

摘要

在現代企業中，當決策者同時面對多個欲投資的專案時，於有限的資金和資源下，還要考慮欲投資專案的時間性與相依性，甚至必須配合公司發展策略或決策者主觀偏好等因素時，如何決定這些龐大專案的投資組合以獲得最大利潤，是決策者所需面對的重要議題之一。由於決策者關心的目標往往不只有一個，故投資組合問題屬於多目標問題，也屬於NP-Hard問題，它會隨著投資專案數量的增加，而增加問題的複雜性，大幅增加求解時間，窮舉法(Exhausive Enumeration)僅能解決小型的專案投資組合問題，遇到大量專案數時，將無法在合理的時間內求解，不符合實際需求，因此，必須藉由啟發式演算法來處理。

本研究利用變動鄰域搜尋法(Variable Neighborhood Search；VNS)求解多目標專案投資組合問題，以各期之利潤及資產週轉率最大化為目標，決定有效的投資組合(Efficient Portfolio)，即為柏拉圖前緣。根據不同的鄰域結構與局部搜尋方式，建立三種不同的VNS方法，分別為VNS-I、VNS-II和VNS-III，並且在兩題實際案例與九題不同規模的隨機產生題型進行測試，以窮舉法所求得的參考柏拉圖集合進行比較，使用E/CE、Hit Rate、 和非支配解個數等四項衡量指標來評估三種演算法的績效表現，最後，在各種試題的測試下以VNS-III表現最佳，其次是VNS-II，而VNS-I求解最不穩定；也證明了VNS-III與VNS-II可在合理時間找到不錯的有效投資組合。

關鍵字

專案投資組合問題、窮舉法、變動鄰域搜尋法、柏拉圖前緣

並列摘要

In most of modern enterprises, selecting the “best” project portfolio out of a given set of investment proposals is an importance issue for decision-makers. They must consider the time and interdependence of the projects and conform to the company strategy or preference under limited resource and funds. The project portfolio problem belongs to multiple-objective problem and also a NP-Hard problem. It is impractical to use exhausive enumeration to determine all of project portfolios within a reasonable computation time as the number of projects grows. Therefore, this research aims at employing a metaheuristics - Variable Neighborhood Search (VNS) to find efficient portfolios (i.e., Pareto front). According to the differences of the neighborhood structures and local search, three kinds of VNS algorithms - VNS-I, VNS-II and VNS-III are proposed and four measures - E/CE, Hit Rate, and the number of non-dominated solutions are employed to evaluate the performance of the proposed algorithms. The result of our experiments shows that VNS-III procedure outperforms the others and the performance of VNS-I procedure is the most unstable. Furthermore, both VNS-II and VNS-III can find satisfied efficient portfolios within reasonable computation time.

並列關鍵字

Project Portfolio, Exhausive Enumeration, Variable Neighborhood Search, Pareto Front

參考文獻

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

陳啟嘉，2006，「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」，元智大學，碩士論文。

林昆霖，2005，「子群體基因演算法於多目標排程之應用─以PCB鑽孔作業為例」，元智大學，碩士論文。

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

蕭裕民，2006，「蟻群最佳化演算法於多目標平行機台排程問題之研究」，元智大學，碩士論文。