 American Journal of Oper ations Research, 2011, 1, 39-45 doi:10.4236/ajor.2011.12006 Published Online June 2011 (http://www.SciRP.org/journal/ajor/) Copyright © 2011 SciRes. AJOR A Multi-Objective Obnoxious Facility Location Model on a Plane Utpal K. Bhattacharya Indian Institute of Management Ind ore, Indore, India E-mail: utpalb@iimidr.ac.in Received February 25, 2011; revised March 15, 201 1; accepted April 8, 2011 Abstract In this paper a Vertex Covering Obnoxious Facility Location model on a Plane has been designed with a combination of three interacting criteria as follows: 1) Minimize the overall importance of the various exist-ing facility points; 2) Maximize the minimum distance from the facility to be located to the existing facility points; 3) Maximize the number of existing facility points covered. Area restriction concept has been incor-porated so that the facility to be located should be within certain restricted area. The model developed here is a class of maximal covering problem, that is covering maximum number of points where the facility is withi n the upper bounds of the corresponding mth feasible region. Two types of compromise solution methods have been designed to get a satisfactory solution of the multi-objective problem. A transformed non-linear pro-gramming algorithm has been designed for the proposed non-linear model. Rectilinear distance norm has been considered as the distance measure as it is more appropriate to various realistic situations. A numerical example has been presented to illustrate the solution algorithm. Keywords: Obnoxious Facility Location, Multi-objective Decision Making, Maximal Covering Problem 1. Introduction For service facility location problems when the costs are the increasing function of distance, it is reasonable to consider either minimum of the sum of distances or the weighted distances. On the other hand, for some vital fa- cilities it may be desired to minimize the maximum dis-tances. However, there are types of location situations where cost decreases as distance increases and is consid-ered the name in the literature as the obnoxious or unde-sirable facility location problems. Erkut and Neuman  have given an excellent survey on undesirable facility location problems. Models con-taining maximization of some function of distances as one of the objectives were considered for analysis. Ex-amples appropriate for the above cases are garbage dump, chemical plant or a nuclear reactor. Another type of problems called semi desirable, have been found in the literature. Examples appropriate for these models are baseball stadium, incineratio n plants etc. In the location literature many people have worked on MAXIMIN criterion with Euclidean distances. Shamos  defines the unweighted MAXIMIN problem as the largest empty circle problem in and provides an algorithm for solving that problem. Dasarathy and White  ex-tended the unweighted maximin problem to a higher di-mensional space and a convex feasible region. They pro-vide an algorithm for a three dimensional space. Drezner and Wesolowsky  present a solution to a maximin pro- blem assuming a feasible region which is the intersection of the circles of prescribed radii whose centers are existing facility points. Melachrinoudis and Cullinane  solved maximin problem for the case of non convex feasible re-gion S in the presence of forbidden circles. 2RDrezner and Wesolowsky  first introduced the rec-tilinear maximin problem for locating an obnoxious fa-cility. They developed a solution procedure by dividing the feasible region into rectilinear sub regions and solv-ing a linear programming problem for each of this sub regions. Melachrinoudis  proved several properties of the optimal solution, dev eloped elimination strategies for the sub regions and solved the duals of the LPs for the remaining sub regions. Mehrez et al.  suggested an improvement of Drezner and Wesolowsky’s algorithm, based on bounds, which reduces the size as well as the number of sub problems to be solved. Arie Tamir  has presented a subquadratic algorithm for location two ob-noxious facilities using the weighted maximin criterion. U. K. BHATTACHARYA 40 nBanez et. al.  have considered a problem of locat-ing an obnoxious plane and solved in O() time and O( ) space. Plastria and Carrizosa  have considered of locating an undesirable facility within some feasible region of any shape in the plane or on a planar network by considering two criteria: a radius of influence to be maximized and the total covered population to be mini-mized. Low complexity polynomial algorithms are de-rived to determine all non dominated solutions. 3n2nA bibliography for some fundamental problem catego-ries such covering models are given by C.S. Revelle, H.A. Eiselt, M.S. Daskin . In this present investigation a vertex covering obnox-ious facility location model has been designed with multi-ple objectives. In this model weights as importance has been assigned to the various demand points and considers as a separate objective. Because of undesirable facility, the facility points which has to be kept more distance away from the undesirable facility location should be given less weitages compared to the facility points which may be kept comparatively closer. The problem has been modeled as a pure planar location problem. Area restriction concept has been incorporated so that the facility to be located should be within certain restricted area. Incorporation of the area restriction has been implemented by inducting a convex polygon in the feasible region. Another advantage of introduction of a convex polygon in the constraint set is that it might reduce the number of transformed non-linear programming problems to be solved. Two types of com-promise solution methods have been designed to get the satisfactory solution of the original multi-objective non linear model. The proposed model has another advantage to give different weightages to the different criteria sepa-rately to reach out to a desired compromise solution. Rec-tilinear distance norm has been considered as a distance measure to design the model. A numerical example has been presented to illustrate the solution algorithm. Preliminaries are mentioned in Section 2. Model for-mulation for the vertex covering obnoxious facility problem has been given in Section 3. An algorithm has been designed in Section 4. A numerical example has been presented in Section 5. Concluding remarks are made in Section 6. 2. Preliminaries 1-Maxi-min Problem: Single facility location problem with maximum objective can be broadly classified into maximin and maxi sum objectives. The problem 1-maxi min which is u nder st u dy i n t his paper i s descri bed bel o w. Let for be the location of n de-mand points. ,iiab 1, 2,,i,xy be the co-ordinates of the facility to be located. Then ,min iiiFxyx ay b be the mini-mum rectangular distances from the facility to the de-mand poi nt i. Then the mathematical model is Max ,Fxy subject to ,0AXb x. 3. Mathematical Formulation Let ,iiab be the location of the ith existing facility and ,xy is the coordinates of the point to be located. The objective corresponding to the Minimize the overall importance of the various demand points is formulated as P1. Min 1niiiwxwhere 1,0.iiiixaybZxOtherwise  and wi is the weights as importance assigned to the ith demand points for every i. The objective corresponding to maximize the mini-mum distance from the facility to the demand points ob-jective can be written as follows. P2. Maximize ,iMinimizedx y ,xyS i where ,iidxyxa ybi The third objective maximize the demand units cov-ered can be formulated as P3. Maximize 1niix where ix is as defined earlier. Thus the multi-objective formulation of the vertex covering obnoxious facility location problem may be written as follows P4. Minimize 1niiiwxMaximize 1Z Maximize 1niix subject to, 1,iixaybZ 1, 2,,in12 ,3jjcx cycj 1, 2,,jk,xyS Copyright © 2011 SciRes. AJOR U. K. BHATTACHARYA 41 where 11,0iiiif xaybZxOtherwise 4. Algorithm for Vertex Covering Obnoxious Facility Location Problem Let us consider the grid of lines formed by drawing hori-zontal and vertical lines through every demand point . This will form at most rectangular re-gions, some of them bounded by infinity. Consider now the mathematical formulation which may be written as ,iiab21nP5. Maximize 1Z Minimize 1niiiwxMaximize 1niix subject to, 1,iiixaybZX 1, 2,,in1mZUB 12 ,3jjy cjcx c 1, 2,,jkwhere 11,0iiiif xaybZxOtherwise and is the upper bound corresponding to the rec-tangle m. mUBNext to find the upper bound inside rectangle m. The maximum value of 1Z on m is as given below: miiZMax Minxayb ,xym iiiMin Maxxayb i ,xym The maximum inside rectangle m must occur on V, where V is the set of four vertices of the rectangle (some of this vertices may be at infinity). Hence, an upper bound on 1Z is miUBMin Maxxaybi i ,xym For an open rectangle UB in infi nite. The single objective formulation of the above mul-ti-objective problem is as given below. The non-linear constraints of Problem (5) can be bro-ken down into four alternative sub problems by using the P6. inequality relations. The four sub problems are as follows. imize Max1Z 1niiiwx Minimize Maximize 1niix subject to, 10ii ixyabZx 1mZUB 12 ,3jjjcx cyc or imize 1, 2,,jk.P7.Max 1Z 1niiiwx Minimize Maximize 1niix subject to, 10ii ixyabZx 1mZUB 12 ,3jjjcx cyc or P8. ize 1, 2,,jk.Maxim 1Z 1niiiwx Minimize Maximize 1niix subject to, 10ii ixyabZx 1mZUB 12 ,3jjjcx cyc or P9. ize 1, 2,,jk.Maxim 1Z Minimize wx1niii 1niix Maximize subject to, 10ii ixyabZx 1mZUB Copyright © 2011 SciRes. AJOR U. K. BHATTACHARYA 42 312jjjcx cycfour problems P6 For all the 1, 2,,jk.P9 - 11, iif xayx0.iib ZOtherwise And is the upper bound corresponding to the rectangle . g the above multi-objective problem two mUB mFor solvinapproaches are suggested. Type Ⅰ Compromise solution: Define the variable KU in such a way that *kKkZXUXSZ For getting the compromise solution following objec-tive function is defined. P10. 112 233Maximize VUUU  such that XS Where *KZ is t maximum value ofhe KZ over the constraint *set.KZ can be obtained by solv the indi-vidual single octive problem. ingbjeK is the weight at-tached to the ith objective function. The problem thus transformed to fur sets as the con-ostsolution is obtained byize raints given in P6, P7, P8, P9 with objective function for all the problems as given in P10. Type Ⅱ compromise solution e The second type of compromis defining the objective function P11. Minim 321KKkWU Where KU is defined as follows:  12 312 312 31,1 ,1fX fXUU UZZ Z       Where fX *KZ is the maximum value of KZ over the constraint *set.KZcan be obtained by solv the indi-vidual single octive problem. ingbjeK is the weight at-tached to the ith objective function. Adjustment in 3U to avoid zero in the denominator. The Algorithm for solving multi objective formulation of the Obnoxious Facility Location Problem is as given below. Step-1. Formulate the multi-objective problem as given in P10 for Type Ⅰ compromise solution and P11 for Type Ⅱcompromise solution. Choose the weightages to be assigned to the different objectives. Step-2.nd the enclosing feasible rectangle by the procedure-1. Fie within the enclosing feasible rectangle. Step-3. Restrict the grid and rectangles to be considered to those that liStep-4. Eliminate all i nfeasi ble rect angl es by Result 1. Step-5. Find the upper bound on 1Z for all the re-m -peaining rectangles by using Procedure 1. Sort these upr bounds of 1Z from the largest to the smallest. Step-6. Solve the multi-objective non-linear program-ming problem breaking the problem into four albyterna-tivhest upper bound on e sub problems. Step-7. Solve the sub problems starting with the rec-tangle with the hig1Z. Stop when the upper bound fo r the next rectangle is no t greater than the best 1Z va lue solution found so far. Step-8. Take the solution of the sub problem which gives mimum objective function vaxalue for type Ⅰcompromise solution and the solution of the sub prob-lem which gives minimum objective function value. Procedure 1. Find the enclosing feasible rectangle (Drezner & Wesolowsky (1983)). To find LxX, the left vertical line defining the rec-tangle, solve a linear programming problem with x as the ob be minjective toimized and the constraints ( ). Maximizing x will give UX, which defines the right vertical line. The lower and upper horizontal lines LyY and UyY are fousimilarly. Let us consider the rectangle m defined by the lines 1ind xa 2ixa 3iyb 4iyb, where 12iiaa and 34iibb. Also we define the segments  iiLUxx and  iLyyiU where  ,iiiiLUL Uxxy y the ; these areparts of the line respectively andiyb ixa. . If all thitions hold, then Result 1e folloondde recm (Der & Wwing cthere is no feasible point insitangle reznesolowsky (1983)).  11ii43LiUi3Yboryb (1)  224iiLiUyborybi1 (2) 334iiLiU ixaorx a 1 (3) 442iiLiU ixaorx a 5. Numerical Example 4,1), E(9,7) be the five de-and points on a plane, and (4) Let A(2,1), B(3,5), C(6,9), D(m35 45xy, 5442xy, 0, 0xy are the boundary of the convex feasible re-gion. Let the weights attached 15, 0.20, 0.10, 0.25 respectively. The upper bound corresponding to the twenty feasible to the five demand pointsare 0.30, 0.rectangles (see Figure 1) are obtained by procedure 1 Copyright © 2011 SciRes. AJOR U. K. BHATTACHARYA Copyright © 2011 SciRes. AJOR 43, starting frresponding to the hiand theorem 1 and are given in the sorted form Solution obtained for is as given below: om largest to the smallest in Table 1. For Type Ⅰ compromise solution In the first iteration the mathematical programming formulation of the first sub problem corSP-1 0.426,V 1231 23459,4, 0.7,1.53,8.07,0, 1ZZZxyxxxxx ghest upper bound of 1Z as 9 is given in the following Where 9,5,1 are the ideal solutions obtained for the first, second and the third objectives respectively. The weights attached to the three objectives are 0.4,0.3,0.3 reMaximize 1230.4(0.11) 0.060.3VZ ZZ Subject to, Similarly the solutions for the other sub problems are as given below. 1112131415123452123453123451 0;0;15 0;50;16 0;0;0.30.150.20.10.25 50;35 45;54 40;0; 0;,,,, 0,1;ZxZxxy Zxxy Zxxy Zxxxxxxzxxxxxzxyxyxyxxxxx     2xy SP-2 8xyV = 0.411, 1231345 29, 1,0.15,8, 0,0, 1ZZZxyxxxx x  SP-3 V = 0.426, 1231235 49, 1,0.10,0, 9,0, 1ZZZxyxxxx x  SP-4 V = 0.396 19;Z 123123459,0, 0,0, 0,0ZZZxyxxxxx spectively. Table 1. Upper boundRectangle Nu for various rectangles. mber1069578111415161718192014121323UBm 9 666555 5 5 5 5 5 4 5 333 3 22 Figure 1. Rectangles. U. K. BHATTACHARYA 44 If we go to the next iteration with the next 1Z value, the solution obtained can not dominate the1Z value sat-isfactory solution for the multi-objective are the solutions of SP-1 and SP-3. So in this case we are get-ting the alternative optimal compromise solutions. For Type Ⅱ compromise solution In the first iteration the mathematical programming formulation of the first sub problem corresponding to the highest upper bound of problem1Z as 9 is given in the following. Minimize 22120.41(0.11) 0.31(0.2) 0.31WZZ Z  23Subject to, The solution obtained by using software LINGO for the four sub problems are as given below. The weights at-tached to the three objectives are 0.4,0.3,0.3 respectively. SP-1 W = 0.4E-04 Similarly the solution obtained for the other three sub problems are as given below. SP-2 W = 0.5887 SP-3 W = 0.555 SP-4 W = 0.594 111213141512345212345312345121 0;80;15 0;50;16 0;0;0.3 0.150.20.10.250;35 45;54 40;0; 0;,,,, 0,1;9;xy Zxxy Zxxy Zxxy Zxxy ZxxxxxxzxxxxxzxyxyxyxxxxxZ      123123459,5, 1,7, 0,1ZZZxyxxxxx 1231345 29, 1,0.15,8, 0,0, 1ZZZxyxxxxx  1231235 49, 1,0.10,0, 9,0, 1ZZZxyxxxx x  1231345 28, 1,0.10,0, 0,0, 1ZZZxyxxxxx  1ZThe solution obtained with the next value can not dominate the solution obtained so far. us we stop the process here and the satisfactory solution for the multi- objective problem by using Type Ⅱ compromise solu-tion methods are the solution of SP-1. In the Type Ⅰ compromise solution method we have got the alternative optimal solutions where as for the Type Ⅱ compromise solution method we have got first sub problem as the optimal compromise solution. 6. Concluding Remarks  In this paper a vertex covering obnoxious facility on problem has been modeled as a mul-ti-objective planar location model.  A modified non linear programming algorithm has been designed to solve the proposed model.  Two types of compromise solution methods have been designed. In the first method each individual objec-tives are divided by the ideal solutions and the sum of them are maximized. Where as in the second method each objective deviations have been divided by the ideal solution and square of them has been minimized.  Other distance norm such as Euclidean, Geodesic etc. may be considered to model various other situations.  Models with general feasible regions (Union of dis-joint and non-convex sets) may be considered to mo- del various geographic regions.  The model developed here is a class of maximal cov-ering problem, that is covering maximum number of points where the facility is within the upper bounds of the corresponding mth feasible region. 7. References  E. Erkut and S. Neuman, “Analytical Models for Locat-ing Undesirable Facilities,” European Journal of Opera-tional Research, Vol. 40, No. 3, 1989, pp. 275-291. doi:10.1016/0377-2217(89)90420-7Thlocati  M. I. Shamos, “Computational Geometry,” Ph.D. Disser-tation, Department of Computer Science, Yale University, New Haven, 1977.  B. Dasarathy and L. White, “A Maximin Location Prob-lem,” Operations Research, Vol. 28, No. 6, 1980, pp. 1385-1401. doi:10.1016/0377-2217(89)90420-7  Z. Drezner and G. O. Wesolowsky, “A Maximin Loca-tion Problem with Maximum Distance Constraints,” AIIE Transaction, Vol. 12, No. 3, 1980, pp. 249-252. Copyright © 2011 SciRes. AJOR U. K. BHATTACHARYA 45 doi:10.1080/05695558008974513  E. Melachrinoudis and T. P. Cullinane,Locating an Undesirable facility within a Geographical Region Using the Maximin Criterion,” Journal of Regional Science, Vol.25, No. 1, 1985, pp. 115-127. 7.x “ doi:10.1111/j.1467-9787.1985.tb0029  Z. Drezner and G. O. Wesolowsky, “The Location of an Obnoxious Facility with Rectangular Distance,” Journal of Regional Science, Vol. 23, No. 2, 1983, pp. 241-248. 11/j.1467-9787.1983.tb00800.xdoi:10.11  hrindis, “An Efficient Computational Procedure for the Rectilinear Maximin Location Problem,” Trans-cience, Vol. 22, No. 3, 1988, pp. 217-223. 7/trsc.22.3.217 E. Melacportation Sdoi:10.128  A. Mehrez, Z. Sinuany-Stern and A. Stulman, “An En-hancement of the Drezner-Wesolowsky Algorithm for Single Facility Location with Maximin of Rectangular Distance,” Journal of Operations Research Society, Vol. No. 10, 1986, pp. 971-977.  “Locating Two Obnoxious Facilities using the Weighted Maximin Criterion,” Operations Research Let-ter, Vol. 34, No. 1, 2006, pp. 97-105. doi:10.1016/j.orl.2005.02.00437, A. Tamir,  J. M. Diaz-Banez, M. A. Lopez and J. A. Sellaves, “Lo-cating an Obnoxious Plane,” European Journal of Opera- pptions Research, Vol. 173, No. 2, 2006,. 556-564. doi:10.1016/j.ejor.2005.02.048  F. Plastria, and E. Carrizosa, “Undesirable Facility Loca-tion with Minimal Covering Objectives,” European Journal of Operational Research, Vol. 119, No. 1, 1999, pp. 158-180. doi:10.1016/S0377-2217(98)00335-X  C. S. ReVelle, H. A. Eiselt, M. S. Daskin, “A Bibliogra-phy for Some Fundamental Problem Categories in Dis-crete Location Science,” European Journal of Opera-tional Rsearch, Vol. 184, No. 3, 2008, pp. 817-848. doi:10.1016/j.ejor.2006.12.044 Copyright © 2011 SciRes. AJOR