Satellite Network, Design, Optimization, and Management

Abstract

We introduce several network design and planning problems that arise in the context of commercial satellite networks. At the heart of most of these problems we deal with a traffic routing problem over an extended planning horizon. In satellite networks route changes are associated with significant monetary penalties that are usually in the form of discounts (up to 40%) offered by the satellite provider to the customer that is affected. The notion of these rerouting penalties requires the network planners to consider management problems over multiple time periods and introduces novel challenges that have not been considered previously in the literature. Specifically, we introduce a multiperiod traffic routing problem and a multiperiod network design problem that incorporate rerouting penalties. For both of these problems we present novel path-based reformulations and develop branch-and-price-and-cut approaches to solve them. The pricing problems in both cases present new challenges and we develop special purpose approaches that can deal with them. We also show how these results can be extended to deal with traffic routing and network design decisions in other settings with much more general rerouting penalties. Our computational work demonstrates the benefits of using the branch-and-price-and-cut procedure developed that can deal with the multiperiod nature of the problem as opposed to straightforward, myopic period-by-period optimization approaches. In order to deal with cases in which future demand is not known with certainty we present the stochastic version of the multiperiod traffic routing problem and formulate it as a stochastic multistage recourse problem with integer variables at all stages. We demonstrate how an appropriate path-based reformulation and an associated branch-and-price-and-cut approach can solve this problem and other more general multistage stochastic integer multicommodity flow problems. Finally, we motivate the notion of reload costs that refer to variable (i.e., per unit of flow) costs for the usage of pairs of edges, as opposed to single edges. We highlight the practical and theoretical significance of these cost structures and present two extended graphs that allow us to easily capture these costs and generate strong formulations.