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

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

Research output: Contribution to journalArticleAcademicpeer-review

33 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)902-909
Number of pages14
JournalComputers & operations research
Volume39
Issue number5
DOIs
Publication statusPublished - 2012

Keywords

  • VRP
  • IR-77727
  • Restricted DP
  • Giant-Tour Representation
  • METIS-278490

Fingerprint Dive into the research topics of 'Restricted dynamic programming: A flexible framework for solving realistic VRP's.'. Together they form a unique fingerprint.

  • Cite this