In 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.
In 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.
Range minimization problems in path-facility location on trees / Puerto, J.; Ricca, F.; Scozzari, A.. - STAMPA. - (2011), pp. 231-234. (Intervento presentato al convegno CTW 2011: 10th Cologne Twente Workshop on Graphs and Combinatorial Optimization tenutosi a Frascati nel 14-16 giugno 2011).
Range minimization problems in path-facility location on trees
F. Ricca;
2011
Abstract
In 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
