The simple plant location problem (SPLP) is considered and a genetic algorithm is proposed to solve this problem. By using the developed algorithm it is possible to solve SPLP with more than 1000 facility sites and customers. Computational results are presented and compared to dual based algorithms.

Keywords: simple plant location problem, genetic algorithms, combinatorial optimization

^{}; Tošic, Dušan

^{}; Filipović, Vladimir

^{}; Ljubić, Ivana

^{1}

@article{RO_2001__35_1_127_0, author = {Kratica, Jozef and To\v{s}ic, Du\v{s}an and Filipovi\'c, Vladimir and Ljubi\'c, Ivana}, title = {Solving the simple plant location problem by genetic algorithm}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {127--142}, publisher = {EDP-Sciences}, volume = {35}, number = {1}, year = {2001}, mrnumber = {1841818}, zbl = {0995.90055}, language = {en}, url = {http://archive.numdam.org/item/RO_2001__35_1_127_0/} }

TY - JOUR AU - Kratica, Jozef AU - Tošic, Dušan AU - Filipović, Vladimir AU - Ljubić, Ivana TI - Solving the simple plant location problem by genetic algorithm JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2001 SP - 127 EP - 142 VL - 35 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/item/RO_2001__35_1_127_0/ LA - en ID - RO_2001__35_1_127_0 ER -

%0 Journal Article %A Kratica, Jozef %A Tošic, Dušan %A Filipović, Vladimir %A Ljubić, Ivana %T Solving the simple plant location problem by genetic algorithm %J RAIRO - Operations Research - Recherche Opérationnelle %D 2001 %P 127-142 %V 35 %N 1 %I EDP-Sciences %U http://archive.numdam.org/item/RO_2001__35_1_127_0/ %G en %F RO_2001__35_1_127_0

Kratica, Jozef; Tošic, Dušan; Filipović, Vladimir; Ljubić, Ivana. Solving the simple plant location problem by genetic algorithm. RAIRO - Operations Research - Recherche Opérationnelle, Volume 35 (2001) no. 1, pp. 127-142. http://archive.numdam.org/item/RO_2001__35_1_127_0/

[1] Facility Location Models for Distribution Planning. European J. Oper. Res. 22 (1985) 263-279. | MR | Zbl

,[2] Simulated Annealing Algorithm for the Simple Plant Location Problem: A Computational Study. Rev. Invest. 12 (1992).

and ,[3] Polynomially Solvable Cases of the Simple Plant Location Problem, in Proc. of the First Integer Programming and Combinatorial Optimization Conference, edited by R. Kannan and W.R. Pulleyblank. University of Waterloo Press, ON, Canada (1990) 1-6.

, ,[4] An Overview of Genetic Algorithms. Univ. Computing 15 (1993) 170-181.

, and ,[5] Obtaining Test Problems via Internet. J. Global Optim. 8 (1996) 429-433, http://mscmga.ms.ic.ac.uk/info.html | MR | Zbl

,[6] Lagrangean Heuristic for Location Problems. European J. Oper. Res. 65 (1993) 383-399. | Zbl

,[7] A Projection Method for the Uncapacitated Facility Location Problem. Math. Programming 46 (1990) 273-298. | MR | Zbl

and ,[8] The Uncapacitated Facility Location Problem, in Discrete Location Theory, edited by P.B. Mirchandani and R.L. Francis. John Wiley & Sons (1990), Chapter 3, pp. 120-171. | MR | Zbl

, and ,[9] Location Problems. Oper. Res. Lett. 4 (1985) 95-98. | MR | Zbl

,[10] Using Genetic Algorithms to Solve NP-Complete Problems, in Proc. of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA (1989) 124-132.

and ,[11] Easy Instances of the Plant Location Problem, Technical Report R-427. Gennaio, University of Roma, Italy (1996).

and ,[12] A New Genetic Local Search Algorithm for Graph Coloring, in Proc. of the 5th Conference on Parallel Problem Solving from Nature - PPSN V. Springer-Verlag, Lecture Notes in Comput. Sci. 1498 (1998) 745-754.

and ,[13] A Dual-Based Procedure for Uncapacitated Facility Location. Oper. Res. 26 (1978) 992-1009. | MR | Zbl

,[14] Locational Analysis. European J. Oper. Res. 12 (1983) 220-252. | MR | Zbl

, and ,[15] New Genetic Local Search Operators for the Traveling Salesman Problem, in Proc. of the 4th Conference on Parallel Problem Solving from Nature - PPSN IV. Springer-Verlag Lecture Notes in Comput. Sci. 1141 (1996) 890-899.

and ,[16] Zbl

, and Jr. Powell, Uncapacitated Facility Location: General Solution Procedure and Computational Experience. European J. Oper. Res. 76 (1994) 410-427. |[17] On Polynomial Solvability Conditions for the Simplest Plant Location Problem, in Selected topics in discrete mathematics, edited by A.K. Kelmans and S. Ivanov. American Mathematical Society, Providence, RI (1994) 37-46. | MR | Zbl

,[18] A Lagrangean Dual Ascent Algorithm for Simple Plant Location Problems. European J. Oper. Res. 35 (1988) 193-200. | MR | Zbl

,[19] Experiments with Primal-Dual Decomposition and Subgradient Methods for the Uncapacitated Facility Location Problem, Research Report LiTH-MAT/OPT-WP-1995-08, Optimization. Department of Mathematics, Linkoping Institute of Technology, Sweden (1995). | MR

,[20] An Evolutionary Approach to Combinatorial Optimization Problems, in Proc. of CSC'94. Phoenix, Arizona (1994).

, and ,[21] On the Exact Solution of Large-Scale Simple Plant Location Problems. European J. Oper. Res. 39 (1989) 157-173. | MR | Zbl

,[22] The Simple Plant Location Problem: Survey and Synthesis. European J. Oper. Res. 12 (1983) 36-81. | MR | Zbl

and ,[23] Improving Performances of the Genetic Algorithm by Caching. Comput. Artificial Intelligence 18 (1999) 271-283. | Zbl

,[24] A Genetic Local Search Approach to the Quadratic Assignment Problem, in Proc. of the Seventh International Conference on Genetic Algorithms. Morgan Kaufmann (1997) 465-472.

and ,[25] Genetic Local Search for the TSP: New Results, in Proc. of the 1997 IEEE International Conference on Evolutionary Computation. IEEE Press (1997) 159-164.

and ,[26] An Exact Algorithm for the Simple Plant Location Problem with an Aggregate Capacity Constraint, TIMS/ORSA Meeting. Orlando, FL (1992) 92-04-09.

and ,[27] A Dual Simplex Algorithm for the Canonical Representation of the Uncapacitated Facility Location Problem. Oper. Res. Lett. 8 (1989) 279-286. | MR

and ,[28] Uniform Crossover in Genetic Algorithms, in Proc. of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA (1989) 2-9.

,[29] The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best, in Proc. of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA (1989) 116-123.

,