Premium
Multicast routing under quality of service constraints for vehicular ad hoc networks: mathematical formulation and a relax‐and‐fix heuristic
Author(s) -
Ribeiro Celso C.,
Santos Tiago de A.,
de Souza Cid C.
Publication year - 2019
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12605
Subject(s) - computer science , multicast , heuristic , integer programming , benchmark (surveying) , mathematical optimization , routing (electronic design automation) , quality of service , distributed computing , computer network , algorithm , artificial intelligence , mathematics , geodesy , geography
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.