Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs	(revision 4370)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs	(revision 4376)
@@ -28,9 +28,10 @@
 using HeuristicLab.Problems.VehicleRouting.Encodings.General;
 using HeuristicLab.Problems.VehicleRouting.Interfaces;
+using HeuristicLab.Problems.VehicleRouting.Variants;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
   [Item("AlbaEncoding", "Represents an Alba encoding of VRP solutions. It is implemented as described in Alba, E. and Dorronsoro, B. (2004). Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms.")]
   [StorableClass]
-  public class AlbaEncoding : PermutationEncoding {   
+  public class AlbaEncoding : PermutationEncoding, ISingleDepotEncoding, ITimeWindowedEncoding, IHeterogenousCapacitatedEncoding  {   
     #region IVRPEncoding Members
     public override List<Tour> GetTours() {
@@ -60,8 +61,27 @@
     #endregion
 
+    #region IHeterogenousCapacitatedEncoding Members
+
+    public int GetVehicleAssignment(int tour) {
+      int vehicleAssignment = -1;
+      Tour currentTour = GetTours()[tour];
+
+      int lastStop = currentTour.Stops[
+        currentTour.Stops.Count - 1] - 1;
+
+      int lastStopIndex = this.IndexOf(lastStop);
+
+      if (lastStopIndex == this.Length - 1)
+        vehicleAssignment = this.ProblemInstance.Vehicles.Value - 1;
+      else
+        vehicleAssignment = this[lastStopIndex + 1] - this.ProblemInstance.Cities.Value;
+
+      return vehicleAssignment;
+    }
+    #endregion
+
     public override IDeepCloneable Clone(HeuristicLab.Common.Cloner cloner) {
       AlbaEncoding clone = new AlbaEncoding(
-        new Permutation(this.PermutationType, this.array), 
-        (IVRPProblemInstance)cloner.Clone(ProblemInstance));
+        new Permutation(this.PermutationType, this.array), ProblemInstance);
       cloner.RegisterClonedObject(this, clone);
       clone.readOnly = readOnly;
@@ -103,4 +123,52 @@
         instance);
     }
+
+    public static AlbaEncoding ConvertFrom(IVRPEncoding encoding, IVRPProblemInstance instance) {
+      List<Tour> tours = encoding.GetTours();
+
+      int cities = 0;
+      foreach (Tour tour in tours) {
+        cities += tour.Stops.Count;
+      }
+
+      int emptyVehicles = instance.Vehicles.Value - tours.Count;
+
+      int[] array = new int[cities + tours.Count + emptyVehicles - 1];
+      int delimiter = 0;
+      int arrayIndex = 0;
+      
+      foreach (Tour tour in tours) {
+        foreach (int city in tour.Stops) {
+          array[arrayIndex] = city - 1;
+          arrayIndex++;
+        }
+
+        if (arrayIndex != array.Length) {
+          if (encoding is IHeterogenousCapacitatedEncoding) {
+            array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
+          } else {
+            array[arrayIndex] = cities + delimiter;
+          }
+          
+          delimiter++;
+          arrayIndex++;
+        }
+      }
+
+      for (int i = 0; i < emptyVehicles - 1; i++) {
+        if (encoding is IHeterogenousCapacitatedEncoding) {
+          array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
+        } else {
+          array[arrayIndex] = cities + delimiter;
+        }
+
+        delimiter++;
+        arrayIndex++;
+      }
+
+      AlbaEncoding solution = new AlbaEncoding(new Permutation(PermutationTypes.RelativeUndirected, new IntArray(array)), instance);
+
+      return solution;
+    }
   }
 }
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Crossovers/AlbaCrossover.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Crossovers/AlbaCrossover.cs	(revision 4370)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Crossovers/AlbaCrossover.cs	(revision 4376)
@@ -53,8 +53,7 @@
         IVRPEncoding solution = ParentsParameter.ActualValue[i];
 
-        /*if (!(solution is AlbaEncoding)) {
-          parents[i] = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value,
-            DistanceMatrixParameter);
-        } else*/ {
+        if (!(solution is AlbaEncoding)) {
+          parents[i] = AlbaEncoding.ConvertFrom(solution, ProblemInstance);
+        } else {
           parents[i] = solution;
         }
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Manipulators/AlbaManipulator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Manipulators/AlbaManipulator.cs	(revision 4370)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Manipulators/AlbaManipulator.cs	(revision 4376)
@@ -62,5 +62,5 @@
       IVRPEncoding solution = VRPToursParameter.ActualValue;
       if (!(solution is AlbaEncoding)) {
-        //VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value, DistanceMatrixParameter);
+        VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, ProblemInstance);
       }
 
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Moves/AlbaMoveGenerator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Moves/AlbaMoveGenerator.cs	(revision 4370)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Moves/AlbaMoveGenerator.cs	(revision 4376)
@@ -43,6 +43,5 @@
       IVRPEncoding solution = VRPToursParameter.ActualValue;
       if (!(solution is AlbaEncoding)) {
-        //VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value,
-        //  DistanceMatrixParameter);
+        VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, ProblemInstance);
       }
       
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs	(revision 4370)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs	(revision 4376)
@@ -71,12 +71,4 @@
     protected IVRPProblemInstance ProblemInstance { get; set; }
 
-    public override IDeepCloneable Clone(Cloner cloner) {
-      TourEncoding clone = (TourEncoding)base.Clone(cloner);
-
-      clone.ProblemInstance = (IVRPProblemInstance)cloner.Clone(ProblemInstance);
-
-      return clone;
-    }
-
     public TourEncoding(IVRPProblemInstance problemInstance) {
       Tours = new ItemList<Tour>();
@@ -87,5 +79,25 @@
     [StorableConstructor]
     protected TourEncoding(bool serializing)
-      : base() {
+      : base(serializing) {
+    }
+
+    public static void ConvertFrom(IVRPEncoding encoding, TourEncoding solution, IVRPProblemInstance problemInstance) {
+      solution.Tours = new ItemList<Tour>(encoding.GetTours());
+    }
+
+    public static void ConvertFrom(List<int> route, TourEncoding solution) {
+      solution.Tours = new ItemList<Tour>();
+
+      Tour tour = new Tour();
+      for (int i = 0; i < route.Count; i++) {
+        if (route[i] == 0) {
+          if (tour.Stops.Count > 0) {
+            solution.Tours.Add(tour);
+            tour = new Tour();
+          }
+        } else {
+          tour.Stops.Add(route[i]);
+        }
+      }
     }
   }
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinCrossover.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinCrossover.cs	(revision 4376)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinCrossover.cs	(revision 4376)
@@ -0,0 +1,142 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using HeuristicLab.Optimization;
+using System.Collections.Generic;
+using HeuristicLab.Problems.VehicleRouting.Encodings.General;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  [Item("PotvinCrossover", "A VRP crossover operation.")]
+  [StorableClass]
+  public abstract class PotvinCrossover : VRPCrossover, IStochasticOperator, IPotvinOperator {
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
+    }
+
+    [StorableConstructor]
+    protected PotvinCrossover(bool deserializing) : base(deserializing) { }
+
+    public PotvinCrossover() {
+      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
+    }
+
+    protected abstract PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2);
+
+    protected bool FindInsertionPlace(PotvinEncoding individual, int city, out int route, out int place) {
+      return individual.FindInsertionPlace(
+        city, -1, out route, out place);
+    }
+
+    protected Tour FindRoute(PotvinEncoding solution, int city) {
+      Tour found = null;
+
+      foreach (Tour tour in solution.Tours) {
+        if (tour.Stops.Contains(city)) {
+          found = tour;
+          break;
+        }
+      }
+
+      return found;
+    }
+
+    protected bool Repair(IRandom random, PotvinEncoding solution, Tour newTour) {
+      bool success = true;
+      
+      //remove duplicates from new tour      
+      for (int i = 0; i < newTour.Stops.Count; i++) {
+        for (int j = 0; j < newTour.Stops.Count; j++) {
+          if (newTour.Stops[i] == newTour.Stops[j] && i != j) {
+            if (random.NextDouble() < 0.5)
+              newTour.Stops[i] = 0;
+            else
+              newTour.Stops[j] = 0;
+          }
+        }
+      }
+      while (newTour.Stops.Contains(0))
+        newTour.Stops.Remove(0);
+
+      //remove duplicates from old tours
+      for (int i = 0; i < newTour.Stops.Count; i++) {
+        foreach (Tour tour in solution.Tours) {
+          if (tour != newTour && tour.Stops.Contains(newTour.Stops[i])) {
+            tour.Stops.Remove(newTour.Stops[i]);
+          }
+        }
+      }
+
+      //remove empty tours
+      List<Tour> toBeDeleted = new List<Tour>();
+      foreach (Tour tour in solution.Tours) {
+        if (tour.Stops.Count == 0)
+          toBeDeleted.Add(tour);
+      }
+      foreach (Tour tour in toBeDeleted) {
+        solution.Tours.Remove(tour);
+      }
+
+      //route unrouted vehicles
+      int index = 0;
+      while (index < solution.Unrouted.Count && success) {
+        int unrouted = solution.Unrouted[index];
+
+        int route, place;
+        if(FindInsertionPlace(solution, unrouted, out route, out place)) {
+          solution.Tours[route].Stops.Insert(place, unrouted);
+        } else {
+          success = false;
+        }
+
+        index++;
+      }
+
+      for (int i = 0; i < index; i++)
+        solution.Unrouted.RemoveAt(0);
+
+      return success;
+    }
+
+    public override IOperation Apply() {
+      ItemArray<IVRPEncoding> parents = new ItemArray<IVRPEncoding>(ParentsParameter.ActualValue.Length);
+      for (int i = 0; i < ParentsParameter.ActualValue.Length; i++) {
+        IVRPEncoding solution = ParentsParameter.ActualValue[i];
+
+        if (!(solution is PotvinEncoding)) {
+          parents[i] = PotvinEncoding.ConvertFrom(solution, ProblemInstance);
+        } else {
+          parents[i] = solution;
+        }
+      }
+      ParentsParameter.ActualValue = parents;
+
+      ChildParameter.ActualValue = Crossover(RandomParameter.ActualValue, parents[0] as PotvinEncoding, parents[1] as PotvinEncoding);
+
+      return base.Apply();
+    }
+  }
+}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs	(revision 4376)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs	(revision 4376)
@@ -0,0 +1,64 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  [Item("PotvinRouteBasedCrossover", "The RBX crossover for a VRP representations.  It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.")]
+  [StorableClass]
+  public sealed class PotvinRouteBasedCrossover : PotvinCrossover {
+    [StorableConstructor]
+    private PotvinRouteBasedCrossover(bool deserializing) : base(deserializing) { }
+
+    public PotvinRouteBasedCrossover()
+      : base() { }
+     
+    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
+      PotvinEncoding child = parent2.Clone() as PotvinEncoding;
+
+      int tourParent1 = random.Next(parent1.Tours.Count);
+      Tour replacing = parent1.Tours[tourParent1].Clone() as Tour;
+
+      int tourParent2 = random.Next(child.Tours.Count);
+      Tour replaced = child.Tours[tourParent2];
+
+      child.Tours.Remove(replaced);
+      child.Tours.Add(replacing);
+
+      foreach (int city in replaced.Stops)
+        if (FindRoute(child, city) == null && !child.Unrouted.Contains(city))
+          child.Unrouted.Add(city);
+
+      if (Repair(random, child, replacing))
+        return child;
+      else {
+        if(random.NextDouble() < 0.5)
+          return parent1.Clone() as PotvinEncoding;
+        else
+          return parent2.Clone() as PotvinEncoding;
+      }
+    }
+  }
+}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs	(revision 4376)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs	(revision 4376)
@@ -0,0 +1,80 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  [Item("PotvinSequenceBasedCrossover", "The SBX crossover for a VRP representations.  It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.")]
+  [StorableClass]
+  public sealed class PotvinSequenceBasedCrossover : PotvinCrossover {
+    [StorableConstructor]
+    private PotvinSequenceBasedCrossover(bool deserializing) : base(deserializing) { }
+
+    public PotvinSequenceBasedCrossover()
+      : base() { }
+        
+    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
+      PotvinEncoding child = parent1.Clone() as PotvinEncoding;
+      Tour newTour = new Tour();
+
+      int cities = ProblemInstance.Cities.Value;
+
+      int breakPoint1 = random.Next(1, cities + 1);
+      Tour tour1 = FindRoute(child, breakPoint1);
+      breakPoint1 = tour1.Stops.IndexOf(breakPoint1);
+
+      for (int i = 0; i < breakPoint1; i++)
+        newTour.Stops.Add(tour1.Stops[i]);
+
+      int breakPoint2 = random.Next(1, cities + 1);
+      Tour tour2 = FindRoute(parent2, breakPoint2);
+      breakPoint2 = tour2.Stops.IndexOf(breakPoint2);
+
+      for (int i = breakPoint2; i < tour2.Stops.Count; i++)
+        newTour.Stops.Add(tour2.Stops[i]);
+
+      child.Tours.Remove(tour1);
+      child.Tours.Add(newTour);
+
+      foreach (int city in tour1.Stops)
+        if (FindRoute(child, city) == null && !child.Unrouted.Contains(city))
+          child.Unrouted.Add(city);
+
+      foreach (int city in tour2.Stops)
+        if (FindRoute(child, city) == null && !child.Unrouted.Contains(city))
+          child.Unrouted.Add(city);
+
+      if (ProblemInstance.Feasible(newTour) &&
+          Repair(random, child, newTour)) {
+        return child;
+      } else {
+        if (random.NextDouble() < 0.5)
+          return parent1.Clone() as PotvinEncoding;
+        else
+          return parent2.Clone() as PotvinEncoding;
+      }
+    }
+  }
+}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/IPotvinOperator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/IPotvinOperator.cs	(revision 4376)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/IPotvinOperator.cs	(revision 4376)
@@ -0,0 +1,37 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Core;
+using HeuristicLab.Parameters;
+using HeuristicLab.Operators;
+using HeuristicLab.Problems.VehicleRouting.Variants;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  public interface IPotvinOperator : 
+    ISingleDepotOperator, IHomogenousCapacitatedOperator, ITimeWindowedOperator {    
+  }
+}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinLocalSearchManipulator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinLocalSearchManipulator.cs	(revision 4376)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinLocalSearchManipulator.cs	(revision 4376)
@@ -0,0 +1,132 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using System.Collections.Generic;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  [Item("PotvinLocalSearchManipulator", "The LSM operator which manipulates a VRP representation.  It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.")]
+  [StorableClass]
+  public sealed class PotvinLocalSearchManipulator : PotvinManipulator {
+    public IValueParameter<IntValue> Iterations {
+      get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
+    }
+
+    [StorableConstructor]
+    private PotvinLocalSearchManipulator(bool deserializing) : base(deserializing) { }
+
+    public PotvinLocalSearchManipulator() : base() {
+      Parameters.Add(new ValueParameter<IntValue>("Iterations", "The number of max iterations.", new IntValue(100)));
+    }
+
+    private bool FindBetterInsertionPlace(
+      PotvinEncoding individual, int tour, int city, int length,
+      out int insertionTour, out int insertionPlace) {
+      bool insertionFound = false;
+      insertionTour = -1;
+      insertionPlace = 1;
+
+      List<int> toBeDeleted = individual.Tours[tour].Stops.GetRange(city, length);
+      double distance = individual.GetTourLength(individual.Tours[tour]);
+      individual.Tours[tour].Stops.RemoveRange(city, length);
+      double removalBenefit = distance - individual.GetTourLength(individual.Tours[tour]);
+
+      int currentTour = 0;
+      while (currentTour < individual.Tours.Count && !insertionFound) {
+        int currentCity = 0;
+        while (currentCity <= individual.Tours[currentTour].Stops.Count && !insertionFound) {
+          distance = individual.GetTourLength(individual.Tours[currentTour]);
+          individual.Tours[currentTour].Stops.InsertRange(currentCity, toBeDeleted);
+          if (ProblemInstance.Feasible(individual.Tours[currentTour])) {
+            double lengthIncrease =
+              individual.GetTourLength(individual.Tours[currentTour]) - distance;
+            if (removalBenefit > lengthIncrease) {
+              insertionTour = currentTour;
+              insertionPlace = currentCity;
+
+              insertionFound = true;
+            }
+          }
+          individual.Tours[currentTour].Stops.RemoveRange(currentCity, length);
+          
+          currentCity++;
+        }
+        currentTour++;
+      }
+
+      individual.Tours[tour].Stops.InsertRange(city, toBeDeleted);
+
+      return insertionFound;
+    }
+
+    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+      //only apply to feasible individuals
+      if (ProblemInstance.Feasible(individual)) {
+        bool insertionFound;
+        int iterations = 0;
+
+        do {
+          insertionFound = false;
+          int length = 3;
+          while (length > 0 && !insertionFound) {
+            int tour = 0;
+            while (tour < individual.Tours.Count && !insertionFound) {
+              int city = 0;
+              while (city <= individual.Tours[tour].Stops.Count - length && !insertionFound) {
+                int insertionTour, insertionPlace;
+                if (FindBetterInsertionPlace(individual, tour, city, length,
+                 out insertionTour, out insertionPlace)) {
+                  insertionFound = true;
+
+                  List<int> toBeInserted = individual.Tours[tour].Stops.GetRange(city, length);
+
+                  individual.Tours[tour].Stops.RemoveRange(city, length);
+                  individual.Tours[insertionTour].Stops.InsertRange(
+                    insertionPlace,
+                    toBeInserted); 
+                }
+                city++;
+              }
+              tour++;
+            }
+            length--;
+          }
+          iterations++;
+        } while (insertionFound && 
+          iterations < Iterations.Value.Value);
+
+        IList<Tour> toBeRemoved = new List<Tour>();
+        foreach (Tour tour in individual.Tours) {
+          if (tour.Stops.Count == 0)
+            toBeRemoved.Add(tour);
+        }
+
+        foreach (Tour tour in toBeRemoved) {
+          individual.Tours.Remove(tour);
+        }
+      }
+    }
+  }
+}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinManipulator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinManipulator.cs	(revision 4376)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinManipulator.cs	(revision 4376)
@@ -0,0 +1,91 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using HeuristicLab.Optimization;
+using HeuristicLab.Problems.VehicleRouting.Encodings.General;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  [Item("PotvinManipulator", "A VRP manipulation operation.")]
+  [StorableClass]
+  public abstract class PotvinManipulator : VRPManipulator, IStochasticOperator, IPotvinOperator {
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
+    }
+
+    [StorableConstructor]
+    protected PotvinManipulator(bool deserializing) : base(deserializing) { }
+
+    public PotvinManipulator() {
+      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
+    }
+
+    protected abstract void Manipulate(IRandom random, PotvinEncoding individual);
+
+    protected int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
+      int tourIndex = -1;
+
+      double sum = 0.0;
+      double[] probabilities = new double[individual.Tours.Count];
+      for (int i = 0; i < individual.Tours.Count; i++) {
+        probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)ProblemInstance.Cities.Value);
+        sum += probabilities[i];
+      }
+
+      for (int i = 0; i < probabilities.Length; i++)
+        probabilities[i] = probabilities[i] / sum;
+
+      double rand = random.NextDouble();
+      double cumulatedProbabilities = 0.0;
+      int index = 0;
+      while (tourIndex == -1 && index < probabilities.Length) {
+        if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])
+          tourIndex = index;
+
+        cumulatedProbabilities += probabilities[index];
+        index++;
+      }
+
+      return tourIndex;
+    }
+
+    protected bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, out int route, out int place) {
+      return individual.FindInsertionPlace(
+        city, routeToAvoid, out route, out place);
+    }
+    
+    public override IOperation Apply() {
+      IVRPEncoding solution = VRPToursParameter.ActualValue;
+      if (!(solution is PotvinEncoding)) {
+        VRPToursParameter.ActualValue = PotvinEncoding.ConvertFrom(solution, ProblemInstance);
+      }
+      
+      Manipulate(RandomParameter.ActualValue, VRPToursParameter.ActualValue as PotvinEncoding);
+
+      return base.Apply();
+    }
+  }
+}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinOneLevelExchangeManipulator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinOneLevelExchangeManipulator.cs	(revision 4376)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinOneLevelExchangeManipulator.cs	(revision 4376)
@@ -0,0 +1,65 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using System.Collections.Generic;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  [Item("PotvinOneLevelExchangeMainpulator", "The 1M operator which manipulates a VRP representation.  It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.")]
+  [StorableClass]
+  public sealed class PotvinOneLevelExchangeMainpulator : PotvinManipulator {
+    [StorableConstructor]
+    private PotvinOneLevelExchangeMainpulator(bool deserializing) : base(deserializing) { }
+
+    public PotvinOneLevelExchangeMainpulator() : base() { }
+    
+    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+      int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
+      Tour route1 =
+        individual.Tours[selectedIndex];
+
+      List<int> replaced = new List<int>();
+      for (int i = 0; i < route1.Stops.Count; i++) {
+        int insertedRoute, insertedPlace;
+
+        if (FindInsertionPlace(individual, route1.Stops[i], selectedIndex, out insertedRoute, out insertedPlace)) {
+          individual.Tours[insertedRoute].Stops.Insert(insertedPlace, route1.Stops[i]);
+          replaced.Add(route1.Stops[i]);
+        }
+      }
+
+      route1.Stops.RemoveAll(
+        new System.Predicate<int>( 
+          delegate(int val) {
+            return (replaced.Contains(val)); 
+          }
+        )
+      );
+
+      if (route1.Stops.Count == 0)
+        individual.Tours.Remove(route1);
+    }
+  }
+}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinTwoLevelExchangeManipulator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinTwoLevelExchangeManipulator.cs	(revision 4376)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinTwoLevelExchangeManipulator.cs	(revision 4376)
@@ -0,0 +1,76 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using System.Collections.Generic;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  [Item("PotvinTwoLevelExchangeManipulator", "The 2M operator which manipulates a VRP representation.  It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.")]
+  [StorableClass]
+  public sealed class PotvinTwoLevelExchangeManipulator : PotvinManipulator {
+    [StorableConstructor]
+    private PotvinTwoLevelExchangeManipulator(bool deserializing) : base(deserializing) { }
+
+    public PotvinTwoLevelExchangeManipulator() : base() { }
+    
+    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+      int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
+      Tour route1 =
+        individual.Tours[selectedIndex];
+
+      for (int customer1Position = 0; customer1Position < route1.Stops.Count; customer1Position++) {
+        foreach (Tour tour in individual.Tours) {
+          if (tour != route1) {
+            for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) {
+              int customer1 = route1.Stops[customer1Position];
+              int customer2 = tour.Stops[customer2Position];
+
+              //customer1 can be feasibly inserted at the location of customer2
+              tour.Stops[customer2Position] = customer1;
+              if (ProblemInstance.Feasible(tour)) {
+                int route, place;
+                if (FindInsertionPlace(individual,
+                  customer2, selectedIndex, out route, out place)) {
+                    individual.Tours[route].Stops.Insert(place, customer2);
+                    route1.Stops.RemoveAt(customer1Position);
+
+                    if (route1.Stops.Count == 0)
+                    individual.Tours.Remove(route1);
+
+                  //two-level exchange has been performed
+                  return;
+                } else {
+                  tour.Stops[customer2Position] = customer2;
+                }
+              } else {
+                tour.Stops[customer2Position] = customer2;
+              }
+            }
+          }
+        }
+      }
+    }
+  }
+}
Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs	(revision 4376)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs	(revision 4376)
@@ -0,0 +1,126 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System.Drawing;
+using System.Collections.Generic;
+using HeuristicLab.Problems.VehicleRouting.Encodings.General;
+using HeuristicLab.Problems.VehicleRouting.Variants;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
+using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  [Item("PotvinEncoding", "Represents a potvin encoding of VRP solutions. It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.")]
+  [StorableClass]
+  public class PotvinEncoding : TourEncoding, ISingleDepotEncoding, ITimeWindowedEncoding, IHomogenousCapacitatedEncoding {   
+    [Storable]
+    public List<int> Unrouted { get; set; }
+
+    public override IDeepCloneable Clone(HeuristicLab.Common.Cloner cloner) {
+      PotvinEncoding clone = new PotvinEncoding(ProblemInstance);
+      cloner.RegisterClonedObject(this, clone);
+      clone.Tours = (ItemList<Tour>)cloner.Clone(this.Tours);
+      clone.Unrouted = new List<int>(Unrouted);
+      return clone;
+    }
+
+    public PotvinEncoding(IVRPProblemInstance instance)
+      : base(instance) {
+      Unrouted = new List<int>();
+    }
+
+    [StorableConstructor]
+    private PotvinEncoding(bool serializing)
+      : base(serializing) {
+    }
+
+    public static PotvinEncoding ConvertFrom(IVRPEncoding encoding, IVRPProblemInstance instance) {
+      PotvinEncoding solution = new PotvinEncoding(instance);
+
+      TourEncoding.ConvertFrom(encoding, solution, instance);
+
+      return solution;
+    }
+
+    public static PotvinEncoding ConvertFrom(List<int> route, IVRPProblemInstance instance) {
+      PotvinEncoding solution = new PotvinEncoding(instance);
+
+      TourEncoding.ConvertFrom(route, solution);
+
+      return solution;
+    }
+
+    public double GetTourLength(Tour tour) {
+      double length = 0;
+
+      if (tour.Stops.Count > 0) {
+        List<int> cities = new List<int>();
+        cities.Add(0);
+        foreach (int city in tour.Stops) {
+          cities.Add(city);
+        }
+        cities.Add(0);
+
+        for (int i = 1; i < cities.Count; i++) {
+          length += ProblemInstance.GetDistance(cities[i - 1], cities[i]);
+        }
+      }  
+
+      return length;
+    }
+
+    public bool FindInsertionPlace(int city, int routeToAvoid, out int route, out int place) {
+      route = -1;
+      place = -1;
+      double minDetour = 0;
+
+      for (int tour = 0; tour < Tours.Count; tour++) {
+        if (tour != routeToAvoid) {
+          for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
+            double length = GetTourLength(Tours[tour]);
+
+            Tours[tour].Stops.Insert(i, city);
+
+            if (ProblemInstance.Feasible(Tours[tour])) {
+              double newLength = GetTourLength(Tours[tour]);
+
+              double detour = newLength - length;
+
+              if (route <= 0 || detour < minDetour) {
+                route = tour;
+                place = i;
+                minDetour = detour;
+              }
+            }
+
+            Tours[tour].Stops.RemoveAt(i);
+          }
+        }
+      }
+
+      return route >= 0 && place >= 0;
+    }
+  }
+}
