Uso de rotas elementares no CVRP

• Ano de defesa: 2010
• Autor(a) principal: PECIN, Diego Galindo
• Orientador(a): LONGO, Humberto José
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Goiás
• Programa de Pós-Graduação: Mestrado em Ciência da Computação
• Departamento: Ciências Exatas e da Terra - Ciências da Computação
• País: BR
• Palavras-chave em Português: 1. CVRP; 2. Enumeração; 3. ESPPCC; 4. ESPPRC; 5. Geração de colunas; 6. Rotas elementares
• Palavras-chave em Inglês: 1. Column generation; 2. CVRP; 3. Elementary Routes; 4. ESPPCC; 5. ESPPRC
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tde/528

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.