Changeset 5202 for branches/VRP

Timestamp:

01/03/11 16:19:17 (14 years ago)

Author:

svonolfe

Message:

Added usage of the TS memory in the customer relocation move (#1177)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4

Files:

• Analyzer/BestSolution/BestVRPSolutionAnalyzer.cs (modified) (3 diffs)
• Encodings/Potvin/Moves/CustomerRelocation/PotvinCustomerRelocationMoveEvaluator.cs (modified) (3 diffs)
• Encodings/Potvin/Moves/CustomerRelocation/PotvinCustomerRelocationMoveMaker.cs (modified) (3 diffs)
• Encodings/Potvin/PotvinEncoding.cs (modified) (2 diffs)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Analyzer/BestSolution/BestVRPSolutionAnalyzer.cs

@@ -58 +58 @@
       get { return (LookupParameter<VRPSolution>)Parameters["BestSolution"]; }
     }
+    public LookupParameter<VRPSolution> BestValidSolutionParameter {
+      get { return (LookupParameter<VRPSolution>)Parameters["BestValidSolution"]; }
+    }
     public ValueLookupParameter<ResultCollection> ResultsParameter {
       get { return (ValueLookupParameter<ResultCollection>)Parameters["Results"]; }
@@ -84 +87 @@
         Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("VehiclesUtilized", "The utilized vehicles of the VRP solutions which should be analyzed."));
 
-        Parameters.Add(new LookupParameter<VRPSolution>("BestSolution", "The best TSP solution."));
+        Parameters.Add(new LookupParameter<VRPSolution>("BestSolution", "The best VRP solution."));
+        Parameters.Add(new LookupParameter<VRPSolution>("BestValidSolution", "The best valid VRP solution."));
         Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the best VRP solution should be stored."));
     }
@@ -140 +144 @@
       }
 
+      VRPSolution validSolution = BestValidSolutionParameter.ActualValue;
+      if (validSolution == null) {
+        if (ProblemInstanceParameter.ActualValue.Feasible(best)) {
+          validSolution = new VRPSolution(problemInstance, best.Clone() as IVRPEncoding, new DoubleValue(qualities[i].Value));
+          BestValidSolutionParameter.ActualValue = validSolution;
+          results.Add(new Result("Best valid VRP Solution", validSolution));
+        }
+      } else {
+        if (qualities[i].Value <= validSolution.Quality.Value) {
+          if (ProblemInstanceParameter.ActualValue.Feasible(best)) {
+            validSolution.ProblemInstance = problemInstance;
+            validSolution.Solution = best.Clone() as IVRPEncoding;
+            validSolution.Quality.Value = qualities[i].Value;
+          }
+        }
+      }
+
       if (bestKnownQuality == null ||
           qualities[i].Value < bestKnownQuality.Value) {

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/CustomerRelocation/PotvinCustomerRelocationMoveEvaluator.cs

@@ -40 +40 @@
     }
 
-    public ILookupParameter<IMemory> MemoryParameter {
-      get { return (ILookupParameter<IMemory>)Parameters["Memory"]; }
+    public ILookupParameter<VariableCollection> MemoriesParameter {
+      get { return (ILookupParameter<VariableCollection>)Parameters["Memories"]; }
     }
 
-    public IValueParameter<StringValue> AdditionFrequencyParameter {
-      get { return (IValueParameter<StringValue>)Parameters["AdditionFrequency"]; }
+    public IValueParameter<StringValue> AdditionFrequencyMemoryKeyParameter {
+      get { return (IValueParameter<StringValue>)Parameters["AdditionFrequencyMemoryKey"]; }
     }
 
@@ -59 +59 @@
        Parameters.Add(new LookupParameter<PotvinCustomerRelocationMove>("PotvinCustomerRelocationMove", "The move that should be evaluated."));
 
-       Parameters.Add(new LookupParameter<IMemory>("Memory", "The TS memory."));
-       Parameters.Add(new ValueParameter<StringValue>("AdditionFrequency", "The key that is used for the addition frequency in the TS memory.", new StringValue("AdditionFrequency")));
+       Parameters.Add(new LookupParameter<VariableCollection>("Memories", "The TS memory collection."));
+       Parameters.Add(new ValueParameter<StringValue>("AdditionFrequencyMemoryKey", "The key that is used for the addition frequency in the TS memory.", new StringValue("AdditionFrequency")));
        Parameters.Add(new ValueParameter<DoubleValue>("Lambda", "The lambda parameter.", new DoubleValue(0.015)));
     }
@@ -82 +82 @@
       //Apply memory, only if move is worse
       if (MoveQualityParameter.ActualValue.Value >= QualityParameter.ActualValue.Value) {
-        IMemory memory = MemoryParameter.ActualValue;
-        string key = AdditionFrequencyParameter.Value.Value;
-        ItemDictionary<PotvinCustomerRelocationMoveAttribute, IntValue> additionFrequency =
-          memory.Get(key) as ItemDictionary<PotvinCustomerRelocationMoveAttribute, IntValue>;
-        if (additionFrequency != null) {
+        VariableCollection memory = MemoriesParameter.ActualValue;
+        string key = AdditionFrequencyMemoryKeyParameter.Value.Value;
+
+        if (memory.ContainsKey(key)) {
+          ItemDictionary<PotvinCustomerRelocationMoveAttribute, IntValue> additionFrequency =
+               memory[key].Value as ItemDictionary<PotvinCustomerRelocationMoveAttribute, IntValue>;
           PotvinCustomerRelocationMoveAttribute attr = new PotvinCustomerRelocationMoveAttribute(0, move.Tour, move.City);
           if (additionFrequency.ContainsKey(attr)) {

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/CustomerRelocation/PotvinCustomerRelocationMoveMaker.cs

@@ -53 +53 @@
     }
 
-    public ILookupParameter<IMemory> MemoryParameter {
-      get { return (ILookupParameter<IMemory>)Parameters["Memory"]; } 
+    public ILookupParameter<VariableCollection> MemoriesParameter {
+      get { return (ILookupParameter<VariableCollection>)Parameters["Memories"]; } 
     }
 
-    public IValueParameter<StringValue> AdditionFrequencyParameter {
-      get { return (IValueParameter<StringValue>)Parameters["AdditionFrequency"]; }
+    public IValueParameter<StringValue> AdditionFrequencyMemoryKeyParameter {
+      get { return (IValueParameter<StringValue>)Parameters["AdditionFrequencyMemoryKey"]; }
     }
 
@@ -71 +71 @@
       Parameters.Add(new ValueParameter<DoubleValue>("MaxPenaltyFactor", "The maximum penalty factor.", new DoubleValue(1000.0)));
 
-      Parameters.Add(new LookupParameter<IMemory>("Memory", "The TS memory."));
-      Parameters.Add(new ValueParameter<StringValue>("AdditionFrequency", "The key that is used for the addition frequency in the TS memory.", new StringValue("AdditionFrequency")));
+      Parameters.Add(new LookupParameter<VariableCollection>("Memories", "The TS memory collection."));
+      Parameters.Add(new ValueParameter<StringValue>("AdditionFrequencyMemoryKey", "The key that is used for the addition frequency in the TS memory.", new StringValue("AdditionFrequency")));
     }
 
@@ -122 +122 @@
 
       //update memory
-      IMemory memory = MemoryParameter.ActualValue;
-      string key = AdditionFrequencyParameter.Value.Value;
+      VariableCollection memory = MemoriesParameter.ActualValue;
+      string key = AdditionFrequencyMemoryKeyParameter.Value.Value;
+
+      if (!memory.ContainsKey(key)) {
+        memory.Add(new Variable(key,
+            new ItemDictionary<PotvinCustomerRelocationMoveAttribute, IntValue>()));
+      }
       ItemDictionary<PotvinCustomerRelocationMoveAttribute, IntValue> additionFrequency =
-        memory.Get(key) as ItemDictionary<PotvinCustomerRelocationMoveAttribute, IntValue>;
-      if (additionFrequency == null) {
-        additionFrequency = new ItemDictionary<PotvinCustomerRelocationMoveAttribute, IntValue>();
-        memory.Put(key, additionFrequency);
-      }
+        memory[key].Value as ItemDictionary<PotvinCustomerRelocationMoveAttribute, IntValue>;
+
       PotvinCustomerRelocationMoveAttribute attr = new PotvinCustomerRelocationMoveAttribute(0, move.Tour, move.City);
       if (!additionFrequency.ContainsKey(attr))

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

@@ -79 +79 @@
     }
 
-    public double EvaluateTour(Tour tour) {
-      return ProblemInstance.Evaluate(tour);
-    }
-
     public double GetTourLength(Tour tour) {
       double length = 0;
@@ -109 +105 @@
         tour.Stops.Insert(i, city);
 
-        double quality = EvaluateTour(tour);
+        VRPEvaluation eval = ProblemInstance.EvaluatorParameter.Value.Evaluate(ProblemInstance, tour);
+        double quality = eval.Quality + eval.Penalty * (PenaltyFactor - 1.0);
 
         if (place < 0 || quality < minQuality) {