Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.gvu.gatech.edu/%7Ejarek/spm/

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 01:20:55 PM
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section