多重服務之工廠選址問題

The Multi-service Facility Location Problem

林娉婷(Lin, Ping Ting)

指導教授 ： 廖崇碩

國立清華大學/工學院/工業工程與工程管理學系/碩士(2015年)

摘要

我們提出了著名的工廠選址問題的衍生，稱為多重服務之工廠選址問題。在此問題中，每個工廠能夠提供多種不同的服務，而每個客戶對不同的服務有不同的需求，此問題的目標是找到一個開啟工廠的位置集合，決定其中提供的服務給相對應的客戶，使得所有客戶的需求皆被滿足，並且最小化總成本，包括開啟工廠的成本、提供服務的成本及運輸成本。為了解決此問題，我們修改了區域搜尋啟發式演算法，並且提出了一個近似演算法和理論分析，在本研究中，證明了我們提出的演算法所得到的結果最差不會大於三倍的最佳解，並且將演算法實作，透過實驗結果驗證了我們的演算法的效率和有效性。

關鍵字

工廠選址 ； 多重服務 ； 近似演算法

並列摘要

We propose a generalization of the well-known facility location problem, called the multi-service facility location problem. In this problem, each facility has the ability to provide at most p kinds of distinct services, and each client has different requirements from the p kinds of services. The objective is to select a subset of facilities and to identify its corresponding service assignment to clients such that the requirements of each client can be satisfied, and the total cost, including the facility setup cost, service cost and connection cost is minimized. To solve this problem, we modify a local search heuristic algorithm, and present an approximation algorithm with theoretical analysis. In this study, we prove that our algorithm has a locality gap of 3 for this problem. We also implement the algorithm and the experimental result demonstrates its efficiency and effectiveness.

並列關鍵字

facility location ； multi-service ； approximation algorithm

參考文獻

Local search heuristics for k-median and facility location problems. SIAM J.

2. J. Byrka and K. Aardal. An optimal bifactor approximation algorithm for the

metric uncapacitated facility location problem. SIAM Journal on Computing,

3. M. Charikar, and S. Guha. Improved combinatorial algorithms for the facility

location and k-median problems. In Foundations of Computer Science, 1999.