1. ¹University of Toronto, Toronto, Ontario, Canada
2. ²Long Island University, Brookville, NY, USA

Correspondence: J Wang, College of Management, Long Island University, C.W. Post Campus, 720 Northern Boulevard, Brookville, NY 11548, USA. E-mail: Jiamin.Wang@liu.edu

Received April 2006; Accepted April 2007; Published online 29 August 2007.

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.