Relays are regenerators extending the reach of optical signals in telecommunication networks; they may be strategic locations where exchange of drivers, trucks or mode of transportation takes place in transportation networks; they may become refuelling/recharging stations extending the reach of alternative fuel vehicles in green transportation. With different names and characteristics, relays play a crucial role in the design of telecommunication and transportation networks. We study the network design problem with relays and present a multi-commodity flow formulation and a branch-and-price algorithm to solve it. Motivated by the practical applications we investigate the special case where each demand has a common designated source. In this special case, we can show that there exists an optimal design that is a tree. Using this fact, we replace the multi-commodity flow formulation with a tree formulation enhanced with Steiner cuts. Employing a branch-and-price-and-cut schema on this formulation, we are able to further extend computational efficiency. Our extensive computational experiments indicate the efficacy of the proposed solution approaches solving problem instances up to 500 nodes.
Citation
Yıldız, Barış, Oya Ekin Karaşan, and Hande Yaman. “Branch-and-Price Approaches for the Network Design Problem with Relays.” Computers & Operations Research (2018).