Uso de rotas elementares no CVRP
Nenhuma Miniatura disponível
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
CVRP , Enumeração , ESPPCC , ESPPRC , Geração de colunas , Rotas elementares , Column generation , CVRP , Elementary routes , ESPPCC , ESPPRC
Citação
PECIN, D. Uso de rotas elementares no CVRP. 2010. 79 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2010.