A Blood Bank Location Model: A Multiobjective Approach EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol 2, No. 1, 2009 (112-124) ISSN 1307-5543 – www.ejpam.com *Corresponding Author. Email addresses: eycetin@istanbul.edu.tr (E. Çetin), lasinem@istanbul.edu.tr (L. Sarul). Phone: x18352 (E. Çetin), x18256 (L. Sarul) http://www.ejpam.com 112 © 2009 EJPAM All Rights Reserved A Blood Bank Location Model: A Multiobjective Approach Eyüp ÇETİN*, Latife Sinem SARUL Department of Quantitative Methods, School of Business Administration Istanbul University, Istanbul 34320, Turkey Office phone: + 90 212 4737070 Fax: +90 212 590 88 88 Abstract This effort derived a mathematical programming model, which is a hybrid from set covering model of discrete location approaches and center of gravity method of continuous location models, for location of blood banks among hospitals or clinics, rather than blood bank layout in health care institutions. It is initially unknown the number of blood banks will be located within capacity, their geographical locations and their covering area. The solution of the model enlightens the initial darkness in a multiobjective view. The objectives, which are handled via binary nonlinear goal programming, are minimizitation of total fixed cost of location blood banks, total traveled distance between the blood banks and hospitals and an inequality index as a fairness mechanism for the distances. A hypothetical numerical example is solved using MS Excel as a powerful spreadsheet tool. The recipe, which is an application of medical operations research, may be a useful tool for health care policy makers. Key words: Set covering model; Center of gravity method; Binary nonlinear goal programming; Spreadsheet modeling, Medical operations research. E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 113 1. Introduction The location of facilities is an important issue in any application area for both industry and academia. Any poor location decision will result in undesired pathological situations such as increased expenses, capital costs and degraded customer service [1]. In health care, the facility location decisions, which are strategic not an everyday decision [2], are more critical due to that any anomaly may lead to mortality and morbidity [1]. The availability and location of blood banks, which will serve some hospitals or clinics, is also a strategic decision in health care delivery system. In addition to well known importance of the subject, it is a fact that grave shortages of blood occur in over 80% of the countries in the world, one of the reason is inadequate funding of the local transfusion service [3], that may result from inefficient allocation of sources in general. In investigating blood transfusion cost, one important element of variability can be attributed to geographic location of the blood supply source [4]. Some cost- structure analyses (eg, [5]) included distribution and delivery costs of blood as some major variables. Besides, accessibility to a blood bank is an important component of an organ transplant program. Transplantation requires more blood then most other surgeries, for instance, 100 units of blood for a liver transplant patient [6]. Moreover, blood banks may also serve as important education centers for medical staff from hospitals and clinics [7]. It may be said that the literature is rich in general facility location and health care location modeling. Some highlights of the literature are as follows. Hale and Moberg [8] present a broad review of facility location and location science research. Recently, Daskin and Schilling [9] gave the summaries of general location models. Daskin and Dean [1] reviewed some selected location models in both general and health care focus. Some authors studied the location analysis from stochastic standpoint. For instance, Chen et al. [10] developed a model for stochastic facility location modeling. Verter and Lapierre [11] developed a binary programming model for location of E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 114 preventive health care facilities. Flessa [12] studied a linear programming model for allocation of health care resources in developing countries. Wu, Lin and Chen [13] presented the optimal location model adopting the modified Delphi method, the analytical hierarchy method and sensitivity analysis for Taiwanese hospitals. Şahin et al. [14] present a review of health care location and also blood bank location models and developed several location-allocation models to solve the problems of regionalization based on an hierarchical structure. Or and Pierskalla [15] consider a regional blood management problem where hospitals are supplied by a regional blood bank in their region and developed a location-allocation model that minimizes the sum of the transportation costs and the system costs. Shen et al. [16] consider a joint location inventory problem involving regional centers nearby hospitals assigned to them for the supply of the most perishable and most expensive blood product and present a location-allocation model and a set covering model. Nemet and Bailey [17] explore the relationship between distance and the utilization of health care by a group of elderly residents in rural Vermont. Ndiaye and Alfares [18] focus on nomadic population groups that occupy different locations according to the time of the year and develop a binary integer programming model that is formulated to determine the optimal number and locations of primary health units for satisfying a seasonally varying demand. The set covering model is a basic location structure [1] from discrete location models when the center of gravity model is from continuous location models. The latter is useful when the geographic position of a location is important in terms of distribution of the services or materials. As instances, it can be used for specialty laboratories, blood banks and ambulance services [2]. There are some crucial factors for blood bank location, namely, transaction demands (or shipments) [2], population size that the blood bank will serve, blood bank capacities, fixed cost of locating blood bank [1], the distances between hospitals and blood banks and egalitarian distribution of distances [19]. The last three elements may be taken as objectives of a blood bank location model. E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 115 This study developed a mathematical programming model, which is a hybrid from the set covering model of discrete location approaches and the center of gravity method of continuous location models, holding three objectives; minimizing the total fixed cost of locating blood banks, minimizing total distance between hospitals and blood banks and minimizing an inequality index as a fairness mechanism for the distances. The model deals with location of blood banks in a region rather than blood bank layout in health care institutions. The objectives are transformed into a single objective via goal programming, a kind of multiobjective programming (See [20] for further discussion about goal programming). In this effort, the set covering model is modified as that the classical covering parameters are taken as decision variables that are initially unknown. More extensively, that is, it is uncertain at the beginning that how many blood banks are located within capacity, their geographical location and which hospitals are assigned to them. The run of the model clarifies them within the objectives. The paper is organized in the following way. The mathematical model, which is a binary nonlinear goal programming model, is derived in the Methods, Computational results via MS Excel’s Solver as a powerful spreadsheet tool regarding a hypothetical numerical example are presented and some Discussion and conclusions are drawn. 2. The Method The developed model is a hybrid from basic set covering model of discrete location class and center of gravity method of continuous location models. As a consequence, the model holds some natures and assumptions of both location models. This model assumes that demands can be aggregated to a finite number of discrete points (discrete location) when facilities can be located anywhere in the region (continuous location) [1]. The model can be constructed in the following way. We develop the model using the following notation: E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 116 mi ,...,3,2,1= : index of hospitals (demand nodes) nj ,...,3,2,1= : index of candidate blood banks 3,2,1=k : index of goals ih : total annual transaction demand by hospital i ijd : distance from hospital i to candidate blood bank j p : maximum number of blood banks to locate jf : fixed cost of locating blood bank j jc : annual transaction capacity of blood bank j ip : population size of the site at which hospital i is located ix : x coordinate of hospital i with respect to a reference frame, iy : y coordinate of hospital i with respect to a reference frame, jx : x coordinate of the weighted center of gravity for blood bank j jy : y coordinate of the weighted center of gravity for blood bank j kP : priority coefficient for goal k kρ : aspiration level for goal k . + kd : positive deviation from the aspiration level for goal k − kd : negative deviation from the aspiration level for goal k We also define the following decision variables:    = notif jbankbloodcandidatelocateweif Z j 0 1    = notif jbankbloodbyeredbecanihospitalif zij 0 cov1 The mathematical programming model can be formulated as follows. The objective is to minimize the weighted sum of the appropriate deviations from the aspiration levels as a classical effort for goal programming structure. E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 117 Minimize +++ ++ 332211 dPdPdP The model has three goal constraints due to three goals for the location of blood banks. Since they are to be minimized, we choose all the aspiration levels 0321 === ρρρ . The first goal is the minimization of the total fixed cost of locating blood banks, ∑ = −+ =+− n j jj ddZf 1 11 0 . The second goal is the minimization of the total traveled distance from hospitals to blood banks, ∑∑ = = −+ =+− m i n j ijij ddzd 1 1 22 0 where the Euclidean distance ( ) ( )22 jijiij yyxxd −+−= . Here, the center of gravity is weighted by two important factors, which are basic indicators for hospital- blood bank relations, the annual transactions [1] and the population size of the site at which the hospital is located. The weighted center of gravity coordinates are, for all nj ,...,3,2,1= , ∑ ∑ = = + = m i ijii m i ijiii j zph zxph x 1 1 ε and ε+ = ∑ ∑ = = m i ijii m i ijiii j zyh zyph y 1 1 . For the above ratios, the undetermined cases due to binary nature of ijz ’s are avoided by means of 0>ε , which is in the neighborhood of 0. E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 118 The last goal constraint is an inequality index, to be minimized, the coefficient of variance [19] aiming the equality and fairness distribution of sources. In the case of blood bank location, it tries to smooth the extreme distances between hospitals and blood banks as much as possible, which is also an important effort for health care facility location. The goal constraint can be written as ( ) 01 331 2 =+−− + −+ =∑ dddd d m i ij ε , mj ,...,3,2,1=∀ , where d is the arithmetic mean of the all ijd ’s so that the fairness platform is determined for all hospitals and blood banks that we deal. Here, again 0>ε is employed to ensure the absence of undetermined cases. There are naturally some system constraints. The first is the capacity constraint imposing that any blood bank must not exceed its annual transaction capacity, that is, any other extra hospital must not assign to the blood bank, ∑ = ≤ m i jiji czh 1 , nj ,...,3,2,1=∀ . There must be sufficient total capacity to supply the total demand, which can be stated as ∑ ∑ = = ≤− m i n j ji ch 1 1 0 , mi ,...,3,2,1=∀ , nj ,...,3,2,1=∀ . The following constraints stipulates that each hospital (demand node) must be covered by exactly one of the selected blood banks, since the primary decision variables are binary, E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 119 ∑ = = n j ijj zZ 1 1 and ∑ = = n j ijz 1 1, mi ,...,3,2,1=∀ . The number of located blood banks must not excess the maximum number of blood bank, which may be located, ∑ = ≤ n j j pZ 1 . The following constraints impose that there must not be any empty blood bank to which no hospital assigned, { } { } ,0max,...,,,max 321 =− jmjjjj Zzzzz nj ,...,3,2,1=∀ . Finally, revisiting the decision variables completes the mathematical model, { }1,0∈jZ , { }1,0∈ijz and 0, ≥−+ kk dd , mi ,...,3,2,1=∀ , nj ,...,3,2,1=∀ , .3,2,1=∀k Note that the foregoing model implicitly locates the selected blood banks with respect to weighted center of gravity and assigns the hospitals to appropriate blood banks. The mathematical model, which works without any candidate geographical location information, is a nonlinear binary goal programming model. It is a fact that since the developed hybrid model, which includes 6)1( ++mn decision variables, inherits from NP-hard like models [1,21], the solution of the model is technically hard. In addition to some heuristics for the general class of location covering models [22-23], as in a recent study [24] proposing MS Excel’s Solver, which uses branch-and-bound methodology [25], it may be employed to reach at least near optimal solutions. Although the nonlinearities in the model may be handled by some appropriate transformations to reduce the CPU time, our empirical observations E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 120 reports that MS Excel’s Solver may solve the original model in reasonable times. Because of the multi-objectivity, the solutions are efficient at the same time for all objectives. The solutions will be at least near optimal due to the nature of the problem. 3. Computational Results A hypothetical numerical example is as follows. There are at most n=3 candidate blood banks (BB1, BB2 and BB3, whose geographical locations are currently unknown) with the capacities of annual transactions 6,000, 4,500 and 5,000, respectively. The fixed costs of locating them are 1.5, 1 and 1.2 (in $100.000), respectively. There exist m=25 hospitals (H1, H2 ,.., H25) waiting for supply with annual transaction demands ranging from 100 to 1,374. The population sizes of the sites that the hospitals serve are ranging from 4,890 to 130,500. The scatter of the hospitals (in 10 km) with respect to a reference frame (origin) is shown in Figure 1 (Data are not shown). The problem is the location of the blood banks within the model (nonpreemptive) objectives and constraints. The model is optimized via MS Excel’s classical Solver tool. (See [20,25] for spreadsheet modeling). Since the model is highly nonlinear, the result is obtained by solutions of different starting points. For the priority levels, we take 1321 === PPP to have a nonpreemptive goal programming model. Also, we choose 001,0=ε . Although the model has 84 (78 of 84 are binary) decision variables, the CPU time of the model solution is 58 s on a PC with Intel (R) Core (TM) 2 CPU 5600, 1.83 GHz and 1.00 GB RAM. According to near optimal results that the model suggest, the three candidate blood banks should be located at the coordinates )33.568.5(),( 11 =yx , )27.2073.5(),( 22 =yx and )08.1264.3(),( 33 =yx , respectively. The near Pareto optimal location policy is also graphed in Figure 1. BB1 should serve 9 hospitals, BB2 is assigned 9 hospitals when BB3 is assigned 7 hospitals. All annual transaction demands are satisfied by the blood banks, namely, the demand distributions 5,077, 4,364 and 4,961, respectively. Total fixed cost is $370,000. Total traveled distance E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 121 between the hospitals and the respective blood banks is 892 km. The inequality index, the coefficient of variance, is 43.7 km. The maximum distance is 72.8 km (H15-BB3) when the minimum is 7.8 km (H2-BB2), hence the range, which is another basic inequality index, is 65 km. As seen in Figure 1, H15 is not attached to either BB1 or BB2. The reason may be that it is so far from the center, and it has relatively lower demand (150) and representative population (14,700). Thus, it is inadequate to attract the weighted center of gravity to itself. Also, not only the distance is a criterion for the model, which takes the blood bank transaction capacities into account. From the distance standpoint, the location strategy is also reasonable, due to, note that, the scatter of hospitals is in range 97.5 km on the x axis when 245 km on the y axis. BB1 BB2 BB3 0 5 10 15 20 25 30 0 2 4 6 8 10 12 y x H10 H21 H17 H7 H6 H24 H23H8 H9 H16 H19H18 H20H11 H15 H3 H5 H4H22 H14 H12 H1 H13 H2 H25 Figure 1. The Hospitals and Location Strategies for the Blood Banks 4. Discussion and Conclusions A blood bank location model, which is a binary nonlinear goal programming model, is formulated in a multiobjective frame. The objectives are minimization of total fixed cost of locating blood banks, total traveled distance between the supply and demand nodes and the inequality index for the distances. The model stemming from set covering model and center of gravity method is a combination of discrete and continuous location approaches. It is initially unknown the number of blood banks will be located, their locations and their covering area. The solution of the model enlightens the initial darkness. E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 122 The recipe may be extended in such a way that the coordinates of demand population weighted center of gravity may be restricted to a specific region within the model formulation because of some geographical restrictions such as governmental regulations. Also, if the parameters of distance or transaction between the blood banks are in agenda, the model may be modified for the desired regulations. Besides, any other objectives or constraints may be integrated to the core model such as transaction costs may appear in the model as another objective of the goal programming model. Moreover, from computational view, this study also shows the ease and use of MS Excel as a spreadsheet tool for technically hard problems. The proposed model may be conducted for not only blood bank location but also other appropriate location issues in both general and health care case. For instance, the model may be utilized for warehouse location or location of hospitals and fire stations with a few modifications. As another further research, the model may be adopted to stochastic modeling nature of location problems. The road map, which the model offers, may be a useful tool for both industry and academia particularly in health care management science. References [1] M.S. Daskin, L.K. Dean, Location of health care facilities. In: Sainfort F, Brandeau M, Pierskalla W, editors. Handbook of OR/MS in health care: A Handbook of Methods and Applications. USA: Kluwer, 2004, p. 43-76 [2] Y.A. Ozcan, Quantitative Methods in Health Care Management: Techniques and Applications. San Francisco CA: Jossey-Bass/Wiley; 2005. [3] M.J. Thomas, The management of overseas emergencies. Travel Med. Infec. Dis. 5, 2: 113-116 (2007). [4] J.M. Forbes, M.D. Anderson, G.F. Anderson, G.C. Bleecker, E.C. Rossi, G.S. Moss, Blood transfusion costs: a multicenter study. Transfusion. 31, 4: 318-23 (1991) [5] R.A Fouty, V.E. Haggen, J.D. Sattler, Problems, personnel, and proficiency of small hospital laboratories. Public Health Rep. 89, 5: 408-417 (1974). E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 123 [6] P.A Lindsey, E.A. McGlynn, Pew Memorial Trust policy synthesis: 5. State coverage for organ transplantation: a framework for decision making. Health Serv Res. 22, 6: 881-922 (1988). [7] M. Amin, D. Fergusson, K. Wilson, A. Tinmouth, A, Aziz, D. Coyle, P. Hebert, The societal unit cost of allogenic red blood cells and red blood cell transfusion in Canada, Transfusion. 44, 10: 1479-86 (2004). [8] T.S. Hale, C.R. Moberg, Location Science Research: A Review, Annals of Operations Research. 123, 1-4: 21-35 (2003). [9] J. Current, M. Daskin, D. Schilling, Discrete network location models. In: Drezner Z, Hamacher, editors. HW Facility Location: Applications and Theory. Berlin: Springer, 2002. [10] G. Chen, M.S. Daskin, Z. Shen, S. Uryasev, A New Model For Stochastic Facility Location Modeling. Research Report 2005-8, ISE Dept., University of Florida, 2005. [11] V. Verter, S.D. Lapierre, Location of preventive health care facilities. Annals of Operations Research. 110, 1-4: 123-132 (2002). [12] S. Flessa, Priorities and allocation of health care resources in developing countries: a case-study from the Mtwara region, Tanzania, Eur. J. Oper. Res. 150, 1: 67-80 (2003). [13] C.R. Wu, C.T. Lin, H.C. Chen, Optimal selection of location for Taiwanese hospitals to ensure a competitive advantage by using the analytic hierarchy process and sensitivity analysis. Build. Environ. 42, 3: 1431-1444 (2007). [14] G. Şahin, H. Süral, S. Meral, Locational Analysis For Regionalization Of Turkish Red Crescent Blood Services, Computers & Operations Research. 34, 3: 692- 704 (2007). [15] I. Or, W.P. Pierskalla, A Transportation Location-Allocation Model for Regional Blood Banking, AIIE Transactions. 11, 2: 86-95 (1979). [16] Z.M. Shen, C. Coullard, MS. Daskin, A Joint Location-Inventory Model, Transportation Science. 37, 1: 40-55 (2003). [17] G.F. Nemet, A.J. Bailey, Distance and Health Care Utilization among the Rural Elderly, Social Science & Medicine. 50, 9: 1197-1208 (2000). E. Çetin, L. Sarul / Eur. J. Pure Appl. Math, 2 (2009) 124 [18] M. Ndiaye, H. Alfares, Modeling Health Care Facility Location for Moving Population Groups, Computers& Operations Resesarch. 35, 7: 2154-2161 (2008). [19] H.A. Eiselt, G. Laporte, Objectives in location problems. In: Drezner Z, editor. Facility Location: A survey of applications and methods. Berlin: Springer-Verlag, 1995. [20] W.L. Winston, Operations Research: Application and Algorithms, fourth ed. Belmont:, Brooks/Cole, 2004. [21] J. Brimberg, P. Hansen, N. Mladenovic, Decomposition strategies for large-scale continuous location-allocation problems. IMA J Manag. Math. 17, 4: 307-316 (2006). [22] J. Zhou, B. Liu, New stochastic models for capacitated location-allocation problem. Computers and Industrial Engineering. 45, 1: 111-125 (2003). [23] A.T. Ernst, , M. Krishnamoorthy, Solution algorithms for the capacitated single allocation hub location problem. Annals of Operations Research. 86, 0: 141-159 (1999). [24] E. Çetin S. Tolun, A weapon-target assignment approach to media allocation. Appl. Math. Comput. 175, 2: 1266-1275 (2006). [25] W.L. Winston, S.C. Albright, Practical Management Science, second edition. Pacific Grove: Brooks/Cole, 2001