Efficient points in the biobjective cent-dian problem

Abstract

This paper analyzes the cent-dian problem on a weighted connected undirected network from a biobjective point of view, that is, considering two costs per edge. The problem consists of determining one facility on the network which minimizes the convex combination of both the total distance and the maximum distance from any point to the rest of the graph. Using computational geometry techniques, we propose a polynomial algorithm in O(|V||E|log|V|) time which determines all efficient points of the network. Several computational results are supplied at the end of the paper.