MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Eisenbrand, Friedrich
Funke, Stefan
Karrenbauer, Andreas
Reichel, Joachim
Schömer, Elmar		dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Funke, Stefan
Schömer, Elmar
Editor(s):
Spencer, Stephen N.dblp
Not MPII Editor(s):
Spencer, Stephen N.
BibTeX cite key*:
Reichel2005
Title, Booktitle
Title*:
Packing a Trunk - now with a Twist!
Booktitle*:
Proceedings SPM 2005 ACM Symposium on Solid and Physical Modeling
Event, URLs
Conference URL::
http://www.gvu.gatech.edu/%7Ejarek/spm/
Downloading URL:
Event Address*:
Cambridge, USA
Language:
English
Event Date*
(no longer used):
Organization:
Association for Computing Machinery (ACM)
Event Start Date:
13 June 2005
Event End Date:
15 June 2005
Publisher
Name*:
ACM
URL:
http://www.acm.org/
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
June
Pages:
197-206
Year*:
2005
VG Wort Pages:
ISBN/ISSN:
1-59593-015-9
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
In an industry project with a German car manufacturer we
are faced with the challenge of placing a maximum number of
uniform rigid rectangular boxes in the interior of a car
trunk. The problem is of practical importance due to a
European industry norm which requires car manufacturers
to state the trunk volume according to this measure.

No really satisfactory automated solution for this problem has been
known in the past. In spite of its NP hardness, combinatorial
optimization techniques, which consider only grid-aligned placements,
produce solutions which are very close to the one achievable by a
human expert in several hours of tedious work. The remaining gap is
mostly due to the constraints imposed by the chosen grid.

In this paper we present a new approach which combines the grid-based
combinatorial method with \emph{Simulated Annealing} on a continuous
model. This allows us to explore arbitrary orientations and placements
of boxes, hence closing the gap even further, and -- in some cases --
even surpass the manual expert solution.

The implemented software system allows our industrial partner to
incorporate the trunk volume in a very early stage of the car design
process without relying on a repeated and cumbersome manual evaluation
of the volume.
Keywords:
Trunk Packing, Car Design, Simulated Annealing, Combinatorial Optimization, Computational Geometry
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
popular
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Reichel2005,
AUTHOR = {Eisenbrand, Friedrich and Funke, Stefan and Karrenbauer, Andreas and Reichel, Joachim and Sch{\"o}mer, Elmar},
 EDITOR = {Spencer, Stephen N.},
 TITLE = {Packing a Trunk - now with a Twist!},
 BOOKTITLE = {Proceedings SPM 2005 ACM Symposium on Solid and Physical Modeling},
 PUBLISHER = {ACM},
 YEAR = {2005},
 ORGANIZATION = {Association for Computing Machinery (ACM)},
 PAGES = {197--206},
 ADDRESS = {Cambridge, USA},
 MONTH = {June},
 ISBN = {1-59593-015-9},
}

Entry last modified by Joachim Reichel, 03/10/2006
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Joachim Reichel		Created
10/31/2005 13:20:55
Revisions
2.
1.
0.

Editor(s)
Joachim Reichel
Christine Kiesel
Joachim Reichel

Edit Dates
03/10/2006 05:48:56 PM
09.11.2005 11:15:28
10/31/2005 01:20:55 PM