Changeset 6752 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.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/PotvinEncoding.cs (modified) (4 diffs)

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);
           }
         }