Scheduling deliveries in vehicles with multiple compartments

Vehicles with multiple compartments are used, among others, for distribution to convenience stores. Based on the convenience stores paradigm we propose optimization models for two possible cargo space layouts and explore their characteristics through computational experiments with randomly generated data sets. In a small real data set an optimal solution of one of the models requires fewer vehicles because compartment capacities are utilized more tightly. We develop and test approximation schemes based on Lagrangean Relaxation that generate good feasible solutions in reasonable time. The good quality of the solutions is guaranteed by the gap between their value and the Lagrangean Relaxation bound. These schemes could be valuable for large real applications.