Heuristic and exact approaches for the open capacitated arc routing problem

Resumo:O problema de roteamento em arcos capacitado e aberto (open capacitated arc routing problem, OCARP) é um problema de otimização combinatorial NP-difícil em que, dado um grafo não-direcionado, o objetivo consiste em encontrar um conjunto de rotas de custo mínimo para veículos com capacidade restrita que atendam a demanda de um subconjunto de arestas. O OCARP está relacionado com o problema de roteamento em arcos capacitado (capacitated arc routing problem, CARP), mas difere deste pois o OCARP não possui um nó depósito e as rotas não estão restritas a ciclos. Aplicações da literatura para o OCARP são discutidas. Uma formula ção de programação linear inteira é fornecida junto com propriedades do problema. Uma metaheurística GRASP (greedy randomized adaptive search procedure) com reconexão por caminhos (path-relinking) é proposta e comparada com outras metaheurísticas bem-sucedidas da literatura. Algumas características do GRASP são: (i) ajuste reativo de parâmetros, cujos valores são estocasticamente selecionados com viés `aqueles valores que produziram, em média, as melhores soluções; (ii) um filtro estatístico que descarta soluções iniciais caso estas tenham baixa probabilidade de superar a melhor solução incumbente; (iii) uma busca local infactível que gera soluções de baixo custo utilizadas para explorar fronteiras factíveis/infactíveis do espaço de soluções; (iv) a reconexão por caminhos evolutiva aprimora progressivamente um conjunto de soluções de elevada qualidade (soluções elites). Testes computacionais foram conduzidos com instâncias CARP e OCARP e os resultados mostram que o GRASP é bastante competitivo, atingindo os melhores desvios entre os custos das soluções e limitantes inferiores conhecidos. Este trabalho também propõe um algoritmo exato para o OCARP que se baseia no paradigma branch-and-bound. Três limitantes inferiores são propostos e um deles utiliza o método dos subgradientes para resolver uma relaxação lagrangeana. Testes computacionais comparam o algoritmo branch-and-bound com o CPLEX resolvendo um modelo reduzido OCARP de programa ção linear inteira. Os resultados revelam que o algoritmo branch-and-bound apresentou resultados melhores que o CPLEX no que diz respeito aos desvios entre limitantes e ao número de melhores soluções.Abstract: The Open Capacitated Arc Routing Problem (OCARP) is an NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours that services a subset of edges with positive demand under capacity constraints. This problem is related to the Capacitated Arc Routing Problem (CARP) but differs from it since OCARP does not consider a depot, and tours are not constrained to form cycles. Applications to OCARP from literature are discussed. An integer linear programming formulation is given, followed by some properties of the problem. A Greedy Randomized Adaptive Search Procedure (GRASP) with path-relinking (PR) solution method is proposed and compared with other successful metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the metaheuristic parameters values are stochastically selected biased in favor of those values which produced the best solutions in average; (ii) a statistical filter, which discards initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend in which a pool of elite solutions is progressively improved by relinking pairs of elite solutions. Computational tests were conducted for both CARP and OCARP instances, and results reveal that the GRASP with PR is very competitive, achieving the best overall deviation from lower bounds. This work also proposes an exact algorithm for OCARP, based on the branch-and-bound paradigm. Three lower bounds are proposed, one of them uses a subgradient method to solve a Lagrangian relaxation. The computational tests compared the proposed branch-and-bound with a commercial state-of-the-art ILP solver. Results reveal that the branch-and-bound outperformed CPLEX in the overall average deviation from lower bounds