Spelling suggestions: "subject:"1. column generation"" "subject:"1. kolumn generation""
1 |
Uso de rotas elementares no CVRP / Using elementary routes to solve the CVRPPECIN, Diego Galindo 23 February 2010 (has links)
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.
|
Page generated in 0.1003 seconds