This paper deals with the container loading problem which involves the selection of a subset of boxes,
each box with a given volume, such that they fit in a single container and maximize its volume
utilization subject to orientation and stability constraints. We propose a multi-start random constructive
heuristic with a load arrangement that is based on maximal cuboids that fit in given empty spaces. Each
instance is adaptively evaluated by a set of criteria, and at each step of the construction process one
maximal cuboid is chosen probabilistically from a restricted list of candidates. In order to enhance the
flexibility in the construction of a solution, a probabilistic reduction on such cuboids is allowed.
Computational tests on several instances from the literature show that the proposed method performs
better than other approaches.