Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

Apresentamos uma nova formulação matemática para o problema de rotas de cobertura multiveículo como um modelo de programação por metas estendida inteiro misto, o qual tem várias aplicações, e envolve um grafo G=(V U W, E), cujos vértices são pontos geográficos estratégicos, como interseções, certas localidades, etc, os quais têm importância própria ou servem para estabelecer locais de referência. V={0,...,n} é o conjunto de vértices que podem pertencer as rotas, W={n+1,...,n+l} é o conjunto de vértices que devem ser cobertos, mas não visitados, e T C V deve ser visitado. Em E estão os arcos não direcionados entre os vértices de V. D=(d_ij) fornece a distância d_ij entre os vértices i,j em V U W, m é o tamanho da frota e c é a distância permitida de um vértice na rota a um vértice que deve ser coberto: a) cada rota é um circuito em G contendo 0; b) cada vértice em V\0 pertence a no máximo uma rota; c) cada vértice em T\0 pertence a exatamente uma rota; d) cada vértice em W está no máximo c de distância de um vértice visitado; e) as diferentes rotas têm tamanhos equilibrados; f) as diferentes rotas têm número de visitas (nv) equilibrado; g) dado D, a distância c deve ser a menor possível. Nosso modelo é mais geral que Hà et al. (2013), onde o nv é limitado, m é variável e c é um parâmetro, e que Oliveira et al. (2015), onde nv, m e c são parâmetros. Adicionamos equilíbrio no tamanho das diferentes rotas, e nv, m e c são variáveis.

Estamos interessados em problemas que envolvem o desenho de rotas para viaturas policiais, onde um conjunto de pontos geográficos determinados estatisticamente pela força policial precisam ser visitados durante o patrulhamento preventivo de rotina: escolas; hospitais; prédios públicos; etc. Outros pontos devem estar a uma distância conveniente de uma rota: parques públicos; centros comunitários; agências bancárias; etc. Existem recursos limitados (tamanho da frota, oficiais) para cobrir grandes áreas geográficas. Portanto, os oficiais devem ser guiados de uma visita para outra evitando circuitos empíricos ruins. Determinar rotas balanceadas em tamanho e número de visitas para cada carro de patrulha, e aproximar o conjunto de visitas de outros pontos importantes é fundamental, pois cada veículo estaciona para interagir com a população, e o oficial pode visualizar outros pontos de interesse. Quanto mais equilibrado, melhor é o serviço de vigilância preventiva e a interação com a comunidade. Incluímos uma correspondência entre eficiência e equidade para o modelo ao incluir a filosofia da programação por metas estendida. Obtivemos resultados promissores de testes conduzidos para exemplares de 100 a 400 vértices construídos a partir de dados do TSPLIB.