Submarine Cable Network Design for Regional Connectivity

This paper optimizes path planning for a trunk-and-branch topology network in an irregular 2-dimensional manifold embedded in 3-dimensional Euclidean space with application to submarine cable network planning. We go beyond our earlier focus on the weighted costs of cables (cable laying cost, resilience, design level and repair rate) to include the cost of branching units (BUs), including material and labor, as well as submarine cable landing stations (CLSs). This optimization also includes choices of locations of BUs and CLSs. These are important issues for the economics of cable laying and significantly change the model and the optimization process. We pose the problem as a variant of the Steiner tree problem, but one in which the Steiner nodes can vary in number, while incurring a penalty. We refer to it as the weighted Steiner node problem. It differs from the Euclidean Steiner tree problem, where Steiner points are forced to have degree three; this is no longer the case, in general, when nodes incur a cost. We are able to prove that our algorithm is applicable to Steiner nodes with degree greater than three, enabling optimization of network costs in this context. The optimal solution is achieved in polynomial-time using dynamic programming.