An Evolutionary based Decomposition Strategy for the Multi-Depot Heterogeneous Vehicle Routing Problem with Time Windows

In this thesis we decompose a large Vehicle Routing Problem with multiple depots, a heterogeneous fleet and customers with time windows. The process, which we call 'multi-process route optimiza­tion', first splits the VRP over smaller sub-problems and then solves these sub-problems simultaneously using multiple processors. The goal is to obtain solutions of similar quality in substantially less time. We develop an evolutionary based decomposition method with a fitness function that considers both the running time and solution quality. Computational experiments on real world problem instances show that solutions can be obtained in substantially less time. After a few iterations we can even obtain better solutions than without decomposition. After a few iterations of splitting and solving, we alternate our splitting method with the Sweep method to create more diversity in our splits.