Locating service facilities to reduce lost demand

We analyze the problem of locating a set of service facilities on a network when the demand for service is stochastic and congestion may arise at the facilities. We consider two potential sources of lost demand: (i) demand lost due to insufficient coverage; and (ii) demand lost due to congestion. Demand loss due to insufficient coverage arises when a facility is located too far away from customer locations. The amount of demand lost is modeled as an increasing function of the travel distance. The second source of lost demand arises when the queue at a facility becomes too long. It is modeled as the proportion of balking customers in a Markovian queue with a fixed buffer length. The objective is to find the minimum number of facilities, and their locations, so that the amount of demand lost from either source does not exceed certain pre-set levels. After formulating the model, we derive and investigate several different integer programming formulations, focusing in particular on alternative representations of closest assignment constraints. We also investigate a wide variety of heuristic approaches, ranging from simple greedy-type heuristics, to heuristics based on time-limited branch and bound, tabu search, and random adaptive search heuristics. The results of an extensive set of computational experiments are presented and discussed.