Load balancing and capacity constraints in a hierarchical location model

Recent work on the location of perinatal facilities in the municipality of Rio de Janeiro resulted in the development of an uncapacitated, three-level hierarchical model. An important issue that arose during the course of the research was the need to include some form of capacity constraints into the model, especially in the higher, resource intensive level of the hierarchy. This need was felt from technical discussions related to the research work and from contacts with municipality health officials. A capacitated model is presented and solved using a Lagrangean heuristic. For smaller problems optimal solutions are found using CPLEX; it is found that the heuristic usually gives high quality solutions. Next a bi-criterion model is formulated in which the additional objective measure is the imbalance in facility loading. This is solved exactly for a small problem and approximately for the 152-vertex Rio de Janeiro data.