Index: branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/Cluster.cs
===================================================================
--- branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/Cluster.cs	(revision 14424)
+++ branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/Cluster.cs	(revision 14430)
@@ -7,4 +7,5 @@
 using HeuristicLab.Core;
 using HeuristicLab.Problems.VehicleRouting.Interfaces;
+using HeuristicLab.Problems.VehicleRouting.Variants;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -42,16 +43,18 @@
     public int Id;
     protected readonly IVRPProblemInstance instance;
-    public List<T> Objects { get; private set; }
+    public List<T> Elements { get; private set; }
 
     public T Mean { get; set; }
+
+    public double Variance { get; set; }
 
     public Cluster(IVRPProblemInstance instance, int id) {
       this.instance = instance;
       Id = id;
-      Objects = new List<T>();
+      Elements = new List<T>();
 
     }
     public bool AddObject(T o) {
-      Objects.Add(o);
+      Elements.Add(o);
 
       bool clusterChanged = o.ClusterId != Id;
@@ -67,4 +70,6 @@
     public abstract void CalculateMean();
 
+    public abstract void CalculateVariance();
+
     public abstract double CalculateImpact(T o);
 
@@ -76,12 +81,23 @@
     public override void CalculateMean() {
       int dimensions = instance.Coordinates.Columns;
-      SpatialDistanceClusterElement mean = new SpatialDistanceClusterElement(-1, Id, dimensions);
-      foreach (SpatialDistanceClusterElement o in Objects) {
+      SpatialDistanceClusterElement mean = new SpatialDistanceClusterElement(-1, dimensions, Id);
+      foreach (SpatialDistanceClusterElement o in Elements) {
         double[] coordinates = instance.GetCoordinates(o.Id);
         for (int i = 0; i < coordinates.Length; i++) {
-          mean.Coordinates[i] += (coordinates[i] / Objects.Count);
+          mean.Coordinates[i] += (coordinates[i] / Elements.Count);
         }
       }
       Mean = mean;
+    }
+
+    public override void CalculateVariance() {
+      if(Mean == null)
+        CalculateMean();
+
+      Variance = 0.0;
+      foreach (SpatialDistanceClusterElement o in Elements) {
+        Variance += Math.Pow(Mean.GetDistance(o), 2);
+      }
+      Variance /= Elements.Count;
     }
 
@@ -90,5 +106,40 @@
         CalculateMean();
 
-      return Math.Pow(Mean.GetDistance(o), 2) / ((Objects.Count > 0) ? Objects.Count : 1);
+      double newVariance = (Variance*Elements.Count + Math.Pow(Mean.GetDistance(o), 2))/(Elements.Count + 1);
+      return newVariance - Variance;
+    }
+  }
+
+  public class TemporalDistanceCluster : Cluster<TemporalDistanceClusterElement> {
+    public TemporalDistanceCluster(ITimeWindowedProblemInstance instance, int id) : base(instance, id) {
+    }
+
+
+    public override void CalculateMean() {
+      TemporalDistanceClusterElement mean = new TemporalDistanceClusterElement(-1, Id);
+      foreach (TemporalDistanceClusterElement e in Elements) {
+        mean.ReadyTime += e.ReadyTime/Elements.Count;
+        mean.DueTime += e.DueTime/Elements.Count;
+      }
+      Mean = mean;
+    }
+
+    public override void CalculateVariance() {
+      if (Mean == null)
+        CalculateMean();
+
+      Variance = 0.0;
+      foreach (TemporalDistanceClusterElement e in Elements) {
+        Variance += Math.Pow(Math.Abs(Mean.ReadyTime - e.ReadyTime) + Math.Abs(Mean.DueTime - e.DueTime), 2);
+      }
+      Variance /= Elements.Count;
+    }
+
+    public override double CalculateImpact(TemporalDistanceClusterElement o) {
+      if(Mean == null)
+        CalculateMean();
+
+      double newVariance = (Variance * Elements.Count + Math.Pow(Math.Abs(Mean.ReadyTime - o.ReadyTime) + Math.Abs(Mean.DueTime - o.DueTime), 2)) / (Elements.Count + 1);
+      return newVariance - Variance;
     }
   }
@@ -131,5 +182,5 @@
       var other = o as SpatialDistanceClusterElement;
       if (other == null) {
-        throw new ArrayTypeMismatchException(string.Format("Distance calculation between {0} and {1} is not possible.",
+        throw new ArgumentException(string.Format("Distance calculation between {0} and {1} is not possible.",
           typeof(SpatialDistanceClusterElement), o.GetType()));
       }
@@ -143,4 +194,43 @@
     }
   }
+
+  public class TemporalDistanceClusterElement : ClusterElement {
+    public double ReadyTime { get; set; }
+    public double DueTime { get; set; }
+
+    public TemporalDistanceClusterElement(int id, int clusterId = -1) : base(id, clusterId) {
+    }
+
+    public TemporalDistanceClusterElement(int id, double readyTime, double dueTime, int clusterId = -1) : base(id, clusterId) {
+      ReadyTime = readyTime;
+      DueTime = dueTime;
+    }
+
+    public override double GetDistance(IClusterElement o) {
+      var other = o as TemporalDistanceClusterElement;
+      if (other == null) {
+        throw new ArgumentException(string.Format("Distance calculation between {0} and {1} is not possible.",
+          typeof(TemporalDistanceClusterElement), o.GetType()));
+      }
+
+      double distance = 0.0;
+      distance += Math.Abs(ReadyTime - other.ReadyTime);
+      distance += Math.Abs(DueTime - other.DueTime);
+
+      return distance;
+
+      //return GetDistanceEuklid(other);
+    }
+
+    public double GetDistanceEuklid(TemporalDistanceClusterElement other) {
+      double distance = 0.0;
+      distance += Math.Pow(ReadyTime - other.ReadyTime, 2);
+      distance += Math.Pow(DueTime - other.DueTime, 2);
+
+      return Math.Sqrt(distance);
+    }
+
+  }
+
   #endregion ClusterElement
 }
Index: branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs
===================================================================
--- branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs	(revision 14424)
+++ branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs	(revision 14430)
@@ -83,11 +83,11 @@
         if (creationOption == 0) {
           // (a) shuffle
-          c.Objects.Shuffle(random);
-          foreach (var o in c.Objects) {
+          c.Elements.Shuffle(random);
+          foreach (var o in c.Elements) {
             newTour.Stops.Add(o.Id);
           }
         } else {
           // (b) greedy
-          foreach (var o in c.Objects) {
+          foreach (var o in c.Elements) {
             newTour.Stops.Add(o.Id);
           }
@@ -128,5 +128,5 @@
 
       // remove empty clusters
-      clusters.RemoveAll(c => c.Objects.Count.Equals(0));
+      clusters.RemoveAll(c => c.Elements.Count.Equals(0));
 
       return clusters;
@@ -137,11 +137,11 @@
 
       foreach (var c in clusters) {
-        c.Objects.Clear();
+        c.Elements.Clear();
       }
 
       foreach (var o in objects) {
-        int bestClusterIdx = -1;
-        double minImpact = double.MaxValue;
-        for (int i = 0; i < clusters.Count; i++) {
+        int bestClusterIdx = 0;
+        double minImpact = clusters[0].CalculateImpact(o);
+        for (int i = 1; i < clusters.Count; i++) {
           double impact = clusters[i].CalculateImpact(o);
           if (impact < minImpact) {
@@ -156,4 +156,5 @@
       foreach (var c in clusters) {
         c.CalculateMean();
+        c.CalculateVariance();
       }
 
Index: branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/TemporalDistanceClusterCreator.cs
===================================================================
--- branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/TemporalDistanceClusterCreator.cs	(revision 14430)
+++ branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/TemporalDistanceClusterCreator.cs	(revision 14430)
@@ -0,0 +1,195 @@
+﻿#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2016 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 HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
+using HeuristicLab.Problems.VehicleRouting.Variants;
+using HeuristicLab.Random;
+
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+  [Item("TemporalDistanceClusterCreator", "Creates a VRP solution by clustering customers first with a KMeans-algorithm based on their geographic position and building tours afterwards alternatevly in a random or a greedy fashion.")]
+  [StorableClass]
+  public sealed class TemporalDistanceClusterCreator : ClusterCreator {
+
+    [StorableConstructor]
+    private TemporalDistanceClusterCreator(bool deserializing) : base(deserializing) { }
+
+    public TemporalDistanceClusterCreator() : base() {
+    }
+
+    private TemporalDistanceClusterCreator(TemporalDistanceClusterCreator original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new TemporalDistanceClusterCreator(this, cloner);
+    }
+
+    public static List<TemporalDistanceClusterElement> CreateClusterObjects(ITimeWindowedProblemInstance instance) {
+      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
+
+      // add all customers
+      List<int> customers = new List<int>();
+      for (int i = 1; i <= instance.Cities.Value; i++) {
+        if (pdp == null || pdp.GetDemand(i) >= 0)
+          customers.Add(i);
+      }
+
+      // wrap stops in TemporalDistanceClusterElement
+      List<TemporalDistanceClusterElement> clusterObjects = new List<TemporalDistanceClusterElement>();
+      foreach (int customer in customers) {
+        clusterObjects.Add(new TemporalDistanceClusterElement(customer, instance.ReadyTime[customer], instance.DueTime[customer]));
+      }
+      return clusterObjects;
+    }
+
+    public static PotvinEncoding CreateSolution(ITimeWindowedProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
+      PotvinEncoding result = new PotvinEncoding(instance);
+
+      List<TemporalDistanceClusterElement> clusterObjects = CreateClusterObjects(instance);
+
+      int k = random.Next(minK, maxK);
+      List<TemporalDistanceCluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
+
+      // (3) build tours
+      // (a) shuffle
+      // (b) greedy
+      foreach (var c in clusters) {
+        Tour newTour = new Tour();
+        result.Tours.Add(newTour);
+
+        if (creationOption == 0) {
+          // (a) shuffle
+          c.Elements.Shuffle(random);
+          foreach (var o in c.Elements) {
+            newTour.Stops.Add(o.Id);
+          }
+        } else {
+          // (b) greedy
+          foreach (var o in c.Elements) {
+            newTour.Stops.Add(o.Id);
+          }
+          GreedyTourCreation(instance, result, newTour, false);
+        }
+      }
+
+      return result;
+    }
+
+    private static List<TemporalDistanceCluster> KMeans(ITimeWindowedProblemInstance instance, IRandom random, List<TemporalDistanceClusterElement> objects, int k, double changeTreshold) {
+
+      List<TemporalDistanceCluster> clusters = new List<TemporalDistanceCluster>();
+      HashSet<int> initMeans = new HashSet<int>();
+      int nextMean = -1;
+
+      // (1) initialize each cluster with a random first object (i.e. mean)
+      for (int i = 0; i < k && i < objects.Count; i++) {
+        TemporalDistanceCluster cluster = new TemporalDistanceCluster(instance, i);
+
+        do {
+          nextMean = random.Next(0, objects.Count);
+        } while (initMeans.Contains(nextMean));
+        initMeans.Add(nextMean);
+        cluster.SetMean(objects[nextMean]);
+        clusters.Add(cluster);
+      }
+
+      // (2) repeat clustering until change rate is below threshold
+      int changes = 0;
+      double changeRate = 1.0;
+
+      do {
+        changes = KMeansRun(clusters, objects);
+        changeRate = changes / objects.Count;
+
+      } while (changeRate > changeTreshold);
+
+      // remove empty clusters
+      clusters.RemoveAll(c => c.Elements.Count.Equals(0));
+
+      return clusters;
+    }
+
+    private static int KMeansRun(List<TemporalDistanceCluster> clusters, List<TemporalDistanceClusterElement> objects) {
+      int changes = 0;
+
+      foreach (var c in clusters) {
+        c.Elements.Clear();
+      }
+
+      foreach (var o in objects) {
+        int bestClusterIdx = 0;
+        double minImpact = clusters[0].CalculateImpact(o);
+        for (int i = 1; i < clusters.Count; i++) {
+          double impact = clusters[i].CalculateImpact(o);
+          if ((minImpact > 0 && impact < minImpact) || (minImpact < 0 && impact > minImpact)) { // V1: min positive impact
+          //if(impact > minImpact) { // V2: max impact
+            minImpact = impact;
+            bestClusterIdx = i;
+          }
+        }
+        if (clusters[bestClusterIdx].AddObject(o))
+          changes++;
+      }
+
+      foreach (var c in clusters) {
+        c.CalculateMean();
+        c.CalculateVariance();
+      }
+
+      return changes;
+    }
+
+    public override IOperation InstrumentedApply() {
+      IRandom random = RandomParameter.ActualValue;
+
+      int minK = (MinK.Value.Value > 0) ? MinK.Value.Value : 1;
+      int maxK = (MaxK.Value != null) ? MaxK.Value.Value : ProblemInstance.Vehicles.Value;
+      double clusterChangeThreshold = (ClusterChangeThreshold.Value.Value >= 0.0 &&
+                                       ClusterChangeThreshold.Value.Value <= 1.0)
+        ? ClusterChangeThreshold.Value.Value
+        : 0.0;
+
+      // normalize probabilities
+      double max = TourCreationProbabilities.Value.Max();
+      double[] probabilites = new double[2];
+      for (int i = 0; i < TourCreationProbabilities.Value.Length; i++) {
+        probabilites[i] = TourCreationProbabilities.Value[i] / max;
+      }
+
+      List<int> creationOptions = new List<int>() { 0, 1 };
+      int creationOption = creationOptions.SampleProportional(random, 1, probabilites, false, false).First();
+
+      var instance = ProblemInstance as ITimeWindowedProblemInstance;
+      if (instance == null) {
+        throw new ArgumentException(string.Format("Cannot initialize {0} with data from {1}", instance.GetType(), ProblemInstance.GetType()));
+      }
+
+      VRPToursParameter.ActualValue = CreateSolution(instance, random, minK, maxK, clusterChangeThreshold, creationOption);
+      return base.InstrumentedApply();
+    }
+  }
+}
Index: branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj
===================================================================
--- branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj	(revision 14424)
+++ branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj	(revision 14430)
@@ -198,4 +198,5 @@
     <Compile Include="Encodings\Potvin\Creators\Cluster.cs" />
     <Compile Include="Encodings\Potvin\Creators\ClusterCreator.cs" />
+    <Compile Include="Encodings\Potvin\Creators\TemporalDistanceClusterCreator.cs" />
     <Compile Include="Encodings\Potvin\Creators\GeographicDistanceClusterCreator.cs" />
     <Compile Include="Encodings\Potvin\Crossovers\PotvinEdgePreservingSequenceBasedCrossover.cs" />
