Vehicle Routing Problem

The vehicle routing problem (VRP) is a class of problems that frequently occurs in the field of transportation logistics. The original formulation of the problem has been defined in the late 1950ies and consists of a fleet of vehicles serving a set of customers with a certain demand from a single depot. The implementation in HeuristicLab covers the capacitated problem formulation with time windows (CVRPTW). Additionally, in version 3.4 pickup and delivery formulations and multiple depots are also supported. Find more information about the supported variants in a blog article: ​http://dev.heuristiclab.com/trac/hl/core/blog/svonolfe/vrp_34.

There are several popular variants of the VRP like

• Capacitated VRP
• VRP with Time Windows
• VRP with Pickup and Delivery
• Distance constrained VRP
• Multiple Depot VRP
• VRP with Time Dependent Travel Time
• Multi-Trip VRP
• ... and much more

Benchmark instances

The following benchmark instances can be imported:

• TSPLib format (CVRP)
  • ​http://www.branchandcut.org/VRP/data/ (12-261 customers, includes optimal solution files)
  • ​http://www.rhsmith.umd.edu/faculty/bgolden/Golden.zip (~200-500 customers)
  • ​http://www.rhsmith.umd.edu/faculty/bgolden/Christofides_benchmarks.zip (50-200 customers)

• Solomon format (CVRPTW)
  • ​http://neo.lcc.uma.es/radi-aeb/WebVRP/data/instances/solomon/solomon_100.zip (100 customers)
  • ​http://www.fernuni-hagen.de/WINF/touren/inhalte/probinst.htm (200-1000 customers)
  • ​http://www.sintef.no/Projectweb/TOP/Problems/VRPTW/Solomon-benchmark (Best known qualities)

• ORLib format (CVRP)
  • ​http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/

• Li & Lim format (CVRPTW with pickups and deliveries) - only available in plugin version 3.4
  • ​http://www.sintef.no/Projectweb/TOP/Problems/PDPTW/Li--Lim-benchmark/

• Cordeau format (Multi depot CVRP / CVRPTW) - only available in plugin version 3.4
  • ​http://neo.lcc.uma.es/radi-aeb/WebVRP//data/instances/cordeau/C-mdvrp.zip
  • ​http://neo.lcc.uma.es/radi-aeb/WebVRP//data/instances/cordeau/C-mdvrptw.zip

File formats

• Optimal solution

  Route #1: 22 13 10 6 5 33 4 7
  Route #2: 1 12 2 19 20 23 14 17
  Route #3: 36 29 32 28 31 30 15
  Route #4: 3 24 9 11 27 8 25 35 18 26 34
  Route #5: 21 16
  cost 669
  

Implementing new VRP Variants in HeuristicLab

For an overview see our blog post on the new vehicle routing implementation in HeuristicLab.

Because of the variety of the VRP variants, the HeuristicLab VRP plugin is designed to be extensible and flexible. There are multiple ways of implementing a new VRP variant by extending different components of the VRP-Plugin.

The following figure provides an overview about the most important components and how they interact:

Different ways of extending the VRP

Depending on the nature of the VRP variant there are multiple ways of implementing the variant. Because many popular VRP variants are already implemented, extending the right base-variant can save a lot of implementation effort.

Three basic ways of implementing a new VRP variant are shown in the following tutorials:

• Howto: Implement a new VRP Evaluator?
  • does not require additional model data
  • does not need to optimize additional decision variables
  • interprets existing data differently
• Howto: Implement a new VRP ProblemInstance?
  • require additional model data
  • does not need to optimize additional decision variables
• Howto: Implement a new VRP Encoding?
  • need to optimize additional decision variables

Depending on the VRP variant you often need multiple extension points. For example, if you implement a new ProblemInstance you probably need to implement a new Evaluator to interpret the additional data.

The following figure contains a more detailed overview on the relationships and dependencies in the VRP design and how the components are grouped in different packages: