Solving the semi-desirable facility location problem using bi-objective particle swarm. (English) Zbl 1109.90051
Summary: A new model for the semi-obnoxious facility location problem is introduced. The new model is composed of a weighted minisum function to represent the transportation costs and a distance-based piecewise function to represent the obnoxious effects of the facility. A single-objective particle swarm optimizer (PSO) and a bi-objective PSO are devised to solve the problem. Results are compared on a suite of test problems and show that the bi-objective PSO produces a diverse set of non-dominated solutions more efficiently than the single-objective PSO and is competitive with the best results from the literature. Computational complexity analysis estimates only a linear increase in effort with problem size.
MSC:
| 90B50 | Management decision making, including multiple objectives |
| 90B80 | Discrete location and assignment |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
multiple criteria analysis; semi-obnoxious; location; evolutionary computation; Bi-objective PSOSoftware:
MOPSOReferences:
| [1] | Angeline, P. J., Evolutionary optimization versus particle swarm optimization: Philosophy and performance differences, (Evolutionary Programming VII. Evolutionary Programming VII, Lecture Notes in Computer Science, vol. 1447 (1998), Springer-Verlag: Springer-Verlag Berlin), 601-610 |
| [2] | P.J. Angeline, Using selection to improve particle swarm optimization, in: Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, 1998, pp. 84-89.; P.J. Angeline, Using selection to improve particle swarm optimization, in: Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, 1998, pp. 84-89. |
| [3] | T. Bäck, D.B. Fogel, Z. Michalewicz (Eds.), Evolutionary computation, in: Basic Algorithms and Operators, vol. 1, 2000, Institute of Physics Pub, Bristol, Philadelphia.; T. Bäck, D.B. Fogel, Z. Michalewicz (Eds.), Evolutionary computation, in: Basic Algorithms and Operators, vol. 1, 2000, Institute of Physics Pub, Bristol, Philadelphia. · Zbl 0968.68055 |
| [4] | Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D., Linear Programming and Network Flows (2004), John Wiley & Sons, Ltd.: John Wiley & Sons, Ltd. New York |
| [5] | Berman, O.; Drezner, Z., A note on the location of an obnoxious facility on a network, European Journal of Operational Research, 120, 1, 215-217 (2000) · Zbl 0985.90061 |
| [6] | Brimberg, J.; Juel, H., A minisum model with forbidden regions for locating a semi-desirable facility in the plane, Location Science, 6, 109-120 (1998) |
| [7] | Brimberg, J.; Juel, H., On locating a semi-desirable facility on the continuous plane, International Transactions in Operational Research, 5, 1, 59-66 (1998) · Zbl 0911.90238 |
| [8] | Brimberg, J.; Juel, H., A bi-criteria model for locating a semi-desirable facility in the plane, European Journal of Operational Research, 106, 1, 144-151 (1998) |
| [9] | A. Carlisle, G.V. Dozier, An off-the-shelf PSO, in: Proceedings of the 2001 Workshop on Particle Swarm Optimization, 2001, pp. 1-6.; A. Carlisle, G.V. Dozier, An off-the-shelf PSO, in: Proceedings of the 2001 Workshop on Particle Swarm Optimization, 2001, pp. 1-6. |
| [10] | R.L. Church, J. Cohon, Multiobjective location analysis of regional energy facility siting problems, Report No. BNL 50567, Policy Analysis Division, Brookhaven National Lab., Upton NY, 1976.; R.L. Church, J. Cohon, Multiobjective location analysis of regional energy facility siting problems, Report No. BNL 50567, Policy Analysis Division, Brookhaven National Lab., Upton NY, 1976. |
| [11] | Clerc, M.; Kennedy, J., The particle swarm—explosion, stability, and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation, 6, 1, 58-73 (2002) |
| [12] | C.A. Coello Coello, M.S. Lechuga, MOPSO: A proposal for multiple objective particle swarm optimization, in: Proceedings of the 2002 Congress on Evolutionary Computation, vol. 2, 2002, pp. 1051-1056.; C.A. Coello Coello, M.S. Lechuga, MOPSO: A proposal for multiple objective particle swarm optimization, in: Proceedings of the 2002 Congress on Evolutionary Computation, vol. 2, 2002, pp. 1051-1056. |
| [13] | Coello Coello, C. A.; Pulido, G. T.; Lechuga, M. S., Handling multiple objectives with particle swarm optimization, IEEE Transactions on Evolutionary Computation, 8, 3, 256-279 (2004) |
| [14] | Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms (2001), John Wiley & Sons: John Wiley & Sons New York · Zbl 0970.90091 |
| [15] | G. Dozier, D. Brown, J. Hurley, K. Cain, Vulnerability analysis of AIS-based intrusion detection systems via genetic and particle swarm red teams, in: Proceedings of the 2004 Congress on Evolutionary Computation, vol. 1, 2004, pp. 111-116.; G. Dozier, D. Brown, J. Hurley, K. Cain, Vulnerability analysis of AIS-based intrusion detection systems via genetic and particle swarm red teams, in: Proceedings of the 2004 Congress on Evolutionary Computation, vol. 1, 2004, pp. 111-116. |
| [16] | R.C. Eberhart, Y. Shi, Comparing inertia weights and constriction factors in particle swarm optimization, in: Proceedings of the 2000 Congress on Evolutionary Computation, vol. 1, 2000, pp. 16-19.; R.C. Eberhart, Y. Shi, Comparing inertia weights and constriction factors in particle swarm optimization, in: Proceedings of the 2000 Congress on Evolutionary Computation, vol. 1, 2000, pp. 16-19. |
| [17] | Erkut, E.; Neuman, S., Analytical models for locating undesirable facilities, European Journal of Operational Research, 40, 3, 275-291 (1989) · Zbl 0668.90025 |
| [18] | J.E. Fieldsend, S. Singh, A multi-objective algorithm based upon particle swarm optimisation, an efficient data structure and turbulence, in: Proceedings of the 2002 UK Workshop on Computational Intelligence, 2002, pp. 37-44.; J.E. Fieldsend, S. Singh, A multi-objective algorithm based upon particle swarm optimisation, an efficient data structure and turbulence, in: Proceedings of the 2002 UK Workshop on Computational Intelligence, 2002, pp. 37-44. |
| [19] | Fogel, L. J.; Owens, A. J.; Walsh, M. J., Artificial Intelligence through Simulated Evolution (1966), John Wiley & Sons: John Wiley & Sons New York · Zbl 0148.40701 |
| [20] | Goicoechea, A.; Hansen, D. R.; Duckstein, L., Multiobjective Decision Analysis with Engineering and Business Applications (1982), John Wiley & Sons: John Wiley & Sons New York · Zbl 0584.90045 |
| [21] | Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley New York · Zbl 0721.68056 |
| [22] | Holland, J. H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence (1975), University of Michigan Press: University of Michigan Press Ann Arbor · Zbl 0317.68006 |
| [23] | X. Hu, R. Eberhart, Multiobjective optimization using dynamic neighborhood particle swarm optimization, in: Proceedings of the 2002 Congress on Evolutionary Computation, vol. 2, 2002, pp. 1677-1681.; X. Hu, R. Eberhart, Multiobjective optimization using dynamic neighborhood particle swarm optimization, in: Proceedings of the 2002 Congress on Evolutionary Computation, vol. 2, 2002, pp. 1677-1681. |
| [24] | X. Hu, R. Eberhart, Y. Shi, Particle swarm with extended memory for multiobjective optimization, in: Proceedings of the 2003 IEEE Swarm Intelligence Symposium, Indianapolis, 2003, pp. 193-197.; X. Hu, R. Eberhart, Y. Shi, Particle swarm with extended memory for multiobjective optimization, in: Proceedings of the 2003 IEEE Swarm Intelligence Symposium, Indianapolis, 2003, pp. 193-197. |
| [25] | J. Kennedy, Small worlds and mega-minds: Effects of neighborhood topology on particle swarm performance, in: Proceedings of the 1999 Conference on Evolutionary Computation, 1999, pp. 1931-1938.; J. Kennedy, Small worlds and mega-minds: Effects of neighborhood topology on particle swarm performance, in: Proceedings of the 1999 Conference on Evolutionary Computation, 1999, pp. 1931-1938. |
| [26] | J. Kennedy, The particle swarm: Social adaptation of knowledge, in: Proceedings of the 1997 International Conference on Evolutionary Computation, Indianapolis, IN, 1997, pp. 303-308.; J. Kennedy, The particle swarm: Social adaptation of knowledge, in: Proceedings of the 1997 International Conference on Evolutionary Computation, Indianapolis, IN, 1997, pp. 303-308. |
| [27] | J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of the 1995 IEEE International Conference on Neural Networks, IV, 1995, pp. 1942-1948.; J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of the 1995 IEEE International Conference on Neural Networks, IV, 1995, pp. 1942-1948. |
| [28] | Kennedy, J.; Eberhart, R., Swarm Intelligence (2001), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Francisco |
| [29] | Melachrinoudis, E., Bicriteria location of a semi-obnoxious facility, Computers and Industrial Engineering, 37, 3, 581-593 (1999) |
| [30] | Melachrinoudis, E.; Xanthopulos, Z., Semi-obnoxious single facility location in Euclidean space, Computers and Operations Research, 30, 14, 2191-2209 (2003) · Zbl 1039.90030 |
| [31] | J. Moore, R. Chapman, Application of particle swarm to multiobjective optimization, Department of Computer Science and Software Engineering, Auburn University, 1999.; J. Moore, R. Chapman, Application of particle swarm to multiobjective optimization, Department of Computer Science and Software Engineering, Auburn University, 1999. |
| [32] | Okabe, A.; Boots, B.; Sugihara, K., Spatial Tessellations, Concepts and Applications of Voronoi Diagrams (1992), John Wiley & Sons: John Wiley & Sons Chichester · Zbl 0877.52010 |
| [33] | E. Ozcan, C.K. Mohan, Particle swarm optimization: Surfing the waves, in: Proceedings of the IEEE 1999 Congress on Evolutionary Computation, 1999, pp. 1939-1944.; E. Ozcan, C.K. Mohan, Particle swarm optimization: Surfing the waves, in: Proceedings of the IEEE 1999 Congress on Evolutionary Computation, 1999, pp. 1939-1944. |
| [34] | K.E. Parsopoulos, D.K. Tasoulis, M.N. Vrahatis, Multiobjective optimization using parallel vector evaluated particle swarm optimization, in: Proceedings of the IASTED International Conference on Artificial Intelligence and Applications, vol. 2, 2004, pp. 823-828.; K.E. Parsopoulos, D.K. Tasoulis, M.N. Vrahatis, Multiobjective optimization using parallel vector evaluated particle swarm optimization, in: Proceedings of the IASTED International Conference on Artificial Intelligence and Applications, vol. 2, 2004, pp. 823-828. |
| [35] | K.E. Parsopoulos, M.N. Vrahatis, Particle swarm optimization method in multiobjective problems, in: Proceedings of the 2002 ACM Symposium on Applied Computing, 2002, pp. 603-607.; K.E. Parsopoulos, M.N. Vrahatis, Particle swarm optimization method in multiobjective problems, in: Proceedings of the 2002 ACM Symposium on Applied Computing, 2002, pp. 603-607. · Zbl 1018.68063 |
| [36] | Plastria, F., GBSSS: The generalized big square small square method for planar single-facility location, European Journal of Operational Research, 62, 2, 163-174 (1992) · Zbl 0760.90067 |
| [37] | Romero-Morales, D.; Carrizosa, E.; Conde, E., Semi-obnoxious location models: A global optimization approach, European Journal of Operational Research, 102, 2, 295-301 (1997) · Zbl 0955.90054 |
| [38] | Sarin, R. K., Ranking of multiattribute alternatives with an application to coal power siting, (Fandel, G.; Gal, T., Multiple Criteria Decision Making: Theory and Applications (1980), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0435.90059 |
| [39] | Y. Shi, R.C. Eberhart, A modified particle swarm optimizer, in: Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, 1998, pp. 69-73.; Y. Shi, R.C. Eberhart, A modified particle swarm optimizer, in: Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, 1998, pp. 69-73. |
| [40] | Y. Shi, R.C. Eberhart, Parameter selection in particle swarm optimization, in: Proceedings of 7th Annual Conference on Evolutionary Programming, 1998, pp. 591-600.; Y. Shi, R.C. Eberhart, Parameter selection in particle swarm optimization, in: Proceedings of 7th Annual Conference on Evolutionary Programming, 1998, pp. 591-600. |
| [41] | Skriver, A. J.V.; Andersen, K. A., The bicriterion semi-obnoxious location problem (BSLP) solved by an &z.epsiv;-approximation, European Journal of Operational Research, 146, 3, 517-528 (2003) · Zbl 1037.90043 |
| [42] | H. Yapicioglu, G. Dozier, A.E. Smith, Bi-criteria model for locating a semi-desirable facility on a plane using particle swarm optimization, in: Proceedings of the 2004 Congress on Evolutionary Computation, 2004, pp. 2328-2334.; H. Yapicioglu, G. Dozier, A.E. Smith, Bi-criteria model for locating a semi-desirable facility on a plane using particle swarm optimization, in: Proceedings of the 2004 Congress on Evolutionary Computation, 2004, pp. 2328-2334. |
| [43] | Yu, P. L., Multiple criteria decision making: Five basic concepts, (Nemhauser, G. L.; Rinnooy Kan, A. H.G.; Todd, M. J., Handbooks in Operations Research and Management Science, Optimization (1989), Elsevier Science Publishers: Elsevier Science Publishers Amsterdam), 663-699 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
