Algoritmos para o problema de roteamento de veículos capacitado com restrições de carregamento bidimensional

Abstract

This work addresses the Capacitated Vehicle Routing Problem with two-dimensional loading constraints. Given a central depot and a set of clients, where each demands a specific amount of items, the problem aims to define minimum cost routes for a fleet of homogeneous vehicles that performs customer service. The items have rectangular shapes, they must be transported in a way that there is no overlap between them, and in some cases, sequential loading restrictions, related to the order of visiting the customers, are required. To solve the problem, two hybrid approaches combining heuristics and Column Generation are proposed. Furthermore, the literatures Branch-and-Cut was used to solve a reformulation of the original model of the problem. The methods developed were evaluated by means of the instances used in the literature and the results were compared with those previously published. The hybrid methods achieve satisfactory results, sometimes equal to the optima known, and the Branch-and-Cut could attest to optimality for several instances.