Locating flow-capturing units on a network with multi-counting and diminishing returns to scale

In the paper we consider the problem of locating flow-capturing units (facilities) on a transportation network, where the level of consuming service by customers depends on the number of facilities that they encounter on their pre-planned tour (the effect of multi-counting). Two location problems are considered: Problem 1 – minimizing the number of facilities required to ensure the maximal level of consumption, and Problem 2 – maximizing the total consumption given a restriction on the number of facilities. Both problems are NP-hard on general networks. Integer programming formulations of the problems are given. For Problem 2, a heuristic with worst-case analysis is presented. It is shown that Problem 2 is NP-hard even on a tree (and even without multi-counting). For Problem 1 on a tree a polynomial algorithm is presented. If it is required additionally that at most one facility can be located at each node and locations are restricted to nodes, then both problems are NP-hard on trees.