P-medyan Tesis Yeri Seçim Problemi ve Çözüm Yaklaşımları

Abstract

Her geçen gün globalleşen ve rekabetin sürekli olarak arttığı dünyamızda organizasyonların yaşamlarını devam ettirebilmelerinde başarılı bir tedarik zinciri yönetimi stratejisi vazgeçilmez hale gelmiştir. Organizasyonların giderlerinin önemli bir kısmını ise tedarik zinciri içerisindeki taşımalardan ortaya çıkan maliyetler oluşturmaktadır. Bu sebeple organizasyonların stratejik kararlarından birisi olan tesis yeri seçimi, tedarik zincirinin performansını ve maliyetlerini doğrudan etkileyen bir konudur. Tesis yeri seçimi problemine güncel metotlarla çözüm yaklaşımı geliştirilmesi bu aşamada oldukça önemli hale gelmektedir. Bu çalışmada hizmet veren tesisler ve talep noktaları arasındaki taşımalardan dolayı ortaya çıkan maliyetlerin minimize edilmesini amaçlayan ve tesis yeri seçim problemleri içerisinde önemli bir yer tutan p-medyan problemi tanıtılmaya çalışılmış ve çözüm metotları üzerinde durulmuştur.

Keywords

• tesis yeri seçimi
• tesis yeri seçim problemi
• p-medyan problemi

The p-median Facility Location Problem and Solution Approaches

Abstract

In today’s globalized and increasingly competitive environment, organizations’ need to implement successful strategies for supply chain management has become indispensable. Transportation costs within the supply chain comprise an important part of the organizations’ expenses. For this reason, the strategic selection of location is an issue that directly affects supply chain performance and costs. At this stage, it becomes very important to apply the latest and the best methods to the facility location problem. The focus of this study is the p-median problem and its solution techniques, one of the location allocation problems aimed at minimizing the costs arising from shipments between facilities and demand points.

Keywords

• facility location
• facility location problem
• p-median problem

References

1. Alba, E., Dominguez, E. (2006) “Comparative analysis of modern optimization tools for the p-median problem”, Stat. Comput. 16, 251–260.
2. Alp, O., Erkut, E. & Drezner Z. (2003). “An Efficient Genetic Algorithm for the p-Median Problem”, Annals of Operations Research, Vol.122, No:1-4, pp.21-42.
3. Ardalan, A. (1988), “A comparison of heuristic methods for service facility locations” International Journal of Operations and Production Management, 8(2):52–58.
4. Arya, V., Garg, N. Khandekar, R. Pandit, V. Meyerson, A. & Munagala K. (2004). “Local search heuristics for k-median and facility location problems”, SIAM Journal on Computing, Vol.33, No:3, pp.544–562.
5. Arroyo, J. E. C., Soares, M. S. & Santos, P. M. (2010). “A GRASP heuristic with path-relinking for a bi-objective p-median problem”, 10th International Conference on Hybrid Intelligent Systems, Atlanta, USA, pp.97-102.
6. Ashayeri, J., Heuts, R. & Tammel, B. (2005). “A modified simple heuristic for the p-median problem, with facilities design applications”, Robotics and Computer-Integrated Manufacturing, Vol.21, No:4-5, pp.451–464.
7. Avella, P., Sassano, A. & Vasil’ev, I. (2003). “Computational study of large-scale p-median problems”, Technical Report 08-03, Universita di Roma, La Sapienza.
8. Baiou, M. & Barahona, F. (2011).“On the linear relaxation of the p-median problem”, Discrete Optimization, Vol.8, No:2, pp.344–375.

9. Balinski, M. (1965). “Integer programming, methods, uses and computation”, Manage Science, Vol.12, No:3, pp.253-313.
10. Beasley, J.E. (1985). “A note on solving large p-median problems”, European Journal of Operational Research, Vol.21, No:2, pp.270-273.
11. Beasley, J.E. (1990). “OR-Library: distributing test problems by electronic mail”, Journal of the Operational Research Society, Vol.41, No:11, pp.1069-1072.
12. Beltran, C., Tadonki, C. & Vial J. Ph. (2006). “Solving the p-Median Problem with a Semi- Lagrangian Relaxation”, Computational Optimization And Applications, Vol.35, No:2, pp.239-260.
13. Berman, O. & Drezner, Z. (2008). “A new formulation for the conditional p-median and p- center problems”, Operations Research Letters, Vol.36, No:4, pp.481–483.
14. Bozkaya, B., Zhang, J. & Erkut E. (2002) “An effective genetic algorithm for the p-median problem” , Facility location: applications and theory Ed. by. Horst Hamacher and Zvi Drezner, pp. 179-206.
15. Brito, J., Martinez, F. J. & Moreno, J. A. (2007). “Particle Swarm Optimization for the continuous p-median problem”, 6th WSEAS Int. Conference on Computational Intelligence, Man-Machine Systems and Cybernetics, Tenerife, Spain.
16. Caccetta, L. & Dzator M. (2005). Heuristic Methods for Locating Emergency Facilities, MODSIM-International Congress on Modelling and Simulation, Australia, pp.1744- 1750.
17. Cadenas, J.M., Canos, M.J. Garrido, M.C. Ivorra, C. & Liern, V. (2011). “Soft-computing based heuristics for location on networks: The p-median problem”, Applied Soft Computing, Vol.11, No:2, pp.1540–1547.
18. Captivo, M.E. (1991). “Fast primal and dual heuristics for the pmedian location problem”, European Journal of Operational Research, Vol.52, No:1, pp.65-74.
19. Ceselli, A. (2003). “Two exact algorithms for the capacitated p-median problem,”, 4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies, Vol.1, No:4, pp.319–340.
20. Chiou, Y. & Lan, L.W. (2001). “Genetic clustering algorithms”, European Journal of Operational Research, Vol.135, pp.413-427.
21. Chiyoshi, F. & Galvao, R.D. (2000).“A statistical analysis of simulated annealing applied to the p-median problem”, Annals Operations Research, Vol.96, No:1-4, pp.61-74.
22. Chrobak, M. Kenyon, C. & Young, N. (2006). “The reverse greedy algorithm for the metric k- median problem”, Information Processing Letters, Vol.97, No:2, pp.68–72.
23. Church. R. L. (2003) “COBRA: A new formulation of the classic p-median location problem” Annals of Operations Research, 122:103–120. Cook, S. “The P versus NP Problem”, (Çevrimiçi), http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf, 7.02.2011
24. Cornuejols, G., Fisher, M.L. & Nemhauser, G.L. (1977). “Location of Bank Accounts to Optimise Float: an Analytic Study of Exact and Approximate Algorithms” Management Science, Vol.23, No:8, pp.789–810.
25. Correa, E.S., Steiner M.T.A., Freitas A.A. & Carnieri C. (2004). “A Genetic Algorithm for Solving a Capacitated p-Median Problem: Theory and Practice in Optimization” Numerical Algorithms. Ed. by. Martnez, J. M.and Yuan, J. Y., Vol.35, No:2-4, pp. 373- 388.
26. Current, J., Daskin, M.S. & Schilling, D. (2001). “Discrete Network Location Model”, Facility Location: Applications and Theory, Ed. by. Z. Drezner and H.W. Hamacher, Springer-Verlag, pp.83-120.
27. Crainic, T.G., Gendreau, M., Hansen, P. & Mladenovic, N. (2003). “Parallel variable neighborhood search for the p-median”, Les Cahiers du GERAD, G-2003-4.
28. Daskin, M.S. (1995). “Network and discrete location: Models, algorithms, and applications”, John Wiley & Sons, Inc., New York.
29. Diaz, J.A. & E. Fernandez (2006). “Hybrid scatter search and path relinking for the capacitated p-median problem”, European Journal of Operational Research, Vol.169, No:2, pp.570–585.
30. Dominguez, E. & Munoz, J. (2005) “Applying bio-inspired techniques to the p-median problem”, Computational Intelligence and Bioinspired Systems, Ed. by. J. Cabestany, A. Prieto, and D.F. Sandoval, Springer-Verlag, pp.67-74.
31. Dvorett, J. (1999). “Compatibility-based genetic algorithm: A new approach to the p-median problem”, Technical Report, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL.
32. Efroymson, M. & Ray, T. (1966). “A branch-bound algorithm for plant location”, Operations Research, 14(3), pp.361–368.
33. Estivill-Castro, V. & Torres-Velazquez, R. (1999). “Hybrid genetic algorithm for solving the p-median problem” SEAL’98: Selected Papers from Second Asia-Pacific Conference Simulated Evolution Learning, Springer-Verlag, Berlin, pp.19–25.
34. Fathali, J., Khahki, H. & Burkard, R. (2006). “An ant colony algorithm for the pos/neg weighted p-median problem” Central European Journal of Operations Research, Vol.14, No:3, pp.229–246.
35. Fleszar, K. & Hindi, K.S. (2008). “An effective VNS for the capacitated p-median problem”, European Journal of Operational Research, Vol.191, No:3, pp.612–622.
36. Galvao, R.D. & ReVelle C. (1996). “A Lagrangean Heuristic for the Maximal Covering Location Problem”, European Journal of Operations Research, Vol. 88, No:1, pp.114– 123.
37. Garey, M.R. & Johnson, D. S. (1979). “Computers and intractibility: A guide to the theory of NP-completeness”, W.H. Freeman and Co., San Francisco.
38. Garcia-Lopez, F., Melian-Batista, B. Moreno-Perez & J.A. Moreno-Vega, J.M. (2002).“The parallel variable neighborhood search for the p-median problem”, Journal of Heuristics, Vol.8, No:3, pp.375–388.
39. Glover, F. (1990). Tabu search for the p-median problem, unpublished manuscript.
40. Goldengorin, B. & Krushinsky, D. (2011). “Complexity evaluation of benchmark instances for the p-median problem”, Mathematical and Computer Modelling, Vol.53, No:9-10, pp.1719-1736.
41. Hakimi, S.L. (1964). “Optimum Location of Switching Centers and the Absolute Centers and Medians of a Graph”, Operations Research, Vol.12, No:3, pp.450–459.
42. Hakimi, S.L. (1965). “Optimum distribution of switching centers in a communication network and some related graph theoretic problems”, Operations Research Vol.13, No:3, pp.462–475
43. Hansen, P. & Mladenovic, N. (1997). “Variable neighborhood search for the p-median”, Location Science, Vol.5, No:4, pp.207–226.
44. Hansen, P., Brimberg, J. Urosevic, D. & Mladenovic, N. (2009). “Solving large p-median clustering problems by primal–dual variable neighborhood search”, Data Mining and Knowledge Discovery, Vol.19, No:3, pp.351-375.
45. Hosage C.M. & Goodchild, M.F. (1986), “Discrete space location–allocation solutions from genetic algorithms”, Annals Operations Research, Vol.6, No:2, pp.35–46.
46. Hribar, M. & Daskin, M.S. (1997). “A dynamic programming heuristic for the p-median problem”, European Journal of Operational Research, Vol.101, No:3, pp.499–508.
47. Jamshidi, M. (2009). “Median Location Problem”, Facility Location: Concepts, Models, Algorithms and Case Studies, Ed. by. R.Z. Farahani and M. Hekmatfar, Physica- Verlag Heidelberg, pp.177-191.
48. Kariv, O. & Hakimi, S. L. (1979). “An algorithmic approach to network location problems: Part 2. The p-medians”, SIAM Journal on Applied Mathematics, Vol.37, No:3, pp.539– 560.
49. Kochetov, Y., (2001). Probabilistic local search algorithms for the discrete optimization problems. Discrete Mathematics and Applications, Moscow, MSU, 84–117.
50. Kochetov, Y., Alekseeva, E. Levanova & T. Loresh M. (2005). “Large neighborhood local search for the p-median problem”, Yugoslav Journal of Operations Research, Vol.15, No:1, pp.53-63
51. Kuehn, A.A. & Hamburger, M.J. (1963). “A Heuristic Program for Locating Warehouses”, Management Science, Vol.9, No:4, pp.643-666.
52. Küçükdeniz, T. (2009). “Sürü Zekası Optimizasyon Tekniği ve Tedarik Zinciri Yönetiminde Bir Uygulama”, Yayınlanmamış Doktora Tezi, İstanbul Üniversitesi, Fen Bilimleri Enstitüsü, Endüstri Mühendisliği Anabilim Dalı.
53. Levanova, T. V. & Loresh, M. A. (2004). “Algorithms of Ant System and Simulated Annealing for the p-median Problem”, Automation and Remote Control, Vol.65, No:3, pp.431-438.
54. Lim, G.J., Reese J. & Holder, A. (2009). “Fast and robust techniques for the euclidean p- median problem with uniform weights”, Computers & Industrial Engineering, Vol.57, No:3, pp.896–905.
55. Lorena, L. A. N. & Senne, E. L. F. (2003). “Local search heuristics for capacitated p-median problems” Networks and Spatial Economics, 3:409–419.
56. Mamedsaidov, R. (2009). “Particle Swarm Optimization For P-Median Problems”, Yayınlanmamış Yüksek Lisans Tezi, Fatih Üniversitesi, Fen Bilimleri Enstitüsü, Endüstri Mühendisliği Anabilim Dalı.
57. Maniezzo, V., Mingozzi & A. Baldacci, R. (1998). “A bionomic approach to the capacitated p- median problem”, Journal of Heuristic, Vol.4, No:3, pp.263-280.
58. Manne, A. (1964). “Plant location under economies of scale - decentralization and computation”, Management Science, Vol.11, No:2, pp.213-235.
59. Marianov, V. & Serra, D. (2004). “p-Median Models in Public Sector”, Facility Location: Applications and Theory, Ed. by. Horst W. Hamacher, Zvi Drezner, Berlin, Springer, pp. 119-143.
60. Merino, E.D. Perez, J.M. & Aragones, J. J. (2003). “Neural Network Algorithms for the p- Median Problem”, ESANN'2003 proceedings - European Symposium on Artificial Neural Networks, Bruges, Belgium, pp.385-391
61. Moreno-Perez , J.A., Moreno-Vega, J.M. & Mladenovic, N. (1994). “Tabu search and simulated annealing in p-median problems”, The Canadian Operational Research Society Conferance, Montreal.
62. Osman, I.H. & Ahmadi, S. (2007). “Guided construction search metaheuristics for the capacitated p-median problem with single source constraint”, Journal of the Operational Research Society, Vol.58, No:1, pp.100–114
63. Otto, S. & Kokai, G. (2008). “Decentralized Evolutionary Optimization Approach to the p- Median Problem”, Applications of Evolutionary Computing, Ed. by. M. Giacobini v.d., Springer-Verlag, Berlin, pp.659-668.
64. Pizzolato, N.D. (1994). “A heuristic for large-size p-median location problems with application to school location”, Annals of Operations Research, Vol.50, No:1, pp.473- 485.
65. Pullan, W. (2008). A Population Based Hybrid Metaheuristic for the p-median Problem”, IEEE Congress on Evolutionary Computation, pp.76-82.
66. Resende, M.G.C. & Werneck, R.F. (2003).“On the implementation of a swap-based local search procedure for the p-median problem”, Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, Ed. by. Richard E. Ladner, Society for Industrial Mathematics, pp.119-127.
67. Resende, M.G.C. & Werneck, R.F. (2004). “A hybrid heuristic for the p-median problem”, Journal of Heuristics, Vol.10, No:1, pp.59–88.
68. Rolland, E., Schilling, D.A. & Current, J.R. (1996). “An efficient tabu search procedure for the p-median problem”, European Journal of Operational, Vol. 96, No:2, pp.329–342.
69. ReVelle, C. & Swain, R. (1970).“Central Facilities Location”, Geographical Analysis, Vol.2, No:1, pp.30–42.
70. Righini, G. (1995) “A double annealing algorithm for discrete location/allocation problems”, European Journal of Operational Research, 86(3):452–468.
71. Rosing, K.E., ReVelle, C.S. & Rosing-Vogelaar, H. (1979). “The p-Median and its Linear Programming Relaxation: An Approach to Large Problems” Journal of the Operational Research Society, Vol.30, No:9, pp. 815–822.
72. Salhi, S. (1997). “A perturbation heuristic for a class of location problems”, Journal of the Operational Research Society, 48(12):1233–1240.
73. Sene, E.L.F., Lorena, L.A.N. & Pereira, M.A. (2005). “A branchand-price approach to p- median location problems”, Computers and Operations Research, Vol.32, No:6, pp.1655–1664.
74. Sule, D. R. (2001). Logistics of Facility Location and Allocation, Marcel Dekker, New York, US.
75. Tavakkoli, R. & Shayan, E. (1998). “Facilities Layout Design by Genetic Algorithms”, Computers and Industrial Engineering, Vol.35, No:3-4, pp.527-530.
76. Teitz, M.B. & Bart, P. (1968). “Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph”, Operations Research, Vol.16, No:5, pp.955–961.
77. Tseng, L., Wu, C. (2009). “The OA-Based Swap Method for the P-Median Problem” In SMC, pp.2543-2548.
78. Voss, S. (1996) “A reverse elimination approach for the p-median problem”, Studies in Locational Analysis, 8:49–58.
79. Whitaker, R.A. (1983). “A fast algorithm for the greedy interchange of large-scale clustering and median location problems”, INFOR, Vol.21, No:2, pp.95-108.
80. Xianrui Xua, X. & Xiaojie Lia, H.(2010). “An Improved Scatter Search Algorithm for Capacitated P-Median Problem”, Computer Engineering and Technology (ICCET)2nd International Conference, pp.316-320.