Parts | Days | Selection | Search | Downloads | Help
SOE: Fachverband Physik sozio-ökonomischer Systeme
SOE 3: Traffic Dynamics, Urban and Regional Systems II
SOE 3.4: Talk
Monday, March 22, 2010, 11:15–11:30, H44
Optimization of packing problems — •Johannes J. Schneider, Andre Müller, and Elmar Schömer — Center for Computational Research Methods in Natural Sciences, Johannes Gutenberg University of Mainz, Staudinger Weg 7, 55099 Mainz, Germany
Everybody knows this problem: goods just bought in the supermarket have to be packed in the rear trunk of the car, often while considering constraints, like fruit which must not be squashed. Analogously, we face packing problems when we have to pack suitcases when going on holiday. Also in logistics, packing problems occur: the traveling salesperson has to pack the truck in a way corresponding to the sequence of the customers on the tour. Further packing problems occur in textile industry as well as in wood- and metal-working industry.
In this talk, a multidisperse packing problem shall be considered, in which hard disks with different sizes are packed in a circular environment in a way that the radius of the circumcircle around the disks is minimum. We present our packing algorithm, with which we were able to beat and to match all world records established in an international contest in competition between 155 groups from 32 countries. Our packing algorithm was rated by the Time Magazine to be one of the 50 best inventions of the year 2009.