Solution procedures for the service system design problem

This article studies a service system design problem that involves locating service faclities, determining their number and capacities and assigning user nodes to those facilities. The goal is to minimize total costs made of the costs of accessing facilities by users and waiting for service at these facilities as well as the cost of setting up and operating the facilities. This problem arises mainly in the area of telecommunication network design. But the problem is quite general and can be encountered in several planning contexts such as transportation planning, siting of emergency service facilities and refuse collection and disposal in public sector. The article represents a significant improvement over previous research by presenting a unified model of the problem that includes the number, locations, and capacities of service facilities as variables to be determined in the model and incorporates in the total cost to be minimized the user waiting time (queueing) cost. An integer programming formulation of the problem with a nonlinear objective function is presented. Two heuristic solution procedures based on a Lagrangean relaxation of the problem are developed. Extensive computational results across a variety of problem structures are reported. These results indicate that the second solution procedure is very effective for a wide range of problem structures and traffic loads.