Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/44156
Type: | Dissertação |
Title: | Branch-cut-and-price para o problema de roteamento de veículos generalizado |
Authors: | Jefferson Willian Gouveia Monteiro |
First Advisor: | Geraldo Robson Mateus |
First Co-advisor: | Douglas Guimarães Macharet |
First Referee: | Mayron César de Oliveira Moreira |
Second Referee: | Alexandre Salles da Cunha |
Abstract: | Esta dissertação dedica-se ao estudo do Problema de Roteamento de Veículos Generalizado. Dado um conjunto de consumidores particionado em subconjuntos disjuntos, denominados clusters, o problema consiste em encontrar um conjunto de rotas, uma para cada veículo, tal que cada rota atenda às seguintes restrições: toda rota deve começar e terminar em um depósito específico; a demanda total dos consumidores atendidos em cada rota não deve exceder uma determinada capacidade; e cada cluster deve ter sua demanda atendida em exatamente um consumidor. O objetivo é encontrar um conjunto de rotas — que devem atender às restrições citadas — que minimize a soma dos custos de todas as rotas. Para a resolução do problema, propusemos uma solução exata utilizando um algoritmo branch-cut-and-price que explora a elementariedade parcial da rota durante o algoritmo de precificação. A metodologia foi avaliada utilizando instâncias da literatura para o problema, e os resultados foram comparados aos trabalhos já publicados. Os experimentos apresentaram resultados satisfatórios, de tal forma que conseguimos resolver instâncias que estavam em aberto e reduzimos significativamente o tempo de solução da maior parte delas. |
Abstract: | 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. |
Subject: | Computação – Teses Problema de roteamento de veículos – Teses Algoritmo branch-cut -and-price – Teses |
language: | por |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/44156 |
Issue Date: | 3-May-2019 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
dissertacao_final.pdf | 1.12 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.