Changeset 4860 for branches/VRP/HeuristicLab.Problems.VehicleRouting

Timestamp:

11/19/10 15:43:21 (14 years ago)

Author:

svonolfe

Message:

Merged changes from trunk into branch (#1177)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4

Files:

• Analyzer/BestSolution/BestVRPSolutionAnalyzer.cs (modified) (5 diffs)
• HeuristicLab.Problems.VehicleRouting-3.4.csproj (modified) (1 diff)
• Interfaces/IVRPProblemInstance.cs (modified) (1 diff)
• ProblemInstances/SingleDepotVRP/CVRP/CVRPProblemInstance.cs (modified) (2 diffs)
• ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWProblemInstance.cs (modified) (2 diffs)
• ProblemInstances/VRPProblemInstance.cs (modified) (4 diffs)
• SolutionParser.cs (added)
• VehicleRoutingProblem.cs (modified) (7 diffs)

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

@@ -62 +62 @@
     }
 
+    public LookupParameter<DoubleValue> BestKnownQualityParameter {
+      get { return (LookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
+    }
+    public LookupParameter<VRPSolution> BestKnownSolutionParameter {
+      get { return (LookupParameter<VRPSolution>)Parameters["BestKnownSolution"]; }
+    }
+
     [StorableConstructor]
     private BestVRPSolutionAnalyzer(bool deserializing) : base(deserializing) { }
@@ -69 +76 @@
         Parameters.Add(new LookupParameter<IVRPProblemInstance>("ProblemInstance", "The problem instance."));
         Parameters.Add(new ScopeTreeLookupParameter<IVRPEncoding>("VRPTours", "The VRP tours which should be evaluated."));
+
+        Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
+        Parameters.Add(new LookupParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
 
         Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the VRP solutions which should be analyzed."));
@@ -86 +96 @@
     }
 
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserializationHook() {
+      #region Backwards Compatibility
+      if (!Parameters.ContainsKey("BestKnownQuality")) {
+        Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
+      }
+      if (!Parameters.ContainsKey("BestKnownSolution")) {
+        Parameters.Add(new LookupParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
+      }
+      #endregion
+    }
+
     public override IOperation Apply() {
       IVRPProblemInstance problemInstance = ProblemInstanceParameter.ActualValue;
@@ -96 +118 @@
 
       int i = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
+
+      DoubleValue bestKnownQuality = BestKnownQualityParameter.ActualValue;
 
       IVRPEncoding best = solutions[i].Clone() as IVRPEncoding;
@@ -116 +140 @@
       }
 
+      if (bestKnownQuality == null ||
+          qualities[i].Value < bestKnownQuality.Value) {
+        BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[i].Value);
+        BestKnownSolutionParameter.ActualValue = (VRPSolution)solution.Clone();
+      }
+
       return base.Apply();
     }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

@@ -227 +227 @@
     <Compile Include="Interfaces\IVRPEncoding.cs" />
     <Compile Include="Interfaces\IVRPProblemInstance.cs" />
+    <Compile Include="SolutionParser.cs" />
     <Compile Include="Variants\Capacitated\Heterogenous\IHeterogenousCapacitatedProblemInstance.cs" />
     <Compile Include="Variants\Capacitated\Heterogenous\IHeterogenousCapacitatedOperator.cs" />

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

@@ -32 +32 @@
     IValueParameter<IVRPEvaluator> EvaluatorParameter { get; }
     IValueParameter<IVRPCreator> SolutionCreatorParameter { get; }
+    IValueParameter<DoubleValue> BestKnownQualityParameter { get; }
+    IValueParameter<VRPSolution> BestKnownSolutionParameter { get; }
     IEnumerable<IOperator> Operators { get; }
 

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

@@ -77 +77 @@
       Parameters.Add(new ValueParameter<DoubleValue>("Capacity", "The capacity of each vehicle.", new DoubleValue(0)));
       Parameters.Add(new ValueParameter<DoubleValue>("EvalOverloadPenalty", "The overload penalty considered in the evaluation.", new DoubleValue(100)));
+
+      AttachEventHandlers();
     }
 
@@ -85 +87 @@
     protected CVRPProblemInstance(CVRPProblemInstance original, Cloner cloner)
       : base(original, cloner) {
+        AttachEventHandlers();
     }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserializationHook() {
+      AttachEventHandlers();
+    }
+
+    private void AttachEventHandlers() {
+      CapacityParameter.ValueChanged += new EventHandler(CapacityParameter_ValueChanged);
+      CapacityParameter.Value.ValueChanged += new EventHandler(Capacity_ValueChanged);
+      OverloadPenaltyParameter.ValueChanged += new EventHandler(OverloadPenaltyParameter_ValueChanged);
+      OverloadPenaltyParameter.Value.ValueChanged += new EventHandler(OverloadPenalty_ValueChanged);
+    }
+
+    #region Event handlers
+    void CapacityParameter_ValueChanged(object sender, EventArgs e) {
+      CapacityParameter.Value.ValueChanged += new EventHandler(Capacity_ValueChanged);
+      BestKnownSolution = null;
+    }
+    void Capacity_ValueChanged(object sender, EventArgs e) {
+      BestKnownSolution = null;
+    }
+    void OverloadPenaltyParameter_ValueChanged(object sender, EventArgs e) {
+      OverloadPenaltyParameter.Value.ValueChanged += new EventHandler(OverloadPenalty_ValueChanged);
+      EvalBestKnownSolution();
+    }
+    void OverloadPenalty_ValueChanged(object sender, EventArgs e) {
+      EvalBestKnownSolution();
+    }
+    #endregion
   }
 }

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

@@ -103 +103 @@
       Parameters.Add(new ValueParameter<DoubleValue>("EvalTimeFactor", "The time factor considered in the evaluation.", new DoubleValue(0)));
       Parameters.Add(new ValueParameter<DoubleValue>("EvalTardinessPenalty", "The tardiness penalty considered in the evaluation.", new DoubleValue(100)));
+
+      AttachEventHandlers();
     }
 
@@ -111 +113 @@
     protected CVRPTWProblemInstance(CVRPTWProblemInstance original, Cloner cloner)
       : base(original, cloner) {
+        AttachEventHandlers();
     }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserializationHook() {
+      AttachEventHandlers();
+    }
+
+    private void AttachEventHandlers() {
+      TardinessPenaltyParameter.ValueChanged += new EventHandler(TardinessPenaltyParameter_ValueChanged);
+      TardinessPenaltyParameter.Value.ValueChanged += new EventHandler(TardinessPenalty_ValueChanged);
+      TimeFactorParameter.ValueChanged += new EventHandler(TimeFactorParameter_ValueChanged);
+      TimeFactorParameter.Value.ValueChanged += new EventHandler(TimeFactor_ValueChanged);
+    }
+
+    #region Event handlers
+    void TardinessPenaltyParameter_ValueChanged(object sender, EventArgs e) {
+      TardinessPenaltyParameter.Value.ValueChanged += new EventHandler(TardinessPenalty_ValueChanged);
+      EvalBestKnownSolution();
+    }
+    void TardinessPenalty_ValueChanged(object sender, EventArgs e) {
+      EvalBestKnownSolution();
+    }
+    void TimeFactorParameter_ValueChanged(object sender, EventArgs e) {
+      TimeFactorParameter.Value.ValueChanged += new EventHandler(TimeFactor_ValueChanged);
+      EvalBestKnownSolution();
+    }
+    void TimeFactor_ValueChanged(object sender, EventArgs e) {
+      EvalBestKnownSolution();
+    }
+    #endregion
   }
 }

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

@@ -77 +77 @@
     }
 
+    protected OptionalValueParameter<DoubleValue> BestKnownQualityParameter {
+      get { return (OptionalValueParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
+    }
+    protected OptionalValueParameter<VRPSolution> BestKnownSolutionParameter {
+      get { return (OptionalValueParameter<VRPSolution>)Parameters["BestKnownSolution"]; }
+    }
+
+    IValueParameter<DoubleValue> IVRPProblemInstance.BestKnownQualityParameter {
+      get { return BestKnownQualityParameter; }
+    }
+
+    IValueParameter<VRPSolution> IVRPProblemInstance.BestKnownSolutionParameter {
+      get { return BestKnownSolutionParameter; }
+    }
+
     public DoubleMatrix Coordinates {
       get { return CoordinatesParameter.Value; }
@@ -109 +124 @@
       get { return DistanceFactorParameter.Value; }
       set { DistanceFactorParameter.Value = value; }
+    }
+
+    public DoubleValue BestKnownQuality {
+      get { return BestKnownQualityParameter.Value; }
+      set { BestKnownQualityParameter.Value = value; }
+    }
+    public VRPSolution BestKnownSolution {
+      get { return BestKnownSolutionParameter.Value; }
+      set { BestKnownSolutionParameter.Value = value; }
     }
 
@@ -171 +195 @@
     public double Evaluate(Tour tour) {
       return EvaluatorParameter.Value.Evaluate(this, tour).Quality;
+    }
+
+    protected void EvalBestKnownSolution() {
+      if (BestKnownSolution != null) {
+        //call evaluator
+        BestKnownQuality = new DoubleValue(Evaluate(BestKnownSolution.Solution));
+        BestKnownSolution.Quality = BestKnownQuality;
+      } else {
+        BestKnownQuality = null;
+      }
     }
 
@@ -192 +226 @@
       Parameters.Add(new ValueParameter<IVRPCreator>("SolutionCreator", "The operator which should be used to create new VRP solutions.", Creator));
       Parameters.Add(new ValueParameter<IVRPEvaluator>("Evaluator", "The operator which should be used to evaluate VRP solutions.", Evaluator));
+
+      Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
+      Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
+
+      AttachEventHandlers();
     }
 
     protected VRPProblemInstance(VRPProblemInstance original, Cloner cloner)
       : base(original, cloner) {
-    }
+        AttachEventHandlers();
+    }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserializationHook() {
+      #region Backwards Compatibility
+      if (!Parameters.ContainsKey("BestKnownSolution")) {
+        Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this TSP instance."));
+      }
+      #endregion
+      
+      AttachEventHandlers();
+    }
+
+    private void AttachEventHandlers() {
+      BestKnownSolutionParameter.ValueChanged += new EventHandler(BestKnownSolutionParameter_ValueChanged);
+      DistanceFactorParameter.ValueChanged += new EventHandler(DistanceFactorParameter_ValueChanged);
+      DistanceFactorParameter.Value.ValueChanged += new EventHandler(DistanceFactor_ValueChanged);
+      FleetUsageFactorParameter.ValueChanged += new EventHandler(FleetUsageFactorParameter_ValueChanged);
+      FleetUsageFactorParameter.Value.ValueChanged += new EventHandler(FleetUsageFactor_ValueChanged);
+      DistanceMatrixParameter.ValueChanged += new EventHandler(DistanceMatrixParameter_ValueChanged);
+      if (DistanceMatrix != null) {
+        DistanceMatrix.ItemChanged += new EventHandler<EventArgs<int, int>>(DistanceMatrix_ItemChanged);
+        DistanceMatrix.Reset += new EventHandler(DistanceMatrix_Reset);
+      }
+      UseDistanceMatrixParameter.ValueChanged += new EventHandler(UseDistanceMatrixParameter_ValueChanged);
+      UseDistanceMatrix.ValueChanged += new EventHandler(UseDistanceMatrix_ValueChanged);
+    }
+
+    #region Event handlers
+    void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
+      EvalBestKnownSolution();
+    }
+    void DistanceFactorParameter_ValueChanged(object sender, EventArgs e) {
+      DistanceFactorParameter.Value.ValueChanged += new EventHandler(DistanceFactor_ValueChanged);
+      EvalBestKnownSolution();
+    }
+    void DistanceFactor_ValueChanged(object sender, EventArgs e) {
+      EvalBestKnownSolution();
+    }
+    void FleetUsageFactorParameter_ValueChanged(object sender, EventArgs e) {
+      FleetUsageFactorParameter.Value.ValueChanged += new EventHandler(FleetUsageFactor_ValueChanged);
+      EvalBestKnownSolution();
+    }
+    void FleetUsageFactor_ValueChanged(object sender, EventArgs e) {
+      EvalBestKnownSolution();
+    }
+    void DistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
+      if (DistanceMatrix != null) {
+        DistanceMatrix.ItemChanged += new EventHandler<EventArgs<int, int>>(DistanceMatrix_ItemChanged);
+        DistanceMatrix.Reset += new EventHandler(DistanceMatrix_Reset);
+      }
+      EvalBestKnownSolution();
+    }
+    void DistanceMatrix_Reset(object sender, EventArgs e) {
+      EvalBestKnownSolution();
+    }
+    void DistanceMatrix_ItemChanged(object sender, EventArgs<int, int> e) {
+      EvalBestKnownSolution();
+    }
+    void UseDistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
+      UseDistanceMatrix.ValueChanged += new EventHandler(UseDistanceMatrix_ValueChanged);
+      EvalBestKnownSolution();
+    }
+    void UseDistanceMatrix_ValueChanged(object sender, EventArgs e) {
+      EvalBestKnownSolution();
+    }
+    #endregion
   }
 }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/VehicleRoutingProblem.cs

@@ -64 +64 @@
       get { return BestKnownQualityParameter; }
     }
+    public OptionalValueParameter<VRPSolution> BestKnownSolutionParameter {
+      get { return (OptionalValueParameter<VRPSolution>)Parameters["BestKnownSolution"]; }
+    }
     public IValueParameter<IVRPCreator> SolutionCreatorParameter {
       get { return (IValueParameter<IVRPCreator>)Parameters["SolutionCreator"]; }
@@ -82 +85 @@
       get { return ProblemInstanceParameter.Value; }
       set { ProblemInstanceParameter.Value = value; }
+    }
+
+    public VRPSolution BestKnownSolution {
+      get { return BestKnownSolutionParameter.Value; }
+      set { BestKnownSolutionParameter.Value = value; }
     }
 
@@ -111 +119 @@
       Parameters.Add(new ValueParameter<IVRPProblemInstance>("ProblemInstance", "The VRP problem instance"));
       Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
+      Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
 
       operators = new List<IOperator>();
@@ -172 +181 @@
         Parameters.Remove("SolutionCreator");
 
+      if (Parameters.ContainsKey("BestKnownSolution"))
+        Parameters.Remove("BestKnownSolution");
+
+      if (Parameters.ContainsKey("BestKnownQuality"))
+        Parameters.Remove("BestKnownQuality");
+
+
       if (ProblemInstance != null) {
         ProblemInstance.SolutionCreatorParameter.ValueChanged += new EventHandler(SolutionCreatorParameter_ValueChanged);
@@ -177 +193 @@
         Parameters.Add(ProblemInstance.EvaluatorParameter);
         Parameters.Add(ProblemInstance.SolutionCreatorParameter);
+
+        Parameters.Add(ProblemInstance.BestKnownQualityParameter);
+        Parameters.Add(ProblemInstance.BestKnownSolutionParameter);
       }
     }
@@ -251 +270 @@
       int problemSize = parser.Demands.Length;
 
-      if (parser.Depot != 1)
-        throw new Exception("Invalid depot specification");
-
-      if (parser.WeightType != TSPLIBParser.TSPLIBEdgeWeightType.EUC_2D)
-        throw new Exception("Invalid weight type");
+      if (parser.Depot != 1) {
+        ErrorHandling.ShowErrorDialog(new Exception("Invalid depot specification"));
+        return;
+      }
+
+      if (parser.WeightType != TSPLIBParser.TSPLIBEdgeWeightType.EUC_2D)  {
+        ErrorHandling.ShowErrorDialog(new Exception("Invalid weight type"));
+        return;
+      }
 
       CVRPTWProblemInstance problem = new CVRPTWProblemInstance();
@@ -337 +360 @@
       this.ProblemInstance = problem;
     }
+
+    public void ImportSolution(string solutionFileName) {
+      SolutionParser parser = new SolutionParser(solutionFileName);
+      parser.Parse();
+
+      HeuristicLab.Problems.VehicleRouting.Encodings.Potvin.PotvinEncoding encoding = new Encodings.Potvin.PotvinEncoding(ProblemInstance);
+
+      int cities = 0;
+      foreach (List<int> route in parser.Routes) {
+        Tour tour = new Tour();
+        tour.Stops.AddRange(route);
+        cities += tour.Stops.Count;
+
+        encoding.Tours.Add(tour);
+      }
+
+      if (cities != ProblemInstance.Coordinates.Rows - 1)
+        ErrorHandling.ShowErrorDialog(new Exception("The optimal solution does not seem to correspond with the problem data"));
+      else {
+        VRPSolution solution = new VRPSolution(ProblemInstance, encoding, new DoubleValue(0));
+        ProblemInstance.BestKnownSolutionParameter.Value = solution;
+      }
+    }
   }
 }