Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs @ 6522

Last change on this file since 6522 was 5867, checked in by svonolfe, 13 years ago

Merged changes from trunk into branch (#1177)
File size: 13.7 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;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using HeuristicLab.Problems.VehicleRouting.Interfaces;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using HeuristicLab.Core;
29using HeuristicLab.Parameters;
30using HeuristicLab.Data;
31using HeuristicLab.Optimization;
32using HeuristicLab.PluginInfrastructure;
33using HeuristicLab.Common;
34using HeuristicLab.Problems.VehicleRouting.Encodings.General;
35
36namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
37  [Item("VRPProblemInstance", "Represents a VRP instance.")]
38  [StorableClass]
39  public abstract class VRPProblemInstance: ParameterizedNamedItem, IVRPProblemInstance {
40    public IValueParameter<IVRPEvaluator> EvaluatorParameter {
41      get { return (ValueParameter<IVRPEvaluator>)Parameters["Evaluator"]; }
42    }
43
44    IVRPEvaluator moveEvaluator;
45
46    public IVRPEvaluator MoveEvaluator {
47      get {
48        if (EvaluatorParameter.Value == null)
49          return null;
50        else {
51          if (moveEvaluator == null) {
52            moveEvaluator = EvaluatorParameter.Value.Clone() as IVRPEvaluator;
53
54            foreach (IParameter parameter in moveEvaluator.Parameters) {
55              if (parameter is ILookupParameter
56                && parameter != moveEvaluator.ProblemInstanceParameter
57                && parameter != moveEvaluator.VRPToursParameter) {
58                (parameter as ILookupParameter).ActualName =
59                  VRPMoveEvaluator.MovePrefix +
60                  (parameter as ILookupParameter).ActualName;
61              }
62            }
63          }
64
65          return moveEvaluator;
66        }
67      }
68    }
69
70    public IValueParameter<IVRPCreator> SolutionCreatorParameter {
71      get { return (ValueParameter<IVRPCreator>)Parameters["SolutionCreator"]; }
72    }
73
74    protected abstract IEnumerable<IOperator> GetOperators();
75    protected abstract IEnumerable<IOperator> GetAnalyzers();
76
77    public IEnumerable<IOperator> Operators {
78      get {
79        return GetOperators().Union(GetAnalyzers());
80      }
81    }
82   
83    protected ValueParameter<DoubleMatrix> CoordinatesParameter {
84      get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
85    }
86    protected OptionalValueParameter<DoubleMatrix> DistanceMatrixParameter {
87      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
88    }
89    protected ValueParameter<BoolValue> UseDistanceMatrixParameter {
90      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
91    }
92    protected ValueParameter<IntValue> VehiclesParameter {
93      get { return (ValueParameter<IntValue>)Parameters["Vehicles"]; }
94    }
95    protected ValueParameter<DoubleArray> DemandParameter {
96      get { return (ValueParameter<DoubleArray>)Parameters["Demand"]; }
97    }
98
99    protected IValueParameter<DoubleValue> FleetUsageFactorParameter {
100      get { return (IValueParameter<DoubleValue>)Parameters["EvalFleetUsageFactor"]; }
101    }
102    protected IValueParameter<DoubleValue> DistanceFactorParameter {
103      get { return (IValueParameter<DoubleValue>)Parameters["EvalDistanceFactor"]; }
104    }
105
106    protected OptionalValueParameter<DoubleValue> BestKnownQualityParameter {
107      get { return (OptionalValueParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
108    }
109    protected OptionalValueParameter<VRPSolution> BestKnownSolutionParameter {
110      get { return (OptionalValueParameter<VRPSolution>)Parameters["BestKnownSolution"]; }
111    }
112
113    IValueParameter<DoubleValue> IVRPProblemInstance.BestKnownQualityParameter {
114      get { return BestKnownQualityParameter; }
115    }
116
117    IValueParameter<VRPSolution> IVRPProblemInstance.BestKnownSolutionParameter {
118      get { return BestKnownSolutionParameter; }
119    }
120
121    public DoubleMatrix Coordinates {
122      get { return CoordinatesParameter.Value; }
123      set { CoordinatesParameter.Value = value; }
124    }
125
126    public DoubleMatrix DistanceMatrix {
127      get { return DistanceMatrixParameter.Value; }
128      set { DistanceMatrixParameter.Value = value; }
129    }
130    public BoolValue UseDistanceMatrix {
131      get { return UseDistanceMatrixParameter.Value; }
132      set { UseDistanceMatrixParameter.Value = value; }
133    }
134    public IntValue Vehicles {
135      get { return VehiclesParameter.Value; }
136      set { VehiclesParameter.Value = value; }
137    }
138    public DoubleArray Demand {
139      get { return DemandParameter.Value; }
140      set { DemandParameter.Value = value; }
141    }
142    public virtual IntValue Cities {
143      get { return new IntValue(Demand.Length); }
144    }
145
146    public DoubleValue FleetUsageFactor {
147      get { return FleetUsageFactorParameter.Value; }
148      set { FleetUsageFactorParameter.Value = value; }
149    }
150    public DoubleValue DistanceFactor {
151      get { return DistanceFactorParameter.Value; }
152      set { DistanceFactorParameter.Value = value; }
153    }
154
155    public DoubleValue BestKnownQuality {
156      get { return BestKnownQualityParameter.Value; }
157      set { BestKnownQualityParameter.Value = value; }
158    }
159    public VRPSolution BestKnownSolution {
160      get { return BestKnownSolutionParameter.Value; }
161      set { BestKnownSolutionParameter.Value = value; }
162    }
163
164    private double CalculateDistance(int start, int end) {
165      double distance = 0.0;
166
167      distance =
168          Math.Sqrt(
169            Math.Pow(Coordinates[start, 0] - Coordinates[end, 0], 2) +
170            Math.Pow(Coordinates[start, 1] - Coordinates[end, 1], 2));
171
172      return distance;
173    }
174
175    private DoubleMatrix CreateDistanceMatrix() {
176      DoubleMatrix distanceMatrix = new DoubleMatrix(Coordinates.Rows, Coordinates.Rows);
177
178      for (int i = 0; i < distanceMatrix.Rows; i++) {
179        for (int j = i; j < distanceMatrix.Columns; j++) {
180          double distance = CalculateDistance(i, j);
181
182          distanceMatrix[i, j] = distance;
183          distanceMatrix[j, i] = distance;
184        }
185      }
186
187      return distanceMatrix;
188    }
189   
190    public double GetDistance(int start, int end) {
191      double distance = 0.0;
192      DoubleMatrix distanceMatrix = DistanceMatrix;
193
194      if (distanceMatrix == null && UseDistanceMatrix.Value) {
195        distanceMatrix = DistanceMatrix = CreateDistanceMatrix();
196      }
197
198      if (distanceMatrix != null)
199        distance = distanceMatrix[start, end];
200      else
201        distance = CalculateDistance(start, end);
202
203      return distance;
204    }
205
206    public bool Feasible(IVRPEncoding solution) {
207      return EvaluatorParameter.Value.Feasible(
208        EvaluatorParameter.Value.Evaluate(
209          this, solution));
210    }
211
212    public bool Feasible(Tour tour) {
213      return EvaluatorParameter.Value.Feasible(
214        EvaluatorParameter.Value.Evaluate(
215        this, tour));
216    }
217
218    public double Evaluate(IVRPEncoding solution) {
219      return EvaluatorParameter.Value.Evaluate(this, solution).Quality;
220    }
221
222    public double Evaluate(Tour tour) {
223      return EvaluatorParameter.Value.Evaluate(this, tour).Quality;
224    }
225
226    protected void EvalBestKnownSolution() {
227      if (BestKnownSolution != null) {
228        //call evaluator
229        BestKnownQuality = new DoubleValue(Evaluate(BestKnownSolution.Solution));
230        BestKnownSolution.Quality = BestKnownQuality;
231      } else {
232        BestKnownQuality = null;
233      }
234    }
235
236    protected abstract IVRPEvaluator Evaluator { get; }
237    protected abstract IVRPCreator Creator { get; }
238   
239    [StorableConstructor]
240    protected VRPProblemInstance(bool deserializing) : base(deserializing) { }
241
242    public VRPProblemInstance()
243      : base() {
244      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.", new DoubleMatrix()));
245      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
246      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false.", new BoolValue(true)));
247      Parameters.Add(new ValueParameter<IntValue>("Vehicles", "The number of vehicles.", new IntValue(0)));
248      Parameters.Add(new ValueParameter<DoubleArray>("Demand", "The demand of each customer.", new DoubleArray()));
249
250      Parameters.Add(new ValueParameter<DoubleValue>("EvalFleetUsageFactor", "The fleet usage factor considered in the evaluation.", new DoubleValue(0)));
251      Parameters.Add(new ValueParameter<DoubleValue>("EvalDistanceFactor", "The distance factor considered in the evaluation.", new DoubleValue(1)));
252
253      Parameters.Add(new ValueParameter<IVRPCreator>("SolutionCreator", "The operator which should be used to create new VRP solutions.", Creator));
254      Parameters.Add(new ValueParameter<IVRPEvaluator>("Evaluator", "The operator which should be used to evaluate VRP solutions.", Evaluator));
255
256      Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
257      Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
258
259      AttachEventHandlers();
260    }
261
262    protected VRPProblemInstance(VRPProblemInstance original, Cloner cloner)
263      : base(original, cloner) {
264        AttachEventHandlers();
265    }
266
267    [StorableHook(HookType.AfterDeserialization)]
268    private void AfterDeserializationHook() {
269      #region Backwards Compatibility
270      if (!Parameters.ContainsKey("BestKnownSolution")) {
271        Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this TSP instance."));
272      }
273      if (!Parameters.ContainsKey("BestKnownQuality")) {
274        Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
275      }
276      #endregion
277     
278      AttachEventHandlers();
279    }
280
281    private void AttachEventHandlers() {
282      EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
283      BestKnownSolutionParameter.ValueChanged += new EventHandler(BestKnownSolutionParameter_ValueChanged);
284      DistanceFactorParameter.ValueChanged += new EventHandler(DistanceFactorParameter_ValueChanged);
285      DistanceFactorParameter.Value.ValueChanged += new EventHandler(DistanceFactor_ValueChanged);
286      FleetUsageFactorParameter.ValueChanged += new EventHandler(FleetUsageFactorParameter_ValueChanged);
287      FleetUsageFactorParameter.Value.ValueChanged += new EventHandler(FleetUsageFactor_ValueChanged);
288      DistanceMatrixParameter.ValueChanged += new EventHandler(DistanceMatrixParameter_ValueChanged);
289      if (DistanceMatrix != null) {
290        DistanceMatrix.ItemChanged += new EventHandler<EventArgs<int, int>>(DistanceMatrix_ItemChanged);
291        DistanceMatrix.Reset += new EventHandler(DistanceMatrix_Reset);
292      }
293      UseDistanceMatrixParameter.ValueChanged += new EventHandler(UseDistanceMatrixParameter_ValueChanged);
294      UseDistanceMatrix.ValueChanged += new EventHandler(UseDistanceMatrix_ValueChanged);
295    }
296
297    #region Event handlers
298    void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
299      moveEvaluator = null;
300    }
301
302    void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
303      EvalBestKnownSolution();
304    }
305    void DistanceFactorParameter_ValueChanged(object sender, EventArgs e) {
306      DistanceFactorParameter.Value.ValueChanged += new EventHandler(DistanceFactor_ValueChanged);
307      EvalBestKnownSolution();
308    }
309    void DistanceFactor_ValueChanged(object sender, EventArgs e) {
310      EvalBestKnownSolution();
311    }
312    void FleetUsageFactorParameter_ValueChanged(object sender, EventArgs e) {
313      FleetUsageFactorParameter.Value.ValueChanged += new EventHandler(FleetUsageFactor_ValueChanged);
314      EvalBestKnownSolution();
315    }
316    void FleetUsageFactor_ValueChanged(object sender, EventArgs e) {
317      EvalBestKnownSolution();
318    }
319    void DistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
320      if (DistanceMatrix != null) {
321        DistanceMatrix.ItemChanged += new EventHandler<EventArgs<int, int>>(DistanceMatrix_ItemChanged);
322        DistanceMatrix.Reset += new EventHandler(DistanceMatrix_Reset);
323      }
324      EvalBestKnownSolution();
325    }
326    void DistanceMatrix_Reset(object sender, EventArgs e) {
327      EvalBestKnownSolution();
328    }
329    void DistanceMatrix_ItemChanged(object sender, EventArgs<int, int> e) {
330      EvalBestKnownSolution();
331    }
332    void UseDistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
333      UseDistanceMatrix.ValueChanged += new EventHandler(UseDistanceMatrix_ValueChanged);
334      EvalBestKnownSolution();
335    }
336    void UseDistanceMatrix_ValueChanged(object sender, EventArgs e) {
337      EvalBestKnownSolution();
338    }
339    #endregion
340  }
341}
Note: See TracBrowser for help on using the repository browser.