Construction Line Algorithms for the Connection Location-Allocation Problem

In the connection location-allocation problem we are given a set of material flows between pairs of existing facilities each of which must be routed through a connection facility. The objective is to minimize the total transportation costs by locating a given number of connections and allocating the flows accordingly. For this problem many properties and solution methods of the well-known facility location-allocation problem can be transferred, among others the construction line algorithm, an exact solution method based on discretization results under polyhedral gauge distances. We have implemented construction line algorithms for the connection location-allocation problem without restrictions as well as in the presence of forbidden regions or barriers. We considered various distance functions, ranging from the Manhattan distance to mixed polyhedral gauge distances and applied hull properties to further reduce the dominating set.