source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Analyzer/BestSolution/BestVRPSolutionAnalyzer.cs @ 7854

Last change on this file since 7854 was 7854, checked in by svonolfe, 8 years ago

Adapted BestSolutionAnalyzer to dynamic constraint relaxation (#1177)

File size: 9.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System.Linq;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Operators;
26using HeuristicLab.Optimization;
27using HeuristicLab.Parameters;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29using HeuristicLab.Problems.VehicleRouting.Interfaces;
30using HeuristicLab.Problems.VehicleRouting.Variants;
31using HeuristicLab.Common;
32using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
33
34namespace HeuristicLab.Problems.VehicleRouting {
35  /// <summary>
36  /// An operator for analyzing the best solution of Vehicle Routing Problems.
37  /// </summary>
38  [Item("BestVRPSolutionAnalyzer", "An operator for analyzing the best solution of Vehicle Routing Problems.")]
39  [StorableClass]
40  public sealed class BestVRPSolutionAnalyzer : SingleSuccessorOperator, IAnalyzer, IGeneralVRPOperator {
41    public ILookupParameter<IVRPProblemInstance> ProblemInstanceParameter {
42      get { return (ILookupParameter<IVRPProblemInstance>)Parameters["ProblemInstance"]; }
43    }
44    public ScopeTreeLookupParameter<IVRPEncoding> VRPToursParameter {
45      get { return (ScopeTreeLookupParameter<IVRPEncoding>)Parameters["VRPTours"]; }
46    }
47
48    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
49      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
50    }
51    public ScopeTreeLookupParameter<DoubleValue> DistanceParameter {
52      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Distance"]; }
53    }
54    public ScopeTreeLookupParameter<DoubleValue> VehiclesUtilizedParameter {
55      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["VehiclesUtilized"]; }
56    }
57
58    public LookupParameter<VRPSolution> BestSolutionParameter {
59      get { return (LookupParameter<VRPSolution>)Parameters["BestSolution"]; }
60    }
61    public LookupParameter<VRPSolution> BestValidSolutionParameter {
62      get { return (LookupParameter<VRPSolution>)Parameters["BestValidSolution"]; }
63    }
64    public ValueLookupParameter<ResultCollection> ResultsParameter {
65      get { return (ValueLookupParameter<ResultCollection>)Parameters["Results"]; }
66    }
67
68    public LookupParameter<DoubleValue> BestKnownQualityParameter {
69      get { return (LookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
70    }
71    public LookupParameter<VRPSolution> BestKnownSolutionParameter {
72      get { return (LookupParameter<VRPSolution>)Parameters["BestKnownSolution"]; }
73    }
74
75    public bool EnabledByDefault {
76      get { return true; }
77    }
78
79    [StorableConstructor]
80    private BestVRPSolutionAnalyzer(bool deserializing) : base(deserializing) { }
81
82    public BestVRPSolutionAnalyzer()
83      : base() {
84        Parameters.Add(new LookupParameter<IVRPProblemInstance>("ProblemInstance", "The problem instance."));
85        Parameters.Add(new ScopeTreeLookupParameter<IVRPEncoding>("VRPTours", "The VRP tours which should be evaluated."));
86
87        Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
88        Parameters.Add(new LookupParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
89
90        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the VRP solutions which should be analyzed."));
91        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Distance", "The distances of the VRP solutions which should be analyzed."));
92        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("VehiclesUtilized", "The utilized vehicles of the VRP solutions which should be analyzed."));
93
94        Parameters.Add(new LookupParameter<VRPSolution>("BestSolution", "The best VRP solution."));
95        Parameters.Add(new LookupParameter<VRPSolution>("BestValidSolution", "The best valid VRP solution."));
96        Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the best VRP solution should be stored."));
97    }
98
99    public override IDeepCloneable Clone(Cloner cloner) {
100      return new BestVRPSolutionAnalyzer(this, cloner);
101    }
102
103    private BestVRPSolutionAnalyzer(BestVRPSolutionAnalyzer original, Cloner cloner)
104      : base(original, cloner) {
105    }
106
107    [StorableHook(HookType.AfterDeserialization)]
108    private void AfterDeserializationHook() {
109      #region Backwards Compatibility
110      if (!Parameters.ContainsKey("BestKnownQuality")) {
111        Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
112      }
113      if (!Parameters.ContainsKey("BestKnownSolution")) {
114        Parameters.Add(new LookupParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
115      }
116      #endregion
117    }
118
119    public override IOperation Apply() {
120      IVRPProblemInstance problemInstance = ProblemInstanceParameter.ActualValue;
121      ItemArray<IVRPEncoding> solutions = VRPToursParameter.ActualValue;
122      ResultCollection results = ResultsParameter.ActualValue;
123
124      ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
125      ItemArray<DoubleValue> distances = DistanceParameter.ActualValue;
126      ItemArray<DoubleValue> vehiclesUtilizations = VehiclesUtilizedParameter.ActualValue;
127
128      int i = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
129      IVRPEncoding best = solutions[i].Clone() as IVRPEncoding;
130      VRPSolution solution = BestSolutionParameter.ActualValue;
131      if (solution == null) {
132        solution = new VRPSolution(problemInstance, best.Clone() as IVRPEncoding, new DoubleValue(qualities[i].Value));
133        BestSolutionParameter.ActualValue = solution;
134        results.Add(new Result("Best VRP Solution", solution));
135
136        results.Add(new Result("Best VRP Solution Distance", new DoubleValue(distances[i].Value)));
137        results.Add(new Result("Best VRP Solution VehicleUtilization", new DoubleValue(vehiclesUtilizations[i].Value)));
138      } else {
139        VRPEvaluation eval = problemInstance.Evaluate(solution.Solution);
140        if (qualities[i].Value <= eval.Quality) {
141          solution.ProblemInstance = problemInstance;
142          solution.Solution = best.Clone() as IVRPEncoding;
143          solution.Quality.Value = qualities[i].Value;
144          (results["Best VRP Solution Distance"].Value as DoubleValue).Value = distances[i].Value;
145          (results["Best VRP Solution VehicleUtilization"].Value as DoubleValue).Value = vehiclesUtilizations[i].Value;
146        }
147      }
148
149      var idx = qualities.Select((x, index) => new { index, x.Value }).Where(index => problemInstance.Feasible(solutions[index.index])).OrderBy(x => x.Value).FirstOrDefault();
150      if (idx != null) {
151        int j = idx.index;
152        IVRPEncoding bestFeasible = solutions[j].Clone() as IVRPEncoding;
153        VRPSolution validSolution = BestValidSolutionParameter.ActualValue;
154        if (validSolution == null) {
155          if (ProblemInstanceParameter.ActualValue.Feasible(best)) {
156            validSolution = new VRPSolution(problemInstance, best.Clone() as IVRPEncoding, new DoubleValue(qualities[j].Value));
157            BestValidSolutionParameter.ActualValue = validSolution;
158            if (results.ContainsKey("Best valid VRP Solution"))
159              results["Best valid VRP Solution"].Value = validSolution;
160            else
161              results.Add(new Result("Best valid VRP Solution", validSolution));
162
163            results.Add(new Result("Best valid VRP Solution Distance", new DoubleValue(distances[j].Value)));
164            results.Add(new Result("Best valid VRP Solution VehicleUtilization", new DoubleValue(vehiclesUtilizations[j].Value)));
165          }
166        } else {
167          if (qualities[j].Value <= validSolution.Quality.Value) {
168            if (ProblemInstanceParameter.ActualValue.Feasible(best)) {
169              validSolution.ProblemInstance = problemInstance;
170              validSolution.Solution = best.Clone() as IVRPEncoding;
171              validSolution.Quality.Value = qualities[j].Value;
172              (results["Best valid VRP Solution Distance"].Value as DoubleValue).Value = distances[j].Value;
173              (results["Best valid VRP Solution VehicleUtilization"].Value as DoubleValue).Value = vehiclesUtilizations[j].Value;
174            }
175          }
176        }
177
178        DoubleValue bestKnownQuality = BestKnownQualityParameter.ActualValue;
179        if (bestKnownQuality == null || qualities[j].Value < bestKnownQuality.Value) {
180          BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[j].Value);
181          BestKnownSolutionParameter.ActualValue = (VRPSolution)validSolution.Clone();
182        }
183      }
184
185      return base.Apply();
186    }
187  }
188}
Note: See TracBrowser for help on using the repository browser.