Extensive facility location problems on networks with equity measures |
| |
Authors: | Justo Puerto Federica Ricca |
| |
Institution: | a Universidad de Sevilla, Dep. Estadistica e Investigación Operativa, Spain b Università di Roma “La Sapienza”, Dip. Statistica, Probabilità e Statistiche Applicate, Italy c Università di Roma “La Sapienza”, Dip. Matematica per le Decisioni Economiche, Finanziarie ed Assicurative, Italy |
| |
Abstract: | This paper deals with the problem of locating path-shaped facilities of unrestricted length on networks. We consider as objective functions measures conceptually related to the variability of the distribution of the distances from the demand points to a facility. We study the following problems: locating a path which minimizes the range, that is, the difference between the maximum and the minimum distance from the vertices of the network to a facility, and locating a path which minimizes a convex combination of the maximum and the minimum distance from the vertices of the network to a facility, also known in decision theory as the Hurwicz criterion. We show that these problems are NP-hard on general networks. For the discrete versions of these problems on trees, we provide a linear time algorithm for each objective function, and we show how our analysis can be extended also to the continuous case. |
| |
Keywords: | Path location Range criterion Hurwicz criterion Pareto-optimal paths |
本文献已被 ScienceDirect 等数据库收录! |
|