Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/ESBF-BA8NBU| Type: | Dissertação de Mestrado |
| Title: | Gamma Deployment Problem in Grids: Complexity and a new Integer Linear Programming Formulation |
| Authors: | Marcelo Fonseca Faraj |
| First Advisor: | Sebastián Alberto Urrutia |
| First Co-advisor: | João Fernando Machry Sarubbi |
| First Referee: | Cristiano Maciel da Silva |
| Second Referee: | Geraldo Robson Mateus |
| Third Referee: | João Fernando Machry Sarubbi |
| Abstract: | Redes veiculares constituem um dos componentes mais essenciais dos sistemas inteligentes de transporte. Elas possuem um potencial para facilitar a gestão de tráfego, reduzir taxas de acidente de trânsito e proporcionar outras soluções para a construção de cidades inteligentes. Um dos principais desafios associados a redes veiculares é a escolha das melhores localizações para instalação das infraestruturas de comunicação, as quais são conhecidas como roadside units ou RSUs. Esta dissertação lida com o Problema da Deposição Gamma, o qual consiste em depositar o mínimo número de roadside units em uma rede rodoviária de modo a cumprir a métrica Deposição Gamma. De acordo com esta métrica, uma porcentagem mínima dos veículos transitando pela rede rodoviária devem estar cobertos, sendo que um veículo é considerado coberto caso encontre ao menos uma roadside unit a cada intervalo pré-determinado de sua viagem. Nesta dissertação, propõe-se um tratamento formal baseado em teoria dos grafos e apresenta-se uma prova de que a versão de decisão do Problema da Deposição Gamma em Grades pertence à classe de complexidade NP-completo. Em seguida, expõe-se um problema associado ao modelo multifluxo de programação linear inteira presente na literatura e propõe-se uma pequena correção. Também se introduz um novo modelo de programação linear inteira baseado em cobertura de conjuntos e demonstra-se que o politopo associado a sua relaxação linear está contido no politopo associado à relaxação linear do modelo multifluxo. Por fim, experimentos computacionais com um otimizador comercial mostram que a formulação cobertura de conjuntos se comporta de modo muito superior à formulação multifluxo em termos de gap de relaxação linear e tempo de execução. |
| Abstract: | Vehicular ad hoc networks are one of the most significant components of intelligent transportation systems. They have the potential to ease traffic management, lower accident rates and provide other solutions to smart cities. One of the main challenges on vehicular ad hoc networks is to choose the best places to deploy roadside units. This thesis deals with the Gamma Deployment Problem, which consists of deploying the minimum number of roadside units on a road network meeting the Gamma Deployment metric. Within this metric, at least a given fraction of vehicles passing in the road network must be covered, i.e they should meet at least one roadside unit each predetermined time interval. In this thesis, I propose a formal treatment based on graph theoretical concepts and provide a proof that the decision version of the Gamma Deployment Problem in Grids is NP-complete. In addition, I expose an issue with the multi-flow integer linear programming formulation present in literature and propose a slight correction for it. I also introduce a new integer linear programming formulation based on set covering and provide a proof that the polytope associated with its linear programming relaxation is contained in the polytope associated with the linear programming relaxation of the multi-flow formulation. Finally, computational experiments with a commercial optimizer show that the set covering formulation widely outperforms the multi-flow formulation regarding linear programming relaxation gap and running time. |
| Subject: | Complexidade computacional Problemas da deposição gamma Redes veiculares Computação Programação linear inteira Heurística |
| language: | Inglês |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/ESBF-BA8NBU |
| Issue Date: | 15-Feb-2019 |
| Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| marcelofaraj.pdf | 1.4 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.