A Round-Trip Location Problem on a Tree Graph

The problem considered is to locate one new facility with respect to a finite number of pairs of existing facilities on, a tree graph, which typically represents a road network, so as to minimize the maximum cost, where cost are linear increasing functions of the round-trip distance a vehicle based at the new facility travels via a pair of existing facilities. Based on an attainable lower bound for the minimax problem, an algorithm is developed that yields all optimal solutions to the problem.