Project Description

This thesis addresses the planning problem of reorganizing an existing network of public facilities, such as schools, hospitals or courts of justice, in response to structural changes in the demand for public services and to the need of improving the cost-effectiveness of service provision. “Public facility planning” is here understood as the activity consisting in making decisions on the number, location, type (in terms of the mix of services offered), and capacity of facilities supplying public services, and on their catchment areas (i.e. the population centers served by each facility).

Public facility planning problems are addressed in this thesis with mathematical programming (or optimization) models that aim to help decision makers arrive at efficient solutions in terms of costs to service providers and of quality of service to users in key components such as accessibility to facilities. More specifically, the optimization models studied here are discrete facility location models, formulated as mixed-integer linear programming (MILP or MIP) models. This thesis focuses on the following basic, single-service model and on extensions of it. The geographic setting is represented by a discrete set of population centers with known demands, a discrete set of sites where facilities can be located, and given travel distances (or times, or costs) between centers and sites. The problem is to locate facilities and assign centers to those facilities, so that each center is assigned to the closest facility, each facility satisfies minimum and maximum capacity constraints, and the total travel distance is minimized, i.e. accessibility to facilities is maximized.

The basic model described above, called the capacitated median model, captures relevant ingredients of public facility planning problems, but it has received little attention in the literature, particularly no hierarchical extension considering multiple services and multiple facility types has been presented, and no specialized exact solution method has been proposed.

The contributions of this thesis to the discrete facility location literature are the following:

• Formulation of optimization models combining multiple services, minimum and maximum capacity constraints, and constraints on the spatial pattern of assignments of users to facilities, extending previous hierarchical facility location models;
• Description of applications of models with single and multiple services to real-world problems of reorganizing networks of schools and courts of justice in Portugal;
• Development of new valid inequalities for the MIP formulation of the single service capacitated median model and proposal of an exact solution method, composed of a priori reformulation and branch-and-cut, that reduces solution times relatively to a generic MIP optimizer;
• Presentation of computational experiments on solving single service models with a modern generic MIP optimizer, including the fixed-charge capacitated facility location problem and the capacitated median model, in order to identify the most efficient formulation, among variants known from the literature, to solve these models to optimality without resorting to a specialized algorithm.

Research Team

CITTA

• João Teixeira
• António Pais Antunes (supervisor)

Université catholique de Louvain

• Laurence Wolsey (supervisor)

Financial Support

• FCT

Stage of Progress

• Concluded in 2012