Restricted dynamic programming: a flexible framework for solving realistic VRPs

J. Gromicho, J.J. van Hoorn, A.L. Kok, Johannes M.J. Schutten

Research output: Book/ReportReportProfessional

123 Downloads (Pure)

Abstract

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.
Original languageUndefined
Place of Publicationonbekend
PublisherOperational Methods for Production & Logistics (OMPL)
Number of pages14
ISBN (Print)9789038615301
Publication statusPublished - 2009

Publication series

NameBETA Working Papers
PublisherBeta Research School for Operations Management and Logistics, University of Twente
No.266

Keywords

  • METIS-256612
  • IR-70220
  • Giant-Tour Representation
  • Restricted DP
  • VRP

Cite this

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).