Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Packing a Trunk

MPG-Autoren
/persons/resource/persons44373

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

/persons/resource/persons44464

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

/persons/resource/persons45275

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

/persons/resource/persons45414

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

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Eisenbrand, F., Funke, S., Reichel, J., & Schömer, E. (2003). Packing a Trunk. In Algorithms - ESA 2003 (pp. 618-629). Berlin: Springer.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-2DB7-C
Zusammenfassung
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to pack as many identical boxes of size $4 × 2 × 1$ units as possible into the interior of the trunk. This measure is important for car manufacturers, because it is a standard in the European Union. First, we prove that a natural formal variant of this problem is NP-complete. Further, we use a combination of integer linear programming techniques and heuristics that exploit the geometric structure to attack this problem. Our experiments show that for all considered instances, we can get very close to the optimal solution in reasonable time.