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

Timestamp:

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

Author:

svonolfe

Message:

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

File:

• branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs (modified) (2 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);