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

32 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

Fingerprint

Vehicle routing
Vehicle Routing Problem
Dynamic programming
Dynamic Programming
Heuristics
Vehicle Scheduling
Framework
Vehicle routing problem
Computational Experiments
Local Search
Scheduling Problem
Optimal Solution
Flexibility
Scheduling
Benchmark
Restriction

Keywords

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

Cite this

@article{88ecd83cec164176b4e98133af308427,
title = "Restricted dynamic programming: A flexible framework for solving realistic VRP's.",
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.",
keywords = "VRP, IR-77727, Restricted DP, Giant-Tour Representation, METIS-278490",
author = "J. Gromicho and {van Hoorn}, J.J. and A.L. Kok and Schutten, {Johannes M.J.}",
year = "2012",
doi = "10.1016/j.cor.2011.07.002",
language = "English",
volume = "39",
pages = "902--909",
journal = "Computers & operations research",
issn = "0305-0548",
publisher = "Elsevier",
number = "5",

}

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

In: Computers & operations research, Vol. 39, No. 5, 2012, p. 902-909.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Gromicho, J.

AU - van Hoorn, J.J.

AU - Kok, A.L.

AU - Schutten, Johannes M.J.

PY - 2012

Y1 - 2012

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

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

KW - VRP

KW - IR-77727

KW - Restricted DP

KW - Giant-Tour Representation

KW - METIS-278490

U2 - 10.1016/j.cor.2011.07.002

DO - 10.1016/j.cor.2011.07.002

M3 - Article

VL - 39

SP - 902

EP - 909

JO - Computers & operations research

JF - Computers & operations research

SN - 0305-0548

IS - 5

ER -