Made available in DSpace on 2014-07-29T14:57:52Z (GMT). No. of bitstreams: 1
Dissertacao Diego Galindo Pecin.pdf: 448272 bytes, checksum: 755b351108c1082bc3bdb084b7add6ec (MD5)
Previous issue date: 2010-02-23 / 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. / Esta 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tde/528 |
| Date | 23 February 2010 |
| Creators | PECIN, Diego Galindo |
| Contributors | LONGO, Humberto José |
| Publisher | Universidade Federal de Goiás, Mestrado em Ciência da Computação, UFG, BR, Ciências Exatas e da Terra - Ciências da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0088 seconds