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

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.