The delivery of goods to car factories is a challenging problem. The French car manufacturer Renault is facing daily a complex truck loading problem where various goods must be packed into a truck such that they fulfill different constraints. As trucks can deliver goods to different factories on the same tour, classes of items have been defined, where a class is associated with a delivery point. The consideration of these classes in addition to large standard deviations over the sizes of the items are new features in the packing literature. Because of the problem structure and of the computation time limit constraint imposed by practitioners, it will be shown that exact algorithms are not appropriate from a practical standpoint. We propose efficient metaheuristics to tackle this problem. First, in contrast with the classical literature, the proposed tabu search relies on the joint use of different types of moves (an efficient diversification mechanism is also proposed to enhance its performance). Then, the recombination operator used in the developed genetic algorithm takes into account all the problem features and is able to build well-balanced offspring solutions. Finally, within the framework of ant algorithms, the benefit of an unconventional decision selection mechanism is discussed. An extension of the problem is proposed at the end, which consists in tackling all the instances within a common time limit. In this context, it will be showed that a combination of the algorithms is the most powerful strategy.