Matheurísticas em modelos estendidos

Abstract

In this work, we study matheuristic approaches to find good feasible solutions for two variants of the profitable vehicle routing problem, namely the capacitated profitable tour problem and the vehicle routing problem with private fleet and common carrier. We propose an extended model and a branch-and-price algorithm, with heuristics applied in the column generation phase. We propose the use of a Relax-and-Fix and a Large Neighborhood Search as matheuristics to find valid primal bounds by solving a column selection problem that can be reduced to the disjunctively constrained knapsack problem. The results indicate that heuristic of pricing and the use of the matheuristics within selected nodes of the branch-and-price tree can obtain promising results.