Please use this identifier to cite or link to this item:
標題: 解無限容量P-中位問題之兩層式基因區域搜尋法
A Two Layered Genetic Local Search Algorithm for the Uncapacitated P-median problem
作者: 吳建學 
Wu, Jan-Shiue 
關鍵字: Two Layered Genetic Local Search Algorithm;兩層式基因區域尋法;metaheuristic;Genetics Algorithm;Local Search;P-median problem;超啟發式演算法;基因演算法;區域搜尋法;P-中位問題
出版社: 資訊科學研究所
本研究將提出一種混合型的超啟發式演算法(Metaheuristic),並應用於解P-中位問題(P-median Problem)上,演算法之主體為基因區域搜尋法(Genetic Local Search Algorithm),而以兩層式的架構來解問題,故稱作之為兩層式基因區域搜尋演算法(Two Layered Genetic Local Search Algorithm)。
因近年來物流產業的發展,設施位置問題(Facility Location Problem)因而受到重視,如何選置適當的位置以降低產業成本,變得相當重要,而設施位置問題中不乏重要的問題,本研究探討的P-中位問題便是諸多設施位置問題中的一個,本研究主要將所提出之演算法應用到P-中位問題,並根據問題的特性設計適合的基因運算元與區域搜尋法,以期達到求解最佳解的最終目的。透過本研究所提出之演算法來求解OR-Library上的P-中位問題例題,可以在有效率的時間內得到相當不錯的解。

The P-median problem belongs to the category of the facilities location problems and is a well-studied combinatorial optimization problem. Give a set of N locations , the P-median problem aims to choose p locations out of them as the locations of facilities so as to satisfy the demand of the users at the other N-P locations with the minimum transportation cost. Each user is supplied by the nearest facility. In this thesis, we consider only the uncapacitated P-median problem, that is , the amount that each facility can supply is unlimited.
We proposed a two layered genetic local search algorithm for this problem. The first layer acts as the global search and the second layer acts as the local search. We test our method on the OR Library benchmarks and compare the results with another method's results.
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM


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