Uso de rotas elementares no CVRP

Página do item simplificado
dc.contributor.advisor1Longo, Humberto José
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/0188685041571480pt_BR
dc.contributor.referee1Longo, Humberto José
dc.contributor.referee2Meneses, Cláudio Nogueira de
dc.contributor.referee3Aragão, Marcus Vinicius Soledade Poggi de
dc.creatorPecin, Diego Galindo
dc.creator.Latteshttp://lattes.cnpq.br/7648677337334837pt_BR
dc.date.accessioned2022-12-26T12:26:26Z
dc.date.available2022-12-26T12:26:26Z
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.provenanceSubmitted by Leandro Machado (leandromachado@ufg.br) on 2022-12-19T18:31:53Z No. of bitstreams: 2 Dissertação - Diego Galindo Pecin - 2010.pdf: 548561 bytes, checksum: abc59fcfc95841c504a81621160ddb9f (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2022-12-26T12:26:25Z (GMT) No. of bitstreams: 2 Dissertação - Diego Galindo Pecin - 2010.pdf: 548561 bytes, checksum: abc59fcfc95841c504a81621160ddb9f (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceMade available in DSpace on 2022-12-26T12:26:26Z (GMT). No. of bitstreams: 2 Dissertação - Diego Galindo Pecin - 2010.pdf: 548561 bytes, checksum: abc59fcfc95841c504a81621160ddb9f (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5) Previous issue date: 2010-02-23en
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.pt_BR
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESpt_BR
dc.identifier.citationPECIN, 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.pt_BR
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/12516
dc.languageporpt_BR
dc.publisherUniversidade Federal de Goiáspt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto de Informática - INF (RMG)pt_BR
dc.publisher.initialsUFGpt_BR
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)pt_BR
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 International*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectCVRPpor
dc.subjectEnumeraçãopor
dc.subjectESPPCCpor
dc.subjectESPPRCpor
dc.subjectGeração de colunaspor
dc.subjectRotas elementarespor
dc.subjectColumn generationeng
dc.subjectCVRPeng
dc.subjectElementary routeseng
dc.subjectESPPCCeng
dc.subjectESPPRCeng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAOpt_BR
dc.titleUso de rotas elementares no CVRPpt_BR
dc.title.alternativeUsing elementary routes to solve the CVRPeng
dc.typeDissertaçãopt_BR

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Dissertação - Diego Galindo Pecin - 2010.pdf
Tamanho:
535.7 KB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

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