Changeset 6752 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin

Timestamp:

09/13/11 16:00:19 (13 years ago)

Author:

svonolfe

Message:

Added support for incremental evaluation to improve performance (#1177)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin

Files:

• Crossovers/PotvinInsertionBasedCrossover.cs (modified) (2 diffs)
• PotvinEncoding.cs (modified) (4 diffs)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs

@@ -156 +156 @@
         return false;
 
-      bool bestFeasible = false;
+      if (tour.Stops.Count == 0) {
+        place = 0;
+        return true;
+      }
+
       double minDetour = 0;
-
       VRPEvaluation eval = ProblemInstance.Evaluate(tour);
-      double length = eval.Quality;
+      bool originalFeasible = ProblemInstance.Feasible(eval);
+
       for (int i = 0; i <= tour.Stops.Count; i++) {
-        tour.Stops.Insert(i, city);
-
-        eval = ProblemInstance.Evaluate(tour);
-        bool feasible = ProblemInstance.Feasible(eval);
-
-        if (feasible || allowInfeasible && !bestFeasible) {
-          double newLength = eval.Quality;
-          double detour = newLength - length;
-
-          if (place < 0 || detour < minDetour || feasible && !bestFeasible) {
+        bool feasible;
+        double detour = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);
+        if (feasible || allowInfeasible) {
+          if (place < 0 || detour < minDetour) {
             place = i;
             minDetour = detour;
-
-            if (feasible)
-              bestFeasible = true;
           }
         }
-
-        tour.Stops.RemoveAt(i);
       }
 
@@ -248 +241 @@
 
           int place = -1;
-          if (FindRouteInsertionPlace(childTour, city, allowInfeasible, out place)) {
+          bool found = FindRouteInsertionPlace(childTour, city, allowInfeasible, out place); 
+          if (found) {
             childTour.Stops.Insert(place, city);
 

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs

@@ -39 +39 @@
     public List<int> Unrouted { get; set; }
 
-    [Storable]
-    public double PenaltyFactor { get; set; }
-
     public PotvinEncoding(IVRPProblemInstance instance)
       : base(instance) {
       Unrouted = new List<int>();
-      PenaltyFactor = 1;
     }
 
@@ -60 +56 @@
       : base(original, cloner) {
         this.Unrouted = new List<int>(original.Unrouted);
-        this.PenaltyFactor = original.PenaltyFactor;
     }
 
@@ -87 +82 @@
       double minQuality = -1;
 
+      VRPEvaluation eval = ProblemInstance.Evaluate(tour);
+
       for (int i = 0; i <= tour.Stops.Count; i++) {
-        tour.Stops.Insert(i, city);
-
-        VRPEvaluation eval = ProblemInstance.Evaluate(tour);
-        double quality = eval.Quality + eval.Penalty * (PenaltyFactor - 1.0);
-
+        bool feasible;
+        double quality = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);
         if (place < 0 || quality < minQuality) {
           place = i;
           minQuality = quality;
         }
-
-        tour.Stops.RemoveAt(i);
       }
 
@@ -110 +102 @@
       route = -1;
       place = -1;
-      bool bestFeasible = false;
       double minDetour = double.MaxValue;
+
+      VRPEvaluation eval = ProblemInstance.Evaluate(this);
+      bool originalFeasible = ProblemInstance.Feasible(eval);
 
       for (int tour = 0; tour < Tours.Count; tour++) {
         if (tour != routeToAvoid) {
-          VRPEvaluation eval = ProblemInstance.Evaluate(Tours[tour]);
           double length = eval.Quality;
 
           for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
-            Tours[tour].Stops.Insert(i, city);
-
-            eval = ProblemInstance.Evaluate(Tours[tour]);
-            bool feasible = ProblemInstance.Feasible(eval);
-
-            if (feasible || allowInfeasible && !bestFeasible) {
-              double newLength = eval.Quality;
-              double detour = newLength - length;
-
-              if (route < 0 || detour < minDetour || feasible && !bestFeasible) {
+            bool feasible;
+            double detour = ProblemInstance.GetInsertionCosts(eval, city, tour, i, out feasible);
+            
+            if (feasible || allowInfeasible) {
+              if (route < 0 || detour < minDetour) {
                 route = tour;
                 place = i;
                 minDetour = detour;
-
-                if (feasible)
-                  bestFeasible = true;
               }
             }
-
-            Tours[tour].Stops.RemoveAt(i);
           }
         }