A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities

João F. Machry Sarubbi; Daniel Cravieé de A. Vieira; Elizabeth F. Wanner; Cristiano M. Silva

doi:10.1109/NOMS.2016.7502985

A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities

João F. Machry Sarubbi
, Daniel Cravieé de A. Vieira
, Elizabeth F. Wanner
, Cristiano M. Silva

College of Engineering and Physical Sciences

Centro Federal de Educação Tecnológica de Minas Gerais
Universidade Federal de São João del-Rei

Research output: Chapter in Book/Published conference output › Conference publication

4 Citations (Scopus)

90 Downloads (Pure)

Abstract

In this work the allocation of Roadside Units (RSUs) in a V2I network is modeled as a Maximum Coverage Problem. The main objective is to maximize the number of distinct vehicles contacting the infrastructure. Two different approaches are presented to solve the problem. The first one is an ILP model that can found optimal solutions or give sharp upper and lower bounds for the problem. The second one is a GRASP-based heuristic that can found close-to-optimal solutions. The GRASP-based heuristic is compared with a previous work achieving better results. Furthermore, a new metric to measure the efficiency of a Deployment strategy is presented.

Original language	English
Title of host publication	Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016
Editors	Sema Oktug, Mehmet Ulema, Cicek Cavdar, et al
Publisher	IEEE
Pages	1187-1192
Number of pages	6
ISBN (Electronic)	978-1-5090-0223-8
DOIs	https://doi.org/10.1109/NOMS.2016.7502985
Publication status	Published - 30 Jun 2016
Event	2016 IEEE/IFIP Network Operations and Management Symposium - Istanbul, Turkey Duration: 25 Apr 2016 → 29 Apr 2016

Publication series

Name
ISSN (Print)	2374-9709

Symposium

Symposium	2016 IEEE/IFIP Network Operations and Management Symposium
Abbreviated title	NOMS 2016
Country/Territory	Turkey
City	Istanbul
Period	25/04/16 → 29/04/16

Bibliographical note

© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Keywords

deployment strategies
GRASP heuristic
ILP model
vehicular networks

Access to Document

10.1109/NOMS.2016.7502985

GRASP-based heuristic for allocating the roadside infrastructure
© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Accepted author manuscript, 623 KB

Cite this

Sarubbi, J. F. M., Cravieé de A. Vieira, D., Wanner, E. F., & Silva, C. M. (2016). A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities. In S. Oktug, M. Ulema, C. Cavdar, & et al (Eds.), Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016 (pp. 1187-1192). IEEE. https://doi.org/10.1109/NOMS.2016.7502985

Sarubbi, João F. Machry ; Cravieé de A. Vieira, Daniel ; Wanner, Elizabeth F. et al. / A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities. Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016. editor / Sema Oktug ; Mehmet Ulema ; Cicek Cavdar ; et al. IEEE, 2016. pp. 1187-1192

@inproceedings{b027cf64a60048018ff4c621e79ff5f4,

title = "A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities",

abstract = "In this work the allocation of Roadside Units (RSUs) in a V2I network is modeled as a Maximum Coverage Problem. The main objective is to maximize the number of distinct vehicles contacting the infrastructure. Two different approaches are presented to solve the problem. The first one is an ILP model that can found optimal solutions or give sharp upper and lower bounds for the problem. The second one is a GRASP-based heuristic that can found close-to-optimal solutions. The GRASP-based heuristic is compared with a previous work achieving better results. Furthermore, a new metric to measure the efficiency of a Deployment strategy is presented.",

keywords = "deployment strategies, GRASP heuristic, ILP model, vehicular networks",

author = "Sarubbi, \{Jo{\~a}o F. Machry\} and \{Cravie{\'e} de A. Vieira\}, Daniel and Wanner, \{Elizabeth F.\} and Silva, \{Cristiano M.\}",

note = "{\textcopyright} 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.; 2016 IEEE/IFIP Network Operations and Management Symposium, NOMS 2016 ; Conference date: 25-04-2016 Through 29-04-2016",

year = "2016",

month = jun,

day = "30",

doi = "10.1109/NOMS.2016.7502985",

language = "English",

publisher = "IEEE",

pages = "1187--1192",

editor = "Sema Oktug and Mehmet Ulema and Cicek Cavdar and \{et al\}",

booktitle = "Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016",

address = "United States",

}

Sarubbi, JFM, Cravieé de A. Vieira, D, Wanner, EF & Silva, CM 2016, A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities. in S Oktug, M Ulema, C Cavdar & et al (eds), Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016. IEEE, pp. 1187-1192, 2016 IEEE/IFIP Network Operations and Management Symposium, Istanbul, Turkey, 25/04/16. https://doi.org/10.1109/NOMS.2016.7502985

A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities. / Sarubbi, João F. Machry; Cravieé de A. Vieira, Daniel; Wanner, Elizabeth F. et al.
Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016. ed. / Sema Oktug; Mehmet Ulema; Cicek Cavdar; et al. IEEE, 2016. p. 1187-1192.

Research output: Chapter in Book/Published conference output › Conference publication

TY - GEN

T1 - A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities

AU - Sarubbi, João F. Machry

AU - Cravieé de A. Vieira, Daniel

AU - Wanner, Elizabeth F.

AU - Silva, Cristiano M.

N1 - © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

PY - 2016/6/30

Y1 - 2016/6/30

N2 - In this work the allocation of Roadside Units (RSUs) in a V2I network is modeled as a Maximum Coverage Problem. The main objective is to maximize the number of distinct vehicles contacting the infrastructure. Two different approaches are presented to solve the problem. The first one is an ILP model that can found optimal solutions or give sharp upper and lower bounds for the problem. The second one is a GRASP-based heuristic that can found close-to-optimal solutions. The GRASP-based heuristic is compared with a previous work achieving better results. Furthermore, a new metric to measure the efficiency of a Deployment strategy is presented.

AB - In this work the allocation of Roadside Units (RSUs) in a V2I network is modeled as a Maximum Coverage Problem. The main objective is to maximize the number of distinct vehicles contacting the infrastructure. Two different approaches are presented to solve the problem. The first one is an ILP model that can found optimal solutions or give sharp upper and lower bounds for the problem. The second one is a GRASP-based heuristic that can found close-to-optimal solutions. The GRASP-based heuristic is compared with a previous work achieving better results. Furthermore, a new metric to measure the efficiency of a Deployment strategy is presented.

KW - deployment strategies

KW - GRASP heuristic

KW - ILP model

KW - vehicular networks

UR - http://ieeexplore.ieee.org/document/7502985/

UR - https://www.scopus.com/pages/publications/84979783766

U2 - 10.1109/NOMS.2016.7502985

DO - 10.1109/NOMS.2016.7502985

M3 - Conference publication

AN - SCOPUS:84979783766

SP - 1187

EP - 1192

BT - Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016

A2 - Oktug, Sema

A2 - Ulema, Mehmet

A2 - Cavdar, Cicek

A2 - et al,

PB - IEEE

T2 - 2016 IEEE/IFIP Network Operations and Management Symposium

Y2 - 25 April 2016 through 29 April 2016

ER -

Sarubbi JFM, Cravieé de A. Vieira D, Wanner EF, Silva CM. A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities. In Oktug S, Ulema M, Cavdar C, et al, editors, Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium 2016. IEEE. 2016. p. 1187-1192 doi: 10.1109/NOMS.2016.7502985

A GRASP-based heuristic for allocating the roadside infrastructure maximizing the number of distinct vehicles experiencing contact opportunities

Abstract

Publication series

Symposium

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem

Cite this