萬用啟發式演算法求解p 中位問題

Metaheuristic for Solving p-Median Problem

袁芳杰(Fang-Chieh Yuan)

指導教授 ： 胡黃德

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

摘要

廠址選擇在區位指派問題裡主要是在選擇一良好的區位並能提供顧客最佳服務及使得區位設置成本最小化。但顧客對區位的需求會隨著時間而有所變更。因此，無論是公家機關或是私人機構在設廠初期能有效的減少設施設置成本便成為一個很重要的問題。而在設施區位問題中，相當有名的問題是 p 中位問題。為了求解 p 中位問題我們使用基因演算法（GA）來進行求解。特別的是，我們除了使用傳統的基因演算法進行求解外，還加入了變動鄰域搜尋解（VNS），並與OR-Library測試例題來相比較。

關鍵字

設施區位，p中位問題，基因演算法 (GA)，變動鄰域搜尋解 (VNS)

並列摘要

Basic premises in location allocation problems have been to select appropriate locations and design customers to these locations to minimize cost and provide necessary service. These problems recognize that demand may change over time and attempt to account for the effects of these changes in the initial set of locations. However, future demand often is not known with certainty and has been approximated by a deterministic surrogate. For these reasons, how to reduce the costs by set up facility locations became the most important problem both in public and private sector. One of the most well-known facility-location problems is the p-median problem. We propose a genetic algorithm (GA) to solve p-median problem. The proposed GA uses not only the orthodox genetic processes but also merges a new heuristic “variable neighborhood search (VNS)” in this work. The result is compared with OR-Library test problems.

並列關鍵字

facility location, p-median problem, genetic algorithm (GA), variable neighborhood search (VNS)

參考文獻

44. 李珮芸，「大陸台商鞋品物流據點佈署之探討」，國立成功大學，碩士論文，2003。

4. Densham, P. J. and Rushton, G.. (1992). "A more efficient heurisric for solving large p-median problems," Papers In Regional Science, 71, 307-329.

6. Erkut, E., Myroon T. and Strangway, K. (2000). "TransAlta redesigns its service delivery network," Interfaces, 30(2), 54-69.

7. Fitzsimmons, J. A. and Austin, A. L. (1983). "A warehouse location model helps taxes comptroller select out-of-state audit offices," Interface, 13(5), 40-46.

8. Funk, Appel, Roch, D. H., Pellegrini, and Muller (1987). Knowledge acquisition in expert system assisted diagnosis: a machine learning approach. In Proc. AIME-87, 99-103. Springer Verlag