Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 6772 was 6752, checked in by svonolfe, 13 years ago

Added support for incremental evaluation to improve performance (#1177)

File size: 14.0 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, IStatefulItem {
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    //cache for performance improvement
191    private DoubleMatrix distanceMatrix = null;
192    private IVRPEvaluator evaluator = null;
193
194    public double GetDistance(int start, int end) {
195      double distance = 0.0;
196      if (distanceMatrix == null && UseDistanceMatrix.Value) {
197        distanceMatrix = DistanceMatrix = CreateDistanceMatrix();
198      }
199
200      if (distanceMatrix != null)
201        distance = distanceMatrix[start, end];
202      else
203        distance = CalculateDistance(start, end);
204
205      return distance;
206    }
207
208    public bool Feasible(IVRPEncoding solution) {
209      return evaluator.Feasible(
210        evaluator.Evaluate(
211          this, solution));
212    }
213
214    public bool Feasible(Tour tour) {
215      return evaluator.Feasible(
216        evaluator.Evaluate(
217        this, tour));
218    }
219
220    public VRPEvaluation Evaluate(IVRPEncoding solution) {
221      return evaluator.Evaluate(this, solution);
222    }
223
224    public VRPEvaluation Evaluate(Tour tour) {
225      return evaluator.Evaluate(this, tour);
226    }
227
228    public bool Feasible(VRPEvaluation eval) {
229      return evaluator.Feasible(eval);
230    }
231
232    public double GetInsertionCosts(VRPEvaluation eval, int customer, int tour, int index, out bool feasible) {
233      return evaluator.GetInsertionCosts(this, eval, customer, tour, index, out feasible);
234    }
235
236    protected void EvalBestKnownSolution() {
237      if (BestKnownSolution != null) {
238        //call evaluator
239        BestKnownQuality = new DoubleValue(Evaluate(BestKnownSolution.Solution).Quality);
240        BestKnownSolution.Quality = BestKnownQuality;
241      } else {
242        BestKnownQuality = null;
243      }
244    }
245
246    protected abstract IVRPEvaluator Evaluator { get; }
247    protected abstract IVRPCreator Creator { get; }
248   
249    [StorableConstructor]
250    protected VRPProblemInstance(bool deserializing) : base(deserializing) { }
251
252    public VRPProblemInstance()
253      : base() {
254      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.", new DoubleMatrix()));
255      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
256      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false.", new BoolValue(true)));
257      Parameters.Add(new ValueParameter<IntValue>("Vehicles", "The number of vehicles.", new IntValue(0)));
258      Parameters.Add(new ValueParameter<DoubleArray>("Demand", "The demand of each customer.", new DoubleArray()));
259
260      Parameters.Add(new ValueParameter<DoubleValue>("EvalFleetUsageFactor", "The fleet usage factor considered in the evaluation.", new DoubleValue(0)));
261      Parameters.Add(new ValueParameter<DoubleValue>("EvalDistanceFactor", "The distance factor considered in the evaluation.", new DoubleValue(1)));
262
263      Parameters.Add(new ValueParameter<IVRPCreator>("SolutionCreator", "The operator which should be used to create new VRP solutions.", Creator));
264      Parameters.Add(new ValueParameter<IVRPEvaluator>("Evaluator", "The operator which should be used to evaluate VRP solutions.", Evaluator));
265
266      Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
267      Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
268
269      AttachEventHandlers();
270    }
271
272    protected VRPProblemInstance(VRPProblemInstance original, Cloner cloner)
273      : base(original, cloner) {
274        AttachEventHandlers();
275    }
276
277    [StorableHook(HookType.AfterDeserialization)]
278    private void AfterDeserializationHook() {
279      AttachEventHandlers();
280    }
281
282    private void AttachEventHandlers() {
283      evaluator = EvaluatorParameter.Value;
284      EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
285      BestKnownSolutionParameter.ValueChanged += new EventHandler(BestKnownSolutionParameter_ValueChanged);
286      DistanceFactorParameter.ValueChanged += new EventHandler(DistanceFactorParameter_ValueChanged);
287      DistanceFactorParameter.Value.ValueChanged += new EventHandler(DistanceFactor_ValueChanged);
288      FleetUsageFactorParameter.ValueChanged += new EventHandler(FleetUsageFactorParameter_ValueChanged);
289      FleetUsageFactorParameter.Value.ValueChanged += new EventHandler(FleetUsageFactor_ValueChanged);
290      DistanceMatrixParameter.ValueChanged += new EventHandler(DistanceMatrixParameter_ValueChanged);
291      if (DistanceMatrix != null) {
292        DistanceMatrix.ItemChanged += new EventHandler<EventArgs<int, int>>(DistanceMatrix_ItemChanged);
293        DistanceMatrix.Reset += new EventHandler(DistanceMatrix_Reset);
294      }
295      UseDistanceMatrixParameter.ValueChanged += new EventHandler(UseDistanceMatrixParameter_ValueChanged);
296      UseDistanceMatrix.ValueChanged += new EventHandler(UseDistanceMatrix_ValueChanged);
297    }
298
299    public virtual void InitializeState() {
300    }
301
302    public virtual void ClearState() {
303    }
304
305    #region Event handlers
306    void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
307      moveEvaluator = null;
308      evaluator = EvaluatorParameter.Value;
309    }
310
311    void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
312      EvalBestKnownSolution();
313    }
314    void DistanceFactorParameter_ValueChanged(object sender, EventArgs e) {
315      DistanceFactorParameter.Value.ValueChanged += new EventHandler(DistanceFactor_ValueChanged);
316      EvalBestKnownSolution();
317    }
318    void DistanceFactor_ValueChanged(object sender, EventArgs e) {
319      EvalBestKnownSolution();
320    }
321    void FleetUsageFactorParameter_ValueChanged(object sender, EventArgs e) {
322      FleetUsageFactorParameter.Value.ValueChanged += new EventHandler(FleetUsageFactor_ValueChanged);
323      EvalBestKnownSolution();
324    }
325    void FleetUsageFactor_ValueChanged(object sender, EventArgs e) {
326      EvalBestKnownSolution();
327    }
328    void DistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
329      if (DistanceMatrix != null) {
330        DistanceMatrix.ItemChanged += new EventHandler<EventArgs<int, int>>(DistanceMatrix_ItemChanged);
331        DistanceMatrix.Reset += new EventHandler(DistanceMatrix_Reset);
332      }
333      distanceMatrix = DistanceMatrix;
334      EvalBestKnownSolution();
335    }
336    void DistanceMatrix_Reset(object sender, EventArgs e) {
337      EvalBestKnownSolution();
338    }
339    void DistanceMatrix_ItemChanged(object sender, EventArgs<int, int> e) {
340      distanceMatrix = DistanceMatrix;
341      EvalBestKnownSolution();
342    }
343    void UseDistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
344      UseDistanceMatrix.ValueChanged += new EventHandler(UseDistanceMatrix_ValueChanged);
345      if (!UseDistanceMatrix.Value)
346        distanceMatrix = null;
347      EvalBestKnownSolution();
348    }
349    void UseDistanceMatrix_ValueChanged(object sender, EventArgs e) {
350      if (!UseDistanceMatrix.Value)
351        distanceMatrix = null;
352      EvalBestKnownSolution();
353    }
354    #endregion
355  }
356}
Note: See TracBrowser for help on using the repository browser.