Modeling and solving an economies-of-scale service system design problem

This paper studies the design of a service system in the presence of economies of scale (EoS). The goal is to decide on the number, location, service capacities of facilities, and the allocation of customers to the opened facilities to minimize the total cost of the system. The total cost includes the opening and serving costs of facilities as well as customers' transportation and waiting costs. To reflect the EoS in the modeling, a general opening cost function is assumed for each service facility with the characteristic of being concave and nondecreasing in its service capacity. A Lagrangian relaxation algorithm is developed for solving the problem in its general form. The algorithm decomposes the relaxed model into homogeneous subproblems where each one can be optimally solved in polynomial time with no need for an optimization solver. Furthermore, the optimal service capacity of each open facility is determined as a closed-form function. Our computational experiment shows that the developed algorithm is both efficient and effective in solving the proposed problem.