Free cookie consent management tool by TermsFeed Policy Generator

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

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

Added adaptive constraint relaxation for all VRP variants (#1177)

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