Premium
Gamma deployment problem in grids: hardness and new integer linear programming formulation
Author(s) -
Faraj Marcelo Fonseca,
Urrutia Sebastián,
Sarubbi João F. M.
Publication year - 2020
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.12759
Subject(s) - software deployment , computer science , solver , integer programming , linear programming , metric (unit) , mathematical optimization , set (abstract data type) , distributed computing , computer network , mathematics , algorithm , engineering , operations management , programming language , operating system
Vehicular networks are mobile networks designed for the domain of vehicles and pedestrians. These networks are an essential component of intelligent transportation systems and have the potential to ease traffic management, lower accident rates, and offer other solutions to smart cities. One of the most challenging aspects in the design of a vehicular network is the distribution of its infrastructure units, which are called roadside units (RSUs). In this work, we tackle the gamma deployment problem that consists of deploying the minimum number of RSUs in a vehicular network in accordance with a quality of service metric called gamma deployment. This metric defines a vehicle as covered if it connects to some RSUs at least once in a given time interval during its whole trip. Then, the metric parameterizes the minimum percentage of covered vehicles necessary to make a deployment acceptable or feasible. In this paper, we prove that the decision version of the gamma deployment problem in grids is NP‐complete. Moreover, we correct the multiflow integer linear programming formulation present in the literature and introduce a new formulation based on set covering that is at least as strong as the multiflow formulation. In experiments with a commercial solver, the set covering formulation widely outperforms the multiflow formulation with respect to running time and linear programming relaxation gap.