Most solution methods for solving large vehicle routing and schedu- ling problems are based on local search. A drawback of these ap- proaches 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 los- ing 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 con- struction heuristic which finds provably optimal solutions when unre- stricted. 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.
|Place of Publication||onbekend|
|Publisher||Operational Methods for Production & Logistics (OMPL)|
|Number of pages||14|
|Publication status||Published - 2009|
|Name||BETA Working Papers|
|Publisher||Beta Research School for Operations Management and Logistics, University of Twente|
- Giant-Tour Representation
- Restricted DP
Gromicho, J., van Hoorn, J. J., Kok, A. L., & Schutten, J. M. J. (2009). Restricted dynamic programming: a flexible framework for solving realistic VRPs. (BETA Working Papers; No. 266). onbekend: Operational Methods for Production & Logistics (OMPL).