Changes between Version 3 and Version 4 of Documentation/Howto/ImplementANewVRPEncoding

Timestamp:

02/20/14 11:42:57 (10 years ago)

Author:

pfleck

Comment:

--

Documentation/Howto/ImplementANewVRPEncoding

@@ -167 +167 @@
 = Sample Foundations =
 
-In order to implement the sample we need a new {{{ProblemInstance}}} and a new {{{Evaluator}}} for the '''MultiTrip VRP''' variant. For detailed information about creating new {{{VRPInstances}}} and {{{VRPEvaluators}}} see [wiki:UsersHowtosImplementANewVRPProblemInstance How to ... implement a new VRP ProblemInstance] and [wiki:UsersHowtosImplementANewVRPEvaluator How to ... implement a new VRP Evaluator].
+In order to implement the sample we need a new {{{ProblemInstance}}} and a new {{{Evaluator}}} for the ''MultiTrip VRP'' variant. For detailed information about creating new {{{VRPInstances}}} and {{{VRPEvaluators}}} see [wiki:UsersHowtosImplementANewVRPProblemInstance How to ... implement a new VRP ProblemInstance] and [wiki:UsersHowtosImplementANewVRPEvaluator How to ... implement a new VRP Evaluator].
 
 == MultiTripVRPInstance ==
@@ -251 +251 @@
 }}}
 
-We will override more methods in the {{{MultiTripProblemInstance}}} class when we deal with '''operators''' in this tutorial later.
+We will override more methods in the {{{MultiTripProblemInstance}}} class when we deal with ''operators'' in this tutorial later.
 
 == MultiTripEvaluator ==
@@ -423 +423 @@
 == Link Encoding/Operators to VRP variants ==
 
-Because different encodings store different information, encodings are able to handle different VRP variants. Each variant specify a '''marker interface''' to indicate its "variant type" (e.g. TimeWindowedOperator). A VRP variant compatible encoding can implement this variant type (e.g. {{{GVROperator}}} implements the {{{TimeWindowedOperator}}}). This way, each encoding can specify compatible variants and implements the operators based on the encodings abilities. 
+Because different encodings store different information, encodings are able to handle different VRP variants. Each variant specify a ''marker interface'' to indicate its "variant type" (e.g. TimeWindowedOperator). A VRP variant compatible encoding can implement this variant type (e.g. {{{GVROperator}}} implements the {{{TimeWindowedOperator}}}). This way, each encoding can specify compatible variants and implements the operators based on the encodings abilities. 
 
 In order to link the compatible operators to a VRP variant, the {{{ProblemInstance}}} have to provide a list of compatible {{{Operators}}}. Because a {{{ProblemInstance}}} usually derives from a base {{{ProblemInstance}}}, it uses the operators from the base implementation and selects only the compatible ones. For instance, the {{{CVRPTWProblemInstance}}} uses the operators from the {{{CVRPProblemInstance}}} and only uses those operators which implement the {{{TimeWindowedOperator}}}.
@@ -429 +429 @@
 The following figure shows a small sample and overview:
 
-[[Image(1_MTVRP_operator_featuremodel.png, 600px)]]
-
-The {{{SingleDepotOperator}}}, {{{CapcaitatedOperator}}} and {{{TimeWindowedOperator}}} represent '''VRP variants''' or '''parts of VRP variants'''. The {{{AlbaOperator}}} implements all three of them and therefore can be used for all of them. In comparison, the {{{GVROperator}}} (not show in the diagram) does not implement {{{MultiDepotOperator}}}(also not shown) and therefore is not compatible with variants that use multiple depots.
+[[Image(1_MTVRP_operator_featuremodel.png, 800px)]]
+
+The {{{SingleDepotOperator}}}, {{{CapcaitatedOperator}}} and {{{TimeWindowedOperator}}} represent ''VRP variants'' or ''parts of VRP variants''. The {{{AlbaOperator}}} implements all three of them and therefore can be used for all of them. In comparison, the {{{GVROperator}}} (not show in the diagram) does not implement {{{MultiDepotOperator}}}(also not shown) and therefore is not compatible with variants that use multiple depots.
 
 Specific and {{{VRPProblemInstances}}} then specifies which operators are compatible. For instance the {{{CVRPProblemInstance}}} filters the operators by {{{CapacitatedOperator}}}. The {{{CVRPTWProblemInstance}}}, which derives from {{{CVRPProblemInstances}}} used the prefiltered operators and filters by {{{TimeWindowedOperator}}}: 
@@ -476 +476 @@
 }}}
 
-
 == Implementing new Creator ==
+
+The implementation of the new {{{MultiTripIterativeInsertionCreator}}} is very easy. We use the functionality of the {{{IterativeInsertionCreator}}} of the {{{PotvinEncoding}}} to create a {{{PotvinEncoding}}} and convert it with the method from the previous section of the tutorial.
+
+Note that all initial solution candidates created with no delimiters, because random delimiters would mainly yield infeasible solutions, which are hard to repair afterwards.
+
+{{{
+#!cs
+[Item("MultiTripIterativeInsertionCreator", "Creates a randomly initialized VRP solution.")]
+[StorableClass]
+public sealed class MultiTripIterativeInsertionCreator
+  : PotvinCreator, IStochasticOperator, IMultiTripOperator {
+ 
+  #region IStochasticOperator Members
+  public ILookupParameter<IRandom> RandomParameter {
+    get { return (LookupParameter<IRandom>)Parameters["Random"]; }
+  }
+  #endregion
+ 
+  [StorableConstructor]
+  private MultiTripIterativeInsertionCreator(bool deserializing)
+    : base(deserializing) { }
+ 
+  public MultiTripIterativeInsertionCreator()
+    : base() {
+    Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
+  }
+ 
+  public override IDeepCloneable Clone(Cloner cloner) {
+    return new MultiTripIterativeInsertionCreator(this, cloner);
+  }
+ 
+  private MultiTripIterativeInsertionCreator(MultiTripIterativeInsertionCreator original, Cloner cloner)
+    : base(original, cloner) {
+  }
+ 
+  public override IOperation InstrumentedApply() {
+    PotvinEncoding singleTripSolution = IterativeInsertionCreator.CreateSolution(
+      ProblemInstanceParameter.ActualValue, RandomParameter.ActualValue, false);
+ 
+    VRPToursParameter.ActualValue = MultiTripEncoding.ConvertFrom(ProblemInstanceParameter.ActualValue, singleTripSolution);
+ 
+    return base.InstrumentedApply();
+  }
+}
+}}}
+
+A more intelligent {{{Creator}}}, which implements a heuristic to place reasonable delimiters for initial solutions would be nice and would help the algorithm a lot, but is not part of this tutorial.
+
 == Implementing new Manipulator ==
+
+The {{{MultiTripManipulator}}} randomly flips a delimiter in a random tour. This is a very simple mutation and many more implementations are possible, for example to shift a delimiter within a tour. Also a more intelligent manipulators are possible, for example a manipulator who looks for good delimiter positions in long sub-tours, or one who tries to remove delimiters in short sub-tours.
+
+{{{
+#!cs
+[Item("MultiTripManipulator", "The manimulation operator which flips a random tour delimiter in a multi trip VRP.")]
+[StorableClass]
+public class MultiTripManipulator
+  : PotvinManipulator, IMultiTripOperator {
+
+  [StorableConstructor]
+  private MultiTripManipulator(bool deserializing) : base(deserializing) { }
+ 
+  public MultiTripManipulator() : base() { }
+ 
+  public override IDeepCloneable Clone(Cloner cloner) {
+    return new MultiTripManipulator(this, cloner);
+  }
+ 
+  private MultiTripManipulator(MultiTripManipulator original, Cloner cloner)
+    : base(original, cloner) {
+  }
+ 
+  protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+    var multiTripIndividual = individual as MultiTripEncoding;
+    if (multiTripIndividual != null && multiTripIndividual.Tours.Count > 0) {
+      int tour = random.Next(individual.Tours.Count);
+ 
+      if (multiTripIndividual.Tours[tour].Stops.Count > 0) {
+        int position = random.Next(multiTripIndividual.Tours[tour].Stops.Count);
+ 
+        multiTripIndividual.FlipDelimiter(tour, position);
+      }
+    }
+  }
+}
+}}}
+
 == Implement new Crossover ==
 
+To implement a new {{{Crossover}}} which only combines two sets of ''delimiters'' would not yield  good results. Therefore we implement a crossover that first performs a {{{PotvinRouteBasedCrossover}}} and afterwards copy the delimiters from the copied tour into the new replaced tour of the new solution.
+
+Unfortunately, the implementation of the crossover does not return which route was replaced, so we have to look it up first with a small helper method. Then we copy the delimiters from the old tour onto the new, replaced tour.
+
+{{{
+#!cs
+[Item("MultiTripRBX", "The RBX crossover for multi-trip VRP representations.")]
+[StorableClass]
+public class MultiTripRBX
+  : PotvinCrossover, IMultiTripOperator {
+ 
+  [StorableConstructor]
+  private MultiTripRBX(bool deserializing) : base(deserializing) { }
+ 
+  public MultiTripRBX()
+    : base() { }
+ 
+  public override IDeepCloneable Clone(Cloner cloner) {
+    return new MultiTripRBX(this, cloner);
+  }
+ 
+  private MultiTripRBX(MultiTripRBX original, Cloner cloner)
+    : base(original, cloner) {
+  }
+ 
+  private int FindReplacedTour(PotvinEncoding original, PotvinEncoding manipulated) {
+    int replacedTour = -1;
+    for (int tourIdx = 0; tourIdx < original.Tours.Count; tourIdx++) {
+      if (original.Tours[tourIdx].Stops.Count != manipulated.Tours[tourIdx].Stops.Count) {
+        replacedTour = tourIdx;
+        break;
+      }
+ 
+      for (int stopIdx = 0; stopIdx < original.Tours[tourIdx].Stops.Count; stopIdx++) {
+        if (original.Tours[tourIdx].Stops[stopIdx] != manipulated.Tours[tourIdx].Stops[stopIdx]) {
+          replacedTour = tourIdx;
+          break;
+        }
+      }
+ 
+      if (replacedTour >= 0)
+        break;
+    }
+ 
+    return replacedTour;
+  }
+ 
+  protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
+    MultiTripEncoding p1 = parent1 as MultiTripEncoding;
+    MultiTripEncoding p2 = parent2 as MultiTripEncoding;
+ 
+    PotvinEncoding child = PotvinRouteBasedCrossover.Apply(random, parent1, parent2, ProblemInstance, AllowInfeasibleSolutions.Value.Value);
+    MultiTripEncoding ch = child as MultiTripEncoding;
+ 
+    if (ch != null && p1 != null) {
+      int tourIdx = FindReplacedTour(parent2, child);
+      if (tourIdx != -1) {
+        ch.TripDelimiters[tourIdx] = p1.TripDelimiters[tourIdx];
+      }
+    }
+ 
+    return child;
+  }
+}
+}}}
+
 = Result =
+
 == Configure Algorithm ==
+
+Before we can run the {{{MultiTrip}}} variant inside an algorithm we need to configure the algorithm beforehand. This tutorial provides step by step instructions on how to setup the algorithm and load the problem instance. To avoid this procedure you could write a new {{{VRPDataInterpreter}}} (see [wiki:UsersHowtosImplementANewVRPProblemInstance How to ... implement a new VRP ProblemInstance]). In the attachments of this tutorial you also find a configured ready-to-run algorithm.
+
+1. Create a new {{{Genetic Algorithm}}} (you can chose a variant like Offspring Selection GA too, then the configuration changes slightly)
+  a. Set a new {{{Vehicle Routing Problem}}}
+  b. Set the {{{ProblemInstance}}} to a new {{{MultiTripVRPInstance}}}
+2. Configure the {{{Genetic Algorithm}}}
+  a. In the {{{Problem}}} set the {{{SolutionCreator}}} to {{{MultiTripIterativeInsertionCreator}}} (if not already set automatically)
+  b. In the {{{Algorithm Parameters}}} set the {{{Crossover}}} to {{{MultiTripRBX }}}(if you like, you can use the other {{{PotvinCrossovers}}} as well in a {{{MultiVRPSolutionCrossover}}})
+  c. Set the {{{Mutator}}} to a {{{MultiVRPSolutionManipulator}}}
+    i. Enable the {{{MultiTripManipulator}}}, {{{PotvinOneLevelExchange}}} and {{{PotvinTwoLevelExchange}}} manipulator
+    i. If you want, increase the ''propability'' of the {{{MultiTripManipulator}}} (e.g. to 2)
+  d. If you want, activate the {{{CapacityRelaxion}}} in the Analyzers
+  e. Set the MutationProbability to 25%
+  f. Set the PopulationSize to 20 (or higher for better results)
+  g. Set the Generations to 2000 (or higher for better results)
+3. Open a separate {{{Vehicle Routing Problem}}}
+  a. Open a {{{CVRP problem}}} (your own or from a library) (e.g. Augerat P-n50-k7)
+  b. Open the original {{GA ProblemInstance}}} and the {{{ProblemInstance}} from the new separate problem side by side
+  c. Copy the {{{Coordinates}}} and {{{Demands}}} to the empty {{{MultiTripVRPInstance}}} by drag and drop them
+  d. Set the remaining parameters (capacity, vehicles, ...)
+  e. Set the {{{MaxDistance}}} (e.g. to 500)
+4. Run the Algorithm
+
 == Interpretation ==
+
+To visualize the sub-tours of a vehicle use the visualization-patch from the attachments. Compared to the original CVRP solution, now the algorithm finds solutions with less vehicles.
+
+If you set the {{{MaxDistance}}} high enough, the algorithm will find a solution with only one vehicle. However the algorithm needs very long and needs a bit of luck to find the optimal vehicle usage because our mutation and crossover operators actualy does not perform well. The {{{PotvinCrossovers}}} always treat tours at whole and ignore the tour delimiters. A specialized crossover which merges small ''sub-tours'' into other tours and preserves the ''sub-tours'' would be a good solution. Still, the solutions yielded by the algorithm use less vehicles than the original CVRP variant.
+
+[[Image(2_MTVRP_result.png, 700px)]]