Changeset 7806 for branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting

Timestamp:

05/14/12 15:46:27 (13 years ago)

Author:

jkarder

Message:

#1331: VRPPathRelinker now performs tour matching

File:

• branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/PathRelinkers/VRPPathRelinker.cs (modified) (3 diffs)

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/PathRelinkers/VRPPathRelinker.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -26 +28 @@
 using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Problems.VehicleRouting.Encodings;
+using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
 
 namespace HeuristicLab.Problems.VehicleRouting {
@@ -44 +48 @@
 
     public static ItemArray<IItem> Apply(IItem initiator, IItem guide, PercentValue n) {
-      // TODO: path relinking
-      return new ItemArray<IItem>();
+      PotvinEncoding sol1 = initiator.Clone() as PotvinEncoding;
+      PotvinEncoding sol2 = guide.Clone() as PotvinEncoding;
+      PotvinEncoding sol3 = new PotvinEncoding();
+
+      // match tours
+      foreach (Tour tour1 in sol1.Tours) {
+        int highestMatch = -1;
+        Tour bestMatchingTour = null;
+        foreach (Tour tour2 in sol2.Tours) {
+          int matchingCities = MatchingCities(tour1, tour2);
+          if (matchingCities > highestMatch) {
+            bestMatchingTour = tour2;
+            highestMatch = matchingCities;
+          }
+        }
+        sol2.Tours.Remove(bestMatchingTour);
+        sol3.Tours.Add(bestMatchingTour);
+      }
+      // add all remaining tours
+      sol3.Tours.AddRange(sol2.Tours);
+
+      IList<PotvinEncoding> solutions = new List<PotvinEncoding>();
+      // TODO: add local search
+
+      IList<IItem> selection = new List<IItem>();
+      if (solutions.Count > 0) {
+        int noSol = (int)(solutions.Count * n.Value);
+        if (noSol <= 0) noSol++;
+        double stepSize = (double)solutions.Count / (double)noSol;
+        for (int i = 0; i < noSol; i++)
+          selection.Add(solutions.ElementAt((int)((i + 1) * stepSize - stepSize * 0.5)));
+      }
+
+      return new ItemArray<IItem>(selection);
+    }
+
+    private static int MatchingCities(Tour tour1, Tour tour2) {
+      return tour1.Cities.Intersect(tour2.Cities).Count();
     }