Gamma deployment problem in grids: hardness and new integer linear programming formulation

• Author: Marcelo Fonseca Faraj,Sebastián Urrutia,João F. M. Sarubbi
• Published date: 01 November 2020
• Date: 01 November 2020
• DOI: http://doi.org/10.1111/itor.12759

Intl. Trans. in Op. Res. 27 (2020) 2740–2759

DOI: 10.1111/itor.12759

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Gamma deployment problem in grids: hardness and new

integer linear programming formulation

Marcelo Fonseca Faraja,b, Sebasti´

an Urrutiaa,c,∗and Jo˜

ao F. M. Sarubbid

aComputer Science Department, Federal University of Minas Gerais, Belo Horizonte, MG 31270-901, Brazil

bFaculty of Computer Science, University of Vienna, 1010 Vienna,Austria

cFaculty of Logistics, Molde University College, 6410 Molde, Norway

dComputing Department, Federal Center of Technological Education of Minas Gerais, Belo Horizonte,30510-000, Brazil

E-mail: marcelofaraj@gmail.com [Faraj]; surrutia@dcc.ufmg.br[Urrutia]; joao@cefetmg.br [Sarubbi]

Received 15 July2019; received in revised form 12 November 2019; accepted 15 November 2019

Abstract

Vehicular networks are mobile networks designed for the domain of vehicles and pedestrians. These net-

works 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.

Keywords:gamma deployment; complexity; integer linear programming

1. Introduction

Vehicular networks (Aslam et al., 2012; Zeadally et al., 2012; Silva et al., 2016b; Sarubbiet al., 2017)

are wireless communication networks designed to the domain of vehicles, including pedestrians and

transit authorities, which support cooperative driving among communicating vehicles on the road

and received remarkable attention in last years. They have potential to provide greater safety on the

∗Corresponding author.

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

M. F. Faraj et al. / Intl. Trans. in Op. Res. 27 (2020) 2740–2759 2741

Fig. 1. Communication in vehicular networks.

roads by (a) cooperative collision warning, (b) postcrash notification, (c) traffic vigilance against

driving offenses, and (d) real-time traffic. Vehicular networks also afford commercial applications

as (a) Internet access, (b) digital map downloading, and (c) value-added advertisement. Besides,

vehicular networks can reduce fuel consumption using electronic toll collection, help drivers with

parking availability, and choose alternative routes according to traffic jams and accidents (Kumar

et al., 2013). These benefits transform our lifestyle and are aligned with the concept of smart

cities.

Communication in vehicular networks can occur in three distinct classes (Sarubbi et al., 2017):

(a) between vehicles (V2V), (b) between infrastructure units (I2I), and (c) between a vehicle and an

infrastructure unit (V2I). Figure 1 presents these three communication classes, which can co-occur

in practice. The presence of infrastructure units named roadside units (RSUs) can significantly

increase the efficiency of the network and assure that it will work properly even in low traffic

conditions. The quantity and distribution of RSUs depend on the quality of service metric used in

the vehicular network.

The problem of deploying RSUs to compose a vehicular network has been studied with a wide

variety of constraints, objective functions, and quality of service metrics (Lochert et al., 2008;

Trullols et al., 2010; Sun and Yang, 2011; Aslam et al., 2012; Rebai et al., 2012; Trullols-Cruces

et al., 2012; Liu et al., 2013). Even though many of these approaches and interesting, we will not

go through them since their diversity goes beyond the scope of this work. Instead, we use the next

paragraphs to describe some previous works relevant to our research context.

Silva and Meira (2015) proposed a QoS metric called delta deployment, which ensures that at

least a fraction of the vehicles in the road network are covered during a given percentage of their

trips. They also proposeda greedy heuristic to minimize the number of RSUs deployed ensuring this

metric. Other works have also proposed heuristics to deploy RSUs based on the delta deployment

metric such as Sarubbi and Silva (2016) and Sarubbi et al. (2016). Rashidi et al. (2012) analyzed the

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation of OperationalResearch Societies