Scheduling deliveries in vehicles with multiple compartments

Vehicles with multiple compartments are used, among others, for distribution to convenience stores. Based on the convenience srores paradigm we propose optimazation models for two possible cargp 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 quaranteed by the gap between their value and the Lagrangean Relaxation bound. These schemes could be valuable for large real applications.