On multimodality of obnoxious faclity location models

Universidad de Málaga in co-operation with Wageningen University and University of Almeria Dpt.Computer Architecture, Operations Research and Logistics – Computer Architecture and Electronics ON MULTIMODALITY OF OBNOXIOUS FACILITY LOCATION MODELS MSC. THESIS º Author: Supervisors: Ditte Frank Eligius M.T. Hendrix Pilar Martinez Ortigosa Almeria, 9 March 2009 1 2 Preface Writing this Master thesis was an interesting and joyful journey. First of all it was a scientific journey, where I learned more than I could ever imagine on forehand. The first person I need to thank for that is my supervisor Dr. Eligius Hendrix. The second supervisor, Dra. Pilar Martinez Ortigosa, I am very grateful for sharing her in dept knowledge on algorithms. I like to thank Dra. Juana Lopez Redondo for her useful comments on my thesis. Dr. Leocadio Gonzalez Casado taught me the basics of programming and Branch and Bound algorithms in the course ´Algoritmos de Optimizacion Global: Estrategias Paralelas´ of the University of Almeria (UAL), he was very patient if I didn’t understand everything immediately. Furthermore I want to thank all people of the department of Computers Architecture and Electronics of the UAL, led by Dra. Inmaculada Garcia Fernandez, for giving me a warm welcome and the necessary facilities for writing this thesis. The journey I have made during the research for my thesis was not bounded by the walls of the university. I’ve got the opportunity to meet many international researchers on location science during the Euro Working Group on Locational Analysis (EWGLA XVII) in Elche, Spain, see (EWGLA, 2008). It helped me to get a better insight in locational problems. The University of Seville invited me to present my research at their University. I am really grateful that they gave me the chance to share ideas about my research. Finally, Wageningen University gave me the education that led to this MSc. thesis, the result of my journey. 3 4 Contents Abstract ......................................................................................................................................... 7 1.1 Background of the problem................................................................................................. 8 1.2 Objective ............................................................................................................................. 8 1.3 Research questions ............................................................................................................ 9 2. Literature on Obnoxious Facility Location Models .................................................................. 10 2.1 Literature overview............................................................................................................ 10 2.1 Literature search ............................................................................................................... 12 3. Obnoxious Single Facility Location Models............................................................................. 13 3.1 Notation............................................................................................................................. 13 3.2 Maximin Models ................................................................................................................ 14 3.2.1 Model 0. Generic model ............................................................................................ 14 3.2.2 Model 1. Obnoxious linesegment .............................................................................. 15 3.2.3 Model 2. Polyhedral forbidden regions...................................................................... 15 3.2.4 Model 3. Mixed Integer Programming ....................................................................... 16 3.2.5 Model 4. Circular and rectangular forbidden regions ................................................ 16 3.2.6 Model 5, 7, 8. Generic model with weights................................................................ 17 3.2.7 Model 6. Minimize maximum damage....................................................................... 18 3.3 Maxisum Models ............................................................................................................... 19 3.3.1 Model 0. Generic model ............................................................................................ 19 3.3.2 Model 1, 2. Generic model with weights.................................................................... 19 3.4 Minisum Models ................................................................................................................ 20 3.4.1 Model 0. Generic model ............................................................................................ 20 3.4.2 Model 1, 3 Wind dispersion (wind direction).............................................................. 20 3.4.3 Model 2. Wind dispersion (wind velocity) .................................................................. 21 3.4.4 Model 4. Global repulsion.......................................................................................... 22 3.4.5 Model 5. Generic model with weights........................................................................ 22 4. Algorithms for solving multimodal location problems .............................................................. 23 4.1 Introduction ....................................................................................................................... 23 4.2 Grid Search....................................................................................................................... 23 4.3 Controlled Random Search............................................................................................... 24 4.4 Genetic Algorithm.............................................................................................................. 24 4.5 Multistart............................................................................................................................ 25 4.6 MILP Branch-and-Bound .................................................................................................. 26 5. Solvers..................................................................................................................................... 27 5.1 Fmincon (Multistart) .......................................................................................................... 27 5.2 CPLEX .............................................................................................................................. 27 6. Test cases ............................................................................................................................... 28 6.1 Test Case 1....................................................................................................................... 28 6.2 Test Case 2....................................................................................................................... 28 6.3 Test Case 3....................................................................................................................... 28 6.4 Illustration Case Andalucía ............................................................................................... 29 7. Results Algorithm Testing ....................................................................................................... 30 7.1 Introduction ....................................................................................................................... 30 7.2 Results Grid Search.......................................................................................................... 31 7.3 Results Controlled Random Search.................................................................................. 32 7.4 Results Genetic Algorithm ................................................................................................ 33 7.5 Results Multistart............................................................................................................... 34 7.7 Conclusion Results Algorithms ......................................................................................... 35 8.Analysis Models ....................................................................................................................... 37 8.1 Introduction ....................................................................................................................... 37 8.2 Results Maximin models................................................................................................... 38 8.3 Results Maxisum models.................................................................................................. 40 8.4 Results Minisum models................................................................................................... 41 8.5 Conclusion Results models............................................................................................... 42 8.6 Discussion Results distance metrics................................................................................. 42 9. Conclusions............................................................................................................................. 46 10. Discussion ............................................................................................................................. 46 5 11. Recommendations for future research.................................................................................. 47 References .................................................................................................................................. 48 Appendix A. Results of Scopus search ....................................................................................... 53 Appendix B. Selection of Obnoxious Single Facility Models....................................................... 57 Appendix C. Data of Test Cases 1, 2 and 3................................................................................ 61 Appendix D. Data of Illustration Case Andalucía ........................................................................ 62 Content Cd-rom Appendix A. Results of Scopus search Appendix B. Selection of Obnoxious Single Facility Models Appendix C. Data of Test Cases 1, 2 and 3 Appendix D. Data of Illustration Case Andalucía Appendix E. GAMS file Appendix F. GAMS result Appendix G. Matlab files Appendix G.1. M-files Algorithms Appendix G.1.1. M-files Grid Search Appendix G.1.1.1. Maximin Grid Search Appendix G.1.1.2. Maxisum Grid Search Appendix G.1.1.3. Minisum Grid Search Appendix G.1.2. M-files Controlled Random Search Appendix G.1.2.1. Maximin Controlled Random Search Appendix G.1.2.2. Maxisum Controlled Random Search Appendix G.1.2.3. Minisum Controlled Random Search Appendix G.1.3. M-files Genetic Algorithm Appendix G.1.3.1. Maximin GA Appendix G.1.3.2. Maxisum GA Appendix G.1.3.3. Minisum GA Appendix G.1.4. M-files Multistart Appendix G.1.4.1. Maximin Multistart Appendix G.1.4.2. Maxisum Multistart Appendix G.1.4.3. Minisum Multistart Appendix G.2. M-files Models Appendix G.2.1. M-files Maximin Models Appendix G.2.1.1. M-files Discussion Results Distance Metric Appendix G.2.1.1.1. Euclidean Appendix G.2.1.1.2. Rectilinear Appendix G.2.1.2. M-files Euclidean Appendix G.2.1.2.1. M-files Maximin Model 0 Appendix G.2.1.2.2. M-files Maximin Model 1 Appendix G.2.1.2.3. M-files Maximin Model 2 Appendix G.2.1.2.4. M-files Maximin Model 4 Appendix G.2.1.2.5. M-files Maximin Model 5,7,8, Appendix G.2.1.2.6. M-files Maximin Model 6 Appendix G.2.1.3. M-files Rectilinear Appendix G.2.1.3.1. M-files Maximin Model 0 Appendix G.2.1.3.2. M-files Maximin Model 5,7,8 Appendix G.2.2. M-files Maxisum Models Appendix G.2.2.1. M-files Discussion Results Distance Metric Appendix G.2.2.1.1. Euclidean Appendix G.2.2.1.2. Rectilinear Appendix G.2.2.2. M-files Euclidean Appendix G.2.2.2.1. M-files Maxisum Model 0 Appendix G.2.2.2.2. M-files Maxisum Model 1,2 Appendix G.2.2.3. M-files Rectilinear Appendix G.2.2.3.1. M-files Maxisum Model 0 Appendix G.2.2.3.2. M-files Maxisum Model 1,2 Appendix G.2.3. M-files Minisum Models Appendix G.2.3.1. M-files Discussion Results Distance Metric Appendix G.2.3.1.1. Euclidean 6 Appendix G.2.3.1.2. Rectilinear Appendix G.2.3.2. M-files Euclidean Appendix G.2.3.2.1. M-files Minisum Model 0 Appendix G.2.3.2.2. M-files Minisum Model 1,3 Appendix G.2.3.2.3. M-files Minisum Model 2 Appendix G.2.3.2.4. M-files Minisum Model 4 Appendix G.2.3.2.5. M-files Minisum Model 5 Appendix G.2.3.3. M-files Rectilinear Appendix G.2.3.3.1. M-files Minisum Model 0 Appendix H. Matlab Results Appendix H.1. Results Algorithms Appendix H.1.1. Results Grid Search Appendix H.1.2. Results Stochastic Algorithms Appendix H.2. Results Models Appendix H.2.1. Results Models Euclidean Appendix H.2.2. Results Models Rectilinear 7 Abstract Obnoxious single facility location models are models that have the aim to find the best location for an undesired facility. Undesired is usually expressed in relation to the so-called demand points that represent locations hindered by the facility. Because obnoxious facility location models as a rule are multimodal, the standard techniques of convex analysis used for locating desirable facilities in the plane may be trapped in local optima instead of the desired global optimum. It is assumed that having more optima coincides with being harder to solve. In this thesis the multimodality of obnoxious single facility location models is investigated in order to know which models are challenging problems in facility location problems and which are suitable for site selection. Selected for this are the obnoxious facility models that appear to be most important in literature. These are the maximin model, that maximizes the minimum distance from demand point to the obnoxious facility, the maxisum model, that maximizes the sum of distance from the demand points to the facility and the minisum model, that minimizes the sum of damage of the facility to the demand points. All models are measured with the Euclidean distances and some models also with the rectilinear distance metric. Furthermore a suitable algorithm is selected for testing multimodality. Of the tested algorithms in this thesis, Multistart is most appropriate. A small numerical experiment shows that Maximin models have on average the most optima, of which the model locating an obnoxious linesegment has the most. Maximin models have few optima and are thus not very hard to solve. From the Minisum models, the models that have the most optima are models that take wind into account. In general can be said that the generic models have less optima than the weighted versions. Models that are measured with the rectilinear norm do have more solutions than the same models measured with the Euclidean norm. This can be explained for the maximin models in the numerical example because the shape of the norm coincides with a bound of the feasible area, so not all solutions are different optima. The difference found in number of optima of the Maxisum and Minisum can not be explained by this phenomenon. 8 1.Introduction 1.1 Background of the problem Since the second half of the last century, recent advances and innovations in technology and industry created many facilities that are needed but may pose a serious danger to the individuals living nearby. These facilities are called obnoxious (or undesired) facilities. Obnoxious is usually expressed in relation to the so-called demand points that represent locations hindered by the facility. Erkut and Neuman (1989) defined an obnoxious facility as one that generates a disservice to the people nearby while producing an intended product or service. Examples of obnoxious facilities are a hazardous waste disposal site or a nuclear plant. In order to find the optimal site for an obnoxious facility existing (friendly) facility location models are adjusted (Carrizosa, 1999). Instead of locating the facility as near as possible, the new models aim for maximizing the minimal distance between the facility and the demand point (Boas Ben-Moshe, 2000). As a result of adapting existing friendly facility location models, things are more complicated from an algorithmic point of view. Carrizosa states in (Carrizosa, 1999) that because obnoxious models as a rule are multimodal, the standard techniques of convex analysis used for locating desirable facilities in the plane (e.g. Michelot, 1993) may be trapped in local optima instead of the desired global optimum (see Figure 1). Multimodal functions are characterized by having more than one optima, but can either have a single or more than one global optima. In ´Stochastic Global Optimization´ (Zhigljavsky, 2008) an objective function is called multimodal if either there is more than one local minimum or the number of local minima is unknown. Fig. 1. Optimization problem with nonconvex objective f(x) (a) with local optima point a and c and a global optimum in point b and convex objective (b) with only a global optima, indicated by d (Demeulenaere, 2008). Many optima as an outcome of the model are undesired because the aim of the model is to find a global optimum, as this is the best location for the obnoxious facility. More optima give a higher chance to get stuck in a local optimum. The objective of this thesis is to determine which obnoxious single facility location models are suitable for site selection, detecting a globally optimal plan, which means there are no better plans in the rest of the feasible area (Hendrix, 2007). 1.2 Objective The objective of this thesis is to investigate which obnoxious single facility location models are suitable to determine the optimal location for an obnoxious facility by having a globally optimal plan. Therefore the obnoxious single facility location models are tested on their multimodality since is assumed that models with more optima are harder to solve. 15 Search II: Undesirable facility model: Model 3 (article nr. 1: Nadirler et al. 2007) Model 4 (article nr. 6: Caceres et al. 2007) Model 5 (article nr. 8: Saameno et al. 2006) Model 6 (article nr. 23: Carrizosa et al. 1998) Model 7 (article nr. 29: Erkut et al. 1989) Model 8 (article nr. 32: Melachrinoudis, 1985) In the following sections these models are discussed. 3.2.2 Model 1. Obnoxious linesegment This paper is considering an obnoxious facility that is not a point but a line segment. A location for an undesirable anchored segment of fixed length has to be found. An example for an application is the transportation of hazardous materials from a fixed site across a linear path with a bounded length. Fig. 3.1. Obnoxious linesegment where ε is the damage radius of the obnoxious linesegment (Barcia, 2003). In Figure 3.1, the distance of size ε from the obnoxious linesegment x to a demand point i , if the demand point is on the hippodrome, is shown. Objective function b z max (1.3) Subject to ( ) xPdz ib , ≤ for all i (1.4) Where d(P i , x) is the Euclidean minimum distance between demand point i and a point of linesegment x               ⋅−+         =∈= 2 1 02 01 2 )1(/ E E x x x x xRxx λλ 10 ≤ ≤ λ (1.5) lxxxx EE =−+− ))()(( 2 022 2 01 1 (1.6) Sx ∈ (1.7) 3.2.3 Model 2. Polyhedral forbidden regions The problem deals with locating a point in a given convex polyhedron which maximizes the minimum Euclidean distance from a given set of convex polyhedra representing protected areas around population points (Figure 3.2). The problem is to locate a single undesirable facility in the permissible region so as to maximize its Euclidean distance from the nearest polygonal forbidden region. This means that the facility should be located as far away as possible from the protection area around the nearest demand point. In the test case there is no information on size of protection areas around demand points. Therefore weights are given to the demand points, depending on the size of the areas around them. If an area around a demand point is large, a high weight is given (e.g. 5). The other way around, a low weight is given (e.g. 1). These weights are assigned to generated protection areas. The aim of this is to locate the facility as far away as possible from the closest border of the protection area. 16 Objective function c zmax (1.8) Subject to ( ) xEdz jc ,≤ for all j (1.9) Where d ( E j , , x ) is the minimum Euclidean distance from facility location x to a point of protected area E j Tx ∈ (1.10) Fig. 3.2. X 1* is a global maximum although it is not equidistant to E 1 and E 2 (Fernandez, 1997). 3.2.4 Model 3. Mixed Integer Programming In this paper a 1-maximin problem with rectilinear distances is studied. A single undesirable facility in a continuous planar region is located while considering the interaction between the facility and existing demand points. The 1-maximin problem has been formulated as an MIP model in the literature (Sayin, 2000). New bounding schemes are suggested to increase the solution efficiency. It is an adjustment on Sayins model to make it easier to solve. Objective function a zmax (1.11) Subject to ia dz ≤ for all i (1.12) i d = −+−+ +++ 2211 iiii dddd for all i (1.13) illilil Pxdd −=− −+ for all i, for all l (1.14) ilil Mtd ≤ + for all i, for all l (1.15) )1( ilil tMd −≤ − for all i, for all l (1.16) 0, ≥ −+ ilil dd for all i (1.17) }1,0{∈ il t for all i, for all l (1.18) Sx ∈ (1.19) Sayin tries to linearize the problem by using a mixed integer mathematical model in which the rectilinear distance is calculated by a set of constraints controlled by binary variables. 3.2.5 Model 4. Circular and rectangular forbidden regions All demand points are surrounded by a protection area. The aim is to locate the facility as far as possible from the closest border, while remaining in the feasible area. The shape of the border can have the shape of a rectangle or of a circle (see Figure 3.3). The sides of the rectangle should be parallel to the axes. A set of points and line segments should be considered in order to find the optimal location for the facility. 17 Objective function c zmax (1.20) Subject to ( ) xCdz kkc ,≤ for all k (1.21) ( ) xRdz mmc ,≤ for all m (1.22) Where d k (C k , x) is the Euclidean distance from obnoxious facility x to the circular protected area k and d m (R m , x) is the Euclidean distance from obnoxious facility x to the rectangular protected area m. Tx ∈ (1.23) Fig. 3.3. A situation with a rectilinear protected area R m and circular protected areas C k (Carceres, 2007). 3.2.6 Model 5, 7, 8. Generic model with weights Model 5. This paper describes a method to determine a finite set in which an optimal solution is located for a general Euclidean problem of locating an undesirable facility in a polygonal region. It can be determined in polynomial time. The general problem that is proposed leads to several well known problems, such as the maximin problem. Model 7. This paper contains a survey of the maximization location models in the Operations Research literature. One of the models is the maximin model. In this article both Euclidian and rectilinear distances are suggested as distance metric. Model 8. The problem in this paper is formally defined to be the selection of a location within the convex region that maximizes the minimum weighted Euclidean distances with respect to all existing facilities (Figure 3.4). Fig. 3.4. An example with 3 weighted demand points and a possible location in between them (Melachrinoudis, 1985). The models of articles 5, 7 and 8 have the same model formulation. The Maximin model in these articles is formulated as the generic maximin model, model 0, only weights are attached to the demand points. Constraint 1.1 of model 0 is replaced by constraint 1.24: ( ) xPdwz iia ,≤ for all i (1.24) 18 3.2.7 Model 6. Minimize maximum damage Suppose that an undesirable facility is to be located at some point x within a region S. The facility will affect the existing population. In this paper a model is described which seeks location x for which the highest damage to any of the demand points P i is minimized. Objective function qmin (1.25) Subject to ( ) i L i i xPd w q, ≥ for all i (1.26) Where d(P i , x) is the Euclidean distance between P i and x Sx ∈ (1.27) 19 3.3 Maxisum Models Introduction The maxisum criterion (or maxian or antimedian) attempts to maximize the sum of the distances from the undesirable (obnoxious) facility to the population centres. The optimal facility location will always be in the boundary of the feasible region (Saameño, 2006). This means that there is a limited number of optimal solutions. A generic single facility maxisum location problem is given by model 0. 3.3.1 Model 0. Generic model Objective function d z max (2) Subject to ∑ = = n i id xPdz 1 ),( (2.1) Where d(P i , x) is the Euclidean or rectilinear distance from the obnoxious facility x to the demand point i . Sx ∈ (2.2) Result of the literature research In the literature research two Maxisum models are found in articles that correspond with the number between brackets (see Appendix A for article titles). Maxisum models that satisfy all criteria: Search II: Undesirable facility model: Model 1 (article nr. 8: Saameno et al. 2006) Model 2 (article nr. 29: Erkut et al. 1989) In the following sections these models are discussed. 3.3.2 Model 1, 2. Generic model with weights Model 1. The general problem that is proposed in this article leads to several well known problems, such as the maxisum problem. The Maxisum model given in this article is the same as model 2 (Erkut et al.,1989). Model 2. Erkut et al. express the generic single facility maximum problem an the feasible region S . They give Euclidean as well as rectilinear versions of this problem. The model is defined as the generic model, only weights are attached to the demand points. Constraint (2.1) of model 0 is replaced by constraint (2.3). ∑ = = n i iid xPdwz 1 ),( (2.3) The authors state that there is little literature on 1-maxisum problems. In search for Maxisum problems for this thesis the same can be concluded. 20 3.4 Minisum Models The objective of a Minisum model is to locate an obnoxious facility such that it gives minimum damage to all demand points. A generic single facility Minisum model is given by model 0. 3.4.1 Model 0. Generic model Objective function e zmin (3) Subject to ∑ = ⋅= n i L i ie i xPd fz 1 ),( 1 (3.1) Where d(P i , x) is the Euclidean or rectilinear distance from obnoxious facility x to demand point i . = i f    1 0 if if GxPd GxPd i i ≤ > ),( ),( for all i (3.2) Sx ∈ (3.3) Result of the literature research Five Minisum models are found in articles corresponding to the numbers between brackets (see Appendix A for article titles). Minisum models that satisfy all criteria: Search I: Obnoxious facility model: Model 1 (article nr. 34: Karkazis et al. 1992) Model 2 (article nr. 35: Karkazis et al. 1991) Model 3 (article nr. 36: Karkazis et al. 1992) Search II: Undesirable facility model: Model 4 (article nr. 20: Fernandez et al. 2000) Model 5 (article nr. 23: Carrizosa et a. 1998) In the following sections these models are discussed. 3.4.2 Model 1, 3 Wind dispersion (wind direction) Model 1. This article describes a minisum problem, with wind dispersion in Euclidean distances, see Figure 3.5. With regard to the location of the facility it is reasonable to search for a point minimizing the total pollution load, z f , over all demand points and all wind velocities. The Minisum model given in this article is based on model 3 and therefore only model 3 is described below. Model 3. Fig. 3.5. The pollutant dispersion model 21 Objective function f zmin (3.4) Subject to ∑ ∑ = i n ininf xPfwnz ),( (3.5) )) )( () )( ((5.0exp( )()( ),( 22 ii i iin in pV h pq y pVpq O xPf +−⋅= πµ ) for all n (3.6) Where f n is the pollution dispersion function for wind direction n 8929.0 0804.0)( ii ppq = (3.7) and q is the horizontal diffusion parameter for 100 m ≤ p ≤ 120000 m. 4/13/12/1 3357.27445.19069.13913.8)( iiii ppppV −+−+= (3.8) V is the vertical diffusion parameter. Sx ∈ (3.9) For a certain wind direction n the damage to all demand points is calculated for obnoxious facility x . The goal of the model is to minimize the sum of damage of all these wind directions. The blue shape in Figure 3.6 shows the influence area from the obnoxious facility located in the middle of the circle, if there is a strong wind velocity from the Nord (N) East (O), with a high frequency of occurrence. Fig. 3.6. The blue shape is an example of an influence area of an obnoxious facility that is located with model 1 and 3. The space within the orange circle is a possible influence are of an obnoxious facility located with model 2. 3.4.3 Model 2. Wind dispersion (wind velocity) The model in this article is called the wind model. It has similarities to model 1, 3 but there are some differences. Index o in this model is the index of wind velocity instead of the index of wind directions. Constraint (3.6) of model 1,3 is replaced by constraint (3.10). )) )( () )( ((5.0exp( )()( ),( 22 ii i iio io pV h pq y pVpqu O xPf +−⋅= π ) for all o (3.10) The difference between this model and model in article 1 and article 3 is that the ´mean wind velocity µ n ´, which is the average wind velocity of wind direction n, is replaced by ´wind velocity u o ´, which stands for the o t h wind velocity and where the wind velocity is independent of the direction of the wind. 22 3.4.4 Model 4. Global repulsion The objective of the model presented is to minimize the global repulsion of the inhabitants of the geographical region where the facility has to be located as they feel it. A non-linear decay function is proposed to measure the different degrees of repulsion that the inhabitants may feel depending on the kind of facility to be located or the special characteristics of the inhabitants of a city. Furthermore, environmental concerns are taking into account through the definition of protected areas where the location is not allowed. Around each city there is also a forbidden region to avoid the location of the polluting facility too close to it (see Figure 3.7). Fig. 3.7. An example of a feasible set in grey with the cities located in the solid black spots. Objective function g zmin (3.11) Subject to ∑ = ⋅= n i iig xPrpwz 1 ),( (3.12) )),(exp(1 1 ),( xPd xPrp iii i ⋅++ = βα (3.13) Ux ∈ (3.14) The lower the value of α i , the higher the repulsion of the inhabitants to the location of the facility near their city or its outlaying areas, and the higher the value of β i , the faster is the change in the opinion from considering a distance non-acceptable to acceptable. 3.4.5 Model 5. Generic model with weights Carrizosa presents a model in which one minimizes the total damage caused by the facility to the demand points. This model is the weighted version of the generic model. Besides the weights, model 5 differs because it has no influence radius involved. All demand points in the feasible region are considered. Constraint 3.1 is therefore replaced by constraint (3.15) and constraint (3.2) is deleted. ∑ = = n i L i i e i xPd w z 1 ),( (3.15) 23 4. Algorithms for solving multimodal location problems 4.1 Introduction In this chapter algorithms are presented that are tested on their ability of finding all optima of an obnoxious single facility location model. The algorithms described are: 1. Grid Search 2. Controlled Random Search 3. Genetic Algorithm 4. Multistart 5. MILP Branch-and-bound For each algorithm the pseudo-code is given. 4.2 Grid Search One of the simplest approaches to find an approximation of all optima is doing a grid search. Low dimensional problems can be solved by laying a grid on top of the feasible area (see Figure 4.1). At each grid point the function value is measured. A drawback of this method is that it is possible to miss an optimum. Another drawback is the relative high number of evaluations. The method requires K points to be evaluated. K is ((range of x / grid size of x ) + 1) * ((range of y / grid size of y ) + 1) (Hendrix, 2009). This being said, here Grid Search is used to get an indication of the number of existing optima. The results of Grid Search are used as reference for the outcomes of the other algorithms. Fig. 4.1. Example of a grid over a feasible area (Berkeley Lab, 2009) The Grid Search algorithm (a) Generate grid points uniformly over the feasible area, with a certain mesh size. (b) Evaluate all points on the grid. (c) If a point in the grid has a higher function value than the 8 neighbour grid points, this is regarded an approximation of an optimum, when maximizing (see Table 4). Table 4. In the red circle an optimum of Grid Search is shown. 4.470 4.564 3.996 4.515 5.178 4.702 4.773 5.054 4.565 24 4.3 Controlled Random Search Controlled Random Search (CRS) is the method of Price (1979). It is not very popular by researchers because no analytical property can be derived. Still, the method is often used, because it is easy to implement. It was one of the first algorithms which used population points (Hendrix, 2009). CRS starts with an initial set P of N points sampled uniformly in the feasible area. At every iteration new trial points are generated and replace the worst point in N if they are better. The algorithm stops when all function values are close enough, that is closer than a given accuracy value α. ([Price 1977], influenced by [Becker and Lago 1970]). Fig. 4.2. Generation of a trial point by CRS (Hendrix, 2009) The controlled random search algorithm 1. Generate a population P, of N points uniformly over the feasible area 2. Evaluate all points of population P Iteration process 3. Determine the worst point in P 4. Select random parent points from P 5. Generate a trial point from these parent points If the trial point is feasible, go to the next step, if not, start a new iteration 6. Evaluate the trial point If the trial point is better than the worst point of P go to the next step, if not start a new iteration 7. Replace the worst point of P by the trial point 8. Stop if the stopping criterion is met, this is when best and worst point differ less in function value than α. 4.4 Genetic Algorithm The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce children for the next generation (see Figure 4.3). Over successive generations, the population "evolves" toward an optimal solution (Matlab, 2008). Fig. 4.3. The modification of the population (see left: Nitrogen, 2009) which leads to convergence to an optimal solution (see right: Singh, 2006) 31 7.2 Results Grid Search Implementation The algorithm is executed one time. The stepsize setting is 0.5. The used M-files are in Appendix G.1.1.. Results Maximin model Fig. 7.1. Objective function values of Test case 1 Table 7.1. Results Grid Search Maximin model Maximin Test case Maximum Function E. Global opt. Non global opt. #opt 1 12.04 3721 1 25 26 2 2.83 169 4 5 9 3 1.41 25 4 0 4 Results Maxisum model Fig. 7.2. Objective function values of Test case 1 Table 7.2. Results Grid Search Maxisum model Maxisum Test case Maximum Function E. Global opt. Non global opt. #opt 1 1114.8 3721 1 3 4 2 17.43 169 4 0 4 3 1.41 25 4 0 4 Results Minisum Fig. 7.3. Objective function values of Test case 1 Table 7.3. Results Grid Search Minisum model Minisum Test case Maximum Function E. Global opt. Non global opt. #opt 1 0.23 3721 1 16 17 2 0.80 169 4 1 5 3 0.71 25 4 0 4 0 10 20 30 0 10 20 30 0 5 10 15 0 10 20 30 0 10 20 30 400 600 800 1000 1200 0 10 20 30 0 5 10 15 20 25 30 0 2 4 6 8 10 32 Explanation With mesh size 0.5 it is possible to find all optima of test cases 2 and 3. From this results it is assumed that the number of optima found in test case 1 is a good approximation of the number of existing optima. It is not sure that it is the exact amount of existing optima because it has to be taken into account that there is a possibility of missing a needle point between 4 evaluated points. Another possibility is that an optimum is found that is not a real optimum: in the grid the so called optimum is higher than its eight neighbours, but not higher than a not evaluated point in between. Therefore an optimum found can be on the slope of another optimum. 7.3 Results Controlled Random Search Implementation Population size N = 50 Stop criterion α = 0.05 Number of iterations i = 10000 The used M-files are in Appendix G.1.2. Table 7.4. Results Controlled Random Search Algorithm Maximin Test case Minimum Maximum Mean Variance Function E. min opt max opt # optima 1 11.95 12.04 12.03 0.00 1176.84 1 1 1 2 2.80 2.83 2.82 0.00 722.42 4 4 4 3 1.37 1.41 1.40 0.00 410.89 4 4 4 Maxisum Test case Minimum Maximum Mean Variance Function E. min opt max opt # optima 1 1114.71 1114.77 1114.75 0.00 1713.90 1 1 1 2 17.39 17.43 17.42 0.00 927.98 3 4 3.99 3 1.38 1.41 1.40 0.00 410.82 4 4 4 Minisum Test case Minimum Maximum Mean Variance Function E. min opt max opt # optima 1 0.28 0.35 0.28 0.00 972.24 1 2 1.01 2 0.64 1.00 0.88 0.00 3045.74 1 5 3.86 3 0.71 0.74 0.72 0.00 391.39 4 4 4 Explanation As can be seen in Table 7.4, Controlled Random Search succeeds in finding the global optima of all test cases. The variance of the found optimum function value is approximately zero so it is not hard for the algorithm to find these optima. Controlled Random Search does not find more optima than the global ones, so the algorithm is not effective in detecting local non global optima. 33 7.4 Results Genetic Algorithm Implementation The M-file was generated in Matlab with default settings, except for the population size. The solver is called ´gaGenetic Algorithm´. Population size N = 50 The used M-files are in Appendix G.1.3. Table 7.5. Results Genetic Algorithm Maximin Test case Minimum Maximum Mean Variance Function E. min opt max opt # optima 1 10.61 12.04 11.53 0.42 2600.5 1 1 1 2 2.83 2.83 2.83 0.00 2602.5 1 1 1 3 1.41 1.41 1.41 0.00 2604 1 1 1 Maxisum Test case Minimum Maximum Mean Variance Function E. min opt max opt # optima 1 983.70 1114.76 1104.93 927.02 1066.8 1 1 1 2 17.42 17.43 17.43 0.00 1044.4 1 1 1 3 1.41 1.41 1.41 0.00 1048 1 1 1 Minisum Test case Minimum Maximum Mean Variance Function E. min opt max opt # optima 1 0.28 1.37 0.39 0.05 1052.4 1 1 1 2 0.80 0.80 0.80 0.00 1042.8 1 1 1 3 0.71 0.71 0.71 0.00 1042.6 1 1 1 Explanation Genetic Algorithm is able to find one optimum. The end population converges to one point. This point is not always the same. For test cases 2 and 3 the four different global optima are found, over the 100 runs, but not during one individual run. For test case 1, the number of different optima differs per model. The Maximin and the Minisum models resulted in 5 different optima over 100 runs, while the Maxisum model gave only one optimum. The variance of the optimum function value found is low for the test cases 2 and 3 for all models. It is more difficult for the algorithm to find the global optimum of test case1. Genetic Algorithm is not capable of finding local optima, therefore it is not effective in that sense. 34 7.5 Results Multistart Implementation Number of starting points N = 50 Local optimizer= fmincon The used M-files are in Appendix G.1.4. Table 7.6. Results Multistart Algorithm Maximin Test case Minimum Maximum Mean Variance Function E. min opt max opt # optima 1 12.04 12.04 12.04 0.00 3481.33 7 14 10.53 2 2.83 2.83 2.83 0.00 1233.13 6 9 8.23 3 1.41 1.41 1.41 0.00 599.28 4 4 4 Maxisum Test case Minimum Maximum Mean Variance Function E. min opt max opt # optima 1 1114.77 1114.77 1114.77 0.00 537.03 4 4 4 2 17.43 17.43 17.43 0.00 594.30 4 4 4 3 1.41 1.41 1.41 0.00 602.67 4 5 4.05 Minisum Test case Minimum Maximum Mean Variance Function E. min opt max opt # optima 1 0.28 0.28 0.28 0.00 2270.35 8 17 12.23 2 0.80 0.80 0.80 0.00 315.45 3 8 5.06 3 0.71 0.71 0.71 0.00 530.35 4 5 4.01 Explanation The local optimizer, fmincon, gives the following warning:´Trust-region-reflective method does not currently solve this type of problem, using active-set (line search) instead´. One of the algorithms that is used by fmincon is the ´trust region reflective´ algorithm and it can accept a user-supplied Hessian as the final output of the objective function. Since this algorithm has only bounds or linear constraints, the Hessian of the Lagrangian is the same as the Hessian of the objective function. In this research no Hessian is supplied, so instead of the ´trust region reflective method´ fmincon used another algorithm: the ´active-set´. The active-set algorithm does not accept a user-supplied Hessian. It computes a quasi-Newton approximation to the Hessian of the Lagrangian. (Matlab, 2009). The local solver of the Multistart algorithm is able to find all global optima. The global optima are easy to find by the solver as the variance is approximately zero for all test cases for all models. Besides global optima, other optima are found. From this can be concluded that fmincon is able to find local optima. Fmincon did not find all local optima of test case 1 for the Maximin and the Minisum model. This test case has probably many optima with a small region of attraction. In the results can be observed that the solver converges to more solutions than there actually are optima in test case 3 of the Maxisum model and test cases 2 and 3 of the Minisum model. These points are KarushKuhnTucker points as explained as in Section 5.1. Besides the chance of hitting a KKT point and although it is not possible to find all local optima with the fmincon solver in Multistart, like in test case 1 of the Maximin model and the Minisum model, it is the most promising algorithm. It is the only tested algorithm that is able to find local optima and it gives the correct ratio of optima found between the different test cases and models. 35 7.7 Conclusion Results Algorithms Effectiveness Three algorithms are tested on finding all optima, with Grid Search (the blue bar in Figure 7.4) as a reference algorithm. The Controlled Random Search algorithm (dark green bar in Figure 7.4) is able to find all global optima but it is not effective in finding local optima. The global optima are hit by the genetic algorithm (light green bar in Figure 7.4), but it only converges to one global optimum per run. The Genetic algorithm is not capable of finding local optima, so it is not effective in that sense. The last tested algorithm, Multistart, detects global and local optima (yellow bar in Figure 7.4). The algorithm thus is effective and suitable for testing the selected obnoxious facility location models from literature on their number of optima. Fig. 7.4. Number of optima found per algorithm per test case, for the Maximin, Maxisum and the Minisum model. Efficiency In Table 7.7 the least number of function evaluations per test case per model are marked red. As can be seen there is not one most efficient algorithm for all test cases and models. Table 7.7. Results function evaluations for the algorithms Maximin CRS GA MS Test case Function E. Function E. Function E. 1 1176.84 2600.5 3481.33 2 722.42 2602.5 1233.13 3 410.89 2604 599.28 Maxisum Test case Function E. Function E. Function E. 1 1713.90 1066.8 537.03 2 927.98 1044.4 594.30 3 410.82 1048 602.67 Minisum Test case Function E. Function E. Function E. 1 972.24 1052.4 2270.35 2 3045.74 1042.8 315.45 3 391.39 1042.6 530.35 The Controlled Random Search Algorithm is most efficient on function evaluations for the generic maximin model for all test cases. Multistart is the most efficient algorithm in solving the Maximin 0 5 10 15 20 25 30 123 Test cases # optima Grid Search CRS Genetic Algorithm Multistart Maxisum 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 1 2 3 Test cases # optima Grid Search CRS Genetic Algorithm Multistart Minisum 0 2 4 6 8 10 12 14 16 18 1 2 3 Test cases # optima Grid Search CRS Genetic Algorithm Multistart 36 Maxisum model for test case 1 and 2. For the Minisum model no conclusion can be drawn from the number of function evaluations. Genetic Algorithm is in no situation the most efficient algorithm. Although Controlled Random Search is in 6 out of 9 times the most efficient algorithm, it is not chosen for testing the obnoxious facility location models because it is not effective in detecting local non global optima. 37 8.Analysis Models 8.1 Introduction In the following sections the selected obnoxious facility location models from literature that are described in Chapter 3 are evaluated. The models are evaluated with the illustration case Andalucía (see Section 6.4) on how hard they are to solve assuming that having more optima is a measure for with being harder to solve. Fig. 8.1. Illustration Case Andalucía The computational experiments are conducted on a Intel core 2 duo personal computer with 1024 MB random access memory (RAM) (notebookcheck, 2009). Microsoft Office Excel 2003 SP3, part of the Microsoft Office Professional Edition 2003, is used to make illustrations. Matlab stands for matrix laboratory. It is an interactive system whose basic data element is an array that does not require dimensioning. Version 7.6.0 (R2008b) of Matlab is used for all models, except for Maximin model 3, the Mixed Integer Programming model. Model 3 could not be solved with Matlab, so it is solved with GAMS Version 22.9. GAMS stands for General Algebraic Modeling System, which is a modeling system for mathematical programming and optimization. It consists of a language compiler and a stable of integrated high-performance solvers. The distance metric is Euclidean, but in some articles the rectilinear distance was mentioned as well, so for the models of these articles the distance is both measured Euclidean and rectilinear. These models are: 4. Maximin : Model 0, 5, 7, 8 5. Maxisum: Model 0, 1, 2 6. Minisum: Model 0 Minisum model 0 is the generic minisum model, which is the only model that makes use of an influence radius. If a demand point is in this radius, the obnoxious facility has effect on the demand point. Since other models do not have an influence radius, it is complex to compare. For this reason, the influence radius is set on G= 25, so that every demand point in the feasible area is for certain under influence of the obnoxious facility, like in all the other models. Maximin Model 3 is a Mixed Integer Programming model and therefore it could not be tested in Matlab. The model is solved with GAMS (see Appendix E). Due to license restrictions, a maximum of 50 discrete variables, only 25 of the 32 cities of the case Andalucía could be used as input. So the number of demand points is different from the demand points in the other models. Besides differences in input, there are differences in output. The local solver used in GAMS, CPLEX, does not give the number of local optima, only the global optimum. Instead of the number of function evaluations, CPU time and number of iterations are presented as output. It can be concluded that the input and output of Maximin model 3 is not equal to that of the other models and thus can not be compared. However, the output of the model is presented in Table 8.2 in Section 8.2, Results of the Maximin models, and the global optimum of model 3 is drawn in Figure 8.2. 38 Each model solved with Matlab, is run 100 times. After each run the optima counter algorithm is used to determine the number of optima that are found. The pseudo-code of the optima counter algorithm used is given in Section 7.1. Performance indicators The characteristics of the models are determined by the ability of an algorithm to find the global optimum and this is measured by the number of times that Multistart finds the global optimum (see # Global optima). The second indicator for analysing the models is the variance: a low variance means that it is easy for Multistart to find the global optima (see Variance). Finally the number of optima (see # optima) is an indicator. If the model has few optima, it is considered to be easier to solve. The efficiency of solving the models with Multistart is measured by the average number of function evaluations that is needed to converge per run, over 100 runs (see # Function E.). To calculate the above described indicators to measure how hard a model is to solve, the following performance indicators are measured: 1. # Global opt: the number of times that the optimum is found per 100 runs 7. Minimum: the minimum optimum function value that is found in 100 runs 8. Maximum: the maximum optimum function value that is found in 100 runs 9. Mean: the mean of the optimum function value found in 100 runs - Variance: the variance of the optimum function value over 100 runs - Function E.: the average number of function evaluations per run - Min opt: the minimum number of optima found by a run, per 100 runs - Max opt: the maximum number of optima found by a run, per100 runs - # optima: the average number of optima over 100 runs Performance indicators for Maximin model 3: 10. Global optimum: function value of the global optimum 11. x1, x2: the xand ycoordinate of the global optimum 12. CPU: Central Processing Unit, in seconds 13. DP: Demand Points 14. # iterations: number of iterations needed to find the global optimum 8.2 Results Maximin models In Figure 8.2 the global optima of the Maximin models are shown. The global optima of all models are situated on constraint 4. This appears to be the location where the minimum distance from the obnoxious facility to the closest demand point is at the maximum. Figure 8.2. Location of the global optimum for each Maximin model The algorithm finds the global optimum of all models in approximately 100% of the runs (see Table 8.1), the variances give the same indication. Of the models where the Euclidean distance metric is used, it can be said that on average model 1, the obnoxious linesegment model, has Maximin 0 0.45 0.9 1.35 1.8 2.25 2.7 3.15 3.6 4.05 0 1.125 2.25 3.375 4.5 5.625 6.75 Longitude Latitude dp constraint 1 constraint 2 constraint 3 constraint 4 constraint 5 model 0 model 1 model 2 model 3 model 4 model 5,7,8 model 6 model 0 Rect model 5,7,8 Rect 39 the most optima, and it needs the most function evaluations. Models 5,7,8, the weighted generic maximin model, has on average the most optima if distance is measured rectilinearly. Model 6, the model that minimizes the maximum damage to one demand point, gives five optima as result, which is the smallest number of optima of the Maximin models. This result corresponds with the least number of needed function evaluations. The models measured with rectilinear distances have on average more optima than the same models measured with Euclidean distances. Implementation Number of starting points N=50 Local optimizer = fmincon Matlab files: Appendix G.2.1. Matlab Results: Appendix H.2. Table 8.1. Result Maximin models Euclidean Model #Global opt Minimum Maximum Mean Variance Function E. min opt max opt # optima 0 100 1.19 1.19 1.19 0.00 2831.33 6 16 10.45 1 98 1.01 1.12 1.11 0.00 9727.52 16 29 23.16 2 100 1.09 1.09 1.09 0.00 2590.56 7 17 11.52 4 100 1.09 1.09 1.09 0.00 2554.06 5 14 9.42 5,7,8 100 0.48 0.48 0.48 0.00 3769.46 8 16 11.46 6 97 1.46 1.51 1.46 0.00 1186.19 3 8 5.08 Rectilinear Model #Global opt Minimum Maximum Mean Variance Function E. min opt max opt # optima 0 97 1.28 1.40 1.40 0.00 2150.57 12 23 16.69 5,7,8 100 0.62 0.62 0.62 0.00 2400.87 19 33 24.69 The output of GAMS of model 3 is given in Table 8.2 (Appendix F). The global optimum is approximately on the same location as the other Maximin models. Implementation Global optimizer = CPLEX GAMS file: Appendix E. GAMS Result: Appendix F. Table 8.2. Results Maximin model 3 CPLEX Model Global opt x1 x2 CPU DP #iterations 3 1.40 6.04 2.33 0.016 s 25 882 40 8.3 Results Maxisum models The weighted and generic Maxisum models have the same optimum (Figure 8.3). They are both trying to maximize the distance from the obnoxious facility to all demand points. Maxisum 0 0.45 0.9 1.35 1.8 2.25 2.7 3.15 3.6 4.05 0 1.125 2.25 3.375 4.5 5.625 6.75 Longitude Latitude dp constraint 1 constraint 2 constraint 3 constraint 4 constraint 5 model 0 model 1,2 model 0 Rect model 1,2 Rect Fig. 8.3. Location the global optimum for each Maxisum model The Maxisum models have a 100% score in resulting in one global optimum. They only have 3 optima on average with the Euclidean distance metric. The same models measured with the rectilinear distance metric have an average of 4 optima with the generic model and an average of 5 optima with the weighted model (Table 8.3). Implementation Number of starting points N=50 Local optimizer = fmincon Matlab files: Appendix G.2.2. Matlab Results: Appendix H.2. Table 8.3. Results Maxisum Euclidean and rectilinear Euclidean Model #Global opt Minimum Maximum Mean Variance Function E. min opt max opt # optima 0 100 107.32 107.32 107.32 0.00 523.26 2 4 2.97 1,2 100 80.68 80.68 80.68 0.00 524.04 2 3 2.99 Rectilinear Model #Global opt Minimum Maximum Mean Variance Function E. min opt max opt # optima 0 100 119.12 119.12 119.12 0.00 497.97 3 5 4.02 1,2 100 88.80 88.80 88.80 0.00 465.00 4 5 4.98 47 11. Recommendations for future research The research can be extended to 15. Semiobnoxious facility location models 16. (semi-) obnoxious multi facility location models 17. (semi-) obnoxious multi objective facility location models - a discreet feasible area or a feasible area on a network Although Multistart is a suitable algorithm for testing multimodality, it is interesting to investigate the performance of other methods for finding all optima, like other multimodal methods, for example based on niching. The Mixed Inter Programming model, Maximin model 3, is only tested with 25 demand points due to licence restrictions of GAMS. To be able to compare the model with the other models, an equal number of demand points, 32, should be used as input. Minisum models 1,2 and 3, also referred to as the wind models, are implemented with wind data that are not of Andalucía. With the data that are used as input for this research, the models have unexpected results for the optimal location. By changing the input data to realistic data for Andalucía it is possible that the models give better optimal solutions. To exclude the influence of illustration case Andalucía on the results of the difference in optima when measuring with the Euclidean or rectilinear norm, another illustration case should be used. 48 References Avella, P., Benati, S., Cánovas Martinez, L., Dalby, K., Di Girolamo, D., Dimitrijevic, B., Ghiani, G., (...), Zidda, P. 1998 Some personal views on the current state and the future of Locational Analysis European Journal of Operational Research 104 (2), pp. 269-287 Barcia, J.A., Díaz-Báñez, J.M., Lozano, A.J., Ventura, I. 2003 Computing an obnoxious anchored segment, Operations Research Letters 31 (4), pp. 293-300 Begeleidzelfstandigleren. 2009 (http://www.begeleidzelfstandigleren.com/aardrijkskunde/vijfdes/atmosfeer/windroos.html, 14 February, 2009) Berkeley Lab, Lawrence Berkeley National Laboratory 2009. (http://wwwesd.lbl.gov/iTOUGH2/Minimization/gridsearch.gif, 5 March 2009) Berman, O., Wang, Q. 2008 Locating a semi-obnoxious facility with expropriation Journal of the Operational Research Society 58 (3), pp. 378-390 Berman, O., Wang, Q. 2007 Locating semi-obnoxious facilities with expropriation: Minisum criterion Journal of the Operational Research Society 58 (3), pp. 378-390 Berman, O., Wang, J. 2004 Probabilistic location problems with discrete demand weights Networks 44 (1), pp. 47-57 Berman, O., Drezner, Z., Wesolowsky, G.O. 2000 Routing and location on a network with hazardous threats Journal of the Operational Research Society 51 (9), pp. 1093-1099 Boaz Ben-Moshe, Matthew J. Katz, Michael Segal. 2000 Obnoxious Facility Location: Complete Service with Minimal Harm, International J. of Computational Geometry and Applications 10, pp. 581-592 Boffey, B., Karkazis, J. 1995 Papers from the 6th international symposium on location decisions (ISOLDE VI): the location of hazardous materials facilities Location Science 3 (3), pp. 141-215 Bourne, P.R., Kitney, R.I. 1978 Matching techniques for clinical models of the circulation Medical and Biological Engineering and Computing 16 (6), pp. 689-696 Boyer, C.B., Kegeles, S.M 1991 AIDS risk and prevention among adolescents Social Science and Medicine 33 (1), pp. 11-23 Burkard, R.E., Hatzl, J. 2008 Median problems with positive and negative weights on cycles and cacti Journal of Combinatorial Optimization, pp. 1-20 Burkard, R.E., Fathali, J., Taghizadeh Kakhki, H. 2007 The p-maxian problem on a tree Operations Research Letters 35 (3), pp. 331-335 Burkard, R.E., Fathali, J. 2007 A polynomial method for the pos/neg weighted 3-median problem on a tree Mathematical Methods of Operations Research 65 (2), pp. 229-238 Burkard, R.E., Çela, E., Dollani, H. 2000 2-Medians in trees with pos/neg weights Discrete Applied Mathematics 105 (1-3), pp. 51-71 Burkard, R.E., Krarup, J. 1998 A Linear Algorithm for the Pos / Neg-Weighted 1-Median Problem on a Cactus Computing (Vienna/New York) 60 (3), pp. 193-215 Cáceres, T., Mesa, J.A., Ortega, F.A. 2007 Locating waste pipelines to minimize their impact on marine environment European Journal of Operational Research 179 (3), pp. 1143-1159 49 Cappanera, P., Gallo, G., Maffioli, F. 2003 Discrete facility location and routing of obnoxious activities Discrete Applied Mathematics 133 (1-3), pp. 3-28 Carrizosa, E., Plastria, F. 1998 Locating an undesirable facility by generalized cutting planes Mathematics of Operations Research 23 (3), pp. 680-694 Carrizosa, E., Plastria, F. 1999 Location of SemiObnoxious Facilities, Studies in Locational Analysis, 12, pp.1-27 Church, R.L., Roberts, K.L., Bell, T.L. 1979 Comments on Orloff's net accessibility model. Geographical Analysis 11 (1), pp. 89-93 Church, Richard L., Garfinkel, Robert S. 1978 LOCATING AN OBNOXIOUS FACILITY ON A NETWORK. Transportation Science 12 (2), pp. 107-118 Colebrook, M., Sicilia, J. 2007 Undesirable facility location problems on multicriteria networks Computers and Operations Research 34 (5), pp. 1491-1514 Colebrook, M., Gutiérrez, J., Sicilia, J. 2005 A new bound and an O(mn) algorithm for the undesirable 1-median problem (maxian) on networks Computers and Operations Research 32 (2), pp. 309-325 Colebrook, M., Gutiérrez, J., Alonso, S., Sicilia, J. 2002 A new algorithm for the undesirable 1center problem on networks Journal of the Operational Research Society 53 (12), pp. 13571366 Demeulenaere, B., Convex optimization for dummies, Katholieke Universiteit Leuven (http://people.mech.kuleuven.be/~bdemeule/convex.html, 6-9-2008) Drezner, Z., Wesolowsky, G.O. 1985 Location of multiple obnoxious facilities Transportation Science 19 (3), pp. 193-202 Erkut, E. 1990 The discrete p-dispersion problem European Journal of Operational Research 46 (1), pp. 48-60 Erkut, E., Baptie, T., von Hohenbalken, B. 1990 The discrete p-Maxian location problem Computers and Operations Research 17 (1), pp. 51-61 Erkut, Erhan, Oncu, T.Sabri 1991 Parametric 1-maximin location problem Journal of the Operational Research Society 42 (1), pp. 49-55 Erkut, E., Neuman, S. 1992 A multiobjective model for locating undesirable facilities Annals of Operations Research 40 (1), pp. 209-227 Erkut, E., Neuman, S. 1989 Analytical models for locating undesirable facilities European Journal of Operational Research 40 (3), pp. 275-291 EWGLA. 2008 (http://cio.umh.es/ewgla2008/default.htm, 1-9-2008) Fernández, J., Fernández, P., Pelegrín, B. 2000 Continuous location model for siting a nonnoxious undesirable facility within a geographical region European Journal of Operational Research 121 (2), pp. 259-274 Fernandez, F., Puerto, J., Rodriguez-Chia, A.M. 1997 A maxmin location problem with nonconvex feasible region Journal of the Operational Research Society 48 (5), pp. 479-489 Fortenberry, Jessey C., Cox, James F. 1985 MULTIPLE CRITERIA APPROACH TO THE FACILITIES LAYOUT PROBLEM. International Journal of Production Research 23 (4), pp. 773782 50 Gajghate, D.G., Hasan, M.Z. 2000 Assessment of Air Pollution Impacts due to a Proposed Hazardous Waste Treatment and Disposal Facility Indian Journal of Environmental Protection 20 (8), pp. 597-601 Garcia, H.E. 2000 Operational analysis and improvement of a spent nuclear fuel handling and treatment facility using discrete event simulation Computers and Industrial Engineering 38 (2), pp. 235-249 Gaussier, N. 2001 The spatial foundations of obnoxious goods location: The garbage dumps case Regional Studies 35 (7), pp. 625-636 GIGLIO RJ 1970 Stochastic capacity m%odels Management Science 17 (3), pp. 174-184 Google Maps. 2008 (http://maps.google.es/, 22 December 2008) Hamacher, H.W., Labbé, M., Nickel, S., Skriver, A.J.V. 2002 Multicriteria semi-obnoxious network location problems (MSNLP) with sum and center objectives Annals of Operations Research 110 (1-4), pp. 33-53 Hendrix, E.M.T. 2007, Nonlinear programming, in G.D.H., Hendriks, Th. H.B., Hendrix, E.M.T. Decision Science, theory and applications. Mansholt publication servicesVolume 2 Hendrix, E.M.T., Toth, B.G. 2009. Introduction to Nonlinear and Global Optimization. Almeria University and Budapest University. In press. Huang, C., Wu, Y.-Y. 2006 A study of location problem and vehicle routing problem for the obnoxious facility 2006 IIE Annual Conference and Exhibition Ishii, H., Yung Lung Lee, Kuang Yih Yeh 2007 Fuzzy facility location problem with preference of candidate sites Fuzzy Sets and Systems 158 (17), pp. 1922-1930 Karkazis, J., Papadimitriou, C. 1992 A branch-and-bound algorithm for the location of facilities causing atmospheric pollution European Journal of Operational Research 58 (3), pp. 363-373 Karkazis, J., Boffey, T.B., Malevris, N. 1992 A branch-and-bound algorithm for the location of facilities causing atmospheric pollution European Journal of Operational Research 58 (3), pp. 363-373 Karkazis, J. 1991 The problem of locating facilities causing airborne pollution revisited OR Spektrum 13 (3), pp. 159-166 Khalil, Tarek M. 1973 FACILITIES RELATIVE ALLOCATION TECHNIQUE (FRAT). International Journal of Production Research 11 (2), pp. 183-194 Lappeenranta University of Technology, Finland. 2009. (www.it.lut.fi/kurssit/0607/Ti5416400/Lectures/CH3_2.pdf, 1 March 2009) Lee, T.Y.S. 2004 The effect of workers with different capabilities on customer delay Computers and Operations Research 31 (3), pp. 359-381 LemmenGerdessen, van, 2007, Heuristics, in G.D.H., Hendriks, Th. H.B., Hendrix, E.M.T. Decision Science, theory and applications. Mansholt publication servicesVolume 2 Ma, H.-C., Chen, Y.-W. 2007 A quality-oriented framework with QoS management using Bluetooth as a case Quality & Quantity, pp. 1-8 Melachrinoudis, E., Xanthopulos, Z. 2003 Semi-obnoxious single facility location in Euclidean space Computers and Operations Research 30 (14), pp. 2191-2209 51 Melachrinoudis, E. 1999 Bicriteria location of a semi-obnoxious facility Computers and Industrial Engineering 37 (3), pp. 581-593 Melachrinoudis, Emanuel 1988 EFFICIENT COMPUTATIONAL PROCEDURE FOR THE RECTILINEAR MAXIMIN LOCATION PROBLEM. Transportation Science 22 (3), pp. 217-223 Melachrinoudis, E. 1985 Determining an optimum location for an undesirable facility in a workroom environment Applied Mathematical Modelling 9 (5), pp. 365-369 Melachrinoudis, Emanuel, Cullinane, Thomas 1985 HEURISTIC APPROACH TO THE SINGLE FACILITY MAXIMIN LOCATION PROBLEM. International Journal of Production Research 23 (3), pp. 523-532 Meyer, M. 2007 Microwave production of carbon fiber reinforced plastics | [Herstellung von Kohlenstofffaserverstärkten Kunststoffbauteilen mit Hilfe von Mikrowellen] DLR Deutsches Zentrum fur Luftund Raumfahrt e.V. - Forschungsberichte (6), pp. 1-115 Michelot, C. 1993. The mathematics of continues location, Studies in Locational Analysis, 5, 5983 UAL (Universidad of Almeria) (http://www.ace.ual.es/~leo/master/Temario.Master.pdf, 8-92008) Moreno-Jiménez, A., Hodgart, R.L. 2003 Modelling a single type of environmental impact from an obnoxious transport activity: Implementing locational analysis with GIS Environment and Planning A 35 (5), pp. 931-946 Muñoz-Pérez, J., Saameño-Rodríguez, J.J. 1999 Location of an undesirable facility in a polygonal region with forbidden zones European Journal of Operational Research 114 (2), pp. 372-379 Nadirler, D., Karasakal, E. 2008 Mixed integer programming-based solution procedure for single-facility location with maximin of rectilinear distance Journal of the Operational Research Society 59 (4), pp. 563-570 Nitrogen - Delphi and OpenGL Programming 2009. (www.nitrogen.za.org/tutorials/ga/ga.png, 7 March 2009) Notebookcheck. 2009 (http://www.notebookcheck.nl/Testrapport-HP-Compaq-6710bNotebook.5245.0.html, 1 March 2009) O'Kelly, M.E., Murray, A.T. 2004 A lattice covering model for evaluating existing service facilities Papers in Regional Science 83 (3), pp. 565-580 Ohsawa, Y., Plastria, F., Tamura, K. 2006 Euclidean push-pull partial covering problems Computers and Operations Research 33 (12), pp. 3566-3582 Ohsawa, Y., Tamura, K. 2003 Efficient Location for a Semi-Obnoxious Facility Annals of Operations Research 123 (1-4), pp. 173-188 Redondo, J.L. 2008. Solving Competitive Location Problems via Memetic Algorithms. High Performance Computing Approaches. PhD Thesis. University of Almeria. Romero-Morales, D., Carrizosa, E., Conde, E. 1997 Semi-obnoxious location models: A global optimization approach European Journal of Operational Research 102 (2), pp. 295-301 Saameño Rodríguez, J.J., Guerrero García, C., Muñoz Pérez, J., Mérida Casermeiro, E. 2006 A general model for the undesirable single facility location problem Operations Research Letters 34 (4), pp. 427-436 Sari, N. 2002 Do competition and managed care improve quality? Health Economics 11 (7), pp. 571-584 52 Singh, G., Deb, K. 2006. Comparison of multi-modal optimization algorithms based on evolutionary algorithms. GECCO, ACM Pub., 1305-1312 Skriver, A.J.V., Andersen, K.A. 2003 The bicriterion semi-obnoxious location (BSL) problem solved by an ε-approximation European Journal of Operational Research 146 (3), pp. 517-528 Stowers, Curtis L., Palekar, Udatta S. 1993 Location models with routing considerations for a single obnoxious facility Transportation Science 27 (4), pp. 350-362 Tageo. 2009 (http://www.tageo.com/index-e-sp-cities-ES.htm, 21 January 2009) Tamir, A. 2006 Locating two obnoxious facilities using the weighted maximin criterion Operations Research Letters 34 (1), pp. 97-105 Tan, S.P., Toh, K.C., Wong, Y.W. 2007 Server-rack air flow and heat transfer interactions in data centers 2007 Proceedings of the ASME InterPack Conference, IPACK 2007 1, pp. 845-849 Thomas, P., Chan, Y., Lehmkuhl, L., Nixon, W. 2002 Obnoxious-facility location and dataenvelopment analysis: A combined distance-based formulation European Journal of Operational Research 141 (3), pp. 495-514 Urban, Timothy L. 1987 MULTIPLE CRITERIA MODEL FOR THE FACILITIES LAYOUT PROBLEM. International Journal of Production Research 25 (12), pp. 1805-1812 Welch, S.B., Salhi, S. 1997 The obnoxious p facility network location problem with facility interaction European Journal of Operational Research 102 (2), pp. 302-319 Yapicioglu, H., Smith, A.E., Dozier, G. 2006 Solving the semi-desirable facility location problem using bi-objective particle swarm European Journal of Operational Research 177 (2), pp. 733749 Yu, M.-M. 2004 Measuring physical efficiency of domestic airports in Taiwan with undesirable outputs and environmental factors Journal of Air Transport Management 10 (5), pp. 295-303 Zhang, F.G., Melachrinoudis, E. 2001 The maximin-maxisum network location problem Computational Optimization and Applications 19 (2), pp. 209-234 Zhigljavsky, A. and Zilinskas, A. 2008. Stochastic Global Optimization, Springer Science Business Media, LLC. Zhu, H. 2003 A role agent model for collaborative systems Proceedings of the International Conference on Information and Knowledge Engineering 2, pp. 438-444 53 Appendix A. Results of Scopus search on ¨obnoxious facility model¨ and ¨undesirable facility model¨ = article of search I is the same as article x of search II Search I: Scopus ¨obnoxious facility¨ model Hits:42, no selection 1 Median problems with positive and negative weights on cycles and cacti Burkard, R.E., Hatzl, J. 2008 Journal of Combinatorial Optimization, pp. 1-20. Article in Press 2 Locating a semi-obnoxious facility with expropriation Berman, O., Wang, Q. 2008 Computers and Operations Research 35 (2), pp. 392-403 3 The p-maxian problem on a tree Burkard, R.E., Fathali, J., Taghizadeh Kakhki, H. 2007 Operations Research Letters 35 (3), pp. 331-335 4 A polynomial method for the pos/neg weighted 3-median problem on a tree Burkard, R.E., Fathali, J. 2007 Mathematical Methods of Operations Research 65 (2), pp. 229-238 5 Locating semi-obnoxious facilities with expropriation: Minisum criterion Berman, O., Wang, Q. 2007 Journal of the Operational Research Society 58 (3), pp. 378-390 6 A study of location problem and vehicle routing problem for the obnoxious facility Huang, C., Wu, Y.-Y. 2006 2006 IIE Annual Conference and Exhibition 7 Euclidean push-pull partial covering problems Ohsawa, Y., Plastria, F., Tamura, K. 2006 Computers and Operations Research 33 (12) pp. 3566-3582 8 A general model for the undesirable single facility location problem Saameño Rodríguez, J.J., Guerrero García, C., Muñoz Pérez, J., Mérida Casermeiro, E. 2006 Operations Research Letters 34 (4), pp. 427-436 9 Solving the semi-desirable facility location problem using bi-objective particle swarm Yapicioglu, H., Smith, A.E., Dozier, G. 2006 European Journal of Operational Research 177 (2), pp. 733-749 10 Locating two obnoxious facilities using the weighted maximin criterion Tamir, A. 2006 Operations Research Letters 34 (1), pp. 97-105 11 A new bound and an O(mn) algorithm for the undesirable 1-median problem (maxian) on networks Colebrook, M., Gutiérrez, J., Sicilia, J. 2005 Computers and Operations Research 32 (2), pp. 309-325 3 12 A lattice covering model for evaluating existing service facilities O'Kelly, M.E., Murray, A.T. 2004 Papers in Regional Science 83 (3), pp. 565-580 13 Semi-obnoxious single facility location in Euclidean space Melachrinoudis, E., Xanthopulos, Z. 2003 Computers and Operations Research 30 (14), pp. 2191-2209 14 Discrete facility location and routing of obnoxious activities Cappanera, P., Gallo, G., Maffioli, F. 2003 Discrete Applied Mathematics 133 (1-3), pp. 3-28 8 15 Efficient Location for a Semi-Obnoxious Facility Ohsawa, Y., Tamura, K. 2003 Annals of Operations Research 123 (1-4), pp. 173-188 16 Computing an obnoxious anchored segment Barcia, J.A., Díaz-Báñez, J.M., Lozano, A.J., Ventura, I. 2003 Operations Research Letters 31 (4), pp. 293-300 17 The bicriterion semi-obnoxious location (BSL) problem solved by an ε-approximation Skriver, A.J.V., Andersen, K.A. 2003 European Journal of Operational Research 146 (3), pp. 517-528 18 Modelling a single type of environmental impact from an obnoxious transport activity: Implementing locational analysis with GIS Moreno-Jiménez, A., Hodgart, R.L. 2003 Environment and Planning A 35 (5), pp. 931-946 2 54 19 Multicriteria semi-obnoxious network location problems (MSNLP) with sum and center objectives Hamacher, H.W., Labbé, M., Nickel, S., Skriver, A.J.V. 2002 Annals of Operations Research 110 (1-4), pp. 33-53 2 20 A new algorithm for the undesirable 1-center problem on networks Colebrook, M., Gutiérrez, J., Alonso, S., Sicilia, J. 2002 Journal of the Operational Research Society 53 (12), pp. 1357-1366 21 Obnoxious-facility location and data-envelopment analysis: A combined distance-based formulation Thomas, P., Chan, Y., Lehmkuhl, L., Nixon, W. 2002 European Journal of Operational Research 141 (3), pp. 495-514 22 The spatial foundations of obnoxious goods location: The garbage dumps case Gaussier, N. 2001 Regional Studies 35 (7), pp. 625-636 23 The maximin-maxisum network location problem Zhang, F.G., Melachrinoudis, E. 2001 Computational Optimization and Applications 19 (2), pp. 209-234 24 Routing and location on a network with hazardous threats Berman, O., Drezner, Z., Wesolowsky, G.O. 2000 Journal of the Operational Research Society 51 (9), pp. 1093-1099 25 2-Medians in trees with pos/neg weights Burkard, R.E., Çela, E., Dollani, H. 2000 Discrete Applied Mathematics 105 (1-3), pp. 51-71 26 Assessment of Air Pollution Impacts due to a Proposed Hazardous Waste Treatment and Disposal Facility Gajghate, D.G., Hasan, M.Z. 2000 Indian Journal of Environmental Protection 20 (8), pp. 597-601 27 Bicriteria location of a semi-obnoxious facility Melachrinoudis, E. 1999 Computers and Industrial Engineering 37 (3), pp. 581-593 28 A Linear Algorithm for the Pos / Neg-Weighted 1-Median Problem on a Cactus Burkard, R.E., Krarup, J. 1998 Computing (Vienna/New York) 60 (3), pp. 193-215 29 Semi-obnoxious location models: A global optimization approach Romero-Morales, D., Carrizosa, E., Conde, E. 1997 European Journal of Operational Research 102 (2), pp. 295-301 30 The obnoxious p facility network location problem with facility interaction Welch, S.B., Salhi, S. 1997 European Journal of Operational Research 102 (2), pp. 302-319 31 A maxmin location problem with nonconvex feasible region Fernandez, F., Puerto, J., Rodriguez-Chia, A.M. 1997 Journal of the Operational Research Society 48 (5), pp. 479-489 32 Papers from the 6th international symposium on location decisions (ISOLDE VI): the location of hazardous materials facilities Boffey, B., Karkazis, J. 1995 Location Science 3 (3), pp. 141-215 33 Location models with routing considerations for a single obnoxious facility Stowers, Curtis L., Palekar, Udatta S. 1993 Transportation Science 27 (4), pp. 350-362 34 A branch-and-bound algorithm for the location of facilities causing atmospheric pollution Karkazis, J., Papadimitriou, C. 1992 European Journal of Operational Research 58 (3), pp. 363-373 35 Location of facilities producing airborne pollution Karkazis, J., Boffey, T.B., Malevris, N. 1992 Journal of the Operational Research Society 43 (4), pp. 313-320 36 The problem of locating facilities causing airborne pollution revisited Karkazis, J. 1991 OR Spektrum 13 (3), pp. 159-166 37 The discrete p-Maxian location problem Erkut, E., Baptie, T., von Hohenbalken, B. 1990 Computers and Operations Research 17 (1), pp. 51-61 38 Analytical models for locating undesirable facilities Erkut, E., Neuman, S. 1989 European Journal of Operational Research 40 (3), pp. 275-291 39 EFFICIENT COMPUTATIONAL PROCEDURE FOR THE RECTILINEAR MAXIMIN LOCATION PROBLEM. Melachrinoudis, Emanuel 1988 Transportation Science 22 (3), pp. 217-223 55 40 Location of multiple obnoxious facilities Drezner, Z., Wesolowsky, G.O. 1985 Transportation Science 19 (3), pp. 193-202 41 Comments on Orloff's net accessibility model. Church, R.L., Roberts, K.L., Bell, T.L. 1979 Geographical Analysis 11 (1), pp. 89-93 42 LOCATING AN OBNOXIOUS FACILITY ON A NETWORK. Church, Richard L., Garfinkel, Robert S. 1978 Transportation Science 12 (2), pp. 107-118 Search II: Scopus ¨undesirable facility¨ model Hits: 106, selection: LIMIT-TO(SUBJAREA, "DECI") OR LIMIT-TO(SUBJAREA, "MATH") OR LIMIT-TO(SUBJAREA, "BUSI") OR LIMIT-TO(SUBJAREA, "COMP") OR LIMIT-TO(SUBJAREA, "ECON") OR LIMIT-TO(SUBJAREA, "MULT") Hits: 38 1 Mixed integer programming-based solution procedure for single-facility location with maximin of rectilinear distance Nadirler, D., Karasakal, E. 2008 Journal of the Operational Research Society 59 (4), pp. 563-570 2 Server-rack air flow and heat transfer interactions in data centers Tan, S.P., Toh, K.C., Wong, Y.W. 2007 2007 Proceedings of the ASME InterPack Conference, IPACK 2007 1, pp. 845-849 3 A quality-oriented framework with QoS management using Bluetooth as a case Ma, H.-C., Chen, Y.-W. 2007 Quality & Quantity, pp. 1-8 Article in Press 4 Fuzzy facility location problem with preference of candidate sites Ishii, H., Yung Lung Lee, Kuang Yih Yeh 2007 Fuzzy Sets and Systems 158 (17), pp. 1922-1930 5 Microwave production of carbon fiber reinforced plastics | [Herstellung von Kohlenstofffaserverstärkten Kunststoffbauteilen mit Hilfe von Mikrowellen] Meyer, M. 2007 DLR Deutsches Zentrum fur Luftund Raumfahrt e.V. - Forschungsberichte (6), pp. 1-115 6 Locating waste pipelines to minimize their impact on marine environment Cáceres, T., Mesa, J.A., Ortega, F.A. 2007 European Journal of Operational Research 179 (3), pp. 1143-1159 7 Undesirable facility location problems on multicriteria networks Colebrook, M., Sicilia, J. 2007 Computers and Operations Research 34 (5), pp. 1491-1514 0 8 A general model for the undesirable single facility location problem Saameño Rodríguez, J.J., Guerrero García, C., Muñoz Pérez, J., Mérida Casermeiro, E. 2006 Operations Research Letters 34 (4), pp. 427-436 9 A new bound and an O(mn) algorithm for the undesirable 1-median problem (maxian) on networks Colebrook, M., Gutiérrez, J., Sicilia, J. 2005 Computers and Operations Research 32 (2), pp. 309-325 10 Measuring physical efficiency of domestic airports in Taiwan with undesirable outputs and environmental factors Yu, M.-M. 2004 Journal of Air Transport Management 10 (5), pp. 295-303 11 Probabilistic location problems with discrete demand weights Berman, O., Wang, J. 2004 Networks 44 (1), pp. 47-57 12 The effect of workers with different capabilities on customer delay Lee, T.Y.S. 2004 Computers and Operations Research 31 (3), pp. 359-381 13 Semi-obnoxious single facility location in Euclidean space Melachrinoudis, E., Xanthopulos, Z. 2003 Computers and Operations Research 30 (14), pp.2191-2209 14 A role agent model for collaborative systems Zhu, H. 2003 Proceedings of the International Conference on Information and Knowledge Engineering 2, pp. 438-444 15 The bicriterion semi-obnoxious location (BSL) problem solved by an ε-approximation Skriver, A.J.V., Andersen, K.A. 2003 European Journal of Operational Research 146 (3), pp.517-528 16 A new algorithm for the undesirable 1-center problem on networks Colebrook, M., Gutiérrez, J., Alonso, S., Sicilia, J. 2002 Journal of the Operational Research Society 53 (12), pp. 1357-1366 56 17 Multicriteria semi-obnoxious network location problems (MSNLP) with sum and center objectives Hamacher, H.W., Labbé, M., Nickel, S., Skriver, A.J.V. 2002 Annals of Operations Research 110 (1-4), pp. 33-53 18 Do competition and managed care improve quality? Sari, N. 2002 Health Economics 11 (7), pp. 571-584 19 Operational analysis and improvement of a spent nuclear fuel handling and treatment facility using discrete event simulation Garcia, H.E. 2000 Computers and Industrial Engineering 38 (2), pp. 235-249 20 Continuous location model for siting a non-noxious undesirable facility within a geographical region Fernández, J., Fernández, P., Pelegrín, B. 2000 European Journal of Operational Research 121 (2), pp. 259-274 21 Bicriteria location of a semi-obnoxious facility Melachrinoudis, E. 1999 Computers and Industrial Engineering 37 (3), pp. 581-593 22 Location of an undesirable facility in a polygonal region with forbidden zones Muñoz-Pérez, J., Saameño-Rodríguez, J.J. 1999 European Journal of Operational Research 114 (2) pp. 372-379 23 Locating an undesirable facility by generalized cutting planes Carrizosa, E., Plastria, F. 1998 Mathematics of Operations Research 23 (3), pp. 680-694 24 Some personal views on the current state and the future of Locational Analysis Avella, P., Benati, S., Cánovas Martinez, L., Dalby, K., Di Girolamo, D., Dimitrijevic, B., Ghiani, G., (...), Zidda, P. 1998 European Journal of Operational Research 104 (2), pp. 269-287 25 A multiobjective model for locating undesirable facilities Erkut, E., Neuman, S. 1992 Annals of Operations Research 40 (1), pp. 209-227 26 AIDS risk and prevention among adolescents Boyer, C.B., Kegeles, S.M. 1991 Social Science and Medicine 33 (1), pp. 11-23 50 27 Parametric 1-maximin location problem Erkut, Erhan, Oncu, T.Sabri 1991 Journal of the Operational Research Society 42 (1), pp. 49-55 28 The discrete p-dispersion problem Erkut, E. 1990 European Journal of Operational Research 46 (1), pp. 48-60 29 Analytical models for locating undesirable facilities Erkut, E., Neuman, S. 1989 European Journal of Operational Research 40 (3), pp. 275-291 30 EFFICIENT COMPUTATIONAL PROCEDURE FOR THE RECTILINEAR MAXIMIN LOCATION PROBLEM. Melachrinoudis, Emanuel 1988 Transportation Science 22 (3), pp. 217-223 31 MULTIPLE CRITERIA MODEL FOR THE FACILITIES LAYOUT PROBLEM. Urban, Timothy L. 1987 International Journal of Production Research 25 (12), pp. 1805-1812 32 Determining an optimum location for an undesirable facility in a workroom environment Melachrinoudis, E. 1985 Applied Mathematical Modelling 9 (5), pp. 365-369 33 Location of multiple obnoxious facilities Drezner, Z., Wesolowsky, G.O. 1985 Transportation Science 19 (3), pp. 193-202 34 MULTIPLE CRITERIA APPROACH TO THE FACILITIES LAYOUT PROBLEM. Fortenberry, Jessey C., Cox, James F. 1985 International Journal of Production Research 23 (4), pp. 773-782 35 HEURISTIC APPROACH TO THE SINGLE FACILITY MAXIMIN LOCATION PROBLEM. Melachrinoudis, Emanuel, Cullinane, Thomas 1985 International Journal of Production Research 23 (3), pp. 523-532 36 Matching techniques for clinical models of the circulation Bourne, P.R., Kitney, R.I. 1978 Medical and Biological Engineering and Computing 16 (6), pp. 689-696 37 FACILITIES RELATIVE ALLOCATION TECHNIQUE (FRAT). Khalil, Tarek M. 1973 International Journal of Production Research 11 (2), pp. 183-194 38 Stochastic capacity m%odels GIGLIO RJ 1970 Management Science 17 (3), pp. 174-184 63 1 b. Bounds on the feasible region for the Illustration Case Andalucía. A * x ≤ b A = [-1.10311 -1 0.118788 -1 -0.21495 1 1.027 1 1.918172 -1]; b =[-3.01636 -0.57273 2.17636 8.53588357 10.21766131];