Algorithms for central-median paths with bounded length on trees

Algorithms for central-median paths with bounded length on trees

0.00 Avg rating0 Votes
Article ID: iaor2009135
Country: Netherlands
Volume: 179
Issue: 3
Start Page Number: 1208
End Page Number: 1220
Publication Date: Jun 2007
Journal: European Journal of Operational Research
Authors: , ,
Keywords: graphs, heuristics
Abstract:

The location of path-shaped facilities on trees has been receiving a growing attention in the specialized literature in the recent years. Examples of such facilities include railroad lines, highways and public transit lines. Most of the papers deal with the problem of locating a path on a tree by minimizing either the maximum distance from the vertices of the tree to the facility or of minimizing the sum of the distances from all the vertices of the tree to the path. However, neither of the two above criteria alone capture all essential elements of a location problem. The sum of the distances criterion alone may result in solutions which are unacceptable from the point of view of the service level for the clients who are located far away from the facilities. On the other hand, the criterion of the minimization of the maximum distance, if used alone, may lead to very costly service systems.

Reviews

Required fields are marked *. Your email address will not be published.