source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs @ 8652

Last change on this file since 8652 was 8652, checked in by svonolfe, 10 years ago

The distance matrix was reset when starting an algorithm the first time (#1953)

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