Mauricio G. C. Resende

Abstract. We model a wireless backhaul network design problem as a prize-collecting directed Steiner forest problem. In this problem we are given a set of demand points where wireless traffic originates, along with the amount of traffic, a set of backbone access points, and we want to build a wireless backhaul network to transport the traffic from the demand points to the backbone by using equipment installed on a set of given utility poles. LTE and Wi-Fi are used to capture traffic from demand points and backhaul transmission equipment is used to transmit traffic between utility poles and between utility poles and backbone access points. There are many types of constraints imposed on the design, e.g., maximum transmission equipment coverage, maximum number of hops from the demand point to the backbone node, maximum node in-degree, and link capacity on the sum of flow into a node and the traffic captured by the LTE and Wi-Fi equipment at the node. The objective is to maximize the difference between the monetary value of the backhauled traffic and the cost of building and operating the network. We present a biased random-key genetic algorithm to solve this problem.