Range minimization problems in path-facility location on trees

AbstractIn this paper, we study the problem of locating path-shaped facilities on a tree network with non negative weights associated to the vertices and positive lengths associated to the edges. Our objective is to ensure low variability of the distribution of the distances from the demand points (clients) to a facility. In the location process, we take into account both the maximum and the minimum weighted distances of a client to a facility and we formulate our problem in order to minimize the “Range” function which is defined as the difference between the maximum and the minimum weighted distances from the vertices of the network to a facility. We discuss different formulations of the problem providing polynomial time algorithms for each of them. We solve in polynomial time all the above problems also when an additional constraint on the maximum length of the path is introduced