Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/30/16 09:24:40 (8 years ago)
Author:
jzenisek
Message:

#2707 added temporal distance clustering

Location:
branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4
Files:
3 edited
1 copied

Legend:

Unmodified
Added
Removed

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

    r14424 r14430  
    77using HeuristicLab.Core;
    88using HeuristicLab.Problems.VehicleRouting.Interfaces;
     9using HeuristicLab.Problems.VehicleRouting.Variants;
    910
    1011namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    … …  
    4243    public int Id;
    4344    protected readonly IVRPProblemInstance instance;
    44     public List<T> Objects { get; private set; }
     45    public List<T> Elements { get; private set; }
    4546
    4647    public T Mean { get; set; }
     48
     49    public double Variance { get; set; }
    4750
    4851    public Cluster(IVRPProblemInstance instance, int id) {
    4952      this.instance = instance;
    5053      Id = id;
    51       Objects = new List<T>();
     54      Elements = new List<T>();
    5255
    5356    }
    5457    public bool AddObject(T o) {
    55       Objects.Add(o);
     58      Elements.Add(o);
    5659
    5760      bool clusterChanged = o.ClusterId != Id;
    … …  
    6770    public abstract void CalculateMean();
    6871
     72    public abstract void CalculateVariance();
     73
    6974    public abstract double CalculateImpact(T o);
    7075
    … …  
    7681    public override void CalculateMean() {
    7782      int dimensions = instance.Coordinates.Columns;
    78       SpatialDistanceClusterElement mean = new SpatialDistanceClusterElement(-1, Id, dimensions);
    79       foreach (SpatialDistanceClusterElement o in Objects) {
     83      SpatialDistanceClusterElement mean = new SpatialDistanceClusterElement(-1, dimensions, Id);
     84      foreach (SpatialDistanceClusterElement o in Elements) {
    8085        double[] coordinates = instance.GetCoordinates(o.Id);
    8186        for (int i = 0; i < coordinates.Length; i++) {
    82           mean.Coordinates[i] += (coordinates[i] / Objects.Count);
     87          mean.Coordinates[i] += (coordinates[i] / Elements.Count);
    8388        }
    8489      }
    8590      Mean = mean;
     91    }
     92
     93    public override void CalculateVariance() {
     94      if(Mean == null)
     95        CalculateMean();
     96
     97      Variance = 0.0;
     98      foreach (SpatialDistanceClusterElement o in Elements) {
     99        Variance += Math.Pow(Mean.GetDistance(o), 2);
     100      }
     101      Variance /= Elements.Count;
    86102    }
    87103
    … …  
    90106        CalculateMean();
    91107
    92       return Math.Pow(Mean.GetDistance(o), 2) / ((Objects.Count > 0) ? Objects.Count : 1);
     108      double newVariance = (Variance*Elements.Count + Math.Pow(Mean.GetDistance(o), 2))/(Elements.Count + 1);
     109      return newVariance - Variance;
     110    }
     111  }
     112
     113  public class TemporalDistanceCluster : Cluster<TemporalDistanceClusterElement> {
     114    public TemporalDistanceCluster(ITimeWindowedProblemInstance instance, int id) : base(instance, id) {
     115    }
     116
     117
     118    public override void CalculateMean() {
     119      TemporalDistanceClusterElement mean = new TemporalDistanceClusterElement(-1, Id);
     120      foreach (TemporalDistanceClusterElement e in Elements) {
     121        mean.ReadyTime += e.ReadyTime/Elements.Count;
     122        mean.DueTime += e.DueTime/Elements.Count;
     123      }
     124      Mean = mean;
     125    }
     126
     127    public override void CalculateVariance() {
     128      if (Mean == null)
     129        CalculateMean();
     130
     131      Variance = 0.0;
     132      foreach (TemporalDistanceClusterElement e in Elements) {
     133        Variance += Math.Pow(Math.Abs(Mean.ReadyTime - e.ReadyTime) + Math.Abs(Mean.DueTime - e.DueTime), 2);
     134      }
     135      Variance /= Elements.Count;
     136    }
     137
     138    public override double CalculateImpact(TemporalDistanceClusterElement o) {
     139      if(Mean == null)
     140        CalculateMean();
     141
     142      double newVariance = (Variance * Elements.Count + Math.Pow(Math.Abs(Mean.ReadyTime - o.ReadyTime) + Math.Abs(Mean.DueTime - o.DueTime), 2)) / (Elements.Count + 1);
     143      return newVariance - Variance;
    93144    }
    94145  }
    … …  
    131182      var other = o as SpatialDistanceClusterElement;
    132183      if (other == null) {
    133         throw new ArrayTypeMismatchException(string.Format("Distance calculation between {0} and {1} is not possible.",
     184        throw new ArgumentException(string.Format("Distance calculation between {0} and {1} is not possible.",
    134185          typeof(SpatialDistanceClusterElement), o.GetType()));
    135186      }
    … …  
    143194    }
    144195  }
     196
     197  public class TemporalDistanceClusterElement : ClusterElement {
     198    public double ReadyTime { get; set; }
     199    public double DueTime { get; set; }
     200
     201    public TemporalDistanceClusterElement(int id, int clusterId = -1) : base(id, clusterId) {
     202    }
     203
     204    public TemporalDistanceClusterElement(int id, double readyTime, double dueTime, int clusterId = -1) : base(id, clusterId) {
     205      ReadyTime = readyTime;
     206      DueTime = dueTime;
     207    }
     208
     209    public override double GetDistance(IClusterElement o) {
     210      var other = o as TemporalDistanceClusterElement;
     211      if (other == null) {
     212        throw new ArgumentException(string.Format("Distance calculation between {0} and {1} is not possible.",
     213          typeof(TemporalDistanceClusterElement), o.GetType()));
     214      }
     215
     216      double distance = 0.0;
     217      distance += Math.Abs(ReadyTime - other.ReadyTime);
     218      distance += Math.Abs(DueTime - other.DueTime);
     219
     220      return distance;
     221
     222      //return GetDistanceEuklid(other);
     223    }
     224
     225    public double GetDistanceEuklid(TemporalDistanceClusterElement other) {
     226      double distance = 0.0;
     227      distance += Math.Pow(ReadyTime - other.ReadyTime, 2);
     228      distance += Math.Pow(DueTime - other.DueTime, 2);
     229
     230      return Math.Sqrt(distance);
     231    }
     232
     233  }
     234
    145235  #endregion ClusterElement
    146236}

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

    r14424 r14430  
    8383        if (creationOption == 0) {
    8484          // (a) shuffle
    85           c.Objects.Shuffle(random);
    86           foreach (var o in c.Objects) {
     85          c.Elements.Shuffle(random);
     86          foreach (var o in c.Elements) {
    8787            newTour.Stops.Add(o.Id);
    8888          }
    8989        } else {
    9090          // (b) greedy
    91           foreach (var o in c.Objects) {
     91          foreach (var o in c.Elements) {
    9292            newTour.Stops.Add(o.Id);
    9393          }
    … …  
    128128
    129129      // remove empty clusters
    130       clusters.RemoveAll(c => c.Objects.Count.Equals(0));
     130      clusters.RemoveAll(c => c.Elements.Count.Equals(0));
    131131
    132132      return clusters;
    … …  
    137137
    138138      foreach (var c in clusters) {
    139         c.Objects.Clear();
     139        c.Elements.Clear();
    140140      }
    141141
    142142      foreach (var o in objects) {
    143         int bestClusterIdx = -1;
    144         double minImpact = double.MaxValue;
    145         for (int i = 0; i < clusters.Count; i++) {
     143        int bestClusterIdx = 0;
     144        double minImpact = clusters[0].CalculateImpact(o);
     145        for (int i = 1; i < clusters.Count; i++) {
    146146          double impact = clusters[i].CalculateImpact(o);
    147147          if (impact < minImpact) {
    … …  
    156156      foreach (var c in clusters) {
    157157        c.CalculateMean();
     158        c.CalculateVariance();
    158159      }
    159160

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

    r14424 r14430  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
    … …  
    3031
    3132namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    32   [Item("GeographicDistanceClusterCreator", "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.")]
     33  [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.")]
    3334  [StorableClass]
    34   public sealed class GeographicDistanceClusterCreator : ClusterCreator {
     35  public sealed class TemporalDistanceClusterCreator : ClusterCreator {
    3536
    3637    [StorableConstructor]
    37     private GeographicDistanceClusterCreator(bool deserializing) : base(deserializing) { }
     38    private TemporalDistanceClusterCreator(bool deserializing) : base(deserializing) { }
    3839
    39     public GeographicDistanceClusterCreator() : base() {
     40    public TemporalDistanceClusterCreator() : base() {
    4041    }
    4142
    42     private GeographicDistanceClusterCreator(GeographicDistanceClusterCreator original, Cloner cloner)
     43    private TemporalDistanceClusterCreator(TemporalDistanceClusterCreator original, Cloner cloner)
    4344      : base(original, cloner) {
    4445    }
    4546
    4647    public override IDeepCloneable Clone(Cloner cloner) {
    47       return new GeographicDistanceClusterCreator(this, cloner);
     48      return new TemporalDistanceClusterCreator(this, cloner);
    4849    }
    4950
    50     public static List<SpatialDistanceClusterElement> CreateClusterObjects(IVRPProblemInstance instance) {
     51    public static List<TemporalDistanceClusterElement> CreateClusterObjects(ITimeWindowedProblemInstance instance) {
    5152      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
    5253
    … …  
    5859      }
    5960
    60       // wrap stops in SpatialDistanceClusterElement
    61       List<SpatialDistanceClusterElement> clusterObjects = new List<SpatialDistanceClusterElement>();
     61      // wrap stops in TemporalDistanceClusterElement
     62      List<TemporalDistanceClusterElement> clusterObjects = new List<TemporalDistanceClusterElement>();
    6263      foreach (int customer in customers) {
    63         clusterObjects.Add(new SpatialDistanceClusterElement(customer, instance.GetCoordinates(customer)));
     64        clusterObjects.Add(new TemporalDistanceClusterElement(customer, instance.ReadyTime[customer], instance.DueTime[customer]));
    6465      }
    6566      return clusterObjects;
    6667    }
    6768
    68     public static PotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
     69    public static PotvinEncoding CreateSolution(ITimeWindowedProblemInstance instance, IRandom random, int minK, int maxK, double clusterChangeThreshold, int creationOption) {
    6970      PotvinEncoding result = new PotvinEncoding(instance);
    7071
    71       List<SpatialDistanceClusterElement> clusterObjects = CreateClusterObjects(instance);
     72      List<TemporalDistanceClusterElement> clusterObjects = CreateClusterObjects(instance);
    7273
    7374      int k = random.Next(minK, maxK);
    74       List<SpatialDistanceCluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
     75      List<TemporalDistanceCluster> clusters = KMeans(instance, random, clusterObjects, k, clusterChangeThreshold);
    7576
    7677      // (3) build tours
    … …  
    8384        if (creationOption == 0) {
    8485          // (a) shuffle
    85           c.Objects.Shuffle(random);
    86           foreach (var o in c.Objects) {
     86          c.Elements.Shuffle(random);
     87          foreach (var o in c.Elements) {
    8788            newTour.Stops.Add(o.Id);
    8889          }
    8990        } else {
    9091          // (b) greedy
    91           foreach (var o in c.Objects) {
     92          foreach (var o in c.Elements) {
    9293            newTour.Stops.Add(o.Id);
    9394          }
    … …  
    99100    }
    100101
    101     private static List<SpatialDistanceCluster> KMeans(IVRPProblemInstance instance, IRandom random, List<SpatialDistanceClusterElement> objects, int k, double changeTreshold) {
     102    private static List<TemporalDistanceCluster> KMeans(ITimeWindowedProblemInstance instance, IRandom random, List<TemporalDistanceClusterElement> objects, int k, double changeTreshold) {
    102103
    103       List<SpatialDistanceCluster> clusters = new List<SpatialDistanceCluster>();
     104      List<TemporalDistanceCluster> clusters = new List<TemporalDistanceCluster>();
    104105      HashSet<int> initMeans = new HashSet<int>();
    105106      int nextMean = -1;
    … …  
    107108      // (1) initialize each cluster with a random first object (i.e. mean)
    108109      for (int i = 0; i < k && i < objects.Count; i++) {
    109         SpatialDistanceCluster cluster = new SpatialDistanceCluster(instance, i);
     110        TemporalDistanceCluster cluster = new TemporalDistanceCluster(instance, i);
    110111
    111112        do {
    … …  
    128129
    129130      // remove empty clusters
    130       clusters.RemoveAll(c => c.Objects.Count.Equals(0));
     131      clusters.RemoveAll(c => c.Elements.Count.Equals(0));
    131132
    132133      return clusters;
    133134    }
    134135
    135     private static int KMeansRun(List<SpatialDistanceCluster> clusters, List<SpatialDistanceClusterElement> objects) {
     136    private static int KMeansRun(List<TemporalDistanceCluster> clusters, List<TemporalDistanceClusterElement> objects) {
    136137      int changes = 0;
    137138
    138139      foreach (var c in clusters) {
    139         c.Objects.Clear();
     140        c.Elements.Clear();
    140141      }
    141142
    142143      foreach (var o in objects) {
    143         int bestClusterIdx = -1;
    144         double minImpact = double.MaxValue;
    145         for (int i = 0; i < clusters.Count; i++) {
     144        int bestClusterIdx = 0;
     145        double minImpact = clusters[0].CalculateImpact(o);
     146        for (int i = 1; i < clusters.Count; i++) {
    146147          double impact = clusters[i].CalculateImpact(o);
    147           if (impact < minImpact) {
     148          if ((minImpact > 0 && impact < minImpact) || (minImpact < 0 && impact > minImpact)) { // V1: min positive impact
     149          //if(impact > minImpact) { // V2: max impact
    148150            minImpact = impact;
    149151            bestClusterIdx = i;
    … …  
    156158      foreach (var c in clusters) {
    157159        c.CalculateMean();
     160        c.CalculateVariance();
    158161      }
    159162
    … …  
    181184      int creationOption = creationOptions.SampleProportional(random, 1, probabilites, false, false).First();
    182185
    183       VRPToursParameter.ActualValue = CreateSolution(ProblemInstance, random, minK, maxK, clusterChangeThreshold, creationOption);
     186      var instance = ProblemInstance as ITimeWindowedProblemInstance;
     187      if (instance == null) {
     188        throw new ArgumentException(string.Format("Cannot initialize {0} with data from {1}", instance.GetType(), ProblemInstance.GetType()));
     189      }
     190
     191      VRPToursParameter.ActualValue = CreateSolution(instance, random, minK, maxK, clusterChangeThreshold, creationOption);
    184192      return base.InstrumentedApply();
    185193    }

  • branches/HeuristicLab.VRPEnhancements/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

    r14424 r14430  
    198198    <Compile Include="Encodings\Potvin\Creators\Cluster.cs" />
    199199    <Compile Include="Encodings\Potvin\Creators\ClusterCreator.cs" />
     200    <Compile Include="Encodings\Potvin\Creators\TemporalDistanceClusterCreator.cs" />
    200201    <Compile Include="Encodings\Potvin\Creators\GeographicDistanceClusterCreator.cs" />
    201202    <Compile Include="Encodings\Potvin\Crossovers\PotvinEdgePreservingSequenceBasedCrossover.cs" />
Note: See TracChangeset for help on using the changeset viewer.