Free cookie consent management tool by TermsFeed Policy Generator

Changeset 7815 for branches


Ignore:
Timestamp:
05/14/12 17:55:41 (13 years ago)
Author:
svonolfe
Message:

Added first working version of VRP path relinker (#1331)

Location:
branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/PathRelinkers/VRPPathRelinker.cs

    r7806 r7815  
    3030using HeuristicLab.Problems.VehicleRouting.Encodings;
    3131using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
     32using HeuristicLab.Parameters;
     33using HeuristicLab.Optimization;
    3234
    3335namespace HeuristicLab.Problems.VehicleRouting {
     
    3739  [Item("VRPPathRelinker", "An operator that relinks paths between vehicle routing solutions.")]
    3840  [StorableClass]
    39   public sealed class VRPPathRelinker : PathRelinker {
     41  public sealed class VRPPathRelinker : PathRelinker, IStochasticOperator {
     42    #region Parameters
     43    public ILookupParameter<DoubleMatrix> CoordinatesParameter {
     44      get {
     45        if (Parameters.ContainsKey("Coordinates"))
     46          return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"];
     47        else
     48          return null;
     49      }
     50    }
     51    public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
     52      get {
     53        if (Parameters.ContainsKey("DistanceMatrix"))
     54          return (ILookupParameter<DoubleMatrix>)Parameters["DistanceMatrix"];
     55        else
     56          return null;
     57      }
     58    }
     59    public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
     60      get {
     61        if (Parameters.ContainsKey("UseDistanceMatrix"))
     62          return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"];
     63        else
     64          return null;
     65      }
     66    }
     67    public ILookupParameter<IntValue> VehiclesParameter {
     68      get {
     69        if (Parameters.ContainsKey("Vehicles"))
     70          return (ILookupParameter<IntValue>)Parameters["Vehicles"];
     71        else
     72          return null;
     73      }
     74    }
     75    public ILookupParameter<DoubleValue> CapacityParameter {
     76      get {
     77        if (Parameters.ContainsKey("Capacity"))
     78          return (ILookupParameter<DoubleValue>)Parameters["Capacity"];
     79        else
     80          return null;
     81      }
     82    }
     83    public ILookupParameter<DoubleArray> DemandParameter {
     84      get {
     85        if (Parameters.ContainsKey("Demand"))
     86          return (ILookupParameter<DoubleArray>)Parameters["Demand"];
     87        else
     88          return null;
     89      }
     90    }
     91    public ILookupParameter<DoubleArray> ReadyTimeParameter {
     92      get {
     93        if (Parameters.ContainsKey("ReadyTime"))
     94          return (ILookupParameter<DoubleArray>)Parameters["ReadyTime"];
     95        else
     96          return null;
     97      }
     98    }
     99    public ILookupParameter<DoubleArray> DueTimeParameter {
     100      get {
     101        if (Parameters.ContainsKey("DueTime"))
     102          return (ILookupParameter<DoubleArray>)Parameters["DueTime"];
     103        else
     104          return null;
     105      }
     106    }
     107    public ILookupParameter<DoubleArray> ServiceTimeParameter {
     108      get {
     109        if (Parameters.ContainsKey("ServiceTime"))
     110          return (ILookupParameter<DoubleArray>)Parameters["ServiceTime"];
     111        else
     112          return null;
     113      }
     114    }
     115    public ILookupParameter<DoubleValue> FleetUsageFactor {
     116      get { return (ILookupParameter<DoubleValue>)Parameters["EvalFleetUsageFactor"]; }
     117    }
     118    public ILookupParameter<DoubleValue> TimeFactor {
     119      get { return (ILookupParameter<DoubleValue>)Parameters["EvalTimeFactor"]; }
     120    }
     121    public ILookupParameter<DoubleValue> DistanceFactor {
     122      get { return (ILookupParameter<DoubleValue>)Parameters["EvalDistanceFactor"]; }
     123    }
     124    public ILookupParameter<DoubleValue> OverloadPenalty {
     125      get { return (ILookupParameter<DoubleValue>)Parameters["EvalOverloadPenalty"]; }
     126    }
     127    public ILookupParameter<DoubleValue> TardinessPenalty {
     128      get { return (ILookupParameter<DoubleValue>)Parameters["EvalTardinessPenalty"]; }
     129    }
     130    public ILookupParameter<IRandom> RandomParameter {
     131      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
     132    }
     133
     134    public IValueParameter<IntValue> SampleSizeParameter {
     135      get { return (IValueParameter<IntValue>)Parameters["SampleSize"]; }
     136    }
     137    public IValueParameter<IntValue> IterationsParameter {
     138      get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
     139    }
     140    #endregion
     141
    40142    [StorableConstructor]
    41143    private VRPPathRelinker(bool deserializing) : base(deserializing) { }
    42144    private VRPPathRelinker(VRPPathRelinker original, Cloner cloner) : base(original, cloner) { }
    43     public VRPPathRelinker() : base() { }
     145    public VRPPathRelinker() : base() {
     146      Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The coordinates of the cities."));
     147      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
     148      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false."));
     149      Parameters.Add(new LookupParameter<IntValue>("Vehicles", "The number of vehicles."));
     150      Parameters.Add(new LookupParameter<DoubleValue>("Capacity", "The capacity of each vehicle."));
     151      Parameters.Add(new LookupParameter<DoubleArray>("Demand", "The demand of each customer."));
     152      Parameters.Add(new LookupParameter<DoubleArray>("ReadyTime", "The ready time of each customer."));
     153      Parameters.Add(new LookupParameter<DoubleArray>("DueTime", "The due time of each customer."));
     154      Parameters.Add(new LookupParameter<DoubleArray>("ServiceTime", "The service time of each customer."));
     155      Parameters.Add(new LookupParameter<DoubleValue>("EvalFleetUsageFactor", "The fleet usage factor considered in the evaluation."));
     156      Parameters.Add(new LookupParameter<DoubleValue>("EvalTimeFactor", "The time factor considered in the evaluation."));
     157      Parameters.Add(new LookupParameter<DoubleValue>("EvalDistanceFactor", "The distance factor considered in the evaluation."));
     158      Parameters.Add(new LookupParameter<DoubleValue>("EvalOverloadPenalty", "The overload penalty considered in the evaluation."));
     159      Parameters.Add(new LookupParameter<DoubleValue>("EvalTardinessPenalty", "The tardiness penalty considered in the evaluation."));
     160      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
     161      Parameters.Add(new ValueParameter<IntValue>("SampleSize", new IntValue(250)));
     162      Parameters.Add(new ValueParameter<IntValue>("Iterations", new IntValue(50)));
     163    }
    44164
    45165    public override IDeepCloneable Clone(Cloner cloner) {
     
    47167    }
    48168
    49     public static ItemArray<IItem> Apply(IItem initiator, IItem guide, PercentValue n) {
    50       PotvinEncoding sol1 = initiator.Clone() as PotvinEncoding;
    51       PotvinEncoding sol2 = guide.Clone() as PotvinEncoding;
    52       PotvinEncoding sol3 = new PotvinEncoding();
    53 
    54       // match tours
    55       foreach (Tour tour1 in sol1.Tours) {
    56         int highestMatch = -1;
    57         Tour bestMatchingTour = null;
    58         foreach (Tour tour2 in sol2.Tours) {
    59           int matchingCities = MatchingCities(tour1, tour2);
    60           if (matchingCities > highestMatch) {
    61             bestMatchingTour = tour2;
    62             highestMatch = matchingCities;
     169    private static int MatchingCities(Tour tour1, Tour tour2) {
     170      return tour1.Cities.Intersect(tour2.Cities).Count();
     171    }
     172
     173    private static PotvinEncoding MatchTours(PotvinEncoding initiator, PotvinEncoding guide) {
     174      PotvinEncoding result = new PotvinEncoding();
     175
     176      List<bool> used = new List<bool>();
     177      for (int i = 0; i < initiator.Tours.Count; i++) {
     178        used.Add(false);
     179      }
     180
     181      for (int i = 0; i < guide.Tours.Count; i++) {
     182        int bestMatch = -1;
     183        int bestTour = -1;
     184
     185        for (int j = 0; j < initiator.Tours.Count; j++) {
     186          if (!used[j]) {
     187            int match = MatchingCities(guide.Tours[i], initiator.Tours[j]);
     188            if (match > bestMatch) {
     189              bestMatch = match;
     190              bestTour = j;
     191            }
    63192          }
    64193        }
    65         sol2.Tours.Remove(bestMatchingTour);
    66         sol3.Tours.Add(bestMatchingTour);
    67       }
    68       // add all remaining tours
    69       sol3.Tours.AddRange(sol2.Tours);
    70 
    71       IList<PotvinEncoding> solutions = new List<PotvinEncoding>();
    72       // TODO: add local search
    73 
     194
     195        if (bestTour != -1) {
     196          result.Tours.Add(initiator.Tours[bestTour]);
     197          used[bestTour] = true;
     198        }
     199      }
     200
     201      for (int i = 0; i < initiator.Tours.Count; i++) {
     202        if (!used[i])
     203          result.Tours.Add(initiator.Tours[i]);
     204      }
     205
     206      return result;
     207    }
     208
     209    #region moves
     210    public static void RelocateMove(PotvinEncoding individual, IRandom random) {
     211      int cities = individual.Cities;
     212      int city = 1 + random.Next(cities);
     213      Tour originalTour = individual.Tours.Find(t => t.Cities.Contains(city));
     214      //consider creating new route
     215      individual.Tours.Add(new Tour());
     216
     217      int position = 1 + random.Next(cities + individual.Tours.Count - 1);
     218      if (position >= city) {
     219        position++;
     220      }
     221
     222      int originalPosition = originalTour.Cities.IndexOf(city);
     223      originalTour.Cities.RemoveAt(originalPosition);
     224
     225      Tour insertionTour;
     226      int insertionPosition;
     227      if (position <= cities) {
     228        insertionTour = individual.Tours.Find(t => t.Cities.Contains(position));
     229        insertionPosition = insertionTour.Cities.IndexOf(position) + 1;
     230      } else {
     231        insertionTour = individual.Tours[position - cities - 1];
     232        insertionPosition = 0;
     233      }
     234
     235      insertionTour.Cities.Insert(insertionPosition, city);
     236
     237      individual.Tours.RemoveAll(t => t.Cities.Count == 0);
     238    }
     239
     240    public static void ExchangeMove(PotvinEncoding individual, IRandom random) {
     241      if (individual.Tours.Count > 1) {
     242        int tour1Idx = random.Next(individual.Tours.Count);
     243        int tour2Idx = random.Next(individual.Tours.Count - 1);
     244        if (tour2Idx >= tour1Idx)
     245          tour2Idx++;
     246
     247        Tour tour1 = individual.Tours[tour1Idx];
     248        Tour tour2 = individual.Tours[tour2Idx];
     249
     250        int index1 = random.Next(tour1.Cities.Count);
     251        int city1 = tour1.Cities[index1];
     252
     253        int index2 = random.Next(tour2.Cities.Count);
     254        int city2 = tour2.Cities[index2];
     255
     256        tour1.Cities.RemoveAt(index1);
     257        tour1.Cities.Insert(index1, city2);
     258
     259        tour2.Cities.RemoveAt(index2);
     260        tour2.Cities.Insert(index2, city1);
     261      }
     262    }
     263
     264    public static void TwoOptMove(PotvinEncoding individual, IRandom random) {
     265      List<Tour> tours = individual.Tours.FindAll(t => t.Cities.Count >= 4);
     266
     267      if (tours.Count > 0) {
     268        int tourIdx = random.Next(tours.Count);
     269        Tour tour = tours[tourIdx];
     270
     271        int a;
     272        if (tour.Cities.Count == 4) {
     273          a = 0;
     274        } else if (tour.Cities.Count == 5) {
     275          int idx = random.Next(4);
     276          if (idx >= 2)
     277            idx++;
     278          a = idx;
     279        } else {
     280          a = random.Next(tour.Cities.Count);
     281        }
     282
     283        int b;
     284        List<int> indices = new List<int>();
     285        for (int i = 0; i < tour.Cities.Count; i++) {
     286          if (Math.Abs(i - a) > 2) {
     287            indices.Add(i);
     288          }
     289        }
     290        b = indices[random.Next(indices.Count)];
     291
     292        if (b < a) {
     293          int tmp = a;
     294          a = b;
     295          b = tmp;
     296        }
     297
     298        int index = a + 1;
     299        int count = b - a - 1;
     300        List<int> segment = tour.Cities.GetRange(index, count);
     301        tour.Cities.RemoveRange(index, count);
     302        segment.Reverse();
     303        tour.Cities.InsertRange(index, segment);
     304      }
     305    }
     306
     307    public static void TwoOptStartMove(PotvinEncoding individual, IRandom random) {
     308      //consider creating new tour
     309      individual.Tours.Add(new Tour());
     310
     311      int route1Idx = random.Next(individual.Tours.Count);
     312      int route2Idx = random.Next(individual.Tours.Count - 1);
     313      if (route2Idx >= route1Idx)
     314        route2Idx++;
     315
     316      Tour route1 = individual.Tours[route1Idx];
     317      Tour route2 = individual.Tours[route2Idx];
     318
     319      int x1 = random.Next(route1.Cities.Count + 1);
     320      int x2 = random.Next(route2.Cities.Count + 1);
     321
     322      int count = route1.Cities.Count - x1;
     323      List<int> segmentX1 = new List<int>();
     324      if (count > 0) {
     325        segmentX1 = route1.Cities.GetRange(x1, count);
     326        route1.Cities.RemoveRange(x1, count);
     327      }
     328
     329      count = route2.Cities.Count - x2;
     330      List<int> segmentX2 = new List<int>();
     331      if (count > 0) {
     332        segmentX2 = route2.Cities.GetRange(x2, count);
     333        route2.Cities.RemoveRange(x2, count);
     334      }
     335
     336      route1.Cities.AddRange(segmentX2);
     337      route2.Cities.AddRange(segmentX1);
     338
     339      individual.Tours.RemoveAll(t => t.Cities.Count == 0);
     340    }
     341
     342    public static void OrOptMove(PotvinEncoding individual, IRandom random) {
     343      List<Tour> tours = individual.Tours.FindAll(t => t.Cities.Count >= 2);
     344
     345      if (tours.Count > 0) {
     346        int tourIdx = random.Next(tours.Count);
     347        Tour tour = tours[tourIdx];
     348
     349        int segmentStart = random.Next(tour.Cities.Count);
     350        int segmentLength;
     351        if (segmentStart == 0) {
     352          segmentLength = 1 + random.Next(tour.Cities.Count - 1);
     353        } else {
     354          segmentLength = 1 + random.Next(tour.Cities.Count - segmentStart);
     355        }
     356
     357        List<int> segment = tour.Cities.GetRange(segmentStart, segmentLength);
     358        tour.Cities.RemoveRange(segmentStart, segmentLength);
     359        int newPos;
     360        if (tour.Cities.Count == 1)
     361          newPos = 0;
     362        else
     363          newPos = random.Next(tour.Cities.Count - 1);
     364
     365        if (newPos >= segmentStart)
     366          newPos++;
     367        tour.Cities.InsertRange(newPos, segment);
     368      }
     369    }
     370    #endregion
     371
     372    private static IList<IItem> ChooseSelection(IList<PotvinEncoding> solutions, PercentValue n) {
    74373      IList<IItem> selection = new List<IItem>();
    75374      if (solutions.Count > 0) {
     
    81380      }
    82381
    83       return new ItemArray<IItem>(selection);
    84     }
    85 
    86     private static int MatchingCities(Tour tour1, Tour tour2) {
    87       return tour1.Cities.Intersect(tour2.Cities).Count();
     382      return selection;
     383    }
     384
     385    public static ItemArray<IItem> Apply(PotvinEncoding initiator, PotvinEncoding guide, PercentValue n, int sampleSize, int iterations, IRandom rand,
     386      IntValue vehicles, DoubleArray dueTimeArray,
     387      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
     388      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
     389      DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
     390     
     391      double sigma = 1.5;
     392
     393      DoubleValue currentOverloadPenalty = new DoubleValue(overloadPenalty.Value);
     394      DoubleValue currentTardinessPenalty = new DoubleValue(tardinessPenalty.Value);
     395
     396      PotvinEncoding current = MatchTours(initiator, guide);
     397      double currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
     398
     399      IList<PotvinEncoding> solutions = new List<PotvinEncoding>();
     400      int i = 0;
     401      while(i < iterations && currentSimilarity != 1.0) {
     402        TourEvaluation currentEval = VRPEvaluator.Evaluate(current,
     403          vehicles, dueTimeArray, serviceTimeArray, readyTimeArray,
     404          demandArray, capacity, fleetUsageFactor, timeFactor, distanceFactor,
     405          currentOverloadPenalty, currentTardinessPenalty,
     406          coordinates, distanceMatrix, useDistanceMatrix);
     407        currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
     408
     409        if (currentSimilarity < 1.0) {
     410          for (int sample = 0; sample < sampleSize; sample++) {
     411            PotvinEncoding next = current.Clone() as PotvinEncoding;
     412
     413            int neighborhood = rand.Next(5);
     414            switch (neighborhood) {
     415              case 0: RelocateMove(next, rand);
     416                break;
     417              case 1: ExchangeMove(next, rand);
     418                break;
     419              case 2: TwoOptMove(next, rand);
     420                break;
     421              case 3: TwoOptStartMove(next, rand);
     422                break;
     423              case 4: OrOptMove(next, rand);
     424                break;
     425            }
     426
     427            TourEvaluation nextEval = VRPEvaluator.Evaluate(next,
     428              vehicles, dueTimeArray, serviceTimeArray, readyTimeArray,
     429              demandArray, capacity, fleetUsageFactor, timeFactor, distanceFactor,
     430              currentOverloadPenalty, currentTardinessPenalty,
     431              coordinates, distanceMatrix, useDistanceMatrix);
     432            double nextSimilarity = VRPSimilarityCalculator.CalculateSimilarity(next, guide);
     433
     434            if (nextSimilarity > currentSimilarity && nextEval.Quality <= currentEval.Quality) {
     435              current = next;
     436              solutions.Add(current);
     437              break;
     438            }
     439          }
     440
     441          if (currentEval.Overload > 0)
     442            currentOverloadPenalty.Value *= sigma;
     443          else
     444            currentOverloadPenalty.Value /= sigma;
     445
     446          if (currentEval.Tardiness > 0)
     447            currentTardinessPenalty.Value *= sigma;
     448          else
     449            currentTardinessPenalty.Value /= sigma;
     450
     451          i++;
     452        }
     453      }
     454
     455      return new ItemArray<IItem>(ChooseSelection(solutions, n));
    88456    }
    89457
     
    91459      if (parents.Length != 2)
    92460        throw new ArgumentException("The number of parents is not equal to 2.");
    93       return Apply(parents[0], parents[1], n);
     461
     462      if(!(parents[0] is PotvinEncoding))
     463        parents[0] = PotvinEncoding.ConvertFrom(parents[0] as IVRPEncoding, DistanceMatrixParameter);
     464      if (!(parents[1] is PotvinEncoding))
     465        parents[1] = PotvinEncoding.ConvertFrom(parents[1] as IVRPEncoding, DistanceMatrixParameter);
     466
     467      return Apply(parents[0] as PotvinEncoding, parents[1] as PotvinEncoding, n,
     468        SampleSizeParameter.Value.Value, IterationsParameter.Value.Value, RandomParameter.ActualValue,
     469        VehiclesParameter.ActualValue, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
     470        DemandParameter.ActualValue, CapacityParameter.ActualValue,
     471        FleetUsageFactor.ActualValue, TimeFactor.ActualValue, DistanceFactor.ActualValue, OverloadPenalty.ActualValue, TardinessPenalty.ActualValue,
     472        CoordinatesParameter.ActualValue, DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue);
    94473    }
    95474  }
  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/SimilarityCalculators/VRPSimilarityCalculator.cs

    r7793 r7815  
    2929using HeuristicLab.Problems.VehicleRouting.Encodings;
    3030using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
     31using HeuristicLab.Data;
     32using HeuristicLab.Parameters;
    3133
    3234namespace HeuristicLab.Problems.VehicleRouting {
     
    3739  [StorableClass]
    3840  public sealed class VRPSimilarityCalculator : SimilarityCalculator {
     41    public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
     42      get {
     43        if (Parameters.ContainsKey("DistanceMatrix"))
     44          return (ILookupParameter<DoubleMatrix>)Parameters["DistanceMatrix"];
     45        else
     46          return null;
     47      }
     48    }
     49
    3950    [StorableConstructor]
    4051    private VRPSimilarityCalculator(bool deserializing) : base(deserializing) { }
    4152    private VRPSimilarityCalculator(VRPSimilarityCalculator original, Cloner cloner) : base(original, cloner) { }
    42     public VRPSimilarityCalculator() : base() { }
     53    public VRPSimilarityCalculator() : base() {
     54      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
     55    }
    4356
    4457    public override IDeepCloneable Clone(Cloner cloner) {
     
    4659    }
    4760
    48     protected override double CalculateSimilarity(IScope left, IScope right) {
    49       PotvinEncoding e1 = left.Variables[TargetParameter.ActualName].Value as PotvinEncoding;
    50       PotvinEncoding e2 = right.Variables[TargetParameter.ActualName].Value as PotvinEncoding;
    51 
     61    public static double CalculateSimilarity(PotvinEncoding e1, PotvinEncoding e2) {
    5262      // extract edges from first solution
    5363      var edges1 = new List<Tuple<int, int>>();
    5464      foreach (Tour tour in e1.Tours) {
    5565        edges1.Add(new Tuple<int, int>(0, tour.Cities[0]));
    56         edges1.Add(new Tuple<int, int>(0, tour.Cities[tour.Cities.Count - 1]));
    5766        for (int i = 0; i < tour.Cities.Count - 1; i++)
    5867          edges1.Add(new Tuple<int, int>(tour.Cities[i], tour.Cities[i + 1]));
     68        edges1.Add(new Tuple<int, int>(tour.Cities[tour.Cities.Count - 1], 0));
    5969      }
    6070
     
    6373      foreach (Tour tour in e2.Tours) {
    6474        edges2.Add(new Tuple<int, int>(0, tour.Cities[0]));
    65         edges2.Add(new Tuple<int, int>(0, tour.Cities[tour.Cities.Count - 1]));
    6675        for (int i = 0; i < tour.Cities.Count - 1; i++)
    6776          edges2.Add(new Tuple<int, int>(tour.Cities[i], tour.Cities[i + 1]));
     77        edges2.Add(new Tuple<int, int>(tour.Cities[tour.Cities.Count - 1], 0));
    6878      }
    6979
     
    7383      int identicalEdges = 0;
    7484      foreach (var edge in edges1) {
    75         if (edges2.Any(x => x.Equals(edge) || x.Item1 == edge.Item2 && x.Item2 == edge.Item1))
     85        if (edges2.Any(x => x.Equals(edge)))
    7686          identicalEdges++;
    7787      }
    7888
    79       return identicalEdges * 2.0 / edges1.Count + edges2.Count;
     89      return identicalEdges * 2.0 / (edges1.Count + edges2.Count);
     90    }
     91
     92    protected override double CalculateSimilarity(IScope left, IScope right) {
     93      IVRPEncoding e1 = left.Variables[TargetParameter.ActualName].Value as IVRPEncoding;
     94      if (!(e1 is PotvinEncoding))
     95        e1 = PotvinEncoding.ConvertFrom(e1 as IVRPEncoding, DistanceMatrixParameter);
     96
     97      IVRPEncoding e2 = right.Variables[TargetParameter.ActualName].Value as IVRPEncoding;
     98      if (!(e2 is PotvinEncoding))
     99        e2 = PotvinEncoding.ConvertFrom(e2 as IVRPEncoding, DistanceMatrixParameter);
     100
     101      return CalculateSimilarity(e1 as PotvinEncoding, e2 as PotvinEncoding);
    80102    }
    81103  }
Note: See TracChangeset for help on using the changeset viewer.