Texto completo
| |
| Autor(es): |
Pedro Henrique Del Bianco Hokama
Número total de Autores: 1
|
| Tipo de documento: | Tese de Doutorado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2016-04-03 |
| Membros da banca: |
Flávio Keidi Miyazawa;
Horacio Hideki Yanasse;
Reinaldo Morabito;
Kelly Cristina Poldi;
Luis Augusto Angelotti Meira
|
| Orientador: | Flávio Keidi Miyazawa |
| Resumo | |
Nesta tese investigamos classes de problemas com restrições de empacotamento. Três diferentes problemas foram investigados, e algoritmos foram propostos para cada um deles. O primeiro é o problema de roteamento de veículos com restrições de empacotamento, em que um conjunto de veículos parte de um depósito e deve entregar a demanda de itens de todos os clientes. Cada veículo possui um contêiner retangular, e cada cliente deseja receber uma diversidade de itens também retangulares. Consideramos tanto o caso em que contêineres e itens são bidimensionais, como o caso em que eles são tridimensional. Em cada rota realizada por um veículo é preciso encontrar uma forma de empacotar os itens de todos os clientes dentro do contêiner, de modo que a cada visita, a retirada dos itens daquele cliente possa ser realizada sem que os outros itens precisem ser movidos. O objetivo geral do problema é minimizar o deslocamento total dos veículos. O segundo é o problema online de empacotamento de círculos em contêineres. Nesse problema devemos empacotar círculos em recipientes retangulares. Os círculos chegam de forma online, ou seja, cada círculo que chega deve ser empacotado, e não se sabe a priori quais os tamanhos dos círculos que virão. O objetivo é minimizar o número de contêineres utilizados. O terceiro é o problema da mochila bidimensional com conflitos. Nesse problema é dado um conjunto de itens e um recipiente, bidimensionais e retangulares, sendo que cada item possui um valor associado e alguns pares de itens são conflitantes, ou seja, não podem estar simultaneamente dentro do recipiente. O objetivo do problema é escolher um subconjunto de valor máximo dos itens, mas que seja possível empacotar esses itens dentro do recipiente. A tese é composta por três artigos, cada um dedicado a um dos problemas. Em todos eles, diferentes técnicas de projeto de algoritmos foram utilizadas de forma integrada, dentre as principais estão: programação linear inteira, programação por restrições, heurísticas, meta-heurísticas e algoritmos aproximados. Além das contribuições de cada um dos artigos, o conjunto da obra evidencia a eficiência da integração das técnicas citadas, abrindo o caminho para que as metodologias estudadas possam ser aplicadas a outros problemas (AU) | |
| Processo FAPESP: | 11/13382-3 - Problema de roteamento de veículos com restrições práticas |
| Beneficiário: | Pedro Henrique Del Bianco Hokama |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |