Solving the simple plant location problem by genetic algorithm

Jozef Kratica; Dušan Tošic; Vladimir Filipović; Ivana Ljubić

RAIRO - Operations Research (2010)

  • Volume: 35, Issue: 1, page 127-142
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Kratica, Jozef, et al. "Solving the simple plant location problem by genetic algorithm." RAIRO - Operations Research 35.1 (2010): 127-142. <http://eudml.org/doc/116591>.

@article{Kratica2010,
abstract = { 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. },
author = {Kratica, Jozef, Tošic, Dušan, Filipović, Vladimir, Ljubić, Ivana},
journal = {RAIRO - Operations Research},
keywords = {Simple plant location problem; genetic algorithms; combinatorial optimization; simple plant location problem; genetic algorithm; combinatorial optimization},
language = {eng},
month = {3},
number = {1},
pages = {127-142},
publisher = {EDP Sciences},
title = {Solving the simple plant location problem by genetic algorithm},
url = {http://eudml.org/doc/116591},
volume = {35},
year = {2010},
}

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
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 1
SP - 127
EP - 142
AB - 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.
LA - eng
KW - Simple plant location problem; genetic algorithms; combinatorial optimization; simple plant location problem; genetic algorithm; combinatorial optimization
UR - http://eudml.org/doc/116591
ER -

References

top
  1. C.H. Aikens, Facility Location Models for Distribution Planning. European J. Oper. Res. 22 (1985) 263-279.  
  2. M.L. Alves and M.T. Almeida, Simulated Annealing Algorithm for the Simple Plant Location Problem: A Computational Study. Rev. Invest. 12 (1992).  
  3. A.A. Aqeev, V.S. Beresnev, 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. D. Beasley, D.R. Bull and R.R. Martin, An Overview of Genetic Algorithms. Univ. Computing15 (1993) 170-181.  
  5. J.E. Beasley, Obtaining Test Problems via Internet. J. Global Optim.8 (1996) 429-433, http://mscmga.ms.ic.ac.uk/info.html  
  6. J.E. Beasley, Lagrangean Heuristic for Location Problems. European J. Oper. Res.65 (1993) 383-399.  
  7. A.R. Conn and G. Cornuejols, A Projection Method for the Uncapacitated Facility Location Problem. Math. Programming46 (1990) 273-298.  
  8. G. Cornuejols, G.L. Nemhauser and L.A. Wolsey, 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.  
  9. P.M. Dearing, Location Problems. Oper. Res. Lett.4 (1985) 95-98.  
  10. K.E. De Jong and W.M. Spears, 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.  
  11. C. De Simone and C. Mannino, Easy Instances of the Plant Location Problem, Technical Report R-427. Gennaio, University of Roma, Italy (1996).  
  12. R. Dorne and J.K. Hao, 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.  
  13. D. Erlenkotter, A Dual-Based Procedure for Uncapacitated Facility Location. Oper. Res.26 (1978) 992-1009.  
  14. R.L. Francis, L.F. McGinnis and J.A. White, Locational Analysis. European J. Oper. Res.12 (1983) 220-252.  
  15. B. Freisleben and P. Merz, 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.  
  16. L.L. Gao, E. Robinson and Jr. Powell, Uncapacitated Facility Location: General Solution Procedure and Computational Experience. European J. Oper. Res.76 (1994) 410-427.  
  17. V.P. Grishukhin, 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.  
  18. M. Guignard, A Lagrangean Dual Ascent Algorithm for Simple Plant Location Problems. European J. Oper. Res.35 (1988) 193-200.  
  19. K. Holmberg, 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).  
  20. S. Khuri, T. Back and J. Heitkotter, An Evolutionary Approach to Combinatorial Optimization Problems, in Proc. of CSC'94. Phoenix, Arizona (1994).  
  21. M. Koerkel, On the Exact Solution of Large-Scale Simple Plant Location Problems. European J. Oper. Res. 39 (1989) 157-173.  
  22. J. Krarup and P.M. Pruzan, The Simple Plant Location Problem: Survey and Synthesis. European J. Oper. Res. 12 (1983) 36-81.  
  23. J. Kratica, Improving Performances of the Genetic Algorithm by Caching. Comput. Artificial Intelligence18 (1999) 271-283.  
  24. P. Merz and B. Freisleben, 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.  
  25. P. Merz and B. Freisleben, Genetic Local Search for the TSP: New Results, in Proc. of the 1997 IEEE International Conference on Evolutionary Computation. IEEE Press (1997) 159-164.  
  26. C. Ryu and M. Guignard, An Exact Algorithm for the Simple Plant Location Problem with an Aggregate Capacity Constraint, TIMS/ORSA Meeting. Orlando, FL (1992) 92-04-09.  
  27. H.P. Simao and J.M. Thizy, A Dual Simplex Algorithm for the Canonical Representation of the Uncapacitated Facility Location Problem. Oper. Res. Lett. 8 (1989) 279-286.  
  28. G. Syswerda, Uniform Crossover in Genetic Algorithms, in Proc. of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA (1989) 2-9.  
  29. D. Whitley, 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.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.