Restricted dynamic programming: A flexible framework for solving realistic VRP's

Most solution methods for solving large vehicle routing and scheduling problems are based on local search. A drawback of these approaches is that they are designed and optimized for specific types of vehicle routing problems (VRPs). As a consequence, it is hard to adapt these solution methods to handle new restrictions, without losing solution quality. We present a new framework for solving VRPs that can handle a wide range of different types of VRPs. Within this framework, restricted dynamic programming is applied to the VRP through the giant-tour representation. This algorithm is a construction heuristic which finds provably optimal solutions when unrestricted. We demonstrate the flexibility of the framework for a wide variety of different types of VRPs. The quality of solutions found by the framework is demonstrated by solving a set of benchmark instances for the capacitated VRP. The computational experiments show that restricted dynamic programming, which is a construction heuristic, develops routes of high quality. Therefore, this new framework for solving VRPs is highly valuable in practice.