Facility location under single assignment restriction

Abstract

Consider a capacitated facility location problem in which each customer is assumed to have a uniform demand, and each facility capacity has to be chosen from the given set of admissible levels. Under the restriction that each customer``s uniform demand be met by exactly one facility, the objective is to select a set of facilities to open, along with their capacities, and to assign customer``s demand to them so as to minimize the total cost which includes fixed costs of opening facilities as well as variable assignment costs. The problem is modelled as a pure zero-one program which extends the scope of applicability significantly over that by conventional location models. The purpose of this study is to develop efficient computational procedures for solving the pure zero-one facility location problems with the fixed uniform facility capacity, the fixed facility capacity, and the multiple facility capacity. Due to the special structure of our zero-one location problem with a uniform demand, it can be converted to a location problem with unimodular property. First, a Lagrangean relaxation algorithm is developed to solve the pure zero-one location problem with the fixed uniform facility capacity. The problem may be viewed as a variant of well-known capacitated facility location problems. The algorithm is made efficient by employing a device which exploits the special structure of a surrogate constraint. The efficiency of the algorithm is analyzed through computational experiments with some test problems. Secondly, we give a solution method for the zero-one location problem with the fixed facility capacity based on Cross Decomposition developed by Van Roy. Solution methods to derived sub and master problems in a branch and bound scheme are discussed, and their computational results are given for a number of test problems. We also compare the efficiency of the method with other methods suggested for the fixed uniform capacity case. Finally, we present an implementati...