6533b830fe1ef96bd1297914

RESEARCH PRODUCT

Trunk Packing Revisited

Elmar SchömerErnst AlthausTobias BaumannKai Werth

subject

Linear programming relaxationCombinatoricsDiscrete mathematicsPacking problemsDiscretizationLinear programmingBranch and priceStructure (category theory)Approximation algorithmBranch and cutMathematics

description

For trunk packing problems only few approximation schemes are known, mostly designed for the European standard DIN 70020 [6] with equally sized boxes [8, 9, 11, 12]. In this paper two discretized approaches for the US standard SAE J1100 [10] are presented, which make use of different box sizes. An exact branch-and-bound algorithm for weighted independent sets on graphs is given, using the special structure of the SAE standard. Another branch-and-bound packing algorithm using linear programs is presented. With these algorithms axis-oriented packings of different box sizes in an arbitrary trunk geometry can be computed efficiently.

yearjournalcountryeditionlanguage
2007-06-26
https://doi.org/10.1007/978-3-540-72845-0_32