Branch-cut-and-price para o problema de roteamento de veículos generalizado

• Ano de defesa: 2019
• Autor(a) principal: Jefferson Willian Gouveia Monteiro
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO; Programa de Pós-Graduação em Ciência da Computação; UFMG
• Palavras-chave em Português: Problema de Roteamento de Veículos Generalizado; Problema de Roteamento de Veículos; Branch-Cut-And-Price; Computação – Teses; Problema de roteamento de veículos – Teses; Algoritmo branch-cut -and-price – Teses
• Link de acesso: http://hdl.handle.net/1843/44156

This work addresses the Generalized Vehicle Routing Problem. Given a set of customers partitioned into disjoints subsets, defined as clusters, the problem aim to find a set of routes, one per vehicle, such that each route follows the given constraints: every route starts and ends at a specific depot; the total customers’ demand satisfied by a route must not be higher than a predefined capacity; and each cluster must have its own demand satisfied in exactly one customer. The objective is to find a set of routes — such that all already defined constraints are satisfied — that minimizes the total routes cost. In order to solve this problem, we propose an exact solution with a branch-cut-and-price algorithm that explores partial elementarity of the route during the pricing algorithm. The methodology of our work is evaluated using instances from the literature and the results were compared with previous work. Our experiments showed satisfactory results, such that we were able to solve opened instances from the literature and we reduced significantly the solution time of most of them.