Orientador: Flávio Keidi Miyazawa

Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação

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...

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

Abstract: In this thesis we investigate classes of problems with loading constraints. Three different problems were investigated, and algorithms were proposed for each one of them. The first is the vehicle routing problem with loading constraints, in which a set of vehicles departs from a depot and...

Abstract: In this thesis we investigate classes of problems with loading constraints. Three different problems were investigated, and algorithms were proposed for each one of them. The first is the vehicle routing problem with loading constraints, in which a set of vehicles departs from a depot and have to deliver the items demands of all clients. Each vehicle has a rectangular container (bin), and each client must receive some rectangular items. We consider both cases, in which bin and items are two-dimensional or three-dimensional. In each route, it is necessary to find a packing of all clients' items in the bin. This packing has to be done in such a way that, in each visit, the unloading of the current client's items can be performed without moving the remaining items. The goal is to minimize the total travel distance of the vehicles. The second is the online circle packing problem. In this problem we have to pack circles in rectangular bins. The circles are delivered online, that is, each arrived circle has to be packed, and the sizes of future circles is unkwown. The goal is to minimize the number of used bins. The third is the two-dimensional disjunctively constrained knapsack problem, in which a bin and a set of items, rectangular and two-dimensional, are given. Each item has an associated value and some pairs of items are forbidden to be packed together. The goal is to choose a subset of items, with maximum value, that can be packed in the given bin. The thesis is composed of three articles, each one dedicated to one of the problems. Different techniques of algorithm design were used combined, such as: integer linear programing, constraint programming, heuristics, meta-heuristics and approximated algorithms. Besides the contribution of each individual article, efficiency of the combination of cited techniques is shown, considering that they might provide a good strategy for solving other problems

Requisitos do sistema: Software para leitura de arquivo em PDF