Locating Discretionary Service Facilities Based on Probabilistic Customer Flows

In this paper, we consider the problem of locating discretionary facilities on a network. In contrast to previous work in the area, we no longer assume that information on customers' flows along all paths of the network is known (in practice such information is rarely available). Assuming that the fraction of customers that travel from any node to any adjacent node in the network is available, the problem of locating the facilities so as to maximize the fraction of customers that pass by a facility before reaching their destination is formulated as a nonlinear Integer Program. It is shown that by employing the theory of constrained Markov Decision Processes this problem can be reformulated as a linear Mixed Integer Program. The paper presents some preliminary computational results for this formulation as well as results for a greedy heuristic algorithm.