Matemática Computacional - Aula 04/11/2011 (Problemas do tipo Carteiro Chinês)

Problemas do tipo "Carteiro Chinês"

Em especial o "Problema do Carteiro Rural"

INTRODUÇÃO


O Problema do Carteiro Rural (PCR) (pesquise também em inglês por Rural Postman Problem) considera que o percurso deve ser garantido sobre um subconjunto de ligações do grafo, partindo e retornando de um vértice origem dado (Lenstra & Rinooy Kan, 1981; Christofides et al., 1984; Corberán, 1994; Corberán, 1998; Corberán et al., 2001; Nobert & Picard, 1996; Eiselt et al., 1995ii; Negreiros, 1996).



O problema de roteamento em arcos capacitados (Capacitated Arc Routing Problem - CARP) consiste em visitar um subconjunto de arestas do grafo que descreve o problema, atendendo às suas demandas.


Aplicações possíveis para o CARP são a coleta de lixo urbano e a inspeção de linhas de força.


O CARP é um problema NP-difícil, mesmo no caso onde existe apenas um veículo (chamado de Problema do Carteiro Rural).


Neste caso, o uso de meta-heurísticas surge como uma estratégia de solução eficiente.


Este artigo apresenta um algoritmo genético híbrido para o CARP, que é testado em instâncias disponíveis na literatura.


Os resultados obtidos até o momento demonstram a eficiência do algoritmo proposto quando comparado com limites inferiores descritos na literatura.  





LEITURA SUGERIDA


Antes de continuar, leia os artigo Um Algoritmo Evolutivo para o Problema de Roteamento em Arcos Capacitados, Problema de Roteamento de Veículos sobre Arcos e Um Modelo de Resolução Para o Problema de Roteirização em Arcos com Restrição de Capacidade, em especial a parte sobre Carteiro Rural (página 47, salvo engano).


Você também pode se interessar pela leitura do artigo A Genetic Algorithm for the Undirected Rural Postman Problem, naturalmente em inglês.


O excelente trabalho Algoritmos para Roteamento de Leituristas merece especial atenção para a explicação de diversas e complexas fórmulas.






PROBLEMAS



O roteamento de leituristas consiste em um problema importante de natureza prática, envolvendo grandes empresas fornecedoras de energia elétrica, água e gás, nas quais trabalhadores são incumbidos de registrar o consumo de cada cliente, dispersos geograficamente nas ruas e avenidas de uma localidade. Esse problema, de difícil tratamento e elevado número de restrições, prevê a elaboração de um conjunto de rotas abertas, pelas quais os leituristas devem percorrer, atendendo a demanda por serviço de leitura. Uma solução ótima para esse problema procura minimizar as seguintes propriedades: 

• Número de leituristas necessários para atender toda demanda; 
• O tempo de percurso, ou seja, o tempo utilizado pelo leiturista para se deslocar de uma região a outra sem realizar qualquer leitura; 
• Violação da carga horária do leiturista.

A motivação desse trabalho provém da demanda por soluções computacionais para esse problema, sobretudo por parte das empresas que se utilizam desse serviço, em virtude de diversos fatores, como: 

• Dificuldade de obter soluções manualmente; 
• Reduzida qualidade das soluções atualmente colocadas em prática; 
• Rápida mudança do cenário consumidor, sobretudo nas metrópoles, onde se verifica uma acentuada verticalização do espaço geográfico; 
• Necessidade de obter soluções no curto prazo. 

O roteamento de leituristas envolve um conjunto de particularidades inerentes, por exemplo: modo como o serviço de leitura se realiza (U ou Z); presença de segmentos de rua que não requerem leitura; tolerâncias máxima e mínima de carga horária; diferença entre ler e percorrer um segmento de rua. 


A natureza desse problema permite generalizá-lo como um problema de roteamento em arcos que, por sua vez, consiste em determinar um subconjunto ordenado de arestas E’ sobre um grafo  G(V,E) (E’ ⊆ E), atendendo às restrições (de demanda, capacidade, dentre outras) e minimizando determinada função custo. Ao problema de roteamento em arcos encontra-se ligada uma vasta árvore de subproblemas, dos quais o mais conhecido é o Problema do Carteiro Chinês (CPP), o qual pode ser resolvido polinomialmente sobre um grafo não-direcionado.


Problema do Carteiro Chinês (CPP)

Um vídeo introdutório bem simplificado

Um vídeo mais elaborado e mais profundo

Se algumas arestas do grafo são requeridas, enquanto outras não, o problema passa a se denominar Problema do Carteiro Rural (RPP). Foi demonstrado que o RPP é NP-Completo, portanto difícil de obter soluções ótimas para instâncias suficientemente grandes. Se for adicionada ao RPP uma restrição de capacidade, torna-se ainda mais difícil resolvê-lo até a otimalidade. Verifica-se que o problema de roteamento de leituristas (visto anteriormente) é similar ao RPP capacitado. 


Foram constatadas duas heurísticas na literatura para roteamento de leituristas, que utilizam abordagens distintas, antagônicas inclusive, para tratar do problema. Esses algoritmos foram desenvolvidos para resolver os problemas locais nos quais estavam inseridos, logo são dotados de características específicas não compartilhadas. Nesse trabalho esses algoritmos foram denominados RFCS1 (“route first, cluster second”) e CFRS1 (“cluster first, route second”).


Você ainda pode ler (em inglês) o documento Chinese Postman Problem que explica de maneira lúdica o problema do carteiro chinês. Também pode visitar o link http://eie507.eie.polyu.edu.hk/ss-submission/B7a/. O arquivo PDF The directed Chinese Postman Problem contém alguma implementação em linguagem C++.








PROBLEMA PROPOSTO


Resolver o seguinte problema do carteiro chinês


Sortear n pontos, no mínimo 4 e no máximo 10, num plano XY, de forma que os pontos tenham distâncias variadas entre si. Depois, ligar os n pontos aos outros n - 1 pontos, com k arestas (k aleatoriamente definido entre 1 e n - 1).


Determinar a menor distância total para cobrir com um passeio (ou tour) todos os arcos do grafo assim determinado. Obviamente, o circuito (ou ciclo) euleriano, quando existente no grafo, é a solução do carteiro chinês.






SOLUÇÃO


A ideia para a solução do problema proposto é o desenvolvimento de um software (em alguma linguagem visual, como o Visual Studio C#) para a solução e apresentação gráfica dos passos em busca da solução para o problema do Carteiro Chinês.