The split delivery vehicle routing problem (SDVRP) describes an interesting generalization of the classical VRP. It allows to split-up delivery volumes of single customers between different vehicles, and thus routes/ tours. It is well known that this comes with the potential to further reduce the routing costs, and therefore may provide a competitive advantage to logistics companies.

In our work, we study the SDVRP, and develop some new ideas for neighborhood search in this application. Our concepts are based on the insight that delivery volume choices influence routing decisions, and vice versa. Therefore, we particularly test ideas for the combined modification of both the routing and the volume decisions. By doing so, we extend the set of known local search techniques (neighborhood operators) for problems in which an intersection of delivery volume optimization and routing optimization is present.

Experimental investigations on instances from the literature are carried out, and the effect of the combined operators is studied. Our findings are encouraging, but at the same time, it becomes clear that the efficient implementation of the local search plays a considerable role when comparing and analyzing results.