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

78 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).
Gromicho, J. ; van Hoorn, J.J. ; Kok, A.L. ; Schutten, Johannes M.J. / Restricted dynamic programming: a flexible framework for solving realistic VRPs. onbekend : Operational Methods for Production & Logistics (OMPL), 2009. 14 p. (BETA Working Papers; 266).
@book{034db86bf7a34736976cab39d0cdb1fa,
title = "Restricted dynamic programming: a flexible framework for solving realistic VRPs",
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.",
keywords = "METIS-256612, IR-70220, Giant-Tour Representation, Restricted DP, VRP",
author = "J. Gromicho and {van Hoorn}, J.J. and A.L. Kok and Schutten, {Johannes M.J.}",
year = "2009",
language = "Undefined",
isbn = "9789038615301",
series = "BETA Working Papers",
publisher = "Operational Methods for Production & Logistics (OMPL)",
number = "266",

}

Gromicho, J, van Hoorn, JJ, Kok, AL & Schutten, JMJ 2009, Restricted dynamic programming: a flexible framework for solving realistic VRPs. BETA Working Papers, no. 266, Operational Methods for Production & Logistics (OMPL), onbekend.

Restricted dynamic programming: a flexible framework for solving realistic VRPs. / Gromicho, J.; van Hoorn, J.J.; Kok, A.L.; Schutten, Johannes M.J.

onbekend : Operational Methods for Production & Logistics (OMPL), 2009. 14 p. (BETA Working Papers; No. 266).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Restricted dynamic programming: a flexible framework for solving realistic VRPs

AU - Gromicho, J.

AU - van Hoorn, J.J.

AU - Kok, A.L.

AU - Schutten, Johannes M.J.

PY - 2009

Y1 - 2009

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

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

KW - METIS-256612

KW - IR-70220

KW - Giant-Tour Representation

KW - Restricted DP

KW - VRP

M3 - Report

SN - 9789038615301

T3 - BETA Working Papers

BT - Restricted dynamic programming: a flexible framework for solving realistic VRPs

PB - Operational Methods for Production & Logistics (OMPL)

CY - onbekend

ER -

Gromicho J, van Hoorn JJ, Kok AL, Schutten JMJ. Restricted dynamic programming: a flexible framework for solving realistic VRPs. onbekend: Operational Methods for Production & Logistics (OMPL), 2009. 14 p. (BETA Working Papers; 266).