Uso de rotas elementares no CVRP
Carregando...
Data
2010-02-23
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
This dissertation addresses the optimization of the Elementary Shortest Path Problem with
a Capacity Constraint (ESPPCC) and describes algorithms for its resolution that make use
of concepts such as Label-Setting, Bidirectional Dynamic Programming and Decremental
State Space Relaxation. These algorithms were used in a robust CVRP s Branch-and-
Cut-and-Price framework as the column generation mechanism. The resulting BCP was
used to obtain results (lower bounds, processing time and the number of branching nodes
generated) to several CVRP s test instances. These results are compared with previous
ones obtained with the original BCP, which is based on k-cycle elimination.
Elementary routes are also explored in a route enumeration context, which allows the
enumeration of all possible relevant elementary routes, i.e., all routes that have a chance
of being part of an optimal CVRP s solution. If the number of relevant routes is not too
large (say, in the range of tenths of thousands), the overall problem may be solved by
feeding a general MIP solver with a set-partition formulation containing only those routes.
If this set-partition can be solved, the optimal solution will be found and no branch will be
necessary. Sometimes this leads to very significant speedups when compared to traditional
branch strategies.
Descrição
Palavras-chave
Citação
PECIN, Diego Galindo. Using elementary routes to solve the CVRP. 2010. 80 f. Dissertação (Mestrado em Ciências Exatas e da Terra - Ciências da Computação) - Universidade Federal de Goiás, Goiânia, 2010.