Problema das pseudo-arborescências capacitadas com localização de facilidades

Abstract

Neste trabalho apresentamos o problema das pseudo-arborescências capacitadas com localização de facilidades, um problema novo e relacionado a dois outros problemas clássicos: o problema do roteamento de veículos capacitado e o problema da localização de facilidade capacitada. O problema estudado é uma generalização do problema da pseudo-arborescência capacitada, em inglês capacitated ring tree problem. Propomos neste estudo duas formulações em programação linear inteira para modelar o problema. A primeira é uma formulação estendida baseada em partição de conjuntos e a segunda é uma formulação compacta baseada em fluxos. Propomos também dois algoritmos exatos para resolver o problema. Um deles utiliza a técnica de branch-and-price com a formulação estendida e o outro é um algoritmo do tipo branch-and-bound baseado na formulação compacta. Implementamos também uma heurística primal e uma heurística de pricing com o objetivo de melhorar o desempenho dos métodos exatos. Experimentos computacionais realizados em um grupo de instâncias testes mostram que a formulação estendida fornece limitantes muito mais apertados do que a formulação compacta. Além disso, as heurísticas foram relevantes para acelerar os métodos de branch-and-price e branch-and-bound, em especial a heurística primal.

ABSTRACT - In this work, we present the capacitated pseudo arborescences with facility location problem, which is a new problem related to two classical problems: the capacitated vehicle routing problem and the capacitated facility location problem. The proposed problem generalizes the capacitated ring tree problem. We propose in this study two integer programming formulations to model the problem. The first one is an extended formulation based on set partition and the second one is a compact formulation based on flow models. We also propose two exact algorithms to solve the problem. One of them uses the branch-and-price algorithm with the extended formulation and the other one is a branch-and-bound algorithm based on the compact formulation. We also implemented a primal heuristic and a pricing heuristic aiming to improve the performance of exact methods. Computational experiments shown that the extended formulation provides tighter bounds than the compact formulation. Additionally, we observed that the heuristics were relevant to accelerate the branch-and-price and the branch-and-bound algorithms, mainly the primal heuristic.