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

Timestamp:

05/15/12 10:42:00 (12 years ago)

Author:

svonolfe

Message:

Worked on VRP path relinking (#1331)

File:

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

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

@@ -159 +159 @@
       Parameters.Add(new LookupParameter<DoubleValue>("EvalTardinessPenalty", "The tardiness penalty considered in the evaluation."));
       Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
-      Parameters.Add(new ValueParameter<IntValue>("SampleSize", new IntValue(250)));
+      Parameters.Add(new ValueParameter<IntValue>("SampleSize", new IntValue(10)));
       Parameters.Add(new ValueParameter<IntValue>("Iterations", new IntValue(50)));
     }
@@ -208 +208 @@
 
     #region moves
+    public static void GuidedRelocateMove(PotvinEncoding initiator, PotvinEncoding guide, IRandom random) {
+      List<int> cities = new List<int>();
+      foreach (Tour tour in initiator.Tours) {
+        foreach (int city in tour.Cities) {
+          Tour guideTour = guide.Tours.First(t => t.Cities.Contains(city));
+          if (guide.Tours.IndexOf(guideTour) != initiator.Tours.IndexOf(tour)) {
+            cities.Add(city);
+          }
+        }
+      }
+
+      if (cities.Count == 0) {
+        RelocateMove(initiator, random);
+      } else {
+        int city = cities[random.Next(cities.Count)];
+        Tour tour = initiator.Tours.First(t => t.Cities.Contains(city));
+        tour.Cities.Remove(city);
+
+        Tour guideTour = guide.Tours.First(t => t.Cities.Contains(city));
+        int guideTourIndex = guide.Tours.IndexOf(guideTour);
+
+        if (guideTourIndex < initiator.Tours.Count) {
+          Tour tour2 = initiator.Tours[guideTourIndex];
+
+          int guideIndex = guideTour.Cities.IndexOf(city);
+          if (guideIndex == 0) {
+            tour2.Cities.Insert(0, city);
+          } else {
+            int predecessor = guideTour.Cities[guideIndex - 1];
+            int initIndex = tour2.Cities.IndexOf(predecessor);
+            if (initIndex != -1) {
+              tour2.Cities.Insert(initIndex + 1, city);
+            } else {
+              if (guideIndex == guideTour.Cities.Count - 1) {
+                tour2.Cities.Insert(tour2.Cities.Count, city);
+              } else {
+                int sucessor = guideTour.Cities[guideIndex + 1];
+                initIndex = tour2.Cities.IndexOf(sucessor);
+                if (initIndex != -1) {
+                  tour2.Cities.Insert(initIndex, city);
+                } else {
+                  tour2.Cities.Insert(random.Next(tour2.Cities.Count + 1), city);
+                }
+              }
+            }
+          }
+        } else {
+          Tour tour2 = new Tour();
+          tour2.Cities.Add(city);
+          initiator.Tours.Add(tour2);
+        }
+
+        if (tour.Cities.Count == 0)
+          initiator.Tours.Remove(tour);
+      }
+    }
+
     public static void RelocateMove(PotvinEncoding individual, IRandom random) {
       int cities = individual.Cities;
@@ -305 +362 @@
     }
 
-    public static void TwoOptStartMove(PotvinEncoding individual, IRandom random) {
+    public static void TwoOptStarMove(PotvinEncoding individual, IRandom random) {
       //consider creating new tour
       individual.Tours.Add(new Tour());
@@ -411 +468 @@
             PotvinEncoding next = current.Clone() as PotvinEncoding;
 
-            int neighborhood = rand.Next(5);
+            int neighborhood = rand.Next(2);
             switch (neighborhood) {
-              case 0: RelocateMove(next, rand);
+              case 0: GuidedRelocateMove(next, guide, rand);
                 break;
-              case 1: ExchangeMove(next, rand);
+              case 1: TwoOptMove(next, rand);
                 break;
-              case 2: TwoOptMove(next, rand);
+              case 2: TwoOptStarMove(next, rand);
                 break;
-              case 3: TwoOptStartMove(next, rand);
+              case 3: OrOptMove(next, rand);
                 break;
-              case 4: OrOptMove(next, rand);
+              case 4: ExchangeMove(next, rand);
                 break;
             }
+
+            next = MatchTours(next, guide);
 
             TourEvaluation nextEval = VRPEvaluator.Evaluate(next,