Changeset 14442

Timestamp:

12/02/16 14:03:55 (8 years ago)

Author:

jzenisek

Message:

#2707 fixed min variance bug in time window based k-means clustering

Location:

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators

Files:

• Cluster.cs (modified) (5 diffs)
• GeographicDistanceClusterCreator.cs (modified) (1 diff)
• TemporalDistanceClusterCreator.cs (modified) (1 diff)

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/Cluster.cs

@@ -9 +9 @@
   public class ClusterAlgorithm<C,CO> where C : Cluster<CO> where CO : ClusterElement {
 
-    public static List<C> KMeans(IRandom random, List<CO> clusterElements, int k, double changeThreshold, bool minimizeImpact) {
+    public static List<C> KMeans(IRandom random, List<CO> clusterElements, int k, double changeThreshold) {
       HashSet<int> initMeans = new HashSet<int>();
       int nextMean = -1;
@@ -32 +32 @@
 
       do {
-        int changes = KMeansRun(clusters, clusterElements, minimizeImpact);
+        int changes = KMeansRun(clusters, clusterElements);
         changeRate = (double)changes / clusterElements.Count;
       } while (changeRate > changeThreshold);
@@ -43 +43 @@
     }
 
-    private static int KMeansRun(List<C> clusters, List<CO> clusterElements, bool minimizeImpact) {
+    private static int KMeansRun(List<C> clusters, List<CO> clusterElements) {
       int changes = 0;
 
@@ -57 +57 @@
         for (int i = 1; i < clusters.Count; i++) {
           double impact = clusters[i].CalculateImpact(e);
-          if (
-            // optimal impact: max variance decrease (biggest negative or smallest positive value)
-            (minimizeImpact && impact < optImpact) ||
-            // optimal impact: min variance increase, if no increase possible: min decrease (smallest negative or positive value)
-            //(!minimizeImpact && ((optImpact > 0 && impact < optImpact) || (optImpact < 0 && impact > optImpact)))) {
-            (!minimizeImpact && impact > optImpact)
-            ) { 
-
+          if (impact < optImpact) { 
             optImpact = impact;
             optClusterIdx = i;
@@ -206 +199 @@
     public override double CalculateDistance(TemporalDistanceClusterElement e1, TemporalDistanceClusterElement e2) {
       double distance = 0.0;
-      distance += Math.Abs(e1.ReadyTime - e2.ReadyTime);
-      distance += Math.Abs(e1.DueTime - e2.DueTime);
-
-      return distance;
-      //return euklid(e1, e2);
-    }
-
-    private double euklid(TemporalDistanceClusterElement e1, TemporalDistanceClusterElement e2) {
-      double distance = 0.0;
-      distance += Math.Pow(e1.ReadyTime - e2.ReadyTime + e1.DueTime - e2.DueTime, 2);
+
+      distance += Math.Pow(e1.ReadyTime - e2.ReadyTime, 2);
+      distance += Math.Pow(e1.DueTime - e2.DueTime, 2);
 
       return Math.Sqrt(distance);

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/GeographicDistanceClusterCreator.cs

@@ -75 +75 @@
       int k = random.Next(minK, maxK);
       List<SpatialDistanceCluster> clusters = ClusterAlgorithm<SpatialDistanceCluster, SpatialDistanceClusterElement>
-        .KMeans(random, clusterElements, k, clusterChangeThreshold, true);
+        .KMeans(random, clusterElements, k, clusterChangeThreshold);
       
       // (3) build tours with a (a) shuffling (b) greedy tour creation routine

branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/TemporalDistanceClusterCreator.cs

@@ -76 +76 @@
       int k = random.Next(minK, maxK);
       List<TemporalDistanceCluster> clusters = ClusterAlgorithm<TemporalDistanceCluster, TemporalDistanceClusterElement>
-        .KMeans(random, clusterElements, k, clusterChangeThreshold, false);
+        .KMeans(random, clusterElements, k, clusterChangeThreshold);
 
       // (3) build tours with a (a) shuffling (b) greedy tour creation routine