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

Resumo:
Dado um grafo não-orientado G(V, E), onde V representa o conjunto dos vértices e E o conjunto das arestas, assume-se que cada aresta possui um peso não-negativo e R é um subconjunto de E que representa o conjunto das arestas requeridas. O problema do carteiro rural (RPP) é um problema NP-difícil que consiste em encontrar um circuito de custo mínimo em G(V, E) que passa por toda aresta requerida pelo menos uma vez.
O RPP possui diversas aplicações práticas, dentre elas serviço de coleta de lixo, entrega de correspondências, inspeção de redes (energia, água, gás) e roteamento de leituristas.

O RPP Estocástico (RPP-E) é uma generalização pouco estudada do RPP onde o conjunto das arestas requeridas e seus custos apresentam incertezas. Formalmente o problema é definido em um grafo não-orientado G(V, E) e são considerados dois estágios: o primeiro estágio representa o tempo presente e o segundo estágio contém um conjunto S de cenários que representam possíveis realizações em um tempo futuro. Cada cenário $s \in S$ possui seu próprio conjunto de arestas requeridas R_s, custos das arestas C_{s, e} e uma probabilidade de realização P_s. Uma solução viável do RPP-E consiste em um circuito para cada cenário futuro, formado por arestas adquiridas no primeiro e no segundo estágio. Cada aresta adquirida no primeiro estágio pode ser utilizada no circuito de cada cenário do segundo estágio. O objetivo passa a ser decidir quais arestas devem ser compradas em cada estágio de modo que o custo total esperado para atender as arestas requeridas de todos os cenários seja mínimo.

Neste trabalho foi proposto um modelo de programação linear inteira para o RPP-E. Esse modelo possui uma quantidade exponencial de restrições para eliminação de subciclos ilegais. Para a solução desse modelo foi implementado um algoritmo (em C++) de separação dessas restrições utilizando a técnica lazy constraints, enquanto o modelo foi resolvido pelo solver Gurobi.
Experimentos computacionais foram realizados a partir de um conjunto de instâncias geradas para o RPP-E tomando como base instâncias do RPP utilizadas na literatura. As instâncias RPP representam o primeiro estágio das instâncias RPP-E, enquanto os cenários futuros são gerados a partir de perturbações nos custos das arestas e no conjunto das arestas requeridas. Foram explorados diferentes tipos de distribuições das arestas requeridas e de variações nos custos das arestas para avaliar o comportamento do modelo.
Os resultados foram avaliados com base na qualidade dos limitantes primais, duais e gaps de otimalidade obtidos após uma hora de execução para cada instância.

Palavras-chave: Programação linear inteira, roteamento de arcos, otimização combinatória, otimização estocástica

Abstract:
Given a non-oriented graph G(V, E), where V is the set of vertices, E is the set of edges, where each edge has a non-negative weight, and $R$ is a subset of E, which represents the set of required edges. The rural postman problem (RPP) is an NP-hard problem that consists of finding a circuit of minimum weight in G(V, E) that crosses through all the required edges.
The RPP has a lot of practical applications such as garbage collection service, delivery of correspondence, network inspection (energy, water, gas), and routing of readers.

The stochastic RPP is a generalization of the RPP, where the set of the required edges and its weights have some uncertainties. Formally, the problem is defined in a non-oriented graph G(V, E) where there are two stages: the first stage represents the present time and the second stage has a set S of the future scenarios. Each scenario s has its own required edges R_s, weights of the edges, and a realization probability P_s. A viable solution of the stochastic RPP consists of a circuit for each future scenario, formed by acquired edges in the first and second stages. Each acquired edge on the first stage may be used for every scenario from the second stage. The goal is to decide what edges should be bought in each stage so that the total expected weight is the minimum possible.

In this project, an integer linear programming model was proposed to solve the stochastic RPP. This model has an exponential number of restrictions to remove illegal sub-cycles. For the model's solution, an algorithm was implemented for the separation of these restrictions using lazy constraints, while the model was solved using the Gurobi.
Computational experiments were performed for a set of generated instances to the stochastic RPP based on RPP instances. RPP instances represent the first stage of the instances of the stochastic RPP, while the future scenarios were generated from disturbances in the weight of the edges and the set of required edges. Different distributions of the set of required edges and the weight of edges were explored to evaluate the model behavior.
The results were evaluated based on the quality of the primal, dual, and optimality gaps obtained after one hour of execution for each instance.

KEYWORDS. Integer linear programming, arc routing, combinatorial optimization, sto-
chastic optimization.