Multicast routing under quality of service constraints for vehicular ad hoc networks : mathematical formulation and a relax-and-fix heuristic

Abstract

In this paper, we investigate a multicast routing problem with quality of service constraints on ad hoc vehicular networks. An integer programming formulation for the problem is proposed that forms the basis of a relax-and-fix heuristic designed with the goal of producing feasible solutions of good quality. In addition, preprocessing procedures relying on simple and constrained shortest paths are developed that reduce the model size to the point of making it viable to compute. Computational experiments on benchmark instances generated to mimic realistic settings are reported. The results highlight the effectiveness of the relax-and-fix heuristic and the importance of the preprocessing routines for the computability of the proposed mathematical model