A DISCRETE PARTICLE SWARM OPTIMIZATION ALGORITHM FOR BICRITERIA WAREHOUSE LOCATION PROBLEM

Year 2011, Issue: 13, 114 - 124, 17.06.2011

Tuğba Saraç , Fehmi Özsoydan

Abstract

The uncapacitated warehouse location problem (UWLP) is one of the widely studied discrete location problems, in which the nodes (customers) are connected to a number (w) of warehouses in such a way that the total cost, yields from the dissimilarities (distances) and from the fixed costs of the warehouses is minimized. Despite w is considered as fixed integer number, the UWLP is NP-hard. If the UWLP has two or more objective functions and w is an integer variable, the UWLP becomes more complex. Large size of this kind of complex problems can be solved by using heuristic algorithms or artificial intelligent techniques. It’s shown that Particle Swarm Optimization (PSO) which is one of the technique of artificial intelligent techniques, has achieved a notable success for continuous optimization, however, PSO implementations and applications for combinatorial optimization are still active research area that to the best of our knowledge fewer studies have been carried out on this topic. In this study, the bi-criteria UWLP of minimizing the total distance and total opening cost of warehouses. is presented and it’s shown that promising results are obtained. 

Keywords

Warehouse Location Problem, Particle Swarm Optimization, Discrete Location Problems, Bi-criteria.

A DISCRETE PARTICLE SWARM OPTIMIZATION ALGORITHM FOR BICRITERIA WAREHOUSE LOCATION PROBLEM

Abstract

Kapasitesiz Depo Yeri Belirleme Problemi, açılacak “w” adet deponun toplam açma maliyetlerinin ve
düğümlerde bulunan müşteriler ile açılan depolar arasındaki uzaklıklardan kaynaklanan maliyetlerin
toplamının en küçüklendiği, literatürde yaygınca bilinen bir kesikli yer belirleme problemidir. “w” sabit bir
sayı olmasına rağmen bu problem Np-Hard sınıfında yer almaktadır. Eğer birden fazla amaç fonksiyonu aynı
anda ele alınır ve “w” sayısı sabit yerine değişken kabul edilirse problem daha da zorlaşmaktadır. Büyük
boyutlu örnekleri ise ancak sezgisel tekniklerle ele alınabilmektedir. Öte yandan Parçacık Sürüsü
Optimizasyonu’ nun (PSO), sürekli eniyilemede ciddi bir başarıya sahip olduğu gösterilmiştir. Fakat
Kombinatoriyel Problemlerde uyarlama ve uygulama alanı hala aktif bir araştırma alanıdır ve bilindiği
kadarıyla, bu başlık altında daha az çalışma yürütülmüştür. Bu çalışmada İki Kriterli Kapasitesiz Depo Yeri
Belirleme Probleminin çözümü için bir Parçacık Sürüsü Optimizasyonu Algoritması önerilmiştir.

Keywords

Depo Yeri Belirleme Problemi, Parçacık Sürüsü Optimizasyonu, Kesikli Yer Belirleme Problemleri, İki-Kriter

References

• A. Kaveh, S. Talatahari. A particle swarm ant colony optimization for truss structures with discrete variables. Journal of Constructional Steel Research 65 (2009) 1558-1568.
• Angeline P.J. 1998. Using Selection to Improve Particle Swarm Optimization. In WCCI-98 Proceedings of the IEEE World Congress on Computational Intelligence pp. 84-89. IEEE Press.
• Chankong, V., and Haimes, Y.Y., 1983. Multiobjective Decision Making: Theory and Methodology, Elsevier Science Publishing Co, New York.
• Cornuejols, G., Nemhauser, G.L., Wolsey, L.A. (1990).: The uncapacitated facility location problem, In: Discrete Location Theory, Eds: P.B.Mirchandani and R.L. Francis, John Wiley & Sons, chap III, pp 120-171.
• Dearing, P.M. (1985).: Location problems, OperationsResearch Letters,Vol. 4, pp 95- 98.
• Eberhart, R. C., Dobbins, R. W., and Simpson, P. (1996), Computational Intelligence PC Tools, Boston: Academic Press.
• Eberhart, R. C., and Kennedy, J. (1995). A New Optimizer Using Particles Swarm Theory, Proc. Sixth International Symposium on Micro Machine and Human Science (Nagoya, Japan), IEEE Service Center, Piscataway, NJ, 39-43.
• Ehrgott, M., 2005. Multicriteria Optimization, Springer-Verlag, 2nd edition.
• Fang L., Chen P. and Liu S. Particle Swarm Optimization with Simulated Annealing for TSP. Proceedings of the 6th WSEAS Int. Conf. on Artificial Intelligence, Knowledge Engineering and Data Bases, Corfu Island, Greece, February 16-19, 2007.
• Francis, R.L., McGinnis, L.F., White, J.A. (1983).:Locational analysis, European Journal of Operational Research, Vol. 12, pp 220-252.
• Frans van den Bergh. An Analysis of Particle Swarm Optimizers. PhD thesis, University of Pretoria 2001.
• Grishukhin, V.P. (1994).: On polynomial solvability conditions for the simplest plant location problem,In: Selected topics in discrete mathematics, Eds:A.K.
• Kelmans and S. Ivanov, pp 37-46, American Mathematical Society, Providence, RI.
• Kennedy, J. (1997), The Particle Swarm: Social Adaptation of Knowledge, Proc. IEEE International Conference on Evolutionary Computation (Indianapolis, Indiana), IEEE Service Center, Piscataway, NJ, 303-308.
• Kennedy J. and Russel C. Eberhart. Particle swarm optimization. In proceedings of the IEEE International Conference on Neural Networks, volume IV, pages 1942-1948, Piscataway, NJJ,1995. IEEE Press.
• Kennedy J., Eberhart R. C. and Shi Y., “Swarm Intelligence”, Morgan Kaufmann, San Mateo, 2001, CA.
• Kennedy J. and Eberhart R. C., “A Discrete Binary Version of the Particle Swarm Optimization”, Proc. Of the conference on Systems, Man, and Cybernetics SMC97, pp. 4104- 4109, 1997.
• Krarup, J., Pruzan, P.M. (1983).: The simple plant location problem: Survey and synthesis, European Journal of Operational Research, Vol. 12, pp 36-81.
• Luc, D. T., 1989. Theory of Vector Optimization, Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin.
• Pant M., Thangaraj R., and Singh V. P. Particle Swarm Optimization with Crossover Operator and its Engineering Applications. IAENG International Journal of Computer Science. 36:2, IJCS_36_2_02 (2009).
• S. He, Q.H. Wu, J.Y. Wen, J.R. Saunders, R.C. Paton. A particle swarm optimizer with passive congregation. BioSystems 78 (2004) 135–147.