2014-07-292010-08-102010-02-23PECIN, 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.http://repositorio.bc.ufg.br/tede/handle/tde/528This 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.application/pdfAcesso Aberto1. CVRP2. Enumeração3. ESPPCC4. ESPPRC5. Geração de colunas6. Rotas elementares1. Column generation2. CVRP3. Elementary Routes4. ESPPCC5. ESPPRCCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAODissertação