This paper addresses a periodic vehicle routing problem for the determination of delivery patterns (DPs) using multi-compartment vehicles. The presented problem happens in grocery distribution.

Store delivery policies and the resulting vehicle routes for supplying stores from distribution centers reveal a significant saving potential. Retailers usually apply repetitive weekly DPs for the supply of stores. DPs define the number of visits for each customer in which the complete weekly demand is satisfied. In grocery distribution, stores demand different product categories from different temperature zones. The demand for each category has to be fulfilled and therefore individual DPs need to be defined. Nowadays, retailers have the option of using multi-compartment vehicles. They enable the joint transportation of different temperature zones as their loading space can be split in compartments. The joint delivery directly affects the weekly DPs. For instance, instead of a separate delivery of a single product category twice per week, stores can receive this segment jointly with the daily deliveries of fresh products. This impacts both the delivery frequencies and the daily routing. These decisions are highly interrelated and need to be solved simultaneously. We therefore derive decision-relevant costs and propose a Periodic Multi-Compartment Vehicle Routing Problem (PMCVRP).

The PMCVRP is solved using a specialized heuristic. It combines an adaptive search for the determination of delivery patterns with a large neighborhood search for the routing. In numerical tests and a case study, we show the effectiveness of our approach and the impact of the use of MCVs on DPs.