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

Timestamp:

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

Author:

pfleck

Comment:

--

Documentation/Howto/ImplementANewVRPEvaluator

@@ -1 +1 @@
 work in progress ...
 
-= How to … implement a new VRP Evaluator =
+= How to ... implement a new VRP Evaluator =
 
 == Goals ==
@@ -14 +14 @@
 
 In 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}}}.
+
+== Prerequisites ==
+
+Before 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)].
+
+The plugin need an additional dependency onto the {{{HeuristicLab.Problems.VehicleRouting}}} plugin. Finally, the plugin should look like this:
+{{{
+#!cs
+[Plugin("HeuristicLab.PollutionRoutingProblem", "1.0.0.0")]
+[PluginFile("HeuristicLab.PollutionRoutingProblem.dll", PluginFileType.Assembly)]
+[PluginDependency("HeuristicLab.Problems.VehicleRouting", "3.4")]
+public class PollutionRoutingProblemPlugin : PluginBase {
+}
+}}}
+
+In addition you will need references onto following HeuristicLab assemblies:
+ - HeuristicLab.Collections
+ - HeuristicLab.Common
+ - HeuristicLab.Core
+ - HeuristicLab.Data
+ - HeuristicLab.Operators
+ - HeuristicLab.Optimization
+ - HeuristicLab.Parameters
+ - HeuristicLab.Persistence
+ - '''HeuristicLab.Problems.VehicleRouting'''
+
+= Foundations =
+
+== VRPEvaluator ==
+
+In 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. 
+
+[[Image(1-PRP_EvaluatorEvaluation.png)]]
+
+The {{{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.
+
+In 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. 
+
+== Incremental Evaluation ==
+
+Some 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.
+
+In 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.
+
+[[Image(2-InsertionInfoSample.png)]]
+
+[[Image(3-PRP_EvaluatorEvaluationInfo.png)]]
+
+In 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.
+