Analyzing tradeoffs between zonal constraints and accessibility in facility location

One recent extension of the PMP is the zonally constrained median problem. This model recognizes that site selection often is influenced by the desire to distribute equitably the impacts or benefits of facilities by locating them among multiple regions, districts, or zones. Zonal constraints can be used in one form to ensure a minimum number of facilities in any zone and in another form to prevent too many facilities in any zone. However, a planner’s desire to meet zonal constraints can conflict with the desire to maximize system-wide public accessibility (minimize total distance traveled). Non-inferior compromise solutions which partially enforce zonal constraints could be most helpful to decision-makers, especially in a sensitive political climate. This paper presents a constrained multiobjective model (denoted the extended zonally constrained median problem, or EZCOMP) which can identify both supported non-dominated solutions and unsupported non-dominated solutions (which would be missed using the weighting approach to multiobjectives). A special Lagrangean relaxation is exploited in the proposed solution methodology. This is a first attempt at using a Lagrangean based approach to identify unsupported non-dominated solutions to a location model. Results on two data sets with different types of zones show the Lagrangean approach to be efficient compared to linear-integer programming and a vertex substitution heuristic, even in the solution of problems of over 23000 variables and 23000 constraints.