Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs @ 17698

Last change on this file since 17698 was 17698, checked in by abeham, 4 years ago

#2521: working on VRP (WIP)

File size: 14.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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 HEAL.Attic;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Parameters;
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  [StorableType("9A6CCE89-A4B6-4FA3-A150-181FC315B713")]
36  public abstract class VRPProblemInstance : ParameterizedNamedItem, IVRPProblemInstance, IStatefulItem {
37    IVRPEvaluator moveEvaluator;
38
39    private object locker = new object();
40
41    public IVRPEvaluator MoveEvaluator {
42      get {
43        lock (locker) {
44          if (evaluator == null)
45            return null;
46          else {
47            if (moveEvaluator == null) {
48              moveEvaluator = evaluator.Clone() as IVRPEvaluator;
49
50              foreach (IParameter parameter in moveEvaluator.Parameters) {
51                if (parameter is ILookupParameter
52                  && parameter != moveEvaluator.ProblemInstanceParameter
53                  && parameter != moveEvaluator.VRPToursParameter) {
54                  (parameter as ILookupParameter).ActualName =
55                    VRPMoveEvaluator.MovePrefix +
56                    (parameter as ILookupParameter).ActualName;
57                }
58              }
59            }
60
61            return moveEvaluator;
62          }
63        }
64      }
65    }
66
67    protected abstract IEnumerable<IOperator> GetOperators();
68    protected abstract IEnumerable<IOperator> GetAnalyzers();
69
70    public IEnumerable<IOperator> Operators {
71      get {
72        return GetOperators().Union(GetAnalyzers());
73      }
74    }
75
76    protected ValueParameter<DoubleMatrix> CoordinatesParameter {
77      get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
78    }
79    protected OptionalValueParameter<DoubleMatrix> DistanceMatrixParameter {
80      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
81    }
82    protected ValueParameter<BoolValue> UseDistanceMatrixParameter {
83      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
84    }
85    protected ValueParameter<IntValue> VehiclesParameter {
86      get { return (ValueParameter<IntValue>)Parameters["Vehicles"]; }
87    }
88    protected ValueParameter<DoubleArray> DemandParameter {
89      get { return (ValueParameter<DoubleArray>)Parameters["Demand"]; }
90    }
91
92    protected IValueParameter<DoubleValue> FleetUsageFactorParameter {
93      get { return (IValueParameter<DoubleValue>)Parameters["EvalFleetUsageFactor"]; }
94    }
95    protected IValueParameter<DoubleValue> DistanceFactorParameter {
96      get { return (IValueParameter<DoubleValue>)Parameters["EvalDistanceFactor"]; }
97    }
98
99    public DoubleMatrix Coordinates {
100      get { return CoordinatesParameter.Value; }
101      set { CoordinatesParameter.Value = value; }
102    }
103
104    public DoubleMatrix DistanceMatrix {
105      get { return DistanceMatrixParameter.Value; }
106      set { DistanceMatrixParameter.Value = value; }
107    }
108    public BoolValue UseDistanceMatrix {
109      get { return UseDistanceMatrixParameter.Value; }
110      set { UseDistanceMatrixParameter.Value = value; }
111    }
112    public IntValue Vehicles {
113      get { return VehiclesParameter.Value; }
114      set { VehiclesParameter.Value = value; }
115    }
116    public DoubleArray Demand {
117      get { return DemandParameter.Value; }
118      set { DemandParameter.Value = value; }
119    }
120    public virtual IntValue Cities {
121      get { return new IntValue(Demand.Length); }
122    }
123
124    public DoubleValue FleetUsageFactor {
125      get { return FleetUsageFactorParameter.Value; }
126      set { FleetUsageFactorParameter.Value = value; }
127    }
128    public DoubleValue DistanceFactor {
129      get { return DistanceFactorParameter.Value; }
130      set { DistanceFactorParameter.Value = value; }
131    }
132
133    protected virtual double CalculateDistance(int start, int end) {
134      double distance = 0.0;
135
136      distance =
137          Math.Sqrt(
138            Math.Pow(Coordinates[start, 0] - Coordinates[end, 0], 2) +
139            Math.Pow(Coordinates[start, 1] - Coordinates[end, 1], 2));
140
141      return distance;
142    }
143
144    private DoubleMatrix CreateDistanceMatrix() {
145      DoubleMatrix distanceMatrix = new DoubleMatrix(Coordinates.Rows, Coordinates.Rows);
146
147      for (int i = 0; i < distanceMatrix.Rows; i++) {
148        for (int j = 0; j < distanceMatrix.Columns; j++) {
149          double distance = CalculateDistance(i, j);
150
151          distanceMatrix[i, j] = distance;
152        }
153      }
154
155      return distanceMatrix;
156    }
157
158    public virtual double[] GetCoordinates(int city) {
159      double[] coordinates = new double[Coordinates.Columns];
160
161      for (int i = 0; i < Coordinates.Columns; i++) {
162        coordinates[i] = Coordinates[city, i];
163      }
164
165      return coordinates;
166    }
167
168    public virtual double GetDemand(int city) {
169      return Demand[city];
170    }
171
172    //cache for performance improvement
173    private DoubleMatrix distanceMatrix = null;
174    private IVRPEvaluator evaluator = null;
175
176    public IVRPEvaluator SolutionEvaluator {
177      get {
178        return evaluator;
179      }
180      set {
181        lock (locker) {
182          moveEvaluator = null;
183          evaluator = value;
184          EvalBestKnownSolution();
185        }
186      }
187    }
188
189    public virtual double GetDistance(int start, int end, IVRPEncodedSolution solution) {
190      if (distanceMatrix == null && UseDistanceMatrix.Value) {
191        distanceMatrix = DistanceMatrix ?? CreateDistanceMatrix();
192      }
193
194      if (distanceMatrix != null) return distanceMatrix[start, end];
195      return CalculateDistance(start, end);
196    }
197
198    public virtual double GetInsertionDistance(int start, int customer, int end, IVRPEncodedSolution 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(IVRPEncodedSolution solution) {
211      return evaluator.Feasible(
212        evaluator.Evaluate(
213          this, solution));
214    }
215
216    public bool TourFeasible(Tour tour, IVRPEncodedSolution solution) {
217      return evaluator.Feasible(
218        evaluator.EvaluateTour(
219        this, tour, solution));
220    }
221
222    public VRPEvaluation Evaluate(IVRPEncodedSolution solution) {
223      return evaluator.Evaluate(this, solution);
224    }
225
226    public VRPEvaluation EvaluateTour(Tour tour, IVRPEncodedSolution 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, IVRPEncodedSolution 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(StorableConstructorFlag _) : base(_) { }
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      CoordinatesParameter.ValueChanged += CoordinatesParameter_ValueChanged;
282      Coordinates.Reset += Coordinates_Changed;
283      Coordinates.ItemChanged += Coordinates_Changed;
284      DemandParameter.ValueChanged += DemandParameter_ValueChanged;
285      Demand.Reset += Demand_Changed;
286      Demand.ItemChanged += Demand_Changed;
287      VehiclesParameter.ValueChanged += VehiclesParameter_ValueChanged;
288      VehiclesParameter.Value.ValueChanged += Vehicles_Changed;
289      DistanceFactorParameter.ValueChanged += DistanceFactorParameter_ValueChanged;
290      DistanceFactorParameter.Value.ValueChanged += DistanceFactor_ValueChanged;
291      FleetUsageFactorParameter.ValueChanged += FleetUsageFactorParameter_ValueChanged;
292      FleetUsageFactorParameter.Value.ValueChanged += FleetUsageFactor_ValueChanged;
293      DistanceMatrixParameter.ValueChanged += DistanceMatrixParameter_ValueChanged;
294      if (DistanceMatrix != null) {
295        DistanceMatrix.ItemChanged += DistanceMatrix_ItemChanged;
296        DistanceMatrix.Reset += DistanceMatrix_Reset;
297      }
298      UseDistanceMatrixParameter.ValueChanged += UseDistanceMatrixParameter_ValueChanged;
299      UseDistanceMatrix.ValueChanged += UseDistanceMatrix_ValueChanged;
300    }
301
302    public virtual void InitializeState() {
303    }
304
305    public virtual void ClearState() {
306    }
307
308    #region Event handlers
309    private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
310      if (distanceMatrix != null) distanceMatrix = null;
311      if (DistanceMatrix != null && DistanceMatrix.Rows != Coordinates.Rows) DistanceMatrix = null;
312      Coordinates.Reset += Coordinates_Changed;
313      Coordinates.ItemChanged += Coordinates_Changed;
314      EvalBestKnownSolution();
315    }
316    private void Coordinates_Changed(object sender, EventArgs e) {
317      if (distanceMatrix != null) distanceMatrix = null;
318      if (DistanceMatrix != null && DistanceMatrix.Rows != Coordinates.Rows) DistanceMatrix = null;
319      EvalBestKnownSolution();
320    }
321    private void DemandParameter_ValueChanged(object sender, EventArgs e) {
322      Demand.Reset += Demand_Changed;
323      Demand.ItemChanged += Demand_Changed;
324      EvalBestKnownSolution();
325    }
326    private void Demand_Changed(object sender, EventArgs e) {
327      EvalBestKnownSolution();
328    }
329    private void VehiclesParameter_ValueChanged(object sender, EventArgs e) {
330      Vehicles.ValueChanged += Vehicles_Changed;
331      EvalBestKnownSolution();
332    }
333    private void Vehicles_Changed(object sender, EventArgs e) {
334      EvalBestKnownSolution();
335    }
336    void DistanceFactorParameter_ValueChanged(object sender, EventArgs e) {
337      DistanceFactorParameter.Value.ValueChanged += DistanceFactor_ValueChanged;
338      EvalBestKnownSolution();
339    }
340    void DistanceFactor_ValueChanged(object sender, EventArgs e) {
341      EvalBestKnownSolution();
342    }
343    void FleetUsageFactorParameter_ValueChanged(object sender, EventArgs e) {
344      FleetUsageFactorParameter.Value.ValueChanged += FleetUsageFactor_ValueChanged;
345      EvalBestKnownSolution();
346    }
347    void FleetUsageFactor_ValueChanged(object sender, EventArgs e) {
348      EvalBestKnownSolution();
349    }
350    void DistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
351      if (DistanceMatrix != null) {
352        DistanceMatrix.ItemChanged += DistanceMatrix_ItemChanged;
353        DistanceMatrix.Reset += DistanceMatrix_Reset;
354      }
355      distanceMatrix = DistanceMatrix;
356      EvalBestKnownSolution();
357    }
358    void DistanceMatrix_Reset(object sender, EventArgs e) {
359      EvalBestKnownSolution();
360    }
361    void DistanceMatrix_ItemChanged(object sender, EventArgs<int, int> e) {
362      distanceMatrix = DistanceMatrix;
363      EvalBestKnownSolution();
364    }
365    void UseDistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
366      UseDistanceMatrix.ValueChanged += UseDistanceMatrix_ValueChanged;
367      if (!UseDistanceMatrix.Value)
368        distanceMatrix = null;
369      EvalBestKnownSolution();
370    }
371    void UseDistanceMatrix_ValueChanged(object sender, EventArgs e) {
372      if (!UseDistanceMatrix.Value)
373        distanceMatrix = null;
374      EvalBestKnownSolution();
375    }
376    #endregion
377  }
378}
Note: See TracBrowser for help on using the repository browser.