應用變動鄰域搜尋法於資源分配問題之研究

Solving the Resource Allocation Problem Using Variable Neighborhood Search

高淑娟(Shu-Chuan Kao)

指導教授 ： 梁韵嘉

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

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

摘要

資源分配問題（Resource Allocation Problem；RAP）存在於現今社會中眾多領域，例如全球化分配問題、醫療物資分配問題、政府分配有限預算及各項資源以推動公共建設之議題、高等教育資源分配問題以及工廠分配原料及機器設備以利其生產製造議題等等。由於所包含之領域相當廣泛，故長久以來也吸引了許許多多學者投入相關研究；然而，現實環境中資源往往為有限供應，且往往其分配對象具有相互相依與排擠競爭之特性，故在此限制之下，如何將這些有限的資源做最有效的分配，進而使所設之目標達最佳化，已成為近年來大家重視的議題。
此資源分配問題屬於NP-hard問題，過去很多學者比較偏向於數學規劃求解方式，但當資源量或者是限制式增加時，常常會造成時間上過於冗長，而產生無法有效率求解之情形。本研究主要所使用的求解方法為變動鄰域搜尋法（Variable Neighborhood Search；VNS），此方法是近年來才發展出來的一套萬用啟發式方法（Mladenoviゴ，1995），其特色在於利用改變鄰域結構的簡單觀念來進行搜尋可行解，此概念不但可使求解時間大幅縮減之外，在應用於其他組合性最佳化問題也有相當不錯的表現。
本研究主要以傳統VNS為基礎，並且著重於震動（Shaking）以及區域搜尋機制（Local Search）兩方面做重新設計與改善，另外提出一動態形式的鄰域結構數，其主要概念為透過每次進入區域搜尋之前皆必須重新調整鄰域結構數的方式，使問題架構變大時的資源分配問題也能夠以更快速的方式透過大規模變更分配資源量，做更廣泛的搜尋，且在求解時間上更佳有效率，充分顯示VNS簡單及快速的優點。

關鍵字

變動鄰域搜尋法 ； 資源分配問題 ； 數學規劃

並列摘要

Resource Allocation Problems (RAP) have been applied to many fields including Global Allocation Problem, Medical Material Allocation Problem, and Budget Allocation Problem, etc. Many researchers devote their efforts in developing new methods for tackling this problem. In reality, how to optimize the allocation of limited resources while satisfying all capacity constraints simultaneously, has caused much attention from researchers and practitioners.
RAP belongs to NP-hard problem, but most existing methods for solving RAP are mathematical programming approaches, such as dynamic programming, linear programming, and branch and bound. However, as the number of variables and constraints increase, these exact methods will have to spend a lot of time to find the optimal solution. This research, therefore, aims at applying a metaheuristics - Variable Neighborhood Search (VNS) to solve RAP. This method employs the systematic neighborhood local search to obtain the near-optimal solutions. Different from the traditional VNS structures, the proposed algorithm adopts a dynamic neighborhood structure, i.e., the number of neighborhoods is determined after the shaking operation. The test on a set of benchmark instances has successfully shown the effectiveness and efficiency of the proposed VNS algorithm on solving large size RAPs.

並列關鍵字

Variable Neighborhood Search ； Resource Allocation Problem ； Mathematical Programming

參考文獻

31.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 and Engineering, vol. 20, pp. 1019-1034, 2004.

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

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

5.吳佳娟，2004，「變動鄰域尋優法於串並聯複置配置問題之研究」，元智大學，碩士論文。

12.Avanthay, C., A. Hertz and N. Zufferey, “A variable neighborhood search for graph coloring,” European Journal of Operational Research, vol. 151, pp. 379-388, 2003.