Changeset 4378 for branches/VRP

Timestamp:

09/10/10 13:00:54 (14 years ago)

Author:

svonolfe

Message:

Improved performance of PotvinEncoding(#1177)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4

Files:

• Encodings/Alba/Moves/AlbaMoveMaker.cs (modified) (1 diff)
• Encodings/Potvin/PotvinEncoding.cs (modified) (1 diff)
• Interfaces/IVRPEvaluator.cs (modified) (2 diffs)
• ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs (modified) (2 diffs)
• ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluator.cs (modified) (2 diffs)
• ProblemInstances/SingleDepotVRP/SingleDepotVRPEvaluator.cs (modified) (1 diff)
• ProblemInstances/VRPEvaluator.cs (modified) (2 diffs)
• ProblemInstances/VRPProblemInstance.cs (modified) (1 diff)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Moves/AlbaMoveMaker.cs

@@ -39 +39 @@
       : base() {
     }
-
-    public override IOperation Apply() {
-      IVRPEncoding solution = VRPToursParameter.ActualValue;
-      if (!(solution is AlbaEncoding)) {
-        //VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value,
-        //  DistanceMatrixParameter);
-      }
-
-      return base.Apply();
-    }
   }
 }

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

@@ -99 +99 @@
       for (int tour = 0; tour < Tours.Count; tour++) {
         if (tour != routeToAvoid) {
+          double length = GetTourLength(Tours[tour]);
+
           for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
-            double length = GetTourLength(Tours[tour]);
-
             Tours[tour].Stops.Insert(i, city);
 
-            if (ProblemInstance.Feasible(Tours[tour])) {
-              double newLength = GetTourLength(Tours[tour]);
+            VRPEvaluation eval = ProblemInstance.EvaluatorParameter.Value.Evaluate(
+              ProblemInstance, Tours[tour]);
+            if (ProblemInstance.EvaluatorParameter.Value.Feasible(eval)) {
+              double newLength = eval.Distance;
 
               double detour = newLength - length;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPEvaluator.cs

@@ -26 +26 @@
 using HeuristicLab.Core;
 using HeuristicLab.Optimization;
+using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
 
 namespace HeuristicLab.Problems.VehicleRouting.Interfaces {
@@ -31 +32 @@
     ILookupParameter<IVRPEncoding> VRPToursParameter { get; }
     
-    bool Feasible(IVRPProblemInstance instance, IVRPEncoding solution);
-    bool Feasible(IVRPProblemInstance instance, Tour tour);
-    double Evaluate(IVRPProblemInstance instance, IVRPEncoding solution);
-    double Evaluate(IVRPProblemInstance instance, Tour tour);
+    VRPEvaluation Evaluate(IVRPProblemInstance instance, IVRPEncoding solution);
+    VRPEvaluation Evaluate(IVRPProblemInstance instance, Tour tour);
+    bool Feasible(VRPEvaluation evaluation);
   }
 }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs

@@ -73 +73 @@
       eval.Quality += instance.DistanceFactor.Value * distance;
 
-      eval.Distance = distance;
-      eval.VehicleUtilization = 1;
+      eval.Distance += distance;
+      eval.VehicleUtilization += 1;
 
       double capacity = cvrpInstance.Capacity.Value;
@@ -81 +81 @@
       }
 
-      (eval as CVRPEvaluation).Overload = overweight;
+      (eval as CVRPEvaluation).Overload += overweight;
       double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
       eval.Penalty += penalty;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluator.cs

@@ -101 +101 @@
       eval.Quality += instance.FleetUsageFactor.Value;
       eval.Quality += instance.DistanceFactor.Value * distance;
-      eval.Distance = distance;
-      eval.VehicleUtilization = 1;
+      eval.Distance += distance;
+      eval.VehicleUtilization += 1;
 
       double capacity = cvrpInstance.Capacity.Value;
@@ -109 +109 @@
       }
 
-      (eval as CVRPEvaluation).Overload = overweight;
+      (eval as CVRPEvaluation).Overload += overweight;
       double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
       eval.Penalty += penalty;
       eval.Quality += penalty;
 
-      (eval as CVRPTWEvaluation).Tardiness = tardiness;
-      (eval as CVRPTWEvaluation).TravelTime = time;
+      (eval as CVRPTWEvaluation).Tardiness += tardiness;
+      (eval as CVRPTWEvaluation).TravelTime += time;
 
       penalty = tardiness * vrptw.TardinessPenalty.Value;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/SingleDepotVRPEvaluator.cs

@@ -62 +62 @@
       quality += instance.DistanceFactor.Value * distance;
 
-      eval.Distance = distance;
-      eval.VehicleUtilization = 1;
+      eval.Distance += distance;
+      eval.VehicleUtilization += 1;
 
-      eval.Quality = quality;
+      eval.Quality += quality;
     }
     

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluator.cs

@@ -84 +84 @@
     }
 
-    protected VRPEvaluation EvaluateTour(IVRPProblemInstance instance, Tour tour) {
+    private VRPEvaluation EvaluateTour(IVRPProblemInstance instance, Tour tour) {
       VRPEvaluation evaluation = CreateTourEvaluation();
       EvaluateTour(evaluation, instance, tour);
@@ -92 +92 @@
     #region IVRPEvaluator Members
 
-    public bool Feasible(IVRPProblemInstance instance, IVRPEncoding solution) {
-      bool feasible = true;
+    public bool Feasible(VRPEvaluation evaluation) {
+      return evaluation.Penalty < double.Epsilon;
+    }
+
+    public VRPEvaluation Evaluate(IVRPProblemInstance instance, IVRPEncoding solution) {
+      VRPEvaluation evaluation = CreateTourEvaluation();
 
       foreach (Tour tour in solution.GetTours()) {
-        if (!Feasible(instance, tour)) {
-          feasible = false;
-          break;
-        }
+        EvaluateTour(evaluation, instance, tour);
       }
 
-      return feasible;
+      return evaluation;
     }
 
-    public bool Feasible(IVRPProblemInstance instance, Tour tour) {
-      return EvaluateTour(instance, tour).Penalty < double.Epsilon;
-    }
-
-    public double Evaluate(IVRPProblemInstance instance, IVRPEncoding solution) {
-      double quality = 0;
-
-      foreach (Tour tour in solution.GetTours()) {
-        quality += Evaluate(instance, tour);
-      }
-
-      return quality;
-    }
-
-    public double Evaluate(IVRPProblemInstance instance, Tour tour) {
-      return EvaluateTour(instance, tour).Quality;
+    public VRPEvaluation Evaluate(IVRPProblemInstance instance, Tour tour) {
+      return EvaluateTour(instance, tour);
     }
 

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs

@@ -147 +147 @@
 
     public bool Feasible(IVRPEncoding solution) {
-      return EvaluatorParameter.Value.Feasible(this, solution);
+      return EvaluatorParameter.Value.Feasible(
+        EvaluatorParameter.Value.Evaluate(
+          this, solution));
     }
 
     public bool Feasible(Tour tour) {
-      return EvaluatorParameter.Value.Feasible(this, tour);
+      return EvaluatorParameter.Value.Feasible(
+        EvaluatorParameter.Value.Evaluate(
+        this, tour));
     }
 
     public double Evaluate(IVRPEncoding solution) {
-      return EvaluatorParameter.Value.Evaluate(this, solution);
+      return EvaluatorParameter.Value.Evaluate(this, solution).Quality;
     }
 
     public double Evaluate(Tour tour) {
-      return EvaluatorParameter.Value.Evaluate(this, tour);
+      return EvaluatorParameter.Value.Evaluate(this, tour).Quality;
     }