Changeset 7821

Timestamp:

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

Author:

svonolfe

Message:

Worked on VRP path relinking (#1331)

Location:

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

Files:

• Encodings/Alba/LocalImprovement/AlbaLambdaInterchangeLocalImprovementOperator.cs (modified) (4 diffs)
• Improvers/VRPImprovementOperator.cs (modified) (1 diff)
• PathRelinkers/VRPPathRelinker.cs (modified) (4 diffs)

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/LocalImprovement/AlbaLambdaInterchangeLocalImprovementOperator.cs

@@ -101 +101 @@
     }
 
-    public static void Apply(AlbaEncoding solution, int maxIterations, 
+    public static void Apply(AlbaEncoding solution, int maxIterations, bool firstImprovement,
       int lambda, int samples, IRandom random, ref double quality, out int evaluatedSolutions, 
       DoubleMatrix distanceMatrix, IntValue vehicles, DoubleArray dueTime, DoubleArray serviceTime, DoubleArray readyTime,
@@ -110 +110 @@
 
       evaluatedSolutions = 0;
+
+      if (quality == -1) {
+        quality = VRPEvaluator.Evaluate(solution, vehicles, dueTime, serviceTime, readyTime,
+          demand, capacity, fleetUsageFactor, timeFactor, distanceFactor,
+          overloadPenalty, tardinessPenalty, coordinates,
+          distanceMatrixParameter, useDistanceMatrix).Quality;
+        evaluatedSolutions++;
+      }
 
       for (int i = 0; i < maxIterations; i++) {
@@ -126 +134 @@
 
           evaluatedSolutions++;
-          if (moveQuality < quality || quality == -1) {
+          if (moveQuality < quality) {
             quality = moveQuality;
             bestMove = move;
+
+            if (firstImprovement)
+              break;
           }
         }
@@ -155 +166 @@
       int evaluatedSolutions;
 
-      Apply(solution, maxIterations, lambda, samples, random, ref quality, out evaluatedSolutions,
+      Apply(solution, maxIterations, false, lambda, samples, random, ref quality, out evaluatedSolutions,
         problem.DistanceMatrix, problem.Vehicles, problem.DueTime, problem.ServiceTime,
         problem.ReadyTime, problem.Demand, problem.Capacity, problem.Coordinates,

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/Improvers/VRPImprovementOperator.cs

@@ -146 +146 @@
       int evaluatedSolutions;
 
-      AlbaLambdaInterchangeLocalImprovementOperator.Apply(solution, ImprovementAttemptsParameter.Value.Value, LambdaParameter.Value.Value,
+      AlbaLambdaInterchangeLocalImprovementOperator.Apply(solution, ImprovementAttemptsParameter.Value.Value, true, LambdaParameter.Value.Value,
         SampleSizeParameter.Value.Value, RandomParameter.ActualValue, ref quality, out evaluatedSolutions, DistanceMatrixParameter.ActualValue,
         VehiclesParameter.ActualValue, DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,

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,