Changes between Version 9 and Version 10 of Documentation/Reference/VehicleRoutingProblem


Ignore:
Timestamp:
07/01/14 09:34:10 (5 years ago)
Author:
abeham
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Reference/VehicleRoutingProblem

    v9 v10  
    22The vehicle routing problem (VRP) is a class of problems that frequently occurs in the field of transportation logistics. The original formulation of the problem
    33has 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.
     4
     5There are several popular variants of the VRP like
     6 - Capacitated VRP
     7 - VRP with Time Windows
     8 - VRP with Pickup and Delivery
     9 - Distance constrained VRP
     10 - Multiple Depot VRP
     11 - VRP with Time Dependent Travel Time
     12 - Multi-Trip VRP
     13 - ... and much more
    414
    515== Benchmark instances ==
     
    3646}}}
    3747
     48= Implementing new VRP Variants in HeuristicLab =
     49
     50For an overview see our blog post on the [/blog/category/VehicleRoutingProblem new vehicle routing implementation] in HeuristicLab.
     51
     52Because 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.
     53
     54The following figure provides an overview about the most important components and how they interact:
     55
     56[[Image(1_StaticVrpOverview_Easy.png)]]
     57
     58== Different ways of extending the VRP ==
     59
     60Depending 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.
     61
     62Three basic ways of implementing a new VRP variant are shown in the following tutorials:
     63
     64 - [[Documentation/Howto/Implement a New VRP Evaluator|Howto: Implement a new VRP Evaluator]]
     65  * does not require additional model data
     66  * does not need to optimize additional decision variables
     67  * interprets existing data differently
     68 - [[Documentation/Howto/Implement a New VRP Problem Instance|Howto: Implement a new VRP ProblemInstance]]
     69  * require additional model data
     70  * does not need to optimize additional decision variables
     71 - [[Documentation/Howto/Implement a New VRP Encoding|Howto: Implement a new VRP Encoding]]
     72  * need to optimize additional decision variables
     73
     74Depending 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.
     75
     76= miscellaneous =
     77
     78The following figure contains a more detailed overview on how derived components integrate in the VRP design and how the components are grouped in different packages:
     79
     80[[Image(2_StaticVrpOverview_Full.png, 100%)]]
    3881