The probabilistic 1-maximal covering problem on a network with discrete demand weights

Abstract

We discuss the probabilistic 1-maximal covering problem on a network with uncertain demand. A single facility is to be located on the network. The demand originating from a node is considered covered if the shortest distance from the node to the facility does not exceed a given service distance. 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 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.

Keywords:

• location
• optimization
• probability
• network

Acknowledgements

We would like to thank the two anonymous referees for their comments and suggestions. Oded Berman was supported by grants from NSERC. Jiamin Wang was supported by a grant from the Research Committee at the C. W. Post Campus of Long Island University.