A hybrid MIP-Based heuristic for the optimal design of DVB-T2 networks

Due to the ongoing introduction of the second generation of the Digital Video Broadcasting - Terrestrial standard (DVB-T2), television broadcasters that are already active and new broadcasters entering in the business will be required to (re) design their networks. This is generating a new interest for effective and efficient DVB optimization software tools. In this work, we propose a new fast hybrid heuristic for the design of DVB-T2 networks. The heuristic combines a genetic algorithm, adopted to efficiently explore the solution space of power emissions of DVB stations, with a (very) large neighborhood search formulated as a Mixed Integer Programming (MIP) problem solved exactly. Computational tests on realistic instances show that the new hybrid heuristic is able to identify solutions granting much higher user coverage than those identified by a state-of-the-art optimization solver.