Enhanced solution representations for vehicle routing problems with split deliveries

In this study, we investigate a forest-based solution representation for split delivery vehicle routing problems (SDVRPs), which have several practical applications and are among the most difficult vehicle routing problems. The new solution representation fully reflects the nature of split delivery, and can help reduce the search space when used in heuristic algorithms. Based on the forest structure, we devise three neighborhood search operators. To highlight the effectiveness of this solution representation, we integrate these operators into a standard tabu search framework. We conduct extensive experiments on three main SDVRPs addressed in the literature: The basic SDVRP, the multidepot SDVRP, and the SDVRP with time windows. The experimental results show that the new forest-based solution representation is particularly effective in designing and implementing neighborhood operators, and that our new approach outperforms state-of-the-art algorithms on standard datasets.