Index: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/LocalImprovement/AlbaLambdaInterchangeLocalImprovementOperator.cs
===================================================================
--- trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/LocalImprovement/AlbaLambdaInterchangeLocalImprovementOperator.cs	(revision 6448)
+++ trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/LocalImprovement/AlbaLambdaInterchangeLocalImprovementOperator.cs	(revision 6448)
@@ -0,0 +1,170 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2011 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.Optimization;
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using HeuristicLab.Common;
+using HeuristicLab.Parameters;
+using HeuristicLab.Operators;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
+  [Item("AlbaLambdaInterchangeLocalImprovementOperator", "Takes a solution and finds the local optimum with respect to the lambda interchange neighborhood by decending along the steepest gradient.")]
+  [StorableClass]
+  public class AlbaLambdaInterchangeLocalImprovementOperator : SingleSuccessorOperator, IStochasticOperator, ILocalImprovementOperator {
+    public Type ProblemType {
+      get { return typeof(VehicleRoutingProblem); }
+    }
+
+    [Storable]
+    private VehicleRoutingProblem problem;
+    public IProblem Problem {
+      get { return problem; }
+      set { problem = (VehicleRoutingProblem)value; }
+    }
+
+    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
+    }
+
+    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
+    }
+
+    public ILookupParameter<ResultCollection> ResultsParameter {
+      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
+    }
+
+    public ILookupParameter<IVRPEncoding> VRPToursParameter {
+      get { return (ILookupParameter<IVRPEncoding>)Parameters["VRPTours"]; }
+    }
+
+    public ILookupParameter<DoubleValue> QualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
+    }
+
+    public IValueParameter<IntValue> LambdaParameter {
+      get { return (IValueParameter<IntValue>)Parameters["Lambda"]; }
+    }
+
+    public IValueParameter<IntValue> SampleSizeParameter {
+      get { return (IValueParameter<IntValue>)Parameters["SampleSize"]; }
+    }
+
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
+    }
+
+    [StorableConstructor]
+    protected AlbaLambdaInterchangeLocalImprovementOperator(bool deserializing) : base(deserializing) { }
+    protected AlbaLambdaInterchangeLocalImprovementOperator(AlbaLambdaInterchangeLocalImprovementOperator original, Cloner cloner)
+      : base(original, cloner) {
+      this.problem = cloner.Clone(original.problem);
+    }
+    public AlbaLambdaInterchangeLocalImprovementOperator()
+      : base() {
+      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum amount of iterations that should be performed (note that this operator will abort earlier when a local optimum is reached.", new IntValue(10000)));
+      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The amount of evaluated solutions (here a move is counted only as 4/n evaluated solutions with n being the length of the permutation)."));
+      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The collection where to store results."));
+      Parameters.Add(new LookupParameter<IVRPEncoding>("VRPTours", "The VRP tours to be manipulated."));
+      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value of the assignment."));
+      Parameters.Add(new ValueParameter<IntValue>("Lambda", "The lambda value.", new IntValue(1)));
+      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "The number of moves to generate.", new IntValue(2000)));
+      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator."));
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new AlbaLambdaInterchangeLocalImprovementOperator(this, cloner);
+    }
+
+    public static void Apply(AlbaEncoding solution, int maxIterations, 
+      int lambda, int samples, IRandom random, ref double quality, out int evaluatedSolutions, 
+      DoubleMatrix distanceMatrix, IntValue vehicles, DoubleArray dueTime, DoubleArray serviceTime, DoubleArray readyTime,
+      DoubleArray demand, DoubleValue capacity, 
+      DoubleMatrix coordinates, DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor,
+      DoubleValue overloadPenalty, DoubleValue tardinessPenalty, BoolValue useDistanceMatrix) {
+      ValueLookupParameter<DoubleMatrix> distanceMatrixParameter = new ValueLookupParameter<DoubleMatrix>("DistanceMatrix", distanceMatrix);
+
+      evaluatedSolutions = 0;
+
+      for (int i = 0; i < maxIterations; i++) {
+        AlbaLambdaInterchangeMove bestMove = null;
+        foreach (AlbaLambdaInterchangeMove move in AlbaStochasticLambdaInterchangeMultiMoveGenerator.GenerateAllMoves(solution, lambda, samples, random)) {
+          double moveQuality =
+            AlbaLambdaInterchangeMoveEvaluator.GetMoveQuality(solution,
+            move,
+            vehicles,
+            dueTime, serviceTime,readyTime,
+            demand, capacity,
+            coordinates, fleetUsageFactor,
+            timeFactor, distanceFactor,
+            overloadPenalty, tardinessPenalty,
+            distanceMatrixParameter,useDistanceMatrix).Quality;
+
+          evaluatedSolutions++;
+          if (moveQuality < quality || quality == -1) {
+            quality = moveQuality;
+            bestMove = move;
+          }
+        }
+        if (bestMove != null) 
+          AlbaLambdaInterchangeMoveMaker.Apply(solution, bestMove);
+      }
+    }
+
+    public override IOperation Apply() {
+      int maxIterations = MaximumIterationsParameter.ActualValue.Value;
+      ValueLookupParameter<DoubleMatrix> distanceMatrix = new ValueLookupParameter<DoubleMatrix>("DistanceMatrix", problem.DistanceMatrix);
+
+      AlbaEncoding solution = null;
+
+      if (VRPToursParameter.ActualValue is AlbaEncoding)
+        solution = VRPToursParameter.ActualValue as AlbaEncoding;
+      else
+        VRPToursParameter.ActualValue = solution = AlbaEncoding.ConvertFrom(VRPToursParameter.ActualValue, problem.VehiclesParameter.Value.Value,
+        distanceMatrix);
+
+      int lambda = LambdaParameter.Value.Value;
+      int samples = SampleSizeParameter.Value.Value;
+      IRandom random = RandomParameter.ActualValue;
+
+      double quality = QualityParameter.ActualValue.Value;
+      int evaluatedSolutions;
+
+      Apply(solution, maxIterations, lambda, samples, random, ref quality, out evaluatedSolutions,
+        problem.DistanceMatrix, problem.Vehicles, problem.DueTime, problem.ServiceTime,
+        problem.ReadyTime, problem.Demand, problem.Capacity, problem.Coordinates,
+        problem.FleetUsageFactorParameter.Value, problem.TimeFactorParameter.Value,
+        problem.DistanceFactorParameter.Value, problem.OverloadPenaltyParameter.Value,
+        problem.TardinessPenaltyParameter.Value, problem.UseDistanceMatrix);
+
+      EvaluatedSolutionsParameter.ActualValue.Value += evaluatedSolutions;
+      QualityParameter.ActualValue.Value = quality;
+
+      return base.Apply();
+    }
+  }
+}
Index: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/LambdaInterchange/AlbaExhaustiveLambdaInterchangeMoveGenerator.cs
===================================================================
--- trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/LambdaInterchange/AlbaExhaustiveLambdaInterchangeMoveGenerator.cs	(revision 6441)
+++ trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/LambdaInterchange/AlbaExhaustiveLambdaInterchangeMoveGenerator.cs	(revision 6448)
@@ -39,5 +39,5 @@
     }
 
-    protected override AlbaLambdaInterchangeMove[] GenerateMoves(AlbaEncoding individual, int lambda) {
+    public static AlbaLambdaInterchangeMove[] GenerateAllMoves(AlbaEncoding individual, int lambda) {
       List<AlbaLambdaInterchangeMove> moves = new List<AlbaLambdaInterchangeMove>();
 
@@ -66,4 +66,8 @@
       return moves.ToArray();
     }
+
+    protected override AlbaLambdaInterchangeMove[] GenerateMoves(AlbaEncoding individual, int lambda) {
+      return GenerateAllMoves(individual, lambda);
+    }
   }
 }
Index: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/LambdaInterchange/AlbaStochasticLambdaInterchangeMutliMoveGenerator.cs
===================================================================
--- trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/LambdaInterchange/AlbaStochasticLambdaInterchangeMutliMoveGenerator.cs	(revision 6441)
+++ trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/LambdaInterchange/AlbaStochasticLambdaInterchangeMutliMoveGenerator.cs	(revision 6448)
@@ -50,15 +50,20 @@
       return new AlbaStochasticLambdaInterchangeMultiMoveGenerator(this, cloner);
     }
-    protected override AlbaLambdaInterchangeMove[] GenerateMoves(AlbaEncoding individual, int lambda) {
-      int sampleSize = SampleSizeParameter.ActualValue.Value;
 
+    public static AlbaLambdaInterchangeMove[] GenerateAllMoves(AlbaEncoding individual, int lambda, int sampleSize, IRandom random) {
       AlbaLambdaInterchangeMove[] moves = new AlbaLambdaInterchangeMove[sampleSize];
       for (int i = 0; i < sampleSize; i++) {
         moves[i] = AlbaStochasticLambdaInterchangeSingleMoveGenerator.Apply(
-          individual, Cities, lambda, RandomParameter.ActualValue);
+          individual, individual.Cities, lambda, random);
       }
 
       return moves;
     }
+
+    protected override AlbaLambdaInterchangeMove[] GenerateMoves(AlbaEncoding individual, int lambda) {
+      int sampleSize = SampleSizeParameter.ActualValue.Value;
+
+      return GenerateAllMoves(individual, lambda, sampleSize, RandomParameter.ActualValue);
+    }
   }
 }
Index: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Creators/IterativeInsertionCreator.cs
===================================================================
--- trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Creators/IterativeInsertionCreator.cs	(revision 6448)
+++ trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Creators/IterativeInsertionCreator.cs	(revision 6448)
@@ -0,0 +1,170 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2011 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.Collections.Generic;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using System;
+using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.General {
+  [Item("IterativeInsertionCreator", "Creates a randomly initialized VRP solution using the iterative insertion Heuristic.")]
+  [StorableClass]
+  public sealed class IterativeInsertionCreator : DefaultRepresentationCreator, IStochasticOperator {
+    #region IStochasticOperator Members
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
+    }
+    #endregion
+
+    [StorableConstructor]
+    private IterativeInsertionCreator(bool deserializing) : base(deserializing) { }
+    private IterativeInsertionCreator(IterativeInsertionCreator original, Cloner cloner) : base(original, cloner) { }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new IterativeInsertionCreator(this, cloner);
+    }
+
+    public IterativeInsertionCreator()
+      : base() {
+      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
+    }
+
+    private static double CalculateAngleToDepot(DoubleMatrix coordinates, int city) {
+      double dx = coordinates[0, 0];
+      double dy = coordinates[0, 1];
+
+      double cx = coordinates[city, 0];
+      double cy = coordinates[city, 1];
+
+      double alpha = Math.Atan((cx - dx) / (dy - cy)) * (180.0 / Math.PI);
+      if (cx > dx && cy > dy)
+        alpha = (90.0 + alpha) + 90.0;
+      else if (cx < dx && cy > dy)
+        alpha = alpha + 180.0;
+      else if (cx < dx && cy < dy)
+        alpha = (90.0 + alpha) + 270.0;
+
+      return alpha;
+    }
+
+    private int FindBestInsertionPlace(Tour tour, int city, DoubleArray dueTime,
+      DoubleArray serviceTime, DoubleArray readyTime, DoubleArray demand, DoubleValue capacity,
+      DistanceMatrix distMatrix) {
+      int place = -1;
+      double minQuality = -1;
+
+      for (int i = 0; i <= tour.Cities.Count; i++) {
+        tour.Cities.Insert(i, city);
+        
+        TourEvaluation evaluation = VRPEvaluator.EvaluateTour(tour,
+          dueTime, serviceTime, readyTime, demand, capacity,
+          new DoubleValue(0), new DoubleValue(0), new DoubleValue(1), new DoubleValue(100), new DoubleValue(100),
+            distMatrix);
+        double quality = evaluation.Quality;
+
+        if (place < 0 || quality < minQuality) {
+          place = i;
+          minQuality = quality;
+        }
+
+        tour.Cities.RemoveAt(i);
+      }
+
+      if (place == -1)
+        place = 0;
+
+      return place;
+    }
+
+    protected override List<int> CreateSolution() {
+      int cities = Cities;
+      int vehicles = VehiclesParameter.ActualValue.Value;
+      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
+      IRandom random = RandomParameter.ActualValue;
+      DoubleArray dueTime = DueTimeParameter.ActualValue;
+      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
+      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
+      DoubleArray demand = DemandParameter.ActualValue;
+      DoubleValue capacity = CapacityParameter.ActualValue;
+      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
+
+      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
+
+      PotvinEncoding solution = new PotvinEncoding();
+
+      List<int> customers = new List<int>();
+      for (int i = 0; i < Cities; i++)
+        customers.Add(i + 1);
+      customers.Sort(delegate(int city1, int city2) {
+            double angle1 = CalculateAngleToDepot(coordinates, city1);
+            double angle2 = CalculateAngleToDepot(coordinates, city2);
+
+            return angle1.CompareTo(angle2);
+          });
+
+      Tour currentTour = new Tour();
+      solution.Tours.Add(currentTour);
+      int j = random.Next(customers.Count);
+      for (int i = 0; i < customers.Count; i++) {
+        int index = (i + j) % customers.Count;
+
+        int stopIdx = FindBestInsertionPlace(currentTour, customers[index],
+          dueTime, serviceTime, readyTime, demand, capacity,
+            distMatrix);
+        currentTour.Cities.Insert(stopIdx, customers[index]);
+
+        TourEvaluation evaluation = VRPEvaluator.EvaluateTour(currentTour, 
+          dueTime, serviceTime, readyTime, demand, capacity, 
+          new DoubleValue(0), new DoubleValue(0), new DoubleValue(1), new DoubleValue(100), new DoubleValue(100),
+            distMatrix);
+        if (solution.Tours.Count < vehicles &&
+          ((evaluation.Overload > 0 || evaluation.Tardiness > 0))) {
+          currentTour.Cities.RemoveAt(stopIdx);
+
+          currentTour = new Tour();
+          solution.Tours.Add(currentTour);
+          currentTour.Cities.Add(customers[index]);
+        }
+      }
+
+      List<int> result = new List<int>();
+
+      bool first = true;
+      foreach (Tour tour in solution.GetTours()) {
+        if (first)
+          first = false;
+        else
+          result.Add(0);
+
+        result.AddRange(tour.Cities);
+      }
+
+      while (result.Count < cities + vehicles)
+        result.Add(0);
+
+      return result;
+    }
+  }
+}
Index: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs
===================================================================
--- trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs	(revision 6448)
+++ trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs	(revision 6448)
@@ -0,0 +1,295 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2011 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.Persistence.Default.CompositeSerializers.Storable;
+using System.Collections.Generic;
+using HeuristicLab.Data;
+using System;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  [Item("PotvinInsertionBasedCrossover", "The IBX crossover for VRP representations.")]
+  [StorableClass]
+  public sealed class PotvinInsertionBasedCrossover : PotvinCrossover {
+    [StorableConstructor]
+    private PotvinInsertionBasedCrossover(bool deserializing) : base(deserializing) { }
+    private PotvinInsertionBasedCrossover(PotvinInsertionBasedCrossover original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new PotvinInsertionBasedCrossover(this, cloner);
+    }
+    public PotvinInsertionBasedCrossover()
+      : base() { }
+
+    protected static 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].Cities.Count / (double)individual.Cities);
+        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;
+    }
+
+    private double CalculateCentroidDistance(Tour t1, Tour t2, DoubleMatrix coordinates) {
+      double xSum = 0;
+      double ySum = 0;
+      double c1X, c1Y, c2X, c2Y;
+
+      for (int i = 0; i < t1.Cities.Count; i++) {
+        xSum += coordinates[t1.Cities[i], 0];
+        ySum += coordinates[t1.Cities[i], 0];
+      }
+      c1X = xSum / t1.Cities.Count;
+      c1Y = ySum / t1.Cities.Count;
+
+      for (int i = 0; i < t2.Cities.Count; i++) {
+        xSum += coordinates[t2.Cities[i], 0];
+        ySum += coordinates[t2.Cities[i], 0];
+      }
+      c2X = xSum / t1.Cities.Count;
+      c2Y = ySum / t1.Cities.Count;
+
+      return Math.Sqrt(
+            Math.Pow(c1X - c2X, 2) +
+            Math.Pow(c1Y - c2Y, 2));
+    }
+
+    private double CalculateMeanCentroidDistance(Tour t1, IList<Tour> tours, DoubleMatrix coordinates) {
+      double sum = 0;
+
+      for (int i = 0; i < tours.Count; i++) {
+        sum += CalculateCentroidDistance(t1, tours[i], coordinates);
+      }
+
+      return sum / tours.Count;
+    }
+
+    private int SelectCityBiasedByNeighborDistance(IRandom random, Tour tour, DistanceMatrix distMatrix) {
+      int cityIndex = -1;
+
+      double sum = 0.0;
+      double[] probabilities = new double[tour.Cities.Count];
+      for (int i = 0; i < tour.Cities.Count; i++) {
+        int next = i + 1;
+        if (next >= tour.Cities.Count)
+          next = 0;
+        else 
+          next = tour.Cities[next];
+        double distance = VRPUtilities.GetDistance(
+          tour.Cities[i], next, distMatrix);
+
+        int prev = i - 1;
+        if (prev < 0)
+          prev = 0;
+        else
+          prev = tour.Cities[prev];
+        distance += VRPUtilities.GetDistance(
+          tour.Cities[i], prev, distMatrix);
+
+        probabilities[i] = distance;
+        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 (cityIndex == -1 && index < probabilities.Length) {
+        if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])
+          cityIndex = index;
+
+        cumulatedProbabilities += probabilities[index];
+        index++;
+      }
+
+      return cityIndex;
+    }
+
+    private bool FindRouteInsertionPlace(
+      Tour tour,
+      DoubleArray dueTimeArray,
+      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
+      DistanceMatrix distMatrix,
+      int city, out int place) {
+      place = -1;
+      bool bestFeasible = false;
+      double minDetour = 0;
+
+      for (int i = 0; i <= tour.Cities.Count; i++) {
+        double length = tour.GetLength(distMatrix);
+
+        tour.Cities.Insert(i, city);
+
+        bool feasible = tour.Feasible(dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
+          capacity, distMatrix);
+
+        if (!bestFeasible || feasible) {
+          double newLength = tour.GetLength(distMatrix);
+          double detour = newLength - length;
+
+          if (place <= 0 || (!(bestFeasible && !feasible)) && detour < minDetour || (feasible && !bestFeasible)) {
+            place = i;
+            minDetour = detour;
+
+            if (feasible)
+              bestFeasible = true;
+          }
+        }
+
+        tour.Cities.RemoveAt(i);
+      }
+
+      return place >= 0;
+    }
+
+    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
+      PotvinEncoding child = new PotvinEncoding();
+      bool success = true;
+
+      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
+      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
+      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
+      DoubleArray dueTime = DueTimeParameter.ActualValue;
+      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
+      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
+      DoubleArray demand = DemandParameter.ActualValue;
+      DoubleValue capacity = CapacityParameter.ActualValue;
+
+      List<Tour> R1 = new List<Tour>();
+      PotvinEncoding p1Clone = parent1.Clone() as PotvinEncoding;
+
+      int k = 1;//random.Next(1, Math.Min(10, parent1.Tours.Count + 1));
+      for (int i = 0; i < k; i++) {
+        int index = SelectRandomTourBiasedByLength(random, p1Clone);
+        R1.Add(p1Clone.Tours[index]);
+        p1Clone.Tours.RemoveAt(index);
+      }
+
+      foreach (Tour r1 in R1) {
+        List<int> R2 = new List<int>();
+
+        double r = CalculateMeanCentroidDistance(r1, parent2.Tours, coordinates);
+        foreach (Tour tour in parent2.Tours) {
+          if (CalculateCentroidDistance(r1, tour, coordinates) <= r) {
+            R2.AddRange(tour.Cities);
+          }
+        }
+
+        Tour childTour = new Tour();
+        childTour.Cities.AddRange(r1.Cities);
+
+        //DESTROY - remove cities from r1
+        int removed = random.Next(1, r1.Cities.Count + 1);
+        for (int i = 0; i < removed; i++) {
+          childTour.Cities.RemoveAt(SelectCityBiasedByNeighborDistance(random, childTour, distMatrix));
+        }
+
+        //REPAIR - add cities from R2
+        bool insertSuccess = true;
+        int maxCount = random.Next(1, Math.Min(5, R2.Count));
+        int count = 0;
+
+        while (count < maxCount && R2.Count != 0) {
+          PotvinEncoding newChild = child.Clone() as PotvinEncoding;
+          newChild.Tours.Add(childTour);
+
+          int index = random.Next(R2.Count);
+          int city = R2[index];
+          R2.RemoveAt(index);
+
+          int place = -1;
+          if(FindRouteInsertionPlace(childTour, dueTime, serviceTime, readyTime, 
+            demand, capacity, distMatrix, city, out place)) {
+            childTour.Cities.Insert(place, city);
+
+            if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
+              childTour.Cities.RemoveAt(place);
+              insertSuccess = false;
+            } else {
+              count++;
+            } 
+          } 
+        }
+
+        child.Tours.Add(childTour);
+        if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
+          //success = false;
+          //break;
+        }
+      }
+
+      if (success) {
+        for (int i = 0; i < p1Clone.Tours.Count; i++) {
+          Tour childTour = p1Clone.Tours[i].Clone() as Tour;
+          child.Tours.Add(childTour);
+          if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
+            //success = false;
+            //break;
+          }
+        }
+      }
+
+      if (success) {
+        //route unrouted customers
+        for (int i = 1; i <= parent1.Cities; i++) {
+          if (FindRoute(child, i) == null)
+            child.Unrouted.Add(i);
+        }
+
+        if (!RouteUnrouted(child, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
+          success = false;
+        }
+      }
+
+      if (success)
+        return child;
+      else {
+        /* if (random.NextDouble() < 0.5)
+          return parent1.Clone() as PotvinEncoding;
+        else
+          return parent2.Clone() as PotvinEncoding;   */
+        return child;
+      }
+    }
+  }
+}
