Algorithms for problems with loading constraints

Author(s)

Pedro Henrique Del Bianco Hokama

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2016-04-03

Examining board members

Flávio Keidi Miyazawa; Horacio Hideki Yanasse; Reinaldo Morabito; Kelly Cristina Poldi; Luis Augusto Angelotti Meira

• Advisor: Flávio Keidi Miyazawa

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 (AU)

• FAPESP's process: 11/13382-3 - Vehicle routing problem with practical constraints
• Grantee: Pedro Henrique Del Bianco Hokama
• Support Opportunities: Scholarships in Brazil - Doctorate