Packing Problems with Delivery Order Restrictions

• Grant number: 08/03973-1
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: August 01, 2008
• End date: January 31, 2009
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Eduardo Candido Xavier
• Grantee: Felipe Andrade Holanda
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In this project we are interested in investigating problems of Packing with restrictions arising from issues on vehicle routing. In the Vehicle Routing Problem we assume that customers have a set of demands of two-dimensional items that must be supplied by a facility. A certain number of trucks must deliver all the customers' demands. In this case, the problem is to compute minimum-cost routes that leave the facility and cover all the customers' demands. Besides this problem, we must find for each route, a packing of the items requested by the route's customers, satisfying a withdrawing restriction. That is, when withdrawing items of a route's client,there must not be any items from another client (who is ahead in route) obstructing the truck's exit door. Generating good packing considering this restriction is a fundamental part of algorithms whose objective is the minimization of the costs of the generated routes. Our goal is the study and the implementation of algorithms to solve the problem of two-dimensional packing with delivery order restrictions on the route.