Solving Medium Scale Instances of the Cable-Trench Problem: Applied to the Proposed LOFAR Super Station in Nancay, France

The Cable-Trench Problem (CTP), defined by Vasko et al. (2002), is a formal definition of the NP-hard optimization problem encountered when attempting to connect a set of fixed location facilities by a network of cables that are to be buried in trenches. Previous work has demonstrated methods of solving CTP instances using heuristics for small (20 facilities) and very large (500-25,000 facilities) problems. This thesis investigates the application of various methods for finding optimal, or near optimal, solutions for the CTP with instances consisting of around 100 facilities. Motivating this study is a recent publication describing a cable and trench layout for distributed radio-telescope antenna arrays. Zerka et al. (2012) provided a technical study for defining and prototyping a Low-Frequency Super Station (LSS) in Nancay consisting of 96 Low-Frequency antenna arrays optimally distributed across a 400 x 450 meter area. Girard (2013) produced a sub-optimal layout for cables and trenches required to connect this array to the central control facility by modeling the problem as a CTP and using a divide-and-conquer decomposition strategy. The solution methods investigated in this thesis address CTP instances with similar characteristics and size to that of the Girard problem without using decomposition. We will analyze of the results achieved by applying these methods. In addition, we will describe a novel approach for modeling CTPs based on multi-commodity flows and include the comparative analysis. The problem specified by Girard will be used as a case study to compare the performance of these solution methods. Results demonstrate that the new model based on multi-commodity flows provides the best results when proving optimality for the problem defined by Girard.