Full ordering Voronoi sets for bi-facility bicriterion (max, sum) location on networks

The Bi-facility Max-Sum Location problem on networks consists of finding a pair of points on the network minimizing the maximum and the sum of the distances to a finite set of user points. A solution is Pareto-optimal if no other solution is better for the two objectives. It is a Bayes-optimal solution if it is optimal for some linear combination of the objectives. The analysis of the distance function allows us to identify a kind of Voronoi sets where the order of the user points from the farthest one to the nearest one does not change. We show how to use these sets to geometrically construct the set of pairs of values of the objective functions for all the solutions. This set consists of the union of triangles where the bidimensional objective is a linear function. The dominance between the vertices and sides of these triangles can be used to identify all the Pareto-optimal and Bayes-optimal solutions of the problem.