Paper Menu >>
Journal Menu >>
![]() 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 [1] 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 [2] defines the unweighted MAXIMIN problem as the largest empty circle problem in and provides an algorithm for solving that problem. Dasarathy and White [3] 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 [4] 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 [5] solved maximin problem for the case of non convex feasible re- gion S in the presence of forbidden circles. 2 R Drezner and Wesolowsky [6] 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 [7] 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. [8] 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 [9] has presented a subquadratic algorithm for location two ob- noxious facilities using the weighted maximin criterion. ![]() U. K. BHATTACHARYA 40 n Banez et. al. [10] have considered a problem of locat- ing an obnoxious plane and solved in O() time and O( ) space. Plastria and Carrizosa [11] 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. 3 n 2 n A bibliography for some fundamental problem catego- ries such covering models are given by C.S. Revelle, H.A. Eiselt, M.S. Daskin [12]. 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. , ii ab 1, 2,,i , x y be the co-ordinates of the facility to be located. Then ,min i i i F xyx ay b be the mini- mum rectangular distances from the facility to the de- mand poi nt i. Then the mathematical model is Max , F xy subject to ,0AXb x. 3. Mathematical Formulation Let , ii ab be the location of the ith existing facility and , x y 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 1 n ii i wx where 1, 0. ii ii x aybZ xOtherwise 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 , i M inimizedx y , x yS i where , ii dxyxa yb i The third objective maximize the demand units cov- ered can be formulated as P3. Maximize 1 n i i x where i x is as defined earlier. Thus the multi-objective formulation of the vertex covering obnoxious facility location problem may be written as follows P4. Minimize 1 n ii i wx M aximize 1 Z Maximize 1 n i i x subject to, 1, ii x aybZ 1, 2,,in 12 , 3 j j cx cyc j 1, 2,,jk , x yS Copyright © 2011 SciRes. AJOR ![]() U. K. BHATTACHARYA 41 where 1 1, 0 ii i if xaybZ xOtherwise 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 , ii ab 2 1n P5. Maximize 1 Z Minimize 1 n ii i wx M aximize 1 n i i x subject to, 1, iii x aybZX 1, 2,,in 1m Z UB 12 , 3 j j y c j cx c 1, 2,,jk where 1 1, 0 ii i if xaybZ xOtherwise and is the upper bound corresponding to the rec- tangle m. m UB Next to find the upper bound inside rectangle m. The maximum value of 1 Z on m is as given below: mii Z Max Minxayb , x ym i ii M in Maxxayb i , x ym 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 1 Z is mi UBMin Maxxayb i i , x ym 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 Max1 Z 1 n ii i wx M inimize M aximize 1 n i i x subject to, 10 ii i xyabZx 1m Z UB 12 , 3 j jj cx cyc or imize 1, 2,,jk. P7. Max 1 Z 1 n ii i wx M inimize M aximize 1 n i i x subject to, 10 ii i xyabZx 1m Z UB 12 , 3 j jj cx cyc or P8. ize 1, 2,,jk. Maxim 1 Z 1 n ii i wx M inimize M aximize 1 n i i x subject to, 10 ii i xyabZx 1m Z UB 12 , 3 j jj cx cyc or P9. ize 1, 2,,jk. M axim 1 Z Minimize wx 1 n ii i 1 n i i x M aximize subject to, 10 ii i xyabZx 1m Z UB Copyright © 2011 SciRes. AJOR ![]() U. K. BHATTACHARYA 42 312 j jj cx cyc four problems P6 For all the 1, 2,,jk. P9 - 1 1, i if xay x 0. i i b Z Otherwise And is the upper bound corresponding to the rectangle . g the above multi-objective problem two m UB m For solvin approaches are suggested. Type Ⅰ Compromise solution: Define the variable K U in such a way that * k Kk ZX UXS Z For getting the compromise solution following objec- tive function is defined. P10. 112 233 M aximize VUUU such that X S Where * K Z is t maximum value ofhe K Z over the constraint * set. K Z can be obtained by solv the indi- vidual single octive problem. ing bje K is the weight at- tached to the ith objective function. The problem thus transformed to fur sets as the con-o st solution is obtained by ize 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 32 1 K K k WU Where K U is defined as follows: 12 3 12 3 12 3 1,1 ,1 fX fX UU U ZZ Z Where fX * K Z is the maximum value of K Z over the constraint * set. K Z can be obtained by solv the indi- vidual single octive problem. ing bje K is the weight at- tached to the ith objective function. Adjustment in 3 U 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. Fi e within the enclosing feasible rectangle. Step-3. Restrict the grid and rectangles to be considered to those that li Step-4. Eliminate all i nfeasi ble rect angl es by Result 1. Step-5. Find the upper bound on 1 Z for all the re- m - pe aining rectangles by using Procedure 1. Sort these up r bounds of 1 Z from the largest to the smallest. Step-6. Solve the multi-objective non-linear program- ming problem breaking the problem into four albyterna- tiv hest upper bound on e sub problems. Step-7. Solve the sub problems starting with the rec- tangle with the hig1 Z . Stop when the upper bound fo r the next rectangle is no t greater than the best 1 Z 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 L x X , 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 U X , which defines the right vertical line. The lower and upper horizontal lines L yY and U yY are fousimilarly. Let us consider the rectangle m defined by the lines 1 i nd x a 2 i x a 3 i y b 4 i y b, where 12 ii aa and 34 ii bb . Also we define the segments ii LU x x and i L yy i U where , iiii L UL U x xy y the ; these are parts of the line respectively and i yb i x a. . If all thitions hold, then Result 1e folloond de recm (Der & W wing c there is no feasible point insitangle rezn esolowsky (1983)). 11 ii 43 L iUi 3 Yboryb (1) 22 4 ii L iU yborybi 1 (2) 3 3 4 i i L iU i x aorx a 1 (3) 4 4 2 i i L iU i x aorx 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 points are 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 fr responding to the hi and 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 cor SP-1 0.426,V 123 1 2345 9,4, 0.7, 1.53,8.07, 0, 1 ZZZ xy xxxxx ghest upper bound of 1 Z 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 re Maximize 123 0.4(0.11) 0.060.3VZ ZZ Subject to, Similarly the solutions for the other sub problems are as given below. 11 12 13 14 15 123452 123453 12345 1 0; 0; 15 0; 50; 16 0; 0; 0.30.150.20.10.25 50; 35 45; 54 40; 0; 0; ,,,, 0,1; Zx Zx xy Zx xy Zx xy Zx xxxxxz xxxxxz xy xy xy xxxxx 2xy SP-2 8xy V = 0.411, 123 1345 2 9, 1,0.15, 8, 0, 0, 1 ZZZ xy xxxx x SP-3 V = 0.426, 123 1235 4 9, 1,0.10, 0, 9, 0, 1 ZZZ xy xxxx x SP-4 V = 0.396 19;Z 123 12345 9,0, 0, 0, 0, 0 ZZZ xy xxxxx spectively. Table 1. Upper bound Rectangle Nu for various rectangles. mber1069578111415161718192014121323 UBm 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 1 Z value, the solution obtained can not dominate the1 Z 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 problem 1 Z as 9 is given in the following. Minimize 22 12 0.41(0.11) 0.31(0.2) 0.31WZZ Z 2 3 Subject 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 11 12 13 14 15 123452 123453 12345 1 21 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 Zx xy Zx xy Zx xy Zx xy Zx xxxxxz xxxxxz xy xy xy xxxxx Z 123 12345 9,5, 1, 7, 0, 1 ZZZ xy xxxxx 123 1345 2 9, 1,0.15, 8, 0, 0, 1 ZZZ xy xxxxx 123 1235 4 9, 1,0.10, 0, 9, 0, 1 ZZZ xy xxxx x 123 1345 2 8, 1,0.10, 0, 0, 0, 1 ZZZ xy xxxxx 1 Z The 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 [1] 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-7 Th locati [2] M. I. Shamos, “Computational Geometry,” Ph.D. Disser- tation, Department of Computer Science, Yale University, New Haven, 1977. [3] 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 [4] 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 [5] 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 [6] 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 [7] 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. Melac portation S doi:10.128 [8] 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. [9] “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.004 37, A. Tamir, [10] 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 [11] 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 [12] 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 |