The Multi-Compartment Vehicle Routing Problem with TimeWindows and Split Deliveries

This thesis considers an extension of the Vehicle Routing Problem with Time Windows and Split Deliveries, in which customers demand different types of products. These products must be transported within the right temperature regime and without contaminating other products. To do so, the vehicles can be equipped with bulkheads to divide the vehicle in several compartments, specified by one of the pre-defined vehicle configurations. To solve this problem, we propose an Adaptive Large Neighborhood Search framework, in which the ruin and recreate principle is used for creating the routes, with an order related removal heuristic. This heuristic is specifically designed for this problem and often outperforms the other removal heuristics by improving solutions towards the end of the search. The feasibility of each insertion by one of the insertion heuristics, is checked based on the product related requirements with our developed algorithm. We propose a heuristic method to check per possible vehicle configuration and per temperature regime present in the compartments of that configuration whether or not a feasible assignment to the compartments exists. Computational experiments on both real-life and generated instances show that the heuristic is able to provide an optimal solution for many instances in reasonable time, compared to the much longer runtime which is required to solve the problem with CPLEX. The experiments also show that the overall routing solution can be better when an optimal solution is not always found, compared to when an optimal solution is found for each of these feasibility checks. Finally, we present a method that consolidates the smaller parts of which the customer demand consists into larger groups each of which is transported in one vehicle. This method consolidates in such a way that the routing algorithm can find routes for which vehicles are more efficiently filled, which is demonstrated by the experiments.