$$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}$$
X
INFORMAÇÕES SOBRE DIREITOS AUTORAIS


As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.

A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.

A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.

A violação de direitos autorais é passível de sanções civis e penais.
Coleção Digital

Avançada


Estatísticas | Formato DC |



Título: LIMITES INFERIORES FORTES PARA O CVRP VIA GERAÇÃO DE COLUNAS E CORTES
Autor: MARCELO MALTA RODRIGUES MARTINS
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Colaborador(es):  MARCUS VINICIUS S P DE ARAGAO - ORIENTADOR
RAFAEL MARTINELLI PINTO - COORIENTADOR

Nº do Conteudo: 28669
Catalogação:  11/01/2017 Idioma(s):  INGLÊS - ESTADOS UNIDOS
Tipo:  TEXTO Subtipo:  TESE
Natureza:  PUBLICAÇÃO ACADÊMICA
Nota:  Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]:  https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=28669@1
Referência [en]:  https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=28669@2
Referência DOI:  https://doi.org/10.17771/PUCRio.acad.28669

Resumo:
O Capacitated Vehicle Routing Problems (CVRP) é uma versão seminal do problema de roteamento de veículos, um clássico problema em Pesquisa Operacional. Introduzido por Dantzig e Ramser, o CVRP generaliza o Traveling Salesman Problem (TSP) e o Bin Packing Problem (BPP). Problemas de roteamento aparecem em diversas aplicações no mundo real, geralmente no contexto de diminuição de custos, emissão de poluentes ou energia dentro das atividades relacionadas ao transporte. De fato, estes custos podem ficar entre 5 por cento e 20 por cento do custo total do produto. Por isto, qualquer economia nos custos de roteamento pode ser relevante. O CVRP é definido da seguinte maneira: dado um conjunto de n mais 1 localidades - um depósito e n clientes - as distâncias entre cada par de localidades, as demandas inteiras associadas a cada cliente e a capacidade do veículo, quer se obter um conjunto de rotas que comecem no depósito, visitem cada cliente apenas uma vez e retornem ao depósito. A distâncias percorrida deve ser mínima e a soma das demandas dos clientes presentes em cada rota não pode exceder a capacidade do veículo. Este trabalho considera que o número de veículos disponíveis é conhecido. Algoritmos no estado da arte para encontrar e provar que uma solução é ótima, para o CVRP, calculam seus limites inferiores através de geração de colunas e depois os melhoram com a adição de planos de corte. As colunas geradas podem ser rotas elementares, onde obrigatoriamente cada cliente é visitado somente uma vez, ou uma relaxação desta obrigação com o uso de q-rotas ou ng-rotas, que diferem apenas em como é permitido que um cliente seja revisitado dentro de uma mesma rota. Já os cortes são classificados como robustos, aquele que são definidos sobre as variáveis dos arcos, e não robustos (ou fortes), que são os definidos sobre as variáveis do problema mestre da geração de colunas. O termo robusto, usado acima, se refere a como a adição do corte modifica a eficiência da resolução do problema de pricing. Além do descrito acima, o algoritmo exato mais eficiente para o CVRP usa muitos elementos, o que torna sua replicação uma tarefa difícil e longa. O objetivo deste trabalho é determinar o quão bom são os limites inferiores obtidos com geração de colunas de ng-rotas usando apenas cortes de capacidade e os recentes subset row cuts de memória limitada. Além disto, é avaliado o ganho conseguido com a consideração deste tipo de corte forte e as combinações com outras técnicas, como por exemplo, Decremental Space State Relaxation (DSSR), Completion Bounds, ng-rotas e cortes de capacidade sobre a formulação de Set Partitioning. Extensos experimentos computacionais são apresentados em conjunto com a análise dos resultados obtidos.

Descrição Arquivo
NA ÍNTEGRA  PDF
Logo maxwell Agora você pode usar seu login do SAU no Maxwell!!
Fechar Janela



* Esqueceu a senha:
Senha SAU, clique aqui
Senha Maxwell, clique aqui