Uso de rotas elementares no CVRP

Página do item simplificado
dc.contributor.advisor1LONGO, Humberto José
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/0188685041571480por
dc.creatorPECIN, Diego Galindo
dc.creator.Latteshttp://lattes.cnpq.br/7648677337334837por
dc.date.accessioned2014-07-29T14:57:52Z
dc.date.available2010-08-10
dc.date.issued2010-02-23
dc.description.abstractThis 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.eng
dc.description.resumoEsta dissertação aborda o Problema do Caminho Elementar Mínimo com Restrição de Capacidade (ESPPCC Elementary Shortest Path Problem with a Capacity Constraint) e descreve algoritmos para a sua resolução que fazem uso de conceitos tais como Correção de Rótulos, Programação Dinâmica Bidirecional e Relaxação Decrescente do Espaço de Estados. Esses algoritmos foram usados como geradores de rotas elementares no subproblema de geração de colunas de um algoritmo BCP robusto para o CVRP. Os resultados (limites inferiores, tempo de processamento e número de nós gerados) obtidos, para algumas instâncias de teste do CVRP, são comparados aos obtidos na versão original desse algoritmo BCP, que utiliza rotas não elementares sem 3-ciclos ou 4-ciclos. Rotas elementares também são exploradas em um contexto de enumeração para o CVRP, a qual permite obter rotas (usando um critério baseado em limites e em custo reduzido) que possuem uma chance de pertencer a uma solução ótima. Se o número de rotas não for muito grande (na ordem de poucos de milhares), então todo o problema pode ser resolvido como um problema de particionamento de conjuntos contendo apenas tais rotas. Algumas vezes isso acelera o algoritmo Branch-and-Bound consideravelmente, quando comparado com estratégias tradicionais de particionamento (branching), já que muitos nós da árvore podem ser resolvidos sem a geração de novos nós.por
dc.formatapplication/pdfpor
dc.identifier.citationPECIN, 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.por
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tde/528
dc.languageporpor
dc.publisherUniversidade Federal de Goiáspor
dc.publisher.countryBRpor
dc.publisher.departmentCiências Exatas e da Terra - Ciências da Computaçãopor
dc.publisher.initialsUFGpor
dc.publisher.programMestrado em Ciência da Computaçãopor
dc.rightsAcesso Abertopor
dc.subject1. CVRPpor
dc.subject2. Enumeraçãopor
dc.subject3. ESPPCCpor
dc.subject4. ESPPRCpor
dc.subject5. Geração de colunaspor
dc.subject6. Rotas elementarespor
dc.subject1. Column generationeng
dc.subject2. CVRPeng
dc.subject3. Elementary Routeseng
dc.subject4. ESPPCCeng
dc.subject5. ESPPRCeng
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpor
dc.thumbnail.urlhttp://repositorio.bc.ufg.br/TEDE/retrieve/3073/Dissertacao%20Diego%20Galindo%20Pecin.pdf.jpg*
dc.titleUso de rotas elementares no CVRPpor
dc.title.alternativeUsing elementary routes to solve the CVRPeng
dc.typeDissertaçãopor

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Dissertacao Diego Galindo Pecin.pdf
Tamanho:
437.77 KB
Formato:
Adobe Portable Document Format
Baixar

Coleções

Mestrado em Ciência da Computação (INF)