de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Packing a Trunk - Now with a Twist!

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44373

Eisenbrand,  Friedrich
Discrete Optimization, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44464

Funke,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44737

Karrenbauer,  Andreas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45275

Reichel,  Joachim
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45414

Schömer,  Elmar
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Eisenbrand, F., Funke, S., Karrenbauer, A., Reichel, J., & Schömer, E. (2007). Packing a Trunk - Now with a Twist! International Journal of Computational Geometry and Applications, 17(5), 505-527. doi:10.1142/S021819590700246X.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2172-6
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.