Regensburg 2010 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

SOE: Fachverband Physik sozio-ökonomischer Systeme

SOE 3: Traffic Dynamics, Urban and Regional Systems II

SOE 3.4: Vortrag

Montag, 22. März 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.