O problema do caixeiro viajante com restrições de empacotamento tridimensional / The traveling salesman problem with three-dimensional loading constraints
AUTOR(ES)
Pedro Henrique Del Bianco Hokama
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
14/10/2011
RESUMO
Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática.
ASSUNTO(S)
programação por restrições otimização combinatória problema do corte de estoque programação inteira problema do caixeiro viajante traveling-salesman problem constraint programming (computer science) combinatorial optimization cutting stock problem integer programming
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=000846125Documentos Relacionados
- Rede neural recorrente com perturbação simultânea aplicada no problema do caixeiro viajante
- ALGORITMO EVOLUTIVO PARA O PROBLEMA DO CAIXEIRO VIAJANTE COM DEMANDAS HETEROGÊNEAS
- Three-dimensional cutting and packing problems and integration with vehicle routing
- ESTRATÉGIAS PARALELAS INTELIGENTES PARA O MÉTODO BRANCH-AND-BOUND APLICADAS AO PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO
- Problema de empacotamento em faixa com restrições de ordem e estabilidade