APURROS: Gerenciamento de emergências

Prévia do material em texto

RESUMO 
Apresentamos um estudo sobre problemas de roteamento de 
veículos com interesse especial em investigar o planejamento 
logístico do atendimento da saúde e segurança públicas em 
Coxim - MS, na qual serão propostos modelos matemáticos 
para a solução do problema, com o objetivo de otimizar o 
tempo médio do atendimento desses serviços na cidade. Foram 
feitas simulações implementadas em AMPL e resolvidas com 
CPLEX. O modelo é baseado nos problemas do Caixeiro 
Viajante (PCV), no caso do serviço de segurança da Polícia 
Militar, e Roteamento de Veículos (PRV), no caso do serviço 
de saúde. O PRV consiste no atendimento de um conjunto de 
consumidores por intermédio de uma frota de veículos, que 
partem de um ou mais pontos denominados depósitos. A 
restrição presente no PRV é que cada veículo v possui uma 
capacidade Cv e o somatório de todas as demandas dos 
consumidores atendidos por um veículo v não pode ultrapassar 
Cv. Já o PCV tenta determinar a menor rota para percorrer uma 
série de cidades, visitando uma única vez cada uma delas, 
retornando à cidade de origem. Os modelos construídos foram 
testados e sua performance computacional é mais que 
satisfatória, pois, em apenas alguns segundos, soluções são 
encontradas. O aplicativo surge então como um meio de 
acesso do usuário ao modelo matemático de forma prática e 
intuitiva, para um acesso rápido e atendimento eficaz. 
I. INTRODUÇÃO 
Conforme Silva (2012), segundo o Ministério da Saúde, a 
urgência e a emergência no Brasil são percebidas como setores 
deficientes do sistema de saúde e se configuram como áreas 
problemáticas do Sistema Único de Saúde (SUS), no qual as 
diretrizes de descentralização, regionalização e hierarquização 
estão pouco implementadas. Nesse paradigma, surgiu a 
Política Nacional de Atenção às Urgências e, 
consequentemente, o Serviço de Atendimento Móvel de 
Urgência (SAMU), com o intuito de induzir a organização da 
rede de atenção e estruturação dos serviços, além de constituir 
importante observatório do sistema de saúde brasileiro, sendo 
imprescindível a sua discussão e análise com a finalidade de 
propor soluções frente à problemática. 
É de conhecimento geral que com o passar do tempo certos 
procedimentos ou produtos precisam evoluir para atender às 
necessidades da sociedade, tal fato não se difere no que diz 
respeito ao atendimento público, que, em muitas áreas, 
mostra-se ultrapassado e carente de inovações, como pode ser 
percebido no atual sistema de atendimento do saúde e 
segurança pública móvel nacional, que é o mesmo há anos, e 
vêm mostrando certas falhas quanto à sua metodologia. 
Em relação a tais falhas, não há um número concreto de 
mortes relacionadas à demora de atendimento ao paciente, mas 
se tem conhecimento de que é um caso frequente, e que, em 
alguns casos, a ambulância nem chega a ser encaminhada ao 
paciente, por conta do pedido ser confundido com um trote, ou 
ser mal avaliado, o que não é um absurdo, tendo em vista que, 
de cerca de 8 mil ligações recebidas diariamente pelo Centro 
Integrado de Operações de Segurança Pública (CIOSP), 85 a 
cada 100 delas, são trotes [ARAÚJO, RICARDO; TRIBUNA 
DO NORTE, 2011]. 
Em ocorrências policiais o que acontece não é muito 
diferente, com aparelhos desatualizados, já foi constatado por 
um cidadão uma demora de cinco minutos para ser atendido 
após dez tentativas malsucedidas. Além do tempo da ligação 
para a obtenção de informações do local e situação, a polícia 
ainda leva de quinze a vinte minutos para chegar ao local. 
Totalizando uma demora de, em alguns casos como esse, trinta 
minutos, onde, na maioria dos casos, pode já ser tarde demais 
[G1, 2011]. 
No entanto, essa demora nem sempre é provocada pela 
lentidão ao atendimento da chamada, mas sim, pela demora na 
obtenção de informações e um trânsito muito movimentado, já 
que esses departamentos não usufruem de algum software que 
aponte um caminho mais curto para a chegada ao local 
indicado, ou de um software que indique qual viatura está 
mais próxima desse local e que, consequentemente, levaria 
menos tempo para chegar até lá, ou mesmo, informações que 
os conduzam para um caminho com menos tráfego. 
Tais problemas podem ser solucionados através do uso de 
áreas específicas da Matemática Aplicada voltadas ao objetivo 
de resolver problemas do mundo real, como propõem os 
Problemas de Programação Linear (PPL), uma subárea da 
Pesquisa Operacional (PO), com a qual, através de modelos 
matemáticos planejados minuciosamente, é possível se obter 
uma otimização para as falhas encontradas em problemas do 
cotidiano. 
Os modelos matemáticos nada mais são do que um conjunto 
de equações e inequações que, quando em conjunto, otimizam, 
APURROS: Gerenciamento de emergências 
Eitor Bernardes de Paiva, Mariana Dias Nogueira, Thiago Ferronatto, Fernando Silveira Alves (Orientador), 
Ricardo Tavares Antunes de Oliveira (Coorientador) 
Instituto Federal de Educação, Ciência e Tecnologia de Mato Grosso do Sul, Coxim - MS 
 
seja minimizando ou maximizando, um resultado, de forma a 
extrair o melhor aproveitamento dos mais simples aos mais 
complexos problemas rotineiros, como analisar a melhor 
proposta de compra possível dentre uma variedade de opções 
de produtos ou ainda trabalhar na organização dos períodos 
gastos com variadas atividades, de modo a otimizar o uso do 
tempo disponível, como a problemática discutida no presente 
trabalho. 
O Art. 37 da Constituição Federal diz que: A administração 
pública direta e indireta de qualquer dos Poderes da União, 
dos Estados, do Distrito Federal e dos Municípios obedecerá 
aos princípios de legalidade, impessoalidade, moralidade, 
publicidade e eficiência. A presente proposta de pesquisa está 
relacionada com a eficiência de um serviço público, no caso o 
atendimento a emergências oferecido pelo SAMU, Policia 
Militar e os departamentos de Combate a Incêndios. 
Dado o problema, iniciaram-se as buscas e pesquisas por 
possíveis soluções no que pode ser feito para melhorar a forma 
de atendimento pelo SAMU, Polícia Militar e Combate a 
Incêndios. Sendo assim, o presente trabalho propõe um estudo 
para o planejamento logístico para otimização do atendimento 
de saúde e segurança pública móvel em Coxim - MS, com o 
objetivo de propor a solução de tal problema através de um 
modelo matemático, que terá sua eficiência testada por meio 
na implementação em AMPL na IDE IBM CPLEX. 
Como já citado anteriormente, a proposta do presente 
trabalho é aplicar um mecanismo que possa definir rotas de 
trânsito mais eficientes, para que assim o caminho possa ser 
percorrido pela viatura. No entanto, sua aplicação depende de 
um meio acessível em de fácil manipulação. De tal modo, com 
embasamento em experiências e pesquisas bibliográficas 
anteriores foi decidido que o melhor meio de resolver essa 
problemática, seria o desenvolvimento de um aplicativo. 
Sendo assim, o presente trabalho propõe também o 
desenvolvimento de uma aplicação para chamadas de 
emergências para o uso em sociedade. 
Vale ressaltar ainda que, visando atender a maior camada da 
população, o aplicativo será desenvolvido para a plataforma 
Android, que, de acordo com Dubey e Misra (2016) é o 
Sistema Operacional (SO) usado em cerca de 64% dos 
smartphones atualmente no mundo, sendo a plataforma 
ascendente no momento, superando as demais em diversos 
aspectos, além da quantidade de usuários. Para o 
desenvolvimento será utilizado o Android Studio. 
II. OBJETIVOS 
A. GERAIS 
Planejar de forma eficaz o atendimento de cidadãos em 
qualquer tipo de ocorrência de caráter de urgência ou 
emergência, buscando além de uma obtenção rápida e prática 
de informações minimizando trotes e demora, prover o melhor 
caminho a ser percorrido pela viatura no melhor tempo 
possível, para assim atender a chamada de modo mais simples 
e efetivo, gerando mais segurançaà população de forma geral. 
B. ESPECÍFICOS 
Visando atingir o objetivo geral, alguns objetivos 
específicos são requeridos, entre eles: 
 Replanejar a forma de atendimento dos serviços de 
segurança pública, bem como o atendimento de urgência 
móvel e combate a incêndios; 
 Criar um aplicativo móvel de interface intuitiva com 
pré-cadastro de informações pessoais; 
 Agilizar o atendimento ao cidadão e garantir sua 
segurança e bem-estar; 
 Reduzir o índice de mortes e problemas por atraso no 
atendimento; 
 Impedir que os cidadãos percam seus patrimônios em 
decorrência de incêndio ou assalto; 
 Diminuir o índice de ações criminosas bem-sucedidas 
por conta de atraso no atendimento; 
 Adiantar o atendimento dos prestadores de serviço 
com o pré-cadastro; 
 Conter o índice de trotes feitos aos serviços; 
 Promover a eficiência no atendimento de saúde e 
segurança pública móvel da população coxinense. 
III. FUNDAMENTAÇÃO TEÓRICA 
Para otimizar o roteamento de veículos em uma 
determinada área é necessário conhecer e trabalhar com os 
métodos já existentes inicialmente, para então se avaliar qual é 
o mais eficiente para o problema, para que o processo de 
validação da otimização seja alcançado mais facilmente. De 
tal modo, foi realizada uma revisão bibliográfica com os 
principais casos conhecidos na otimização matemática por 
meio da Programação Linear (PL) no campo de Pesquisa 
Operacional (PO), como o Problema do Caixeiro Viajante e 
sua variação: Problema de Roteamento de Veículos, por conta 
de sua eficiência recorrente na área. 
A. A ESTRUTURA DE UM MODELO MATEMÁTICO 
Conforme Moretti (2010), um modelo matemático é uma 
representação ou interpretação simplificada da realidade, ou 
uma interpretação de um fragmento de um sistema, segundo 
uma estrutura de conceitos mentais ou experimentais. 
Portanto, para que o modelo consiga representar a realidade 
com eficiência, é recomendado seguir as seguintes 
recomendações: 
 É necessário verificar se o decisor tem autoridade para 
escolher o valor numérico do item, se for o caso, esta será uma 
variável de decisão; 
 
 É preciso ser bem claro ao se declarar as unidades 
utilizadas (quantidade, moeda, etc.) às variáveis de decisão; 
 Por fim, é de extrema importância que as variáveis de 
decisão não sejam confundidas com parâmetro do problema. 
1) FUNÇÃO OBJETIVO 
Ainda conforme Moretti (2010), é a representação 
matemática do objetivo a ser atendido pelo modelo. A função 
objetivo mede a eficiência de cada solução possível. Pode-se 
citar como exemplos, o custo ou tempo de produção; o custo 
de transporte na distribuição; o nível de atendimento dos 
pedidos; a perda de material ou a geração de estoques 
intermediários. 
2) RESTRIÇÕES 
Segundo Martins (2011), as restrições estabelecem 
condicionantes entre as variáveis de decisão e a dinâmica do 
sistema, indicando as limitações físicas, disponibilidades de 
material e as necessidades a serem atendidas pelo processo a 
ser modelado. Por exemplo, o tempo disponível de operação 
das máquinas a serem sequenciadas; o número de caminhões 
disponíveis a serem utilizados no plano de distribuição; as 
características dos cortes possíveis, etc. 
3) FORMA GERAL DE UM MODELO 
Todo modelo deve possuir os itens mencionados 
anteriormente. 
4) O CPLEX 
Para resolver estes modelos matemáticos, utiliza-se um 
algoritmo chamado Simplex, em caso de problemas de nível 
mais simples, e o AMPL para casos mais complexos, que 
analisa todas as possíveis soluções e escolhe a melhor 
possível, isto é, a solução ótima. Porém, analisar todas as 
soluções é um tanto maçante, fazendo com que seja necessário 
o uso de processamento computacional. 
Um programa que utiliza de uma biblioteca de métodos de 
solução de PPLs é o IBM CPLEX, este que possui uma 
sintaxe simples e intuitiva, fazendo com que seja possível 
solucionar até mesmo modelos matemáticos de programação 
não-linear. Portanto, esta foi a escolha perfeita para realizar os 
testes necessários a respeito do modelo utilizado no trabalho. 
B. O PROBLEMA DO CAIXEIRO VIAJANTE (PCV) 
Segundo Costa (2008), o Problema do Caixeiro Viajante 
(PCV) é um dos problemas mais famosos de Otimização 
Combinatória para testar a eficiência de metaheurísticas. A 
origem deste problema não é certa, no entanto, segundo 
Goldbarg e Luna (2005), a sua criação é creditada a William 
Rowan Hamilton, criador de um sistema de álgebra não 
comutativa – o Cálculo Icosiano – que pode ser interpretado 
em termos de caminhos sobre um grafo descrito por um 
dodecaedro regular. Hamilton, em 1859, construiu um quebra-
cabeças ao qual chamou de Jogo Icosiano (Figura 1). Neste 
jogo, cada um dos vértices (ou nós) do dodecaedro possuía 
escrito o nome de uma importante cidade e o desafio que se 
era dado ao jogador era o de encontrar um caminho, 
percorrendo as arestas do dodecaedro de modo a passar 
exatamente uma vez por cada uma das cidades e regressar ao 
ponto de partida. 
 
Figura 1 - Jogo Icosiano. Fonte: os autores. 
 
Apenas em 1930 o PCV começa a tomar o rumo que tem 
hoje, quando Karl Menger tenta resolver o problema através 
de um algoritmo que o resolve por força bruta. A sua 
nomeação, no entanto, se deve a Hassler Whitney, que passa a 
chamar o problema de Travelling Salesman Problem, em 
português, Problema do Caixeiro Viajante (PCV). 
Mesmo parecendo um problema simples, o PCV é estudado 
por diversos profissionais da área. Ele possui inúmeras 
aplicações possíveis, desde planejamento e logística até o 
desenvolvimento de microchips, como cita Freitas (2009). 
A solução mais comum encontrada na literatura para a 
solução desses tipos de problema é o uso de algoritmos para 
encontrar soluções exatas, que podem ser consideravelmente 
rápidos para pequenos problemas, ou mesmo heurísticas, que, 
embora apresentem soluções satisfatórias, não são vistas como 
ótimas. 
Conforme Freitas (2009), o PCV se mostra ser NP-difícil1, 
até mesmo quando as cidades estão posicionadas em um plano 
com distâncias Euclidianas (que podem ser provadas pelo 
teorema de Pitágoras) ou para outros casos mais restritivos. 
Eliminar a restrição de que cada cidade seja visitada apenas 
uma única vez, não torna o problema mais fácil, pois a melhor 
rota continuaria sendo a que visitaria cada cidade apenas uma 
vez desde que pela desigualdade triangular, o que diminuiria a 
rota, no entanto, seria um atalho que pula a cidade já visitada, 
conforme propõe Applegate (2006 apud Freitas, 2009). 
Comumente, se a medida de distância é métrica e simétrica, 
o problema se torna um problema APX-Completo, conforme 
Lawler (1985, apud Freitas, 2009), isto é, podem se conseguir 
boas aproximações de solução através do uso de heurísticas. 
 
1 Não-Polinomial - Difícil, ou seja, não existe um método matemático 
que encontre a solução ótima em um tempo polinomial. 
 
Há também o problema de maximização, que, ao contrário do 
que se ouve falar todas as vezes, é um problema que busca 
encontrar a rota mais longa possível. 
O primeiro pensamento de muitos para a solução do 
problema é uma das mais óbvias: tentar todas as permutações, 
o que caracteriza o método de força bruta, isto é, tentar todas 
as combinações disponíveis até que a mais eficiente seja 
encontrada. A ordem de complexidade deste tipo de 
abordagem é denominada O(n!), isto é, o fatorial do número 
de cidades, o que pode tornar esta solução inviável mesmo 
para 20 cidades, sendo extremamente longa e maçante para 
números maiores, como 100, tornando o método ineficiente. 
Uma solução baseada em programação dinâmica pode resolver 
o problema em um tempo O(n2 ∗ 2n), conforme Bellman 
(1962), no entanto a solução de programação dinâmica 
necessita de um espaço exponencial, já que são necessários 
métodos de inclusão e exclusão, tornando a solução tambémineficiente. 
Muitas heurísticas e algoritmos de aproximação que dão 
boas soluções já foram desenvolvidos. Métodos mais recentes 
e inovadores podem dar soluções para problemas de até 
milhares e milhões de cidades em um tempo razoavelmente 
curto, além de possuir uma grande probabilidade de estarem 
há apenas 3% próximas do ótimo, o que, para a matemática, é 
o mais próximo de uma solução perfeita possível. Existem 
ainda as heurísticas construtivas, como o algoritmo do vizinho 
mais próximo, uma solução conhecida como “solução gulosa”, 
onde o caixeiro decide a cidade mais próxima – ainda não 
visitada – para o seu próximo movimento. Esse algoritmo 
funciona de uma forma satisfatoriamente rápida e eficaz. Para 
um número n de cidades distribuídas em um plano de maneira 
aleatória, o algoritmo leva a uma solução cerca de 25% maior 
do que a melhor rota em média (Rosenkrantz, 1977 apud 
Freitas, 2009). Existem ainda diversos outros meios de 
solução, os citados anteriormente, no entanto, são os mais 
comuns. 
C. O PROBLEMA DE ROTEAMENTO DE VEÍCULOS (PRV) 
Conforme Alves (2015), o desenvolvimento de métodos 
eficazes que têm o objetivo de planejar e desenhar rotas de 
veículos é uma área interdisciplinar de pesquisa bastante ativa. 
Nas últimas décadas, novos problemas e métodos têm sido 
propostos na literatura. A atenção dada à estes problemas é, 
em grande parte, motivada pela necessidade constante de 
redução dos gastos nos processos de logística na entrega de 
produtos ou na prestação de serviços à população. 
O Problema de Roteamento de Veículos (PRV) é uma 
extensão natural do Problema do Caixeiro Viajante (PCV), 
quando acrescido de diversas restrições. Como o PRV pode ser 
reduzido a um PCV, ele pertence à classe NP-Difícil. O PRV 
clássico consiste em encontrar a melhor maneira de atender a 
um conjunto de clientes C, cada cliente com uma demanda qi 
por um serviço (ou produto) e, um depósito com veículos de 
capacidade Qi, de maneira que o somatório de todas as 
demandas dos clientes não ultrapasse a capacidade Q dos 
veículos. Os modelos e algoritmos propostos para a solução 
desses problemas, podem ser aplicados de forma eficaz não 
somente a problemas destinados à entrega e coleta de bens, 
mas para a solução de diversos problemas do mundo real que 
derivam em sistemas de transportes. As aplicações mais típicas 
desse tipo de problema são: 
 Coleta de lixo; 
 Limpeza de ruas; 
 Planejamento de transporte escolar; 
 Sistemas dial-a-ride; 
 Transporte de pessoas Portadoras de Necessidades 
Específicas (PNE); 
 Roteamento de vendedores e unidades de manutenção. 
A distribuição de bens se refere ao serviço feito, em um 
determinado período de tempo, para um conjunto de clientes 
por um conjunto de veículos que são operados por um 
conjunto de operadores (motoristas para o caso de caminhões, 
ônibus, etc.), a qual é executado em uma rede de estradas ou 
caminhos convenientes. Em particular, a solução de um PRV 
visa a determinação de um conjunto de rotas (caminhos, 
linhas, etc.), cada uma realizada por um único veículo 
iniciando e terminando em seu próprio depósito, de maneira 
que todos os requisitos de seus clientes sejam cumpridos e 
todas as limitações operacionais sejam satisfeitas e o custo de 
transporte seja minimizado. Descrevemos as características 
típicas dos problemas de roteamento e programação 
considerando seus componentes principais (rede de estradas, 
veículos e motoristas), as principais restrições a serem 
impostas na construção das rotas e os possíveis objetivos a 
serem minimizados. 
A rede de estradas utilizada para o transporte de 
mercadorias geralmente é descrita através de um grafo – 
conjunto cujos elementos são unidos por arcos –, como 
mostrado na Figura 2, no qual os arcos (linhas) representam 
partes da estrada e os vértices (bolinhas) representam os 
cruzamentos, depósitos e localização dos clientes. Os arcos e, 
consequentemente, os grafos correspondentes podem ser 
direcionados ou não, ou seja, eles podem ser percorridos por 
apenas uma direção (vias de único sentido, geralmente de 
cidades ou rodovias) ou em ambas as direções, (vias de mão 
dupla). A cada arco é atribuído um custo que normalmente 
representa a distância a ser percorrida ou o tempo de percurso, 
que irá depender do tipo de veículo usado ou o período em que 
o percurso acontece. Podendo ser em horários de picos e com 
grande congestionamento de veículos. 
 
 
Figura 2 - Exemplo de grafo. Fonte: os autores. 
 
Como observado em Toth e Vigo (2002), normalmente os 
clientes são caracterizados da seguinte forma: 
 Vértice do grafo da rede de estradas em que um cliente 
está localizado; 
 Quantidade de bens (demanda), possivelmente de 
diferentes tipos que devem ser entregues ou coletados nos 
clientes; 
 Períodos do dia (janela de tempo) em que um cliente 
pode ser atendido, possivelmente por motivos em que o cliente 
se encontra aberto ou por limitações de trânsito. Por exemplo, 
nos centros de algumas cidades brasileiras só podem ocorrer 
carga e descarga de mercadorias das 18:00 às 06:00; 
 Tempo necessário para carga e descarga de 
mercadorias que depende do tipo de veículo; 
 Subconjunto de veículos disponíveis que podem ser 
destinados ao cliente, por razão de limitações do acesso ou 
restrições do cliente para carga e descarga. 
Algumas vezes não há possibilidade de atender os clientes. 
Nestes casos as quantidades a serem entregues ou coletadas 
podem ser reduzidas ou não, podendo ocorrer a possibilidade 
de não atendimento de um grupo de clientes. Deste modo, 
podem ser atribuídos prioridades ou penalizações para a falta 
total ou parcial do serviço. 
Os percursos realizados pelos veículos para os clientes 
serem atendidos começam e terminam em um ou mais 
depósitos, localizados nos vértices do grafo que representam 
as estradas. Cada depósito é caracterizado pelo número, tipo 
de veículos e quantidade total de bens que suporta. Em 
algumas aplicações do mundo real os clientes são divididos 
entre os depósitos, e os veículos, por sua vez, devem retornar 
ao depósito de partida ao fim de cada percurso. Quando isso 
ocorre, o PRV pode ser decomposto em problemas 
independentes, cada um associado a um depósito distinto. 
Por outro lado, o transporte de mercadorias é realizado 
usando uma frota de veículos com- postos por tamanhos fixos 
ou definidos de acordo com a exigências de cada cliente. 
Normalmente os veículos são caracterizados como segue: 
 Depósito de saída do veículo, com a possibilidade de 
que o depósito ao final do percurso seja diferente do depósito 
de partida; 
 Capacidade do veículo expressa pela quantidade 
máxima, ou o volume, ou o número de caixas que o veículo 
pode transportar; 
 Possibilidade de o veículo ser dividido em 
compartimentos, cada um caracterizado pela sua capacidade e 
tipo de produtos que podem ser transportados; 
 Dispositivos disponíveis para a operação de carga de 
descarga, por exemplo máquinas empilhadeiras ou material 
humano; 
 Subconjunto de arcos da estrada que podem ser 
percorridos pelos veículos; 
 Custo associado à utilização do veículo que podem ser 
por unidade de distância, por unidade de tempo, por rota etc. 
Os operadores dos veículos devem satisfazer várias 
condições ajustadas por contratos sindicais ou normas das 
empresas como período máximo de trabalho diário, número de 
intervalos durante o serviço, duração máxima de períodos de 
condução, horas extras máxima permitida por dia, etc. Existem 
também restrições impostas aos condutores associados aos 
veículos correspondentes. 
As vias devem satisfazer várias limitações operacionais que 
dependem da natureza dos veículos e dos bens transportados, 
refletindo na qualidade do serviço executado e as 
características de cada cliente. Algumas restrições 
operacionais são: 
 Ao longo da rota a demanda de cargado veículo não 
pode ser maior que a capacidade do mesmo; 
 Os clientes atendidos em uma rota podem exigir a 
entrega, coleta ou ambos de bens; 
 Os clientes podem ser atendidos somente dentro de sua 
janela de tempo ou dentro do período de trabalho dos 
operadores. 
Pode ser imposta uma ordem em que os clientes devem ser 
atendidos na rota, esse tipo de restrição determina que um 
cliente deve ser atendido antes ou depois de um conjunto de 
clientes da mesma rota, este tipo de situação é conhecido 
como o problema da coleta e entrega, em que em uma mesma 
rota um mesmo veículo deve coletar mercadorias e entregar 
em outro cliente, algo como prioridade. 
Outro tipo de restrição de procedência impõe que clientes 
de diferentes tipos são atendidos na mesma rota. Neste caso, 
os clientes têm ordem fixa de atendimento, essa situação 
aparece para os PRVs com Backhauls, que é um problema de 
coleta e entrega, mas pela dificuldade de organização dos 
produtos nos veículos, esse problema restringe-se as entregas 
que devem ser feitas antes das coletas. 
A avaliação do custo total do transporte e a verificação das 
restrições operacionais requerem um conhecimento do custo e 
do tempo de viagem entre cada par de clientes e entre o 
depósito e os clientes. Para isso, o grafo da estrada original, 
que as vezes é muito escasso, é geralmente transformado em 
 
um grafo completo, cujo os vértices do grafo representam os 
clientes e os depósitos. 
Para cada par de vértices i e j do grafo completo é associado 
um custo cij ao arco (i,j) do caminho mínimo que liga o vértice 
i ao vértice j. O tempo de percurso tij é associado ao arco (i,j) 
do grafo completo que representa a soma de todos os tempos 
do caminho mais curto que liga o vértice i ao vértice j, ou seja, 
consideramos um grafo completo ao invés de considerar o 
grafo original da estrada, que pode ser um grafo direcionado 
ou não, dependendo das matrizes de custo e tempo de viagem 
correspondentes que podem ser assimétricas ou simétricas 
respectivamente. 
Vários objetivos para os Problemas de Roteamento de 
Veículos podem ser considerados, alguns deles são: 
 Minimizar o custo total do transporte, dependendo da 
distância ou tempo total da rota e custos fixos associados aos 
veículos e seus operadores correspondentes; 
 Minimizar o número de veículos ou operadores para 
atender todos os clientes; 
 Balanceamento das rotas para o tempo de viagem e 
carregamento dos veículos; 
 Minimizar as punições relativas aos clientes não 
atendidos ou atendidos parcialmente. 
É possível ainda considerar uma combinação desses 
objetivos. Em algumas aplicações os veículos podem operar 
em mais de uma rota e por um tempo maior, onde alguns 
percursos podem durar mais de um dia. Algumas vezes temos 
que levar em consideração versões estocásticas do problema 
que dependem de tempos dinâmicos, ou seja, para alguns 
problemas, a priori, há apenas um conhecimento parcial de 
demandas dos clientes, dos custos e do tempo total de viagem. 
Já em alguns casos, não há nenhum conhecimento associado 
aos arcos das redes de estradas. 
D. QUAL SO E PLATAFORMA DE DESENVOLVIMENTO USAR? 
Seguindo a temática de otimização, surgem ainda os 
questionamentos a respeito de qual plataforma de 
desenvolvimento é a mais adequada em um mundo no qual a 
tecnologia se faz cada vez mais presente com um público cada 
vez mais exigente. Para alcançar essa demanda, dispositivos 
móveis vem se tornando cada vez mais populares e comuns na 
vida das pessoas, com sistemas operacionais que realizam 
diversos tipos de atividades pensadas para sua comodidade e 
facilidade de execução, contando com mecanismos simples e 
interfaces intuitivas. 
De acordo com Dubey e Misra (2016), e ainda os site de 
notícias G1 (2017), um dos mais populares sistemas 
operacionais usados pelos dispositivos mobile hodiernamente, 
é o Android, da Google, que, recentemente, ultrapassou até 
mesmo o Windows, que esteve no topo desde 1980, quando 
foi lançado, alcançando marcos de aproximadamente 70% dos 
usuários. 
Com base nesses fatos, conclui-se que a melhor plataforma 
para desenvolver um aplicativo de otimização, como citado na 
Introdução desse trabalho, é a Android, tendo em vista que a 
maior parte da população teria acesso aos serviços. Pensando a 
longo prazo, no entanto, outras plataformas precisarão ser 
exploradas, para atender de fato todo o público. 
1) O ANDROID STUDIO 
Conforme Lecheta (2015), para o desenvolvimento de 
aplicações no Android, o Android SDK é o software mais 
indicado, já que tem um emulador para simular o dispositivo, 
ferramentas utilitárias e uma API (Interface de Programação 
de Aplicações) completa para a linguagem Java, com todas as 
classes necessárias para desenvolver as aplicações. 
Ainda de acordo com Lecheta (2015), a melhor IDE 
(Integrated Development Environment) para desenvolvimento 
no contexto atual é o Android Studio, que apresenta 
diferenciais importantes se comparado ao Eclipse – outra IDE, 
que costumava ser a ferramenta oficial. O Android Studio 
apresenta um editor visual mais fluido e com mais opções, 
templates de projetos para smartphones, tablets, relógios e 
outros, além de diversos outros pontos positivos, como a 
compilação, que é mais avançada. 
E. APLICATIVOS COM MECANISMOS SEMELHANTES 
Embora não existam aplicativos voltados a chamada de 
emergência com a funcionalidade de desenhar rotas como o do 
presente trabalho, existem aplicativos com mecanismos 
semelhantes dedicados a outras atividades, dentre eles podem 
ser citados: Uber, Waze e Google Mapas. 
1) UBER 
Criado em 2009 como uma maneira mais prática de 
comunicação entre pessoas que precisam se locomover e 
motoristas que estão dispostos a oferecer o serviço, o 
aplicativo Uber tem se tornado mais e mais popular, 
funcionando atualmente em centenas de cidades por mais de 
60 países, gerando um patrimônio estimado em 
aproximadamente US$ 50 bilhões. O Uber surgiu de uma 
maneira na qual Christensen, Raynor e McDonald (2016), 
especialistas na área, acreditam ser uma inovação, embora, 
conceitualmente, ele não tenha surgido como algo nunca visto 
antes, como a primeira televisão ou impressora, que criaram 
uma necessidade nunca antes existente de obter tais 
dispositivos, nem como os celulares, onde os compradores dos 
modelos mais atuais tem acesso a mais recursos do que os que 
compram modelos mais antigos. O aplicativo de transporte, 
nada mais, nada menos, fez uso de um serviço já existente e o 
adaptou de maneira a atender as necessidades do mundo 
contemporâneo, existindo em paralelo aos métodos antigos 
como uma alternativa otimizada. 
 
2) WAZE 
Conforme Silva et al. (2013), Sistemas de Detecção 
Participativa (SDP) estão revolucionando a maneira como 
vemos cidades, sociedades e as interações entre pessoas. SDPs 
fornecem uma interface móvel que permite que pessoas com 
smartphones compartilhem dados sobre o ambiente (ou 
contexto) no qual estão inseridas em qualquer momento ou 
lugar. Tais sistemas certamente têm o poder de contribuir com 
o processo de tornar a computação ubíqua uma realidade. 
Considere a grande variedade de SDPs já implementados e 
funcionando em escala global, como o Waze. Cada um desses 
sistemas pode fornecer informações valiosas sobre algum 
aspecto de uma dada cidade ou sociedade em quase tempo 
real, como o tráfego e condições climáticas, festas e festivais 
locais, rebeliões, entre outros. Mais importante, o custo de 
obtenção de tais dados é quase insignificante, já que é 
distribuído entre todas as pessoas que o estão compartilhando. 
Dos SDPs, podem ser derivadas as Redes de Sensores 
Participativos (RSP), onde cada nó na rede consiste em um 
usuário equipado com um dispositivo móvel, enviando dados 
para os web services. 
Assim, podemos ver as RSPs como camadas de detecção de 
uma rede global de detecção que usahumanos no processo 
sensorial. Por exemplo, do Waze podemos obter uma camada 
sobre o tráfego, do Instagram, uma camada contendo fotos de 
lugares, do Foursquare, uma camada sobre as categorias das 
localizações e do Weddar, uma camada sobre as condições 
climáticas. Cada camada é responsável por detectar dados 
relacionados a um certo aspecto, como tráfego ou tempo, de 
uma área específica no globo, como países, cidades ou bairros. 
Aqui, foca-se a análise em uma camada sensorial específica: 
a camada do tráfego. Os dados coletados dessa camada, assim 
como das outras mencionadas acima, têm o potencial de 
transformar a sociedade. Eles permitem o entendimento das 
dinâmicas das cidades e dos padrões de comportamento 
urbanos de seus habitantes, possibilitando decisões mais 
inteligentes. Na verdade, mapas de tráfego em tempo real 
poderiam informar mais que as condições do fluxo do tráfego 
(normalmente representados por linhas coloridas no mapa), 
por exemplo, e poderiam mostrar rotas que causam menos 
poluição à cidade, áreas perigosas que devem ser evitadas etc. 
Para estimar o potencial da camada sensorial do tráfego, 
analisa-se dados participativos vindos do Waze, a mais popular 
aplicação de dados ligados ao tráfego em cidades. O Waze foi 
criado em 2008 e recentemente tinha aproximadamente 50 
milhões de usuários. O Waze coleta periodicamente dados 
sensoriais dos celulares, e utiliza-os para computar a 
velocidade de seus dispositivos para presumir as condições do 
tráfego naquelas regiões. O sistema oferece também alertar 
predefinidos sobre incidentes como engarrafamentos e blitz, 
estendendo ainda mais a informação sobre o trânsito. Uma das 
principais funções do Waze é a ajuda que cada usuário fornece 
para o bem comum, isto é, o Waze não é um projeto de 
crowdsourcing, mas sim uma participação pessoal. O objetivo 
desse trabalho é de caracterizar as propriedades da RSP 
derivada do Waze, sua cobertura de espaço global e suas 
limitações. 
3) GOOGLE MAPS 
O Google Maps, de uma maneira semelhante, oferece um 
serviço de mapeamento e consulta de rotas popularmente 
conhecido e usado. Uma conexão com a internet e o acesso ao 
banco de dados de coordenadas do sistema é fornecido ao 
usuário, que obtém informações de vias das mais grandes 
metrópoles até as mais pacatas cidades. Com o serviço é 
possível obter estimativas do tempo necessário previsto para a 
conclusão da rota em um carro, trem, bicicleta, a pé etc. de 
modo que as rotas são feitas de maneira online e, em casos 
necessários, caso o usuário erra a rota, a mesma é redesenhada 
para atendê-lo. A maioria dos aplicativos de GPS utiliza o 
Google Maps como base hodiernamente, embora alguns 
tenham criado seu próprio, como o Waze. Também é comum o 
uso do OpenStreetMap, que tem mecanismo parecido. 
II. METODOLOGIA 
Com o objetivo de evitar gargalos por falta de dados e para 
melhor fluência no trabalho, o desenvolvimento precisa ser 
bem detalhado, exigindo muita dedicação, atenção e cuidado, 
portanto este será dividido em duas partes, sendo uma o 
processo de modelagem do modelo matemático e a outra o 
desenvolvimento do aplicativo móvel. 
A. MODELAGEM 
A metodologia empregada será baseada nas fases de estudo 
de problemas de pesquisa operacional: identificação do 
problema, estudo do problema, construção do modelo, 
resolução do modelo e validação do modelo, conforme 
Briesemeister (2014). 
A ferramenta utilizada na metodologia é a “A Mathematical 
Programming Language” conhecida como AMPL, que nada 
mais é do que uma linguagem algébrica descritiva usada para 
modelar problemas de programação linear conforme Fourer 
(1990). De acordo com Gay (2001), o AMPL possibilita 
separar o modelo dos dados fundamentais para informar uma 
instância particular do problema e permite expressar o 
problema de maneira que o computador possa compreender o 
modelo. 
O AMPL do problema será implementado no ILOG CPLEX 
(IMB), uma ferramenta gratuita com os seguintes pacotes para 
solução: Simplex, Pontos Interiores, Barrier, Branch & 
Bound. Resolve problemas de programação inteira, 
programação linear de larga escala, programação quadrática e 
problemas com restrições quadráticas convexas. 
 
1) REVISÃO BIBLIOGRÁFICA 
Inicialmente será feita uma revisão bibliográfica dos 
principais Problemas de Roteamento e Veículos e suas técnicas 
de soluções, conforme Toth e Vigo (2002 apud Alves, 2015), 
que será denominada parte 1. 
2) IDENTIFICAÇÃO DO PROBLEMA 
Será feito o levantamento dos principais problemas 
enfrentados pelo Corpo de Bombeiros (SAMU e Combate a 
incêndios) e Policia Militar da cidade de Coxim - MS para 
atendimentos utilizando os veículos oficiais. 
3) ESTUDO DO PROBLEMA 
Com as informações adquiridas na Parte II, serão definidos 
os problemas a serem resolvidos, onde serão colocadas todas 
as restrições de legislação pertinente e restrições logísticas 
enfrentadas pelo sistema de saúde e segurança pública da 
cidade de Coxim - MS, na qual serão definido três problemas, 
denominados Problema do atendimento SAMU (PA-SAMU), 
Problema do atendimento da PM (PA-PM), Problema do 
atendimento de CI (PA-CI). No PA-SAMU será tratado o 
problema que envolve as melhorias e problemáticas 
enfrentadas pelo Serviço de Atendimento Móvel de Urgência, 
no PA-PM, o problema referente aos atendimentos da Polícia 
Militar e em PA-CI, o problema envolvendo o setor de 
Combate a Incêndios do Corpo de Bombeiros. 
4) CONSTRUÇÃO DO MODELO 
Uma boa escolha do modelo é essencial para a qualidade da 
solução fornecida. Se o modelo proposto tem a forma de um 
modelo já conhecido, a solução por ser obtida através de 
técnicas matemáticas convencionais. Por outro lado, se as 
relações matemáticas são muito complexas, talvez seja 
necessário a utilização de cominações de metodologias para 
sua solução. Com os três problemas bem definidos na Parte III 
do projeto, será proposto um modelo único para todos os 
problemas e ainda um modelo adicional para o PA-PM, 
definindo rotas de supervisão aleatórias para rondas. 
5) RESOLUÇÃO DO MODELO 
O objetivo dessa parte é encontrar uma solução para os 
modelos propostos através da utilização de técnicas mais 
adequadas e que forneçam o resultado ótimo em menor tempo 
possível, esse resultado ótimo, muitas vezes, dependendo da 
complexidade do problema, não é possível de ser encontrado, 
para isso, foram utilizada metodologias de aproximação 
existentes na literatura, algumas dessas metodologias são 
encontradas em Toth e Vigo (2002 apud Alves, 2015). Em 
sequência, os modelos propostos irão ser transformados em 
AMPL conforme proposto por Taha (2008), para que então 
possam ser implementados no ILOG CPLEX (IMB). 
6) VALIDAÇÃO DO MODELO 
Conforme Taha (2005), a validação do modelo verifica se o 
modelo faz ou não o que diz fazer – isto é, ele prevê 
adequadamente o comportamento do sistema de estudo? Em 
outras palavras, a solução faz sentido? Os resultados são 
intuitivamente aceitáveis? – Do lado formal, um método 
comum para verificar a validade de um modelo é comparar 
seus resultados com dados históricos. Se o modelo proposto 
representar um novo sistema, não haverá dados históricos 
disponíveis. Nesses casos, pode ser utilizada a simulação 
como ferramenta independente para verificar os resultados do 
modelo matemático. No presente trabalho, como a proposta é 
para um novo sistema, será feito o uso da simulação de 
chamadas de emergências aleatórias e então será feita a 
comparação com chamadas já registradas pelos sistemas 
atuais, para então ser completa a fase. 
B. DESENVOLVIMENTO DO APLICATIVO 
Conforme Scudero (2017), o uso de um ambiente de 
desenvolvimento para a programação de aplicativos é 
imprescindível, já que a partir disto todo o processo será 
otimizado, desde confecção do código até a sua execução e 
teste. Além de que quando o processo de desenvolvimento setorna menos complicado, o desenvolvedor consegue se dedicar 
mais ao seu aplicativo, trazendo melhorias em aspectos como 
a lógica aplicada em sua criação, conhecida como uma área 
específica chamada Lógica da Programação, de mesma forma, 
sua função e uso em problemas e necessidades da vida real, 
aplicando-se a Orientação a Objetos. 
Por essas razões, como dito diversas vezes no decorrer do 
trabalho, foi optado pelo uso da IDE Android Studio, que, de 
acordo com RAJPUT (2015), é a melhor na área para 
desenvolvimento para Android, já que se trata de um ambiente 
exclusivamente arquitetado para o desenvolvimento de 
aplicados para Android. Para o desenvolvimento do aplicativo, 
como também dito anteriormente, serão utilizadas as 
linguagens Java e XML, geralmente utilizadas no 
desenvolvimento de tais aplicativos por padrão. 
O desenvolvimento poderá ser dividido cinco partes: 
implementação do modelo matemático já em seu formato 
AMPL, escrito agora em Java, aplicando as metodologias de 
tradução de código encontradas em Rubin (2014); criação de 
um aplicativo inicialmente básico utilizando o Android Studio, 
para fins de implantação mecanismos básicos, como o de 
cadastro e também o desenvolvimento de uma interface 
gráfica simples, atrativa e intuitiva para ser usada no 
aplicativo, produzida através de tutoriais encontrados na 
internet; implementação do código Java no aplicativo criado; 
realização de série de testes deverá ser iniciada para que o 
aplicativo esteja limpo e sem problemas técnicos, no qual 
serão avaliados processamento de dados, usabilidade, 
integração com hardware, escalabilidade e feedback dos 
 
usuários, os 5 pilares essenciais da fase de testes conforme 
Quintão (2012); distribuição do aplicativo. 
1) IMPLEMENTAÇÃO DO ALGORITMO HEURÍSTICO EM JAVA 
Será criado um código Java que resolva o modelo 
matemático anteriormente produzido, fazendo uso do código 
AMPL, que primeiramente será analisado. Suas etapas para 
atingir uma solução, e sua estrutura em geral, serão transcritas 
para o código Java, conforme técnica explicada em Rubin 
(2014). Para a execução dessa fase se fará necessária uma 
revisão bibliográfica de uma variada gama de códigos 
voltados a essa área. 
2) CRIAÇÃO DO APLICATIVO-BASE E INTERFACE GRÁFICA 
Será criada a estrutura básica de um aplicativo para 
Android, e já possuirá várias funções do aplicativo final (como 
a possibilidade do usuário se cadastrar no aplicativo, a 
obtenção e o envio de informações de localização etc.). A 
interface gráfica é importante neste processo, para que o 
usuário seja capaz de encontrar menus intuitivos que 
facilitarão a chamada. Esta fase pode ser considerada uma das 
mais complexa de todas, e por isso será subdividida em 
subfases. 
a) CADASTRO DE ATENDENTES E USUÁRIOS 
Uma vez que a pessoa inicie o aplicativo pela primeira vez, 
será necessário um cadastro para poder utilizá-lo. Ela 
encontrará uma tela com duas opções: entrar como atendente e 
entrar como usuário, onde se ela selecionar uma das opções 
deverá entrar com sua conta (caso já possua uma) ou se 
cadastrar no aplicativo: para atendentes, serão necessários os 
dados da agência onde a pessoa trabalha, como o 
departamento, o endereço, etc. Para usuários, serão necessárias 
apenas informações como nome, data de nascimento, telefone 
de contanto, contato de emergência etc., além de algumas 
informações que podem ajudar no atendimento, como tipagem 
sanguínea e alergias. 
b) MENU INICIAL E SUB-MENUS 
Nesta subfase serão construídos os menus principais do 
aplicativo, que serão bem simples para proporcionarem um 
uso intuitivo dos mesmos. Existirão dois menus principais, um 
para os atendentes dos três serviços (polícia, ambulâncias e 
bombeiros) onde eles receberão a chamada e outro para os 
usuários que poderão solicitar ajuda. Nesta subfase a interface 
será de suma importância, para que o usuário se guie bem 
através dela. 
c) ENVIO DOS PEDIDOS COM DADOS DE LOCALIZAÇÃO 
Serão pesquisadas maneiras de se enviar rapidamente 
informações de localização com ou sem fazer uso de internet 
ou de dados móveis de operadoras. Os dados enviados 
consistem na importância da chamada, as coordenadas do 
local de onde a chamada foi feita e a ficha de cadastro do 
usuário, que serão organizados de maneira a gastar o menor 
espaço de armazenamento possível. 
 
Para esta fase serão usados conceitos de programação e 
produção de interface gráfica, que serão obtidos conforme 
Glauber (2015). 
3) IMPLEMENTAÇÃO DO CÓDIGO HEURÍSTICO NO APP 
Na parte 1, já terá sido implementado em Java o algoritmo 
heurístico mencionado. Agora, o código Java será 
implementado no aplicativo de forma que continue funcional 
por si mesmo e que não prejudique o funcionamento do 
aplicativo. Este código será acessado somente quando 
atendentes receberem um pedido, e ajudará a decidir a melhor 
rota e a melhor viatura para o trabalho. 
4) FASE DE TESTES 
Aqui, o app será extensiva e intensivamente testado, para 
que sejam achados todos os defeitos que possam atrapalhar os 
usuários e atendentes a fazer uso das funções essenciais do 
mesmo, baseando-se na técnica de testes dos 5 pilares 
proposta por Quintão (2012), como citado anteriormente. 
Quando erros forem encontrados, o código do aplicativo será 
analisado para se descobrir o que causa os problemas, e assim 
serão consertados. Esta será uma das mais longas fases do 
desenvolvimento, e possivelmente continuará até mesmo 
depois do lançamento do aplicativo. 
5) DISTRIBUIÇÃO DO APLICATIVO 
Todo aparelho com sistema operacional Android faz uso do 
serviço Google Play Store, que como o próprio nome diz, é 
fornecido pela Google. O serviço compreende uma biblioteca 
vasta de aplicativos, jogos, filmes, músicas livros e banca e 
geral, sendo então um meio popular e eficiente para 
distribuição de aplicativos, o que não se faz diferente com o 
presente projeto de pesquisa, que, como fase final, distribuirá 
o aplicativo gratuitamente na plataforma, conforme método 
explicado na página da IDE Android Studio. 
III. RESULTADOS 
A. OS MODELOS 
Para a obtenção do modelo matemático, foram feitas 
diversas perguntas ao SAMU, a PM e ao CI, sendo elas: 
 Existe alguma limitação quanto ao número de 
oficiais/atendentes que podem ser enviados simultaneamente a 
uma emergência? 
 Existe alguma limitação quanto ao número de viaturas 
que podem ser enviadas simultaneamente a uma emergência? 
 
 Qual o total de atendentes e veículos disponíveis? 
 Existe uma média de pessoas que vieram a óbito por 
conta de um atraso no atendimento? Se sim, qual é? 
 Qual o método utilizado para determinar a rota entre o 
departamento e paciente? 
 Vocês recebem trotes com frequência? Existe uma 
média de quantos por mês? Se sim, quantos? 
A partir das quais foi possível desenvolver o modelo (1) a 
seguir. 
 
 
 Em (5.1) temos a função objetivo, que, após discussão 
e observação de que na cidade de Coxim, a maioria das vias 
tem o mesmo limite de velocidade, foi optado por minimizar a 
distância, sendo i o ponto inicial onde a viatura se encontra, j o 
local onde o paciente encontra, dij a distância gasta para 
percorrer estes dois pontos e xij é a variável binária que irá 
decidir se determinado caminho será utilizado; 
 Em (5.2) e (5.3) implica que para ir de um ponto ao 
outro só deverá ser aceita uma rota; 
 Em (5.4) é a restrição responsável por fazer a 
eliminação de sub-rotas; 
 Em (5.5), é apresentada uma restrição de não 
negatividade com relação a distância gasto para chegar até o 
paciente, sendo pertencente aos números reais positivos ℝ+ já 
que não existiria tempo negativo; 
 Em (5.6), é apresentada uma outra restrição de não 
negatividade, porém, desta vez com relação a variável binária 
x que deve ter sempre valor 0 ou 1; 
 Em (5.7), é apresentada uma outra restrição de não 
negatividade, porém, destavez com relação aos conjuntos de 
pontos I que vai de 1 até n; 
Existem ainda os modelos matemáticos (2) e (3) feitos para 
otimizar o desempenho das rondas da PM na cidade de 
Coxim-MS. Seja n o número de pares ordenados composto de 
latitude e longitude, que representam todas as esquinas da 
cidade de Coxim - MS. Definimos então o conjunto E = {1, ..., 
n}, seja p o conjunto de setores na qual desejamos dividir a 
cidade de Coxim - MS. O modelo abaixo divide a cidade em p 
setores e atribui cada ponto ao seu setor, conforme segue: 
 
Onde dij é a distância de um ponto i a um ponto j conforme 
Alves (2015), xij é uma variável binária, sendo 1 se o caminho 
entre i e j é utilizando e 0 caso contrário. Em (5.8) definimos a 
função objetivo, na equação (5.9) temos que entre um vértice i 
e um vértice j só existe um caminho, a equação (5.10) 
determina que devem ser instalados exatamente p setores, em 
(5.11) temos a restrição que determina que um ponto j seja 
atribuído a um setor. 
Após a definição do setor, reaplicamos o modelo anterior no 
setor, agora p representa a quantidade de pontos que a ronda 
da Polícia Militar deve passar obrigatoriamente. Seja A o 
conjunto de todos os arcos (i, j) com i, j ∈ E, Si é o conjunto de 
todos os pontos do setor i, mi a quantidade de pontos em cada 
setor, uk ∈ {2,...,m} propomos o seguinte modelo que define a 
rota da ronda policial: 
 
O ponto o é a origem, no caso, o 5º Batalhão da Polícia 
Militar, em (5.13) temos a função objetivo que minimiza a 
distância percorrida na ronda. A equação (5.14) determina que 
a viatura da PM deve sair da origem. A equação (5.15) e (5.16) 
são do Problema do Caixeiro Viajante, na qual todos os pontos 
fixos da ronda devem ser visitados, em (5.17) temos a equação 
que a viatura deve voltar a origem. Em (5.18) temos a 
eliminação de sub-rotas e finalmente em (5.19) as variáveis 
binárias do problema. 
Para que o modelo pudesse funcionar e as rotas fossem 
geradas, toda a cidade de Coxim - MS precisou ser mapeada 
entre pontos de longitude e latitude de todas as suas esquinas, 
conforme mostrado na Figura 3. 
 
 
 
Figura 3 - Mapa da cidade com esquinas marcadas. 
Fonte: os autores. 
 
Como próximo passo foram calculadas todas as distâncias 
entre as esquinas e elas foram armazenadas para que o modelo 
matemático pudesse compará-las. Tal calculo gerou uma 
matriz de 1384x1384. Uma parte desta matriz é mostrada na 
Tabela 1. 
 
Tabela 1 - Distância entre algumas das centenas de esquinas da 
cidade. Fonte: os autores. 
Tais distâncias foram calculadas com a seguinte fórmula: 
 
 
 Em que dij representa a distância do ponto i ao ponto j. Note 
que dii = 0. 
1) PROBLEMA DE RONDA POLICIAL 
Para a simulação de uma ronda e, consequentemente, o teste 
da eficiência dos modelos (2) e (3), a cidade foi dividida em 
12 setores, e a rota de um desses setores foi criada, partindo do 
ponto o, no caso, o 5º BPM, como segue: 
 
Figura 4 - Rota de uma possível ronda policial. Fonte: os autores. 
2) PROBLEMA DE ATENDIMENTO 
Para a simulação de uma chamada de emergência e, 
consequentemente, o teste da eficiência do modelo (1), foi 
assumido que houvesse um pedido de socorro no 
ponto/esquina 24 (LAT -18.5018998, LONG -54.7453022) do 
mapa. Sendo assim, o serviço utilizado como exemplo foi o do 
SAMU, que tem seu posto localizado no ponto/esquina 595 
(LAT -18.522087, LONG -54.407271) do mapa, gerando o 
resultado a seguir: 
 
Ponto atual Ponto seguinte 
595 866 
866 828 
828 902 
902 916 
916 921 
921 961 
961 965 
965 24 
Tabela 2 – Trajetória da viatura. Fonte: os autores. 
 
 
Figura 5 - Rota do ponto 595 ao 24. Fonte: os autores. 
 
 Distância do modelo: 2.290 m; 
 Distância do Google Maps: 2.900 m; 
 Diferença: 610 m. 
IV. CONSIDERAÇÕES FINAIS 
Os modelos propostos foram implementados no ILOG 
CPLEX (IBM), e executados em uma máquina com 
processador Intel® Core™ i7-7700UHQ, CPU @ 2.8 GHz até 
3.8GHz 6 MB L3 Cache, memória RAM 8 GB DDR4 com 
sistema operacional Microsoft Windows [versão 10.0.10240]. 
Foi necessário apenas cerca de 1 minuto para o modelo (1) e 
cerca de 0,250 segundos para os modelos (2) e (3), para que o 
CPLEX encontrasse uma solução ótima para o problema, 
gerando a rota e calculando sua distância total. Ele utilizou um 
método de solução exata: Método Simplex. 
Vemos assim que, com um modelo simples de programação 
linear, é possível obter soluções mais eficientes para 
problemas do cotidiano de serviços de prestação de socorro. 
 
 
 
V. REFERÊNCIAS BIBLIOGRÁFICAS 
ALVES, F. S. Problemas de roteamento de veiculos aplicados no 
planejamento logistico do transporte escolar da cidade de Coxim-MS. 
Campinas, SP, 2015. 
 
ARAUJO, R. Trotes representam 85 por cento das ligacoes para a 
PM. Tribuna do Norte. Disponivel em: 
<http://www.tribunadonorte.com.br/noticia/trotes-representam-85-
das-ligacoes-para-a-pm/194456>. Acesso em: 15 jun. 2018. 
 
BELLMAN. Dynamic Programming Treatment of the Travelling 
Salesman Problem. 1962. BRIESEMEISTER, M.; BORBA, M. P. de. 
PROGRAMACAO MATEMATICA APLICADA AO 
GERENCIAMENTO DE PROJETOS. 
 
CHRISTENSEN, C. M.; RAYNOR, M.; MCDONALD, R. What 
Is Disruptive Innovation?: Twenty years after the introduction of the 
theory, we revisit what it does – and doesn’t – explain. Boston: 
Harvard Business Review, 2015. 
 
COSTA, C. S. A. G. Problema do caixeiro viajante - resolucao e 
depuracao. Universidade de Aveiro, Departamento de Matematica, 
2008. 
 
DUBEY, A.; MISRA, A. Android Security: Attacks and defenses. 
Nova Iorque, EUA: CRC Press, 2013. 
 
FOURER, R.; GAY, D. M.; KERNIGHAM, B. W. A modeling 
language for mathematical programming. [S.l.: s.n.]. 
 
FREITAS, A. R. R. de. Resolvendo o problema do caixeiro 
viajante via procedimento de busca adaptativa aleatoria gulosa com 
construcao baseada em redes neurais auto-organizaveis. 
UNIVERSIDADE FEDERAL DE OURO PRETO 
DEPARTAMENTO DE COMPUTACAO, 2009. 
 
G1. Demora no atendimento do 190 preocupa quem precisa da 
policia. Disponivel em: 
<http://g1.globo.com/pr/parana/noticia/2011/05/demora-no-
atendimento-do-190-preocupa-quem-precisa-da-policia.html>. 
Acesso em: 15 jun. 2018. 
 
GAY, D. M. Symbolic-algebraic computations in a modeling 
language for mathematical programming. In: Symbolic Algebraic 
Methods and Verification Methods. [S.l.: s.n.]. 
 
GLAUBER, N. Dominando o android: do basico ao avancado. 
Novatec, 2015. 
 
GOLDBARG, M. C.; LUNA, H. P. L. Otimizacao Combinatoria e 
Programacao Linear: Modelos e algoritmos. Sao Paulo: ELSEVIER, 
2000. 519 p. 
 
LECHETA, R. Google Android: aprenda a criar aplicacoes para 
dispositivos moveis com o Android SDK. [S.l.]: Novatec, 2015. p. 
25-41 p. 
MARTINS, F. A. S. Introducao a Pesquisa Operacional. Sao Paulo: 
UNESP, 2011. 
 
MESTRIA, M. Metodos heuristicos usando busca local aleatoria 
em vizinhanca variavel para o problema do caixeiro viajante com 
grupamentos. [S.l.]: Revista Producao Online, 2014. v. 14, n. 4, p. 
1511-1536 p. 
 
MORETTI, A. C. Modelagem Matematica. Unicamp, 2010. 
QUINTAO, G. Metodologia De Testes: Busca Por Bugs. 2012. 
Universidade Federal de Ouro Preto (UFOP)/DECOM/Laboratorio 
Mobilis, Disponivel em: 
<http://www.decom.ufop.br/imobilis/metodologia-de-testes-busca-
por-bugs-em-sistemas-embutidos/>. Acesso: 15 jun. 2018. 
 
RAJPUT, M. Why Android Studio Is Better For Android 
Developers Instead Of Eclipse. 2015. D Zone. Disponivel em: 
<https://dzone.com/articles/why-android-studio-better>. Acesso: 15 
jun. 2018. 
 
RUBIN, P. Setting CPLEX Parameters in Java Revisited. 2014. 
Michigan State University/Spartan Ideas. Disponivel em: 
<http://spartanideas.msu.edu/2014/05/11/setting-cplex-parameters-in-
java-revisited/>. Acesso: 15 jun. 2018. 
 
SAUDE, M. da. Politica nacional de atencao as urgencias. 
SCUDERO, E. A trajetoria de um Desenvolvedor Mobile: tudo 
que voce precisa saber! 2017.Becode. Disponivel em: 
<https://becode.com.br/trajetoria-de-um-desenvolvedor-mobile/>. 
Acesso: 15 jun. 2018. 
 
SILVA et al. Traffic Condition Is More Than Colored Lines on a 
Map: Characterization of Waze Alerts. Belo Horizonte: UFMG, 2013. 
 
SILVA, N. C.; NOGUEIRA, L. T. Avaliacao de indicadores 
operacionais de um servico de atendimento movel de urgencia. [S.l.]: 
Cogitare Enfermagem, 2012. v. 17, n. 3 p. 
 
STUDIO, A. Publicar o aplicativo. Disponivel em: 
<https://developer.android.com/studio/publish/index.html>. Acesso: 
15 jun. 2018. 
 
TAHA, H. A.; MARQUES, A. S.; SCARPEL, R. A. Pesquisa 
Operacional. [S.l.]: Pearson Education do Brasil, 2008. 
 
TOTH, P.; VIGO, D. The vehicle routing problem. [S.l.]: Siam, 
2002. 
 
 
 
 
 
 
 
 
 
 
 
 
Eitor Bernardes de Paiva: Estudante do 
campus Coxim do IFMS desde 2016, está 
agora no 7º e último semestre do curso técnico 
em informática integrado ao ensino médio. 
Veterano em feiras de ciência. Em 2016, 
participou da FECITECX, que acontece em 
Coxim, Mato Grosso do Sul. Em 2017, 
participou novamente da FECITECX. Já em 2018, foi à 
FEBRACE 16, retornou à FECITECX, apresentou na 
FECINORTE, também em Coxim, e depois foi à Mostratec, 
no Rio Grande do Sul. Em todas essas feiras científicas, levou 
projetos da área da Programação Linear. 
 
 
 
 
Mariana Dias Nogueira: Estudante do 
campus Coxim do IFMS desde 2016, está 
agora no 7º e último semestre do curso 
técnico em informática integrado ao ensino 
médio. Ela também não é novata na vida 
acadêmica e nas feiras. Em 2016, 
apresentou na FECITECX. Em 2017, 
retornou à FECITECX e estreou sua 
apresentação na FETEC, feira em Campo Grande, MS. Em 
2018, foi à FEBRACE 16, novamente à FETEC, à 
FECITECX, à FECINORTE e na Mostratec. Além disso, 
participou do LIYSF 2018, em Londres, ao apresentar um 
projeto da área de engenharia a pessoas de todo o mundo. 
 
 
 
 
Thiago Ferronatto: Estudante do campus 
Coxim do IFMS desde 2016, está agora no 7º 
semestre do curso técnico em informática 
integrado ao ensino médio. Assim como os 
outros, apresentou em várias feiras científicas. 
Em 2017, apresentou na FECITECX e na 
FETEC. Em 2018, foi à FEBRACE 16, 
novamente à FECITECX e também à FECINORTE. 
Juntamente à Mariana, também foi ao LIYSF 2018, em 
Londres, apresentar o mesmo projeto da área de engenharia 
para pessoas de vários países diferentes.