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

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

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