Improving the location of minisum facilities through network modification

In this paper, the authors consider the problem of how the transportation network can be modified most efficiently in order to improve the known location of the facilities. The performance of the facilities is measured by the ‘minisum’ objective. The authors examine in the paper two types of network modifications: reductions and additions of links. They analyze various reduction and addition problems for both trees and general networks. For trees, the authors present exact results and algorithms for the majority of problems studied. For general networks, they discuss mainly heuristics.