Benchmark data sets for dynamic vehicle routing problems

Dr. Giselher Pankratz
Veikko Krypczyk

Last Update: 12/11/2009

 

In recent years, a number of approaches and algorithms for dynamic vehicle routing have been developed and published.

In order to be able to compare the approaches to each other, public benchmark problem instances are needed as a basis for international scientific competition. While for static vehicle routing problems a number of widely used benchmark problems are available (e.g., the Solomon instances and the Homberger problems for the VRPTW and the Li/Lim instances for the PDPTW), a similar, well-established set of benchmark instances for dynamic vehicle routing is still missing.

Instead, a wide range of different types of dynamic problem instances can be found in the literature. As a result of this heterogeneity, the reported results are not fully comparable in many cases.

By establishing this web page our research group aims at offering a platform on which people doing research on dynamic vehicle routing problems may share their benchmark instances. We would be happy if many researchers would make use of this possibility.

The following table provides information on data sets authors have made available to us so far. In each row, author names and references are provided along with a short description of the main characteristics of the respective problem instances and a link to the files for download. Some of the data sets are derivates of static routing problems like the Solomon problems or the Li&Lim problems which have been "dynamized" by adding an arrival time stamp to each of the transportation requests.

 

Author(s), see references

Problem type

 Comment

Problem size

Download/ Web-Link/
Description of file format
El-Omari, Jawad A. (2009, reference papers forthcoming) DPDPTW
  • 30 problem instances
  • Varying Effective Degree of Dynamism with Time Windows (edodtw) ranging from 0.17 to 0.70
  • Some requests are known a priori and the rest materialize over time
  • 30 vehicles are available for each instance, but not all are necessarily needed for a solution
  • The central depot has a different location for each problem instance
  • Check summary table in the description file
 58 up to 320 nodes; Check summary table in the description file

Jawad.zip

Description.pdf
Gendreau et al. (2006) DPDPTW
  • 15 instances
  • problem instances for fixed fleet size (10 and 20 vehicles, respectively)
  • Size of service area 5km x 5km
  • time stamps of request arrival added to each instance
  • format details available

up to 200 requests

 gendreau.zip
Chen et al. (2006) DVRPTW
  • 56 instances derived from the Solomon 100-node VRPTW-instances
  • the information about a request are splitting in two files per instance; first file stores time-dependent travel  times and the second file includes demand data
 100 requests

chen.zip
Fabri/ Recht (2006) DDARP
  • between 50 an 60 instances per size
  • derived from static Li & Lim PDPTW instances
  • time stamp of arrival added to each request
  • each instance defined by the contents of two files, containing geographical and request data, respectively

50 (100), 100 (200), 200 (400), 300 (600), 400 (800), 500 (1.000) requests (nodes)

fabri_recht.zip

Author´s Webpage
Pankratz (2005) DPDPTW
  • derived from the Li&Lim PDPTW instances which in turn are based on the Solomon 100-node VRPTW instances
  • time stamp of arrival added to each request
  • varying degrees of urgency and ex-ante-knowledge
 50 requests (100 nodes) DPDPTW_Instances.zip

Description

Montemanni et al. (2002, 2005) DVRPTW
  • 44 instances
  • derived from problem instances of Kilby, Taillard, Christofides/ Beasley and Fisher
  • format details and  details about the soloution status (e.g. exact or heuristic solution) are available
 50-199 requests

montemanni.zip

Author´s Webpage

Branke et al. (2005) DVRP
  • instances derived from the OR-library of Beasly  (instances for different problem types available)
  • time stamp indicating request arrival assigned to each request

up to
1.000 requests

 Link to OR-Library of Beasley
Lackner (2004) DVRPTW
  • 56 problem instances based on 56 Solomon 100-node VRPTW instances
  • request announcement times are defined in seperate file
  • varying degrees of dynamism (10 up to 90 percent of the request have a time of arrival which is later than the start time (0)
 50 requests (100 nodes) lackner.zip
Mitrovic-Minic et al. (2004, 2004a) DPDPTW
  • 90 problem instances (30 instances per size)
  • each problem instance covers a request stream over 10 hours, service area: 60 km x 60 km
  • no capacity constraints
 100, 500, 1.000 requests

mitrovic-minic.zip

Author´s Webpage

Attanasio et al. (2004) DDARP
  • using the problem instances of Cordeau et al. (2003)
  • 26 problem instances (6 of them are real cases)
  • the information about the request arrival are calculated by the program and not stored in the problem files

24-144 requests

 Author´s Webpage

 

If you use dynamic vehicle routing problem data not listed here and if you are willing to share it, please send us a short note. Also, if you you would like to report errors on this web site, feel free to contact us.
If you are interested in problem instances for static vehicle routing problems, please refer to the following pages:

http://www.fernuni-hagen.de/WINF/touren/inhalte/probinst.htm

http://www.sintef.no/static/am/opti/projects/top/vrp/benchmarks.html

 

References:
Attanasio, A.; Cordeau, J. F.; Ghiani, G.; Laporte, G. (2004): ”Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem“, in Parallel Computer 30, 377-387

Branke, J.; Middendorf, M; Noeth, G; Dessouky, M. (2005): “Waiting Strategies for Dynamic Vehicle Routing”, in Transportation Science, Vol. 39, No. 3, August 2005, pp. 298-312       

Chen, H.-K.; Hsueh, C.-F.; Chang, M.-S. (2006): “The real-time time-dependent vehicle routing problem” in Transportation Research Part E: Logistics and Transportation Review, Volume 42, Issue 5, September 2006, Pages 383-408

Christofides, N; Beasley, J (1984): “The period routing problem,” Networks, vol. 14, pp. 237–256, 1984

Cordeau, Jean-Francois; Laporte, Gilbert (2003): "A tabu search heuristic for the static multi-vehicle dial-a-ride problem"

Fabri, A.; Recht, P. (2006): “On dynamic pickup and delivery vehicle routing with several time windows and waiting times”, in: Transportation Research Part B: Methodological, Volume 40, Issue 4, May 2006, Pages: 335-350

Fisher, M.; Jakumar, R.; vanWassenhove, L (1981): “A generalized assignment heuristic for vehicle routing,” Networks, vol. 11, pp. 109–124, 1981

Gendreau, M; Guertina, F; Potvina, J-Y; Séguin, R (2006): “Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries”, Transportation Research Part C: Emerging Technologies, Volume 14, Issue 3, June 2006, Pages 157-174      

Kilby, P; Prosser, P; Shaw,P (1988):  “Dynamic VRPs: A study of scenarios” Technical Report APES-06-1998, University of Strathclyde, U.K., 1998

Lackner, A. (2004): “Dynamische Tourenplanung mit ausgewählten Metaheuristiken“, in Göttinger Wirtschaftsinformatik, Herausgeber: J. Biethahn, M. Schumann, Band 47

Li, H; Lim, A: “A Metaheuristic for the Pickup and Delivery Problem with Time Windows”, National University of Singapore, 2001

Mitrovic-Minic, S.; Laporte, G. (2004): “Waiting strategies for the dynamic pickup and delivery problem with time windows”, in Transportation Research Part B: Methodological, Volume 38, Issue 7, August 2004, Pages: 635-655

Mitrovic-Minic, S.; Krishnamurti, R.; Laporte, G. (2004a): “Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows”, in Transportation Research Part B: Methodological, Volume 38, Issue 8, September 2004, Pages 669-685

Montemanni, R.; Gambardella, L. M.; Rizzoli, A. E.; Donati, A. V. (2002): “A new algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System”, in Journal of Combinatorial Optimization, Springer Netherlands, Volume 10, Number 4, Pages:  327 – 343

Montemanni, R.; Gambardella, L. M.; Rizzoli, A. E.; Donati, A. V. (2005): „Ant Colony Optimisation for Vehicle Routing Problem from theory to applications“ (2005)

Pankratz, G. (2005): “Dynamic Vehicle Routing by Means of a Genetic Algorithm”, in: International Journal of Physical Distribution and Logistics Management (IJPDLM) Vol. 35 No. 5, 2005, S. 362-383