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

Timestamp:

11/30/16 09:24:40 (7 years ago)

Author:

jzenisek

Message:

#2707 added temporal distance clustering

File:

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

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

@@ -7 +7 @@
 using HeuristicLab.Core;
 using HeuristicLab.Problems.VehicleRouting.Interfaces;
+using HeuristicLab.Problems.VehicleRouting.Variants;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -42 +43 @@
     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 +70 @@
     public abstract void CalculateMean();
 
+    public abstract void CalculateVariance();
+
     public abstract double CalculateImpact(T o);
 
@@ -76 +81 @@
     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 +106 @@
         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 +182 @@
       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 +194 @@
     }
   }
+
+  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
 }