Please use this identifier to cite or link to this item:
標題: 解單純設施位址問題之基因區域搜尋法
A Genetic Local Search Algorithm with Lagrangean Heuristics for the Simple Plant Location Problem
作者: 劉東育
Liu, Dongyu
關鍵字: Location problem
Genetic local search algorithm
Lagrangean heuristics
出版社: 資訊科學研究所
摘要: 單純設施位址問題(simple plant location problem)在組合最佳化(combinatorial optimization)的領域是個廣泛被研究的問題,目的是在所有的設施(plant)中選出一群設施來滿足所有客戶的需求而且花費的成本最小。在本篇論文中將介紹拉格蘭茲啟發式演算法(Lagrangean algorithm),基因區域搜尋法(genetic local search algorithm)以及結合拉格蘭茲啟發式演算法和基因區域搜尋法的混合型基因區域搜尋法(genetic local search with Lagrangean heuristics)來解決單純設施位址問題。拉格蘭茲啟發式演算法是使用拉格蘭茲鬆弛法(Lagrangean relaxation)與次梯度最佳化(subgradient optimization)並配合啟發式演算法(heuristics)來解決單純設施位址問題,基因區域搜尋法是用來解決大型的組合最佳化問題的一個強而有力的演算法,它是一種產生最佳解或近似最佳解的演算法,此處也將針對基因區域搜尋法在單純設施位址問題的解法做一個介紹,最後我們將會利用上述兩種演算法的優點來設計一個混合型的演算法,在解決單純設施位址問題當中可得到一個比上述兩種方法還好的結果,在論文的最後也提供這三種方法與一些傳統的啟發式演算法的實驗數據,並對這些方法做比較。
The simple plant location problem is one of the important combinatorial optimization problems and has attracted much attention for many years. It aims to locate a set of plants so that a set of clients can be supplied by them at the minimum cost. In this thesis, we proposed a hybrid metaheuristics for this problem. We first use a Lagrangean heuristic applies the subgradient optimization method to find the solution for the dual problem obtained by Lagrangean relaxation. After the reduction of the solution space, we then apply a genetic local search algorithm to search for the optimal solution. The experimental results of our method on the standard OR Library benchmarks reveal that our method has very good performance.
Appears in Collections:資訊科學與工程學系所



Show full item record
TAIR Related Article

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.