Do Lógico ao Abstrato: A Ciência no Cotidiano
23 a 28 de outubro de 2017
Trabalho 7648
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Ciência da Computação |
| Setor | Departamento de Informática |
| Bolsa | FAPEMIG |
| Conclusão de bolsa | Sim |
| Apoio financeiro | FAPEMIG |
| Primeiro autor | Marcos Valério de Carvalho Loures |
| Orientador | ANDRE GUSTAVO DOS SANTOS |
| Título | Métodos exatos e heurísticos para problemas multicomponentes: covering e scheduling. |
| Resumo | Definir as rotas policiais em uma cidade é algo difícil. Para garantir a melhor segurança dos moradores, é desejável que as rotas cubram de forma eficiente toda a área da cidade. Entretanto, geralmente não há unidades nem viaturas policiais em número suficiente, o que torna inevitável uma cobertura apenas parcial da cidade. Neste caso, tal cobertura parcial deve preferencialmente cobrir regiões de maior periculosidade. A pesquisa realizada foca em resolver este problema, ou seja, dados um mapa com os valores de periculosidade de cada rua, a quantidade de viaturas policiais disponíveis e a distância máxima de cada rota, desejamos achar a melhor combinação de rotas de viaturas policiais de modo a garantir a máxima segurança dos moradores, lançando mão de heurísticas e modelos matemáticos de programação linear. Alguns trabalhos na literatura lidam com alocação de unidades policiais estáticas, como Curtin et al (2010), Mendes et al (2014) e Mendes e Santos (2015). Supõe-se que um policial posicionado em um certo ponto “inibe” crimes em um certo raio de distância. Dado que o contingente policial não é suficiente para cobrir toda uma cidade, é costume usar unidades móveis, ou seja, veículos que fazem ronda seguindo rotas pré-determinadas ou dinâmicas. Assim como unidades estáticas, os veículos são capazes de inibir crimes nas proximidades de sua rota. Alguns trabalhos usam o conceito de hot spot, que são regiões com alto índice de ocorrências criminais (Keskin et al, 2012; Chawathe, 2007). A ideia é visitar periodicamente esses hot spots. Outros buscam traçar rotas sem utilizar estes conceitos, como Vasconcelos (2008). Em nosso trabalho não usamos hot spots, assumimos que qualquer trecho de rua é um lugar potencial para ocorrência de um crime. Entretanto, cada trecho possui um valor associado, que é maior quanto maior for a chance de haver uma ocorrência. Por exempo, locais com histórico de crimes, regiões com agências bancárias, etc. O problema combina componentes de cobertura (covering) com roteamento (routing) e agendamento/programação (scheduling). O roteamento deve ser feito de modo a maximizar a cobertura. E uma sequência de rotas diferentes deve fazer parte da agenda de um policial. Sendo este um trabalho inicial, o foco foi na combinação de cobertura e roteamento. As soluções encontradas serão entrada da etapa seguinte, a ser desenvolvida, que é a programação diária ou horária de rotas. |
| Palavras-chave | covering, scheduling, roteamento |
| Forma de apresentação..... | Oral, Painel |