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

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

10.29977/JCIIE.200701.0001

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

Location-allocation problem ； 遺傳演算法 ； K-means演算法 ； location-allocation problem ； combinatorial optimization problem ； K-means algorithm ； genetic algorithms

工業工程學刊

24卷1期（2007 / 01 / 01）

1 - 19

英文

本研究連用一混合式遺傳演算法(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]作深入之比較，經實驗得知所提出之混合式遺傳演算法可迅速且有效地求解此問題。

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.

1. Brimberg, J.,N. Mladenović(1996).Solving the continuous location-allocation problems with tabu search.Studies in Locational Analysis,8,23-32.
2. Brimberg, J.,N. Mladenović(1996).Variable neighborhood algorithm for solving the continuous location-allocation problem.Studies in Locational Analysis,10,1-10.
3. 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.
4. Cooper, L.(1963).Location-allocation problems.Operations Research,11,331-43.
5. Cooper, L.(1972).The transportation-location problems.Operations Research,20,94-108.
6. Francis, R. L.,J. A. White(1974).Facility layout and location-An analytical approach.Prentice-Hall, Englewood Cliffs, New Jersey.
7. Gamal, M. D.,H., S. Salhi(2001).Constructive heuristics for the uncapacitated cntinuous location-allocation problem.Journal of the Operational Research Society,52,821-29.
8. Gen, M.,R. Cheng(1996).Genetic Algorithms and Engineering Design.John Wisley & Sons.
9. Goldberg, D. E.(1989).Genetic Algorithms in Search, Optimization and Machine Learning.
10. Gong D, M.,W. Xu,G. Yamazaki(1995).Hybrid evolutionary method for obstacle location-allocation.Computers and Industrial Engineering,29,525-530.
11. Gong, D.,M. Gen,G. Yamazaki,W. Xu(1997).Hybrid evolutionary method for capacitated location-allocation problem.Computers & Industrial Engineering,33,577-580.
12. Hosage, C. M.,M. F. Goodchild(1986).Discrete space location-allocation solutions from genetic algorithms.Annals of Operations Research,6,35-46.
13. Houck, C. R.,J. A. Joines,M. G. Kay(1996).Comparison of genetic algorithms, random restart and two-opt switching for solving large location-allocation problems.Computers and Operations Research,23,587-96.
14. Hsieh, K. H.,F. C. Tien(2004).Self-organizing feature maps for solving location-allocation problems with rectilinear distances.Computers and Operations Research,31,1017-1031.
15. Jeong, I.-K.,J.-J. Lee(1996).Adaptive simulated annealing genetic algorithm for system identification.Engineering Application of Artificial Intelligence,9,523-532.
16. Jiang, D.,W. Du,X. Chen(1997).GA based location models for physical distribution centers.Proceedings of the IEEE International Conference on Intelligent Processing Systems, Oct.,28(31),553-557.
17. Keane, J. A.,T. A. Ward(2002).A computational frame-work for location analysis.IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans,32,574-581.
18. Lee, C. Y.(1995).Application of a cross decomposition algorithm to a location and allocation problem in distributed systems.Computer Communications,8(5),367-377.
19. Liu, C. M.,R. L. Kao.,A. H. Wang(1994).Solving location-allocation problems with rectilinear distances by simulated annealing.Journal of the Operational Research Society,45,1304-1315.
20. Love, R. F.,H. Juel(1982).Properties and solution methods for large location-allocation problems.Journal of the Operational Research Society,33,443-52.
21. Love, R. F.,J. G. Morris(1975).A computation procedure for the exact solution of location-allocation problems with rectangular distances.Naval Research Logistics Quarterly,22,442-53.
22. Lozano, S.,F. Guerrero,L. Onieva,J. Larraneta(1998).Kononen maps for solving a class of location-allocation problems.European Journal of Operational Research,108,106-17.
23. Pandya, A. S.,R. B. Macy(1995).Pattern Recognition with Neural Networks in C++.CRC Press mc, Boca Raton, FL.
24. Righini, G.(1995).A double annealing algorithm for discrete location/allocation problems.European Journal of Operational Research,86,452-468.
25. Sherali, A. D.,C. M. Shetty(1977).The rectilinear distance location-allocation problem.AIE Transactions,9,136-43.
26. Tien, F. C.,J. S. Lee(2003).Tuning GALAP by Taguchi method for small-sized location allocation problems, 17th International Conference of Production Research.
27. Xu, J.,S. Y. Chiu,F. Glover(1998).Fine-tuning a tabu search algorithm with statistical tests.International Transaction Operational Research,5,233-244.