Free cookie consent management tool by TermsFeed Policy Generator

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

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

Merged changes from trunk into branch (#1177)

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