Indiana University-Purdue University Indianapolis (IUPUI) / Location Allocation, rooted in Operations Research and Mathematical programming, allows real world problems to be solved using optimization (based on mathematics and science) and equity principles (based on ethics). Finding nearest facilities for everyone simultaneously is a task solved by numerical and algebraic solutions. Bikeshare as a public good requires equitable allocation of bikeshare resources. Distance, as an impediment, can be minimized using location allocation algorithms. Since location allocation of this kind involves large numbers, sophisticated algorithms are needed to solve them due to their combinatorically explosive nature (i.e. as ‘n’ rises, solution time rises at least exponentially – sometimes called ‘Non Polynomial Time-Hard’ problems). Every day, researchers are working to improve such algorithms, since faster and better solutions can improve such algorithms and in turn help improve our daily lives.

Abstract: Provision of three basic infrastructure services (namely education, health and transport) in Rohtak and Bhiwani Districts (India) is examined using three types of data: 1. 507 households spreading in 8 villages, 2. Informal discussion with villagers and services providers in both districts, and 3. Secondary data for 921 villages and 14 towns and cities. These data were analysed using both statistical and GIS techniques. The analysis reveals that quantitatively there has been considerable expansion of education and health services over a period of fifteen years (1981 to 1996), and the average distance people have to travel to access these services has also declined significantly. But little evidence was found of any logical criterion being followed for the location of new services and the upgrading of existing services. Consequently, there was no improvement in the efficiency level (measured in terms of demand and geographical distance) of existing infrastructure services (both public and private); moreover, the efficiency level of private services was significantly lower than that of public services. It was further observed that the poor and women had relatively poor access to education, health and transport; and income, caste, gender, education level and village location had significant impact on access to and utilisation of basic services. In the study area, public services were functioning sub-optimally and service users were not satisfied with the quality of services; a significant proportion of clients had to rely on private services. Although public services may not be available in all the villages, the main focus should now be on improving the quality of existing services. Therefore, a solid transport network is needed in rural areas so that the availability of frequent and reliable transport services facilitate villagers' access to quality services even if located at distant places. Thus far, the role of the public in service provision has been minimal, which may be one of the reasons for poor quality of public services. Therefore, the active involvement of clients (service users) is essential in the operation, maintenance and monitoring of basic services in order to improve their quality and efficient functioning, and to effectively cater for people's needs in general and deprived sections of the society in particular.

This dissertation is concerned with the development of algorithmic approaches for solving the minisum location and location-allocation problems in which the Euclidean metric is used to measure distances. To overcome the nondifferentiability difficulty associated with the Euclidean norm function, specialized solution procedures are developed for both the location and the location-allocation problems. For the multifacility location problem (EMFLP), two equivalent convex differentiable reformulations are proposed. The first of these is formulated directly in the primal space, and relationships between its Karush-Kuhn-Tucker (KKT) conditions and the necessary and sufficient optimality conditions for EMFLP are established in order to explore the use of standard convex differentiable nonlinear programming algorithms that are guaranteed to converge to KKT solutions. The second equivalent differentiable formulation is derived via a Lagrangian dual approach based on the optimum of a linear function over a unit ball (circle). For this dual approach, which recovers Francis and Cabot's (1972) dual problem, we also characterize the recovery of primal location decisions, hence settling an issue that has remained open since 1972. In another approach for solving EMFLP, conjugate or deflected subgradient based algorithms along with suitable line-search strategies are proposed. The subgradient deflection method considered is the Average Direction Strategy (ADS) imbedded within the Variable Target Value Method (VTVM). The generation of two types of subgradients that are employed in conjunction with ADS are investigated. The first type is a simple valid subgradient that assigns zero components corresponding to the nondifferentiable terms in the objective function. The second type expends more effort to derive a low-norm member of the subdifferential in order to enhance the prospect of obtaining a descent direction. Furthermore, a Newton-based line-search is also designed and implemented in order to enhance the convergence behavior of the developed algorithm. Various combinations of the above strategies are composed and evaluated on a set of test problems. Computational results for all the proposed algorithmic approaches are presented, using a set of test problems that include some standard problems from the literature. These results exhibit the relative advantages of employing the new proposed procedures. Finally, we study the capacitated Euclidean distance location-allocation problem. There exists no global optimization algorithm that has been developed and tested for this class of problems, aside from a total enumeration approach. We develop a branch-and-bound algorithm that implicitly/partially enumerates the vertices of the feasible region of the transportation constraints in order to determine a global optimum for this nonconvex problem. For deriving lower bounds on node subproblems, a specialized variant of the Reformulation-Linearization Technique (RLT) is suitably designed which transforms the representation of this nonconvex problem from the original defining space into a higher dimensional space associated with a lower bounding (largely linear) convex program. The maximum of the RLT relaxation based lower bound that is obtained via a deflected subgradient strategy applied to a Lagrangian dual formulation of this problem, and another readily computed lower bound in the projected location space is considered at each node of the branch-and-bound tree for fathoming purposes. In addition, certain cut-set inequalities in the allocation space, and objective function based cuts in the location space are generated to further tighten the lower bounding relaxation. Computational experience is provided on a set of randomly generated test problems to investigate both the RLT-based and the projected location- space lower bounding schemes. The results indicate that the proposed global optimization approach for this class of problem offers a promising viable solution procedure. In fact, for two instances available available in the in the literature, we report significantly improved solutions. The dissertation concludes with recommendations for further research for this challenging class of problems. Data for the collection of test problems is provided in the Appendix to facilitate further testing in this area. / Ph. D.

The absence of water mains in rural areas has the potential to seriously complicate rural wildfire and structure fire suppression. The installation of dry fire hydrants can tremendously reduce these difficulties. But fire managers must then decide where to place these hydrants to efficiently and effectively serve their area of concern. This thesis investigates the role of GIS location-allocation model (LAMs) as a tool to aid fire managers in planning the locations of numerous dry hydrants. LAMs are designed to place central service facilities in a configuration that optimally serves geographically dispersed demand. One of the objectives of this thesis is to determine whether or not this optimization is achieved based on the management needs of the Virginia Department of Forestry. Many variations of LAMs are examined and the most appropriate model, the Maximal Covering Location Problem (MCLP), is selected. The flexibility of the MCLP model is then tested by imposing fine manipulations of hydrant demand weighting schemes. / Master of Science

This research is concerned with bioenergy systems planning and optimization modelling in the context of locating biomass power plants and allocating available biomass feedstock to the active plants. Bioenergy, a promising renewable energy resource, has potentially significant benefits to climate change, global warming, and alternative energy supplies. As modern bioenergy applications in power production have the ability to generate cleaner electricity and reduce Green House Gas (GHG) emissions compared with traditional fossil fuels, many researchers have proposed various approaches to obtain competitive power generation prices from biomass in different ways. However, the highly dispersed geographical distribution of biomass is a big challenge for regional bioenergy systems planning. This thesis introduces an integrated methodology combining Geographic Information Systems (GIS) and discrete location theories for biomass availability assessment, biomass power plant candidate selection, and location-allocation of power plants and biomass supplies. Firstly, a well known discrete location model – the p-Median Problem (PMP) model is employed to minimize the weighted transportation costs of delivering all collectable biomass to active power plants. Then, a p-Uncapacitated Facility Location Problem (p-UFLP) model for minimizing the Levelized Unit Costs of Energy (LUCE) is proposed and genetic algorithms (GAs) for solving these optimization problems are investigated. To find the most suitable sites for constructing biomass power plants, the Analytic Hierarchy Process (AHP) and GIS based suitability analysis are employed subject to economical, societal, public health, and environmental constraints and factors. These methods and models are aimed at evaluating available biomass, optimally locating biomass power plants and distributing all agricultural biomass to the active power plants. The significance of this dissertation is that a fully comprehensive approach mixed with the applications of GIS, spatial analysis techniques, an AHP method and discrete location theories has been developed to address regional bioenergy systems planning, involving agricultural biomass potential estimation, power plants siting, and facility locations and supplies allocation scenarios. With the availability of the spatial and statistical data, these models are capable of evaluating and identifying electric power generation from renewable bioenergy on the regional scale optimally. It thus provides the essential information to decision makers in bioenergy planning and renewable bioenergy management. An application sited in the Region of Waterloo, Ontario Canada is presented to demonstrate the analysis and modelling process.

This research is concerned with bioenergy systems planning and optimization modelling in the context of locating biomass power plants and allocating available biomass feedstock to the active plants. Bioenergy, a promising renewable energy resource, has potentially significant benefits to climate change, global warming, and alternative energy supplies. As modern bioenergy applications in power production have the ability to generate cleaner electricity and reduce Green House Gas (GHG) emissions compared with traditional fossil fuels, many researchers have proposed various approaches to obtain competitive power generation prices from biomass in different ways. However, the highly dispersed geographical distribution of biomass is a big challenge for regional bioenergy systems planning. This thesis introduces an integrated methodology combining Geographic Information Systems (GIS) and discrete location theories for biomass availability assessment, biomass power plant candidate selection, and location-allocation of power plants and biomass supplies. Firstly, a well known discrete location model – the p-Median Problem (PMP) model is employed to minimize the weighted transportation costs of delivering all collectable biomass to active power plants. Then, a p-Uncapacitated Facility Location Problem (p-UFLP) model for minimizing the Levelized Unit Costs of Energy (LUCE) is proposed and genetic algorithms (GAs) for solving these optimization problems are investigated. To find the most suitable sites for constructing biomass power plants, the Analytic Hierarchy Process (AHP) and GIS based suitability analysis are employed subject to economical, societal, public health, and environmental constraints and factors. These methods and models are aimed at evaluating available biomass, optimally locating biomass power plants and distributing all agricultural biomass to the active power plants. The significance of this dissertation is that a fully comprehensive approach mixed with the applications of GIS, spatial analysis techniques, an AHP method and discrete location theories has been developed to address regional bioenergy systems planning, involving agricultural biomass potential estimation, power plants siting, and facility locations and supplies allocation scenarios. With the availability of the spatial and statistical data, these models are capable of evaluating and identifying electric power generation from renewable bioenergy on the regional scale optimally. It thus provides the essential information to decision makers in bioenergy planning and renewable bioenergy management. An application sited in the Region of Waterloo, Ontario Canada is presented to demonstrate the analysis and modelling process.

Natural disasters, specifically hurricanes, can cause catastrophic loss of life and property. In recent years, the United States has endured significant losses due to a series of devastating hurricanes (e.g., Hurricanes Charley and Ivan in 2004, and Hurricanes Katrina and Wilma in 2005). Several Federal authorities report that there are weaknesses in the emergency and disaster planning and response models that are currently employed in practice, thus creating a need for better decision models in emergency situations. The current models not only lack fast communication with emergency responders and the public, but are also inadequate for advising the pre-positioning of supplies at emergency shelters before the storm's impact. The problem of emergency evacuation relief shelter planning during anticipated hurricane events is addressed in this research. The shelter planning problem is modeled as a joint location-allocation-inventory problem, where the number and location of shelter facilities must be identified. In addition, the evacuating citizens must be assigned to the designated shelter facilities, and the amount of emergency supply inventory to pre-position at each facility must be determined. The objective is to minimize total emergency evacuation costs, which is equal to the combined facility opening and preparation cost, evacuee transportation cost and emergency supply inventory cost. A review of the emergency evacuation planning literature reveals that this class of problems has not been largely addressed to date. First, the emergency evacuation relief sheltering problem is formulated under deterministic conditions as a mixed integer non-linear programming (MINLP) model. For three different evacuation scenarios, the proposed MINLP model yields a plan that identifies the locations of relief shelters for evacuees, the assignment of evacuees to those shelters and the amount of emergency supplies to stockpile in advance of an anticipated hurricane. The MINLP model is then used (with minor modifications) to explore the idea of equally distributing the evacuees across the open shelters. The results for the three different scenarios indicate that a balanced utilization of the open shelters is achieved with little increase in the total evacuation cost. Next, the MINLP is enhanced to consider the stochastic characteristics of both hurricane strength and projected trajectory, which can directly influence the storm's behavior. The hurricane's strength is based on its hurricane category according to the Saffir-Simpson Hurricane Scale. Its trajectory is represented as a Markov chain, where the storm's path is modeled as transitions among states (i.e., coordinate locations) within a spherical coordinate system. A specific hurricane that made landfall in the state of Florida is used as a test case for the model. Finally, the stochastic model is employed within a robust optimization strategy, where several probable hurricane behavioral scenarios are solved. Then, a single, robust evacuation sheltering plan that provides the best results, not only in terms of maximum deviation of total evacuation cost across the likely scenarios, but also in terms of maximum deviation of unmet evacuee demand at the shelter locations, is generated. The practical value of this robust plan is quite significant. This plan should accommodate unexpected changes in the behavior of an approaching storm to a reasonable degree with minimal negative impact to the total evacuation cost and the fulfillment of evacuee demand at the shelter locations. Most importantly, the re-allocation and re-mobilization of emergency personnel and supplies are not required, which can cause confusion and potentially increase the response time of responders to the hurricane emergency. The computational results show the promise of this research and usefulness of the proposed models. This work is an initial step in addressing the simultaneous identification of shelter locations, assignment of citizens to those shelters, and determination of a policy for stockpiling emergency supplies in advance of a hurricane. Both the location-allocation problem and the inventory problem have been extensively and individually studied by researchers as well as practitioners. However, this joint location-allocation-inventory problem is a difficult problem to solve, especially in the presence of stochastic storm behavior. The proposed models, even in the deterministic case, are a significant step beyond the current state-of-the-art in the area of emergency and disaster planning.

A variety of practical network optimization problems arising in the context of public supply and commercial transportation, emergency response and risk management, engineering design, and industrial planning are addressed in this study. The decisions to be made in these problems include the location of supply centers, the routing, allocation and scheduling of flow between supply and demand locations, and the design of links in the network. This study is concerned with the development of optimization models and the analysis of five such problems, and the subsequent design and testing of exact and heuristic algorithms for solving these various network optimization problems. The first problem addressed is the time-dependent shortest pair of disjoint paths problem. We examine computational complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. It is shown that this problem, and many variations of it, are nP-Hard and a 0-1 linear programming model that can be used to solve this problem is developed. This model can accommodate various degrees of disjointedness of the pair of paths, from complete to partial with respect to specific arcs. Next, we examine a minimum-risk routing problem and pursue the development, analysis, and testing of a mathematical model for determining a route that attempts to reduce the risk of low probability-high consequence accidents related with the transportation of hazardous materials (hazmat). More specifically, the problem addressed in this study involves finding a path that minimizes the conditional expectation of a consequence, given that an accident occurs, subject to the expected value of the consequence being lesser than or equal to a specified level n, and the probability of an accident on the path being also constrained to be no more than some value h. Various insights into related modeling issues are also provided. The values n and h are user-prescribed and could be prompted by the solution of shortest path problems that minimize the respective corresponding linear risk functions. The proposed model is a discrete, fractional programming problem that is solved using a specialized branch-and-bound approach. The model is also tested using realistic data associated with a case concerned with routing hazmat through the roadways of Bethlehem, Pennsylvania. The third problem deals with the development of a resource allocation strategy for emergency and risk management. An important and novel issue addressed in modeling this problem is the effect of loss in coverage due to the non-availability of emergency response vehicles that are currently serving certain primary incidents. This is accommodated within the model by including in the objective function a term that reflects the opportunity cost for serving an additional incident that might occur probabilistically on the network. A mixed-integer programming model is formulated for the multiple incident - multiple response problem, and we show how its solution capability can be significantly enhanced by injecting a particular structure into the constraints that results in an equivalent alternative model representation. Furthermore, for certain special cases of the MIMR problem, efficient polynomial-time solution approaches are prescribed. An algorithmic module composed of these procedures, and used in concert with a computationally efficient LP-based heuristic scheme that is developed, has been incorporated into an area-wide incident management decision support system (WAIMSS) at the Center for Transportation Research, Virginia Tech. The fourth problem addressed in this study deals with the development of global optimization algorithms for designing a water distribution network, or expanding an already existing one, that satisfies specified flow demands at stated pressure head requirements. The nonlinear, nonconvex network problem is transformed into the space of certain design variables. By relaxing the nonlinear constraints in the transformed space via suitable polyhedral outer approximations and applying the Reformulation-Linearization Technique (RLT), a tight linear lower bounding problem is derived. This problem provides an enhancement and a more precise representation of previous lower bounding relaxations that use similar approximations. Computational experience on three standard test problems from the literature is provided. For all these problems, a proven global optimal solution within a tolerance of 10 -4 % and/or within 1$ of optimality is obtained. For the two larger instances dealing with the Hanoi and New York test networks that have been open for nearly three decades, the solutions derived represent significant improvements, and the global optimality has been verified at the stated level of accuracy for these problems for the very first time in the literature. A new real network design test problem based on the Town of Blacksburg Water Distribution System is also offered to be included in the available library of test cases, and related computational results on deriving global optimal solutions are presented. The final problem addressed in this study is concerned with a global optimization approach for solving capacitated Euclidean distance multifacility location-allocation problems, as well as the development of a new algorithm for solving the generalized lp distance location-allocation problem. There exists no global optimization algorithm that has been developed and tested for this class of problems, aside from a total enumeration approach. Beginning with the Euclidean distance problem, we design depth-first and best-first branch-and-bound algorithms based on a partitioning of the allocation space that finitely converges to a global optimum for this nonconvex problem. For deriving lower bounds at node subproblems in these partial enumeration schemes, we employ two types of procedures. The first approach computes a lower bound via a simple projected location space lower bounding (PLSB) subproblem. The second approach derives a significantly enhanced lower bound by using a Reformulation-Linearization Technique (RLT) to transform an equivalent representation of the original nonconvex problem into a higher dimensional linear programming relaxation. In addition, certain cut-set inequalities generated in the allocation space, objective function based cuts derived in the location space, and tangential linear supporting hyperplanes for the distance function are added to further tighten the lower bounding relaxation. The RLT procedure is then extended to the.general lp distance problem for 1 < p < 2. Various issues related to the selection of branching variables, the design of heuristics via special selective backtracking mechanisms, and the study of the sensitivity of the proposed algorithm to the value of p in the lp - norm, are computationally investigated. Computational experience is also provided on a set of test problems to investigate both the PLSB and the RLT-lower bounding schemes. The results indicate that the proposed global optimization approach using the RLT-based scheme offers a promising viable solution procedure. In fact, among the problems solved, for the only two test instances previously available in the literature for the Euclidean distance case that were posed in 1979, we report proven global optimal solutions within a tolerance of 0.1% for the first time. It is hoped that the modeling, analysis, insights, and concepts provided for these various network based problems that arise in diverse routing, location, distribution, and design contexts, will provide guidelines for studying many other problems that arise in related situations. / Ph. D.

Bibliotek och liknande arkiv har funnits i hundratals år och är en viktig del av ett lands kulturella arbete. De fungerar även som en mötesplats för alla; oavsett ålder, social eller ekonomisk bakgrund. Dessvärre visar färska rapporter att antalet utlåningar och besök minskar på biblioteken. Kulturförvaltningen i Stockholms Stad arbetar för närvarande med att ta fram en Strukturplan gällande biblioteken i staden för en kommande fyraårs period. Syftet med planen är att rekognosera hur läget ser ut idag för att sedan sätta upp mål för hur verksamheten ska utvecklas. För att ge stöd till framtagningen av strukturplanen kommer denna studie utvärdera hur väl lokaliseringsmodellen location-allocation är lämpad som beslutsunderlag för placering av bibliotek samt vilken inverkan olika typer av behovspunkter har på resultatet. Genom att applicera modellen i fallstudien Stockholms Stads bibliotek, kan modellen utvärderas för att se om den kan användas vid liknade frågeställningar i framtiden. Med hjälp av data över var folk bor, arbetar och rör sig utvärderas modellen i två steg. Först kommer varje behovstyp att analyseras var för sig och därefter testas tre metoder för att slå ihop de olika typerna för att skapa en mer enhetlig bild. Resultaten visar att modellen location-allocation har stor potential för att användas som beslutsstöd för bibliotekens verksamhet. Utifrån de olika behovspunkterna kan strategiska placeringar hittas och en bredare bild ges av var folk bor, arbetar och hur de rör sig. Varje enskilt resultat berättar mer om var människorna i staden befinner sig och det är också lätt att se skillnader på till exempel var folk bor och arbetar, samt var man bör finnas för att nå ut till den yngre befolkningen jämfört med befolkningen i sin helhet. De tre metoderna för att sammanslagning av resultaten visade sig alla vara effektiva och pålitliga. Att visa alla delresultat på en och samma karta, förslagsvis med hjälp av en interaktiv PDF, ger en tydlig bild över de olika behovstypernas betydelse och inverkan. Kluster av valda platser kan hittas och ringas in. De två andra metoderna, MCE-analys och linjarisering, ger en bra bild över vilka strategiska placeringar som finns, båda kan vara användbara för att på ett snabbt och enkelt sätt förmedla resultatet. En del begränsningar och osäkerheter finns dock med modellen som är viktiga att beakta. Lösningsalgoritmen sker heuristiskt vilket gör att det kan vara svårt att förstå exakt hur den räknar och vilken inverkan olika parametrar har. Därför är det viktigt att en omfattande genomgång görs för den verksamhet som ska undersökas, det vill säga, vilka behov finns, hur de ser på sin verksamhet och vilka parametrar tror de inverkar på besökarnas rörelsemönster. Slutligen ska det betonas att Kulturförvaltningen, som har varit en del av denna studie och som har gett sin input till analysen, har ansett att modellen och materialet är användbart. Då avsikten med analysen inte var att hitta exakta placeringar av bibliotek utan snarare att få en översiktlig bild av var de bör placeras för att bäst nå ut till kommunens invånare kan slutsatsen dras att resultaten från location-allocation modellen ger en värdefull input som beslutsunderlag. Det är dock viktigt att ha i åtanke att resultatet från modellen inte visar en exakt verklighet, utan att den endast ger ett förslag på hur man bäst når ut till befolkningen. Det ska också tilläggas att detta bara är en del av många när det kommer till biblioteksplanering. Till exempel spelar bibliotekens lånestatistik, utbud och inriktning en viktig roll när det kommer till att utvärdera verksamheten. / Libraries and similar archives have existed for hundreds of years and are an important part of a country's cultural work. It also serves as meeting place for all, regardless of age, social and economic background. However, recent studies state that the physical loaning of literature and the number of visitors at libraries are decreasing. Kulturförvaltningen (The Department of Art and Culture), a part of the municipality of Stockholm, is currently producing a structure plan for the development of the libraries in the coming four years. The purpose of the plan is to evaluate the current circumstances and thereafter set targets on how their business should develop. To support the work with the structure plan this study will evaluate the model location-allocation and examine if it is suitable as a decision basis for locating libraries and what impact different types of demand points have on the result. By applying the model in a case study, consisting of the libraries in Stockholm, the model can be evaluated in terms of usefulness in similar problems in the future. With the help of data of where people live, work and how they move, the model will be evaluated in two stages. In the first stage, different demand points will be examined separately and thereafter three methods will be tested to combine the different types to create a more uniform picture. The results show that the location-allocation model has a large potential to be used as a decision basis for library planning. With the help of different demand points, strategic locations can be found and a wider picture is given of where people live, work and how they move. Each individual result tells more about where the citizens are and it is also easy to see distinctions between the different types of demand, for example where people live and work and where the libraries should be located to reach the younger population in comparison to the population as a whole. The three methods for merging the results all ended up to be both effective and trustworthy. To show all the sub-results in the same map, preferably with the help of an interactive PDF, highlights the importance and impact different demands have as well as allowing patterns or clusters to be found and marked. The two other methods tested, a MCE-analysis and linearization, are both useful to show strategic locations and to quickly and simply communicate results. However, there are some limitations and uncertainties with the model that are important to take into consideration. The algorithm used to solve the problem is heuristic, making it hard to understand exactly how it calculates and what impact different parameters have. Consequently, it is important to make an extensive review of the business that will be examined, more specific, what are their demands, how do they look at their business and what parameters do they believe impact the movement pattern of visitors. Finally, it should be emphasized that Kulturförvaltningen has been a part of this study from the beginning and they have given their support and input into the analysis throughout the process. In the end, they considered the model and the results from it to be useful in the decision-making process. It is important to keep in mind that the results of the model do not show an exact reality, the intention of the analysis was to develop an overview of where libraries should be approximately located, rather than to find exact locations. The end result being libraries located to better reach their citizens. However, the above is only looking at one part of many when it comes to library site planning and many other issues such as the libraries lending rate, supply and overall focus play an important role when it comes to evaluating their business.

While the concept of regional organization (regionalization) of perinatal care aimed at reducing perinatal mortality has remained at the agenda of developed countries since 1970&rsquo / s, Turkey is one of the countries that does not have such a system yet. In this study, a three-level hierarchical location-allocation model is developed for the regionalization of perinatal care in an attempt to have a better distribution of maternal and perinatal health care services in Turkey. Since the mathematical model developed is difficult to solve in a reasonable time, we propose three heuristic approaches: top-down, modified top-down and Lagrangean relaxation based heuristics. These heuristics are computationally tested on a set of problem instances for networks ranging from 10 to 737 vertices. A significant result is that Lagrangean relaxation based heuristic outperforms the other two heuristics in terms of solution quality. In most of the test problems, the modified top-down heuristic outperforms the top-down heuristic in terms of solution quality. Using the proposed approaches, we solve a real life problem corresponding to the Eastern and South Eastern Anatolian Regions (the East Region) of Turkey.