Full text
| |
| Author(s): |
Jefferson Luiz Moisés da Silveira
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2013-02-10 |
| Examining board members: |
Eduardo Candido Xavier;
Cid Carvalho de Souza;
Victor Fernandes Cavalcante;
Reinaldo Morabito;
Horacio Hideki Yanasse
|
| Advisor: | Eduardo Candido Xavier |
| Abstract | |
In this work we are interested in packing and routing problems. Assuming P ? NP, we have that there are no efficient algorithms to deal with such problems. Besides exact algorithms, two approaches to solve such problems are Approximation Algorithms and Heuristics. In this thesis we show algorithms using these three approaches for both packing and routing problems. The first two addressed problems are generalizations of classical packing problems: The Two Dimensional Knapsack problem and the Strip Packing problem. These problems were generalized by adding constraints on the way the items can be inserted/removed into/from the bin (These constraints appear in the context of routing problems). The third problem is combination of packing and routing problems. It is a generalization of the classical Pickup and Delivery problem. We propose the first approximation results for some packing problems. Besides that, we present some practical algorithms for the third problem. The heuristics were assessed through computational experiments by comparing their results with exact algorithms (AU) | |
| FAPESP's process: | 11/08563-9 - Algorithms for Packing Problems with Unloading Constraints |
| Grantee: | Jefferson Luiz Moisés da Silveira |
| Support Opportunities: | Scholarships in Brazil - Doctorate |