Changes between Version 2 and Version 3 of Documentation/Howto/ImplementANewVRPEvaluator

01/28/14 14:16:44 (7 years ago)



  • Documentation/Howto/ImplementANewVRPEvaluator

    v2 v3  
    11work in progress ...
    3 = How to implement a new VRP Evaluator =
     3= How to ... implement a new VRP Evaluator =
    55== Goals ==
    1515In this tutorial the PRP is based on the ''Capacitated Vehicle Routing Problem (CVRP)''. To keep the tutorial as simple as possible only the current mass of a vehicle is considered. The current mass of a vehicle is computable by its current position in a tour. Therefore no additional model data is required and the implementation of the PRP is possible by only extending the {{{VRPEvaluator}}}.
     17== Prerequisites ==
     19Before you start, make sure you have the latest version of the HeuristicLab source code ready. Then create a new plugin called {{{HeuristicLab.PollutionRoutingProblem}}}. For additional help for creating a new plugin, see [wiki:UsersHowtosImplementPluginsStepByStep How to ... create HeuristicLab plugins (step by step)].
     21The plugin need an additional dependency onto the {{{HeuristicLab.Problems.VehicleRouting}}} plugin. Finally, the plugin should look like this:
     24[Plugin("HeuristicLab.PollutionRoutingProblem", "")]
     25[PluginFile("HeuristicLab.PollutionRoutingProblem.dll", PluginFileType.Assembly)]
     26[PluginDependency("HeuristicLab.Problems.VehicleRouting", "3.4")]
     27public class PollutionRoutingProblemPlugin : PluginBase {
     31In addition you will need references onto following HeuristicLab assemblies:
     32 - HeuristicLab.Collections
     33 - HeuristicLab.Common
     34 - HeuristicLab.Core
     35 - HeuristicLab.Data
     36 - HeuristicLab.Operators
     37 - HeuristicLab.Optimization
     38 - HeuristicLab.Parameters
     39 - HeuristicLab.Persistence
     40 - '''HeuristicLab.Problems.VehicleRouting'''
     42= Foundations =
     44== VRPEvaluator ==
     46In order to implement a new VRP variant by extending a {{{VRPEvaluator}}} you need a basic understanding of how a {{{VRPEvaluator}}} works and how it is used.
     50The {{{VRPEvaluator}}} evaluates a VRP solution by calling the {{{Evaluate()}}} Method. A VRP solution contains multiple tours for a given problem instance. In the evaluation process a {{{VRPEvaluation}}} object is created. In the {{{VRPEvaluation}}} object the quality, penalty and other values of the solution candidate are stored.
     52In order to evaluate an entire solution candidate, each tour is evaluated separately. To accomplish this, the abstract method {{{EvaluateTour()}}} is called for each tour. The quality and other values of each tour are summarized into the {{{VRPEvaluation}}}. This is usually done by calculating the distance of each stop and multiplies it with a factor to obtain the quality. If constraints are violated, the penalty value is increased analogously.
     54== Incremental Evaluation ==
     56Some algorithms, like the ''Tabu Search'', work incremental and therefore require a ''move-based evaluation''. A ''move'' corresponds to the insertion of an additional stop into an existing tour. Then, the change of quality is used to determine the further proceeding of the algorithm.
     58In order to enable incremental evaluation, additional information is created in the original evaluation process, namely the {{{InsertionInfo}}}. The {{{InsertionInfo}}} itself contains a list of {{{TourInsertionInfo}}}, which itself contains a list of {{{StopInsertionInfo}}}. These correspond to the solution candidate itself, one tour and one stop in a tour.
     64In the {{{VRPEvaluator}}} the {{{EvaluateTourInsertionCosts()}}} method determine the change in quality (the costs) by inserting an additional stop between two existing stops of a tour. This is usually done by calculating the difference of the distance between the new three stops and the original two stops.