We consider a Rich Vehicle Routing Problem (RVRP) occurring at a large German food retailer. The company has to distribute the goods from a central warehouse to a number of supermarkets with respect to various constraints on a daily basis. To accomplish this task, it engages several carriers which supply the necessary amount of trucks and drivers. The payment of the carriers is regulated by distinct transport tariffs for the supply of each supermarket and each commodity class. Latter results from four different transport temperatures (deep-frozen to non-chilled) and leads to the usage of partitioned vehicles with up to three compartments alike. Since rearranging of the cargo on the load bed is prohibited plus unloading is only possible from the rear end and a compartment is solely accessible if the previous ones are empty a Last-In-First-Out loading policy is needed. Furthermore, the splitting of deliveries is allowed and backhauls are required to return used loading aids. To the best of our knowledge, there is no scientific and exact approach combining those properties.

The described problem is modeled as a mixed integer program (MIP) using the three-index vehicle flow formulation. The MIP is solved by a branch-and-cut algorithm using the solver Gurobi. Known valid inequalities as well as derived problem specific valid inequalities are used to strengthen the linear relaxation and to break the formulation-inherent symmetry. Computational tests show that small instances of this challenging and practice-oriented RVRP can be solved to optimality within reasonable time.