Logistic constraints in container loading problems: the impact of complete shipment conditions

Container loading problems (CLP), in which a set of boxes have to be loaded into containers or onto trucks, are at the core of many transportation problems. Good solutions to these packing problems are crucial for the efficient use of logistic resources. However, to produce solutions that are useful in practice, besides the basic conditions ensuring that boxes do not exceed the container dimensions and do not overlap each other, other physical and logistic constraints have to be included when solving the CLP. In this study, we focus on a special type of logistic constraint: complete shipment constraints, which ensure that either all or none of the boxes in each customer order are loaded. Although these constraints have seldom been considered in the literature, they arise very often in practice. Customers do not want to receive incomplete parts of their orders in successive deliveries and retailers do not want to have to store incomplete orders and wait until the remaining boxes arrive to deliver the orders to the customers. We include these constraints in an integer linear formulation of the CLP and develop four heuristic strategies to deal with them efficiently. An extensive computational study compares the relative performance of these strategies and shows that when a good strategy is used the impact of these constraints on the solution of the CLP is quite small.