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

Timestamp:

11/30/16 14:49:22 (7 years ago)

Author:

jzenisek

Message:

#2707 updated clustering: implemented a quite generic version

File:

• branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/TemporalDistanceClusterCreator.cs (modified) (3 diffs)

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

@@ -49 +49 @@
     }
 
-    public static List<TemporalDistanceClusterElement> CreateClusterObjects(ITimeWindowedProblemInstance instance) {
+    public static List<TemporalDistanceClusterElement> CreateClusterElements(ITimeWindowedProblemInstance instance) {
       IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
 
@@ -70 +70 @@
       PotvinEncoding result = new PotvinEncoding(instance);
 
-      List<TemporalDistanceClusterElement> clusterObjects = CreateClusterObjects(instance);
+      // (1) wrap stops in cluster elements
+      List<TemporalDistanceClusterElement> clusterElements = CreateClusterElements(instance);
 
+      // (2) create a random number k of clusters
       int k = random.Next(minK, maxK);
-      List<TemporalDistanceCluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
+      List<TemporalDistanceCluster> clusters = ClusterAlgorithm<TemporalDistanceCluster, TemporalDistanceClusterElement>
+        .KMeans(random, clusterElements, k, clusterChangeThreshold, false);
 
-      // (3) build tours
-      // (a) shuffle
-      // (b) greedy
+      // (3) build tours with a (a) shuffling (b) greedy tour creation routine
       foreach (var c in clusters) {
         Tour newTour = new Tour();
@@ -93 +94 @@
             newTour.Stops.Add(o.Id);
           }
-          GreedyTourCreation(instance, result, newTour, false);
+          GreedyTourCreation(instance, result, newTour, true); // "true" means include costs
         }
       }
 
       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;
     }