The probabilistic gradual covering location problem on a network with discrete random demand weights

We study the gradual covering location problem on a network with uncertain demand. A single facility is to be located on the network. Two coverage radii are defined for each node. The demand originating from a node is considered fully covered if the shortest distance from the node to the facility does not exceed the smaller radius, and not covered at all if the shortest distance is beyond the larger radius. For a distance between these two radii, the coverage level is specified by a coverage decay function. It is assumed that demand weights are independent discrete random variables. The objective of the problem is to find a location for the facility so as to maximize the probability that the total covered demand weight is greater than or equal to a pre-selected threshold value. We show that the problem is NP-hard and that an optimal solution exists in a finite set of dominant points. We develop an exact algorithm and a normal approximation solution procedure. Computational experiment is performed to evaluate their performance. (C) 2011 Elsevier Ltd. All rights reserved.