Restricted Dynamic Programming: Evaluating an Advanced Construction Algorithm in Solving Vehicle Routing Problems

The purpose of this thesis is to evaluate a new and advanced approach for solving Vehicle Routing Problems (VRPs). This approach is based on an exact solution method, dynamic programming, and by restricting its state space, it becomes a heuristic method which could be used in practice. We compared this restricted dynamic programming (RDP) algorithm on both classical and more realistic VRPs with a simple construction algorithm, the savings heuristic. We showed that, while the computation times of the RDP algorithm were exceptionally higher, it did not always gave better solutions than fast construction heuristics and that the claim that the RDP algorithm competes with state of the art local search solutions when more realistic constraints are considered should be rejected. By using two k-opt local search methods to improve the construction solutions, we also discovered that a better construction solution leads to better solutions after the improvement phase. However, because the RDP algorithm could not provide us with high quality construction solutions within reasonable computing time, we can conclude that this new and advanced solution method cannot compete with other known solution methods for the VRP.