Article ID: | iaor1996955 |
Country: | Switzerland |
Volume: | 60 |
Issue: | 1 |
Start Page Number: | 121 |
End Page Number: | 143 |
Publication Date: | Dec 1995 |
Journal: | Annals of Operations Research |
Authors: | Berman Oded, Krass Dmitry, Xu Chen Wei |
Keywords: | law & law enforcement, location, advertising |
The problem of locating flow-intercepting facilities on a network with probabilistic customer flows and with facility set-up costs is studied in this paper. Two types of models are investigated, namely the double-counting model and the no-double-counting model (double-counting refers to multiple interceptions of the same customer). For each model, a nonlinear integer programming formulation is first obtained via the theory of Markov chains, and an equivalent linear integer program is then derived. A simple greedy heuristic is proposed for solving both models and a worst-case bound is established, which is shown to be tight under certain conditions.