Using Hybrid Genetic Algorithms to Solve Discrete Location Allocation Problems with Rectilinear Distance

運用混合式遺傳演算法求解Location-allocation問題

田方治(Fang-Chih Tien) ； 謝廣漢(Kuang-Han Hsieh) ； 鄭純媛(Chun-Yuan Cheng) ； 劉季旋(Chi-Shuan Liu)

《工業工程學刊》 24卷1期 (2007/01) Pp. 1-19

https://doi.org/10.29977/JCIIE.200701.0001

摘要

本研究連用一混合式遺傳演算法(Genetic Algorithm, GA)成功地求解無産能限制單一分配之Location-allocation問題(LAP)，其以K-means演算法將顧客依垂直距離作群聚分析，並以所得之群聚及中心點作爲遺傳演算法之起始解；本方法將LAP問題解編成兩組相互關聯之碼（染色體），再利用優生原則(elitism)、區域搜尋(local search)、距離式突變法(distance-based mutation)及多重起始法(multi-start)有效地求取最佳解或其進似最佳解。爲有效驗證此本研究之方法，KGA、HGA、LMGA及TGA四種不同之GA以六組常用之驗證問題作比較，並再將本方法與模凝退火法[4]及SOFMGR法[14]作深入之比較，經實驗得知所提出之混合式遺傳演算法可迅速且有效地求解此問題。

關鍵字

Location-allocation problem ； 遺傳演算法 ； K-means演算法

並列摘要

This paper presents a hybrid genetic algorithm to solve the uncapacitated location allocation problems as a combinatorial optimization problem. The proposed method incorporates a modified K-means algorithm that clusters the customers into groups based on the rectilinear distance, and then the initial population of solutions is calculated according to the derived centers of clusters. The hybrid genetic algorithm consists of two evolutionary processes synchronized with each other. It uses the elite strategy, local search, multi-start mechanism and distance-based mutation to efficiently obtain the optimal or approximated solutions. In order to verify the effectiveness of the proposed method, four GAs-KGA, HGA, LMGA and TGA, are built and compared. Furthermore, using six commonly used test problems, the performance of the proposed method is evaluated relative to the Simulated Annealing method [4] and the SOFMGR method [14] as benchmarks. Experimental results show that the proposed method is excellent in quality of solutions and speed of computation.

並列關鍵字

location-allocation problem ； combinatorial optimization problem ； K-means algorithm ； genetic algorithms

參考文獻

Brimberg, J.,N. Mladenović(1996).Solving the continuous location-allocation problems with tabu search.Studies in Locational Analysis.8,23-32.

Brimberg, J.,N. Mladenović(1996).Variable neighborhood algorithm for solving the continuous location-allocation problem.Studies in Locational Analysis.10,1-10.

Brimberg, J.,P. Hansen,N. Mladenović,E. D. Taillard(2000).Improvements and comparison of heuristics for solving the uncapacitated multisource weber problem.Operations Research.48,44-60.

Cooper, L.(1963).Location-allocation problems.Operations Research.11,331-43.

Cooper, L.(1972).The transportation-location problems.Operations Research.20,94-108.