Free cookie consent management tool by TermsFeed Policy Generator

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

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

Made distance calculation virtual (#1177)

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