Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2521: working on VRP

File size: 12.8 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.Interfaces;
31
32namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
33  [Item("VRPProblemInstance", "Represents a VRP instance.")]
34  [StorableType("9A6CCE89-A4B6-4FA3-A150-181FC315B713")]
35  public abstract class VRPProblemInstance : ParameterizedNamedItem, IVRPProblemInstance, IStatefulItem {
36
37    protected ValueParameter<DoubleMatrix> CoordinatesParameter {
38      get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
39    }
40    protected OptionalValueParameter<DoubleMatrix> DistanceMatrixParameter {
41      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
42    }
43    protected ValueParameter<BoolValue> UseDistanceMatrixParameter {
44      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
45    }
46    protected ValueParameter<IntValue> VehiclesParameter {
47      get { return (ValueParameter<IntValue>)Parameters["Vehicles"]; }
48    }
49    protected ValueParameter<DoubleArray> DemandParameter {
50      get { return (ValueParameter<DoubleArray>)Parameters["Demand"]; }
51    }
52
53    protected IValueParameter<DoubleValue> FleetUsageFactorParameter {
54      get { return (IValueParameter<DoubleValue>)Parameters["EvalFleetUsageFactor"]; }
55    }
56    protected IValueParameter<DoubleValue> DistanceFactorParameter {
57      get { return (IValueParameter<DoubleValue>)Parameters["EvalDistanceFactor"]; }
58    }
59
60    public DoubleMatrix Coordinates {
61      get { return CoordinatesParameter.Value; }
62      set { CoordinatesParameter.Value = value; }
63    }
64
65    public DoubleMatrix DistanceMatrix {
66      get { return DistanceMatrixParameter.Value; }
67      set { DistanceMatrixParameter.Value = value; }
68    }
69    public BoolValue UseDistanceMatrix {
70      get { return UseDistanceMatrixParameter.Value; }
71      set { UseDistanceMatrixParameter.Value = value; }
72    }
73    public IntValue Vehicles {
74      get { return VehiclesParameter.Value; }
75      set { VehiclesParameter.Value = value; }
76    }
77    public DoubleArray Demand {
78      get { return DemandParameter.Value; }
79      set { DemandParameter.Value = value; }
80    }
81    public virtual IntValue Cities {
82      get { return new IntValue(Demand.Length); }
83    }
84
85    public DoubleValue FleetUsageFactor {
86      get { return FleetUsageFactorParameter.Value; }
87      set { FleetUsageFactorParameter.Value = value; }
88    }
89    public DoubleValue DistanceFactor {
90      get { return DistanceFactorParameter.Value; }
91      set { DistanceFactorParameter.Value = value; }
92    }
93
94    public virtual IEnumerable<IOperator> FilterOperators(IEnumerable<IOperator> operators) {
95      return operators.Where(x => x is IVRPOperator);
96    }
97
98    protected virtual double CalculateDistance(int start, int end) {
99      var distance =
100          Math.Sqrt(
101            Math.Pow(Coordinates[start, 0] - Coordinates[end, 0], 2) +
102            Math.Pow(Coordinates[start, 1] - Coordinates[end, 1], 2));
103
104      return distance;
105    }
106
107    private DoubleMatrix CreateDistanceMatrix() {
108      DoubleMatrix distanceMatrix = new DoubleMatrix(Coordinates.Rows, Coordinates.Rows);
109
110      for (int i = 0; i < distanceMatrix.Rows; i++) {
111        for (int j = 0; j < distanceMatrix.Columns; j++) {
112          double distance = CalculateDistance(i, j);
113
114          distanceMatrix[i, j] = distance;
115        }
116      }
117
118      return distanceMatrix;
119    }
120
121    public virtual double[] GetCoordinates(int city) {
122      double[] coordinates = new double[Coordinates.Columns];
123
124      for (int i = 0; i < Coordinates.Columns; i++) {
125        coordinates[i] = Coordinates[city, i];
126      }
127
128      return coordinates;
129    }
130
131    public virtual double GetDemand(int city) {
132      return Demand[city];
133    }
134
135    //cache for performance improvement
136    private DoubleMatrix distanceMatrix = null;
137   
138
139    public virtual double GetDistance(int start, int end, IVRPEncodedSolution solution) {
140      if (distanceMatrix == null && UseDistanceMatrix.Value) {
141        distanceMatrix = DistanceMatrix ?? CreateDistanceMatrix();
142      }
143
144      if (distanceMatrix != null) return distanceMatrix[start, end];
145      return CalculateDistance(start, end);
146    }
147
148    public virtual double GetInsertionDistance(int start, int customer, int end, IVRPEncodedSolution solution,
149      out double startDistance, out double endDistance) {
150      double distance = GetDistance(start, end, solution);
151
152      startDistance = GetDistance(start, customer, solution);
153      endDistance = GetDistance(customer, end, solution);
154
155      double newDistance = startDistance + endDistance;
156
157      return newDistance - distance;
158    }
159
160    protected virtual VRPEvaluation CreateTourEvaluation() {
161      return new VRPEvaluation();
162    }
163
164    public VRPEvaluation Evaluate(IVRPEncodedSolution solution) {
165      VRPEvaluation evaluation = CreateTourEvaluation();
166      evaluation.IsFeasible = true;
167      foreach (Tour tour in solution.GetTours()) {
168        EvaluateTour(evaluation, tour, solution);
169      }
170      return evaluation;
171    }
172
173    public VRPEvaluation EvaluateTour(Tour tour, IVRPEncodedSolution solution) {
174      VRPEvaluation evaluation = CreateTourEvaluation();
175      evaluation.IsFeasible = true;
176      EvaluateTour(evaluation, tour, solution);
177      return evaluation;
178    }
179
180    public double GetInsertionCosts(VRPEvaluation eval, IVRPEncodedSolution solution, int customer, int tour, int index, out bool feasible) {
181      bool tourFeasible;
182      double costs = GetTourInsertionCosts(
183        solution,
184        eval.InsertionInfo.GetTourInsertionInfo(tour),
185        index,
186        customer, out tourFeasible);
187
188      feasible = tourFeasible;
189
190      return costs;
191    }
192    protected abstract double GetTourInsertionCosts(IVRPEncodedSolution solution, TourInsertionInfo tourInsertionInfo, int index, int customer, out bool feasible);
193
194    protected abstract void EvaluateTour(VRPEvaluation eval, Tour tour, IVRPEncodedSolution solution);
195
196
197    public event EventHandler EvaluationChanged;
198
199    protected void EvalBestKnownSolution() {
200      EventHandler tmp = EvaluationChanged;
201      if (tmp != null) tmp(this, null);
202    }
203
204    [StorableConstructor]
205    protected VRPProblemInstance(StorableConstructorFlag _) : base(_) { }
206
207    public VRPProblemInstance()
208      : base() {
209      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.", new DoubleMatrix()));
210      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
211      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false.", new BoolValue(true)));
212      Parameters.Add(new ValueParameter<IntValue>("Vehicles", "The number of vehicles.", new IntValue(0)));
213      Parameters.Add(new ValueParameter<DoubleArray>("Demand", "The demand of each customer.", new DoubleArray()));
214
215      Parameters.Add(new ValueParameter<DoubleValue>("EvalFleetUsageFactor", "The fleet usage factor considered in the evaluation.", new DoubleValue(0)));
216      Parameters.Add(new ValueParameter<DoubleValue>("EvalDistanceFactor", "The distance factor considered in the evaluation.", new DoubleValue(1)));
217
218      AttachEventHandlers();
219    }
220
221    protected VRPProblemInstance(VRPProblemInstance original, Cloner cloner)
222      : base(original, cloner) {
223      AttachEventHandlers();
224    }
225
226    [StorableHook(HookType.AfterDeserialization)]
227    private void AfterDeserialization() {
228      AttachEventHandlers();
229    }
230
231    private void AttachEventHandlers() {
232      CoordinatesParameter.ValueChanged += CoordinatesParameter_ValueChanged;
233      Coordinates.Reset += Coordinates_Changed;
234      Coordinates.ItemChanged += Coordinates_Changed;
235      DemandParameter.ValueChanged += DemandParameter_ValueChanged;
236      Demand.Reset += Demand_Changed;
237      Demand.ItemChanged += Demand_Changed;
238      VehiclesParameter.ValueChanged += VehiclesParameter_ValueChanged;
239      VehiclesParameter.Value.ValueChanged += Vehicles_Changed;
240      DistanceFactorParameter.ValueChanged += DistanceFactorParameter_ValueChanged;
241      DistanceFactorParameter.Value.ValueChanged += DistanceFactor_ValueChanged;
242      FleetUsageFactorParameter.ValueChanged += FleetUsageFactorParameter_ValueChanged;
243      FleetUsageFactorParameter.Value.ValueChanged += FleetUsageFactor_ValueChanged;
244      DistanceMatrixParameter.ValueChanged += DistanceMatrixParameter_ValueChanged;
245      if (DistanceMatrix != null) {
246        DistanceMatrix.ItemChanged += DistanceMatrix_ItemChanged;
247        DistanceMatrix.Reset += DistanceMatrix_Reset;
248      }
249      UseDistanceMatrixParameter.ValueChanged += UseDistanceMatrixParameter_ValueChanged;
250      UseDistanceMatrix.ValueChanged += UseDistanceMatrix_ValueChanged;
251    }
252
253    public virtual void InitializeState() {
254    }
255
256    public virtual void ClearState() {
257    }
258
259    #region Event handlers
260    private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
261      if (distanceMatrix != null) distanceMatrix = null;
262      if (DistanceMatrix != null && DistanceMatrix.Rows != Coordinates.Rows) DistanceMatrix = null;
263      Coordinates.Reset += Coordinates_Changed;
264      Coordinates.ItemChanged += Coordinates_Changed;
265      EvalBestKnownSolution();
266    }
267    private void Coordinates_Changed(object sender, EventArgs e) {
268      if (distanceMatrix != null) distanceMatrix = null;
269      if (DistanceMatrix != null && DistanceMatrix.Rows != Coordinates.Rows) DistanceMatrix = null;
270      EvalBestKnownSolution();
271    }
272    private void DemandParameter_ValueChanged(object sender, EventArgs e) {
273      Demand.Reset += Demand_Changed;
274      Demand.ItemChanged += Demand_Changed;
275      EvalBestKnownSolution();
276    }
277    private void Demand_Changed(object sender, EventArgs e) {
278      EvalBestKnownSolution();
279    }
280    private void VehiclesParameter_ValueChanged(object sender, EventArgs e) {
281      Vehicles.ValueChanged += Vehicles_Changed;
282      EvalBestKnownSolution();
283    }
284    private void Vehicles_Changed(object sender, EventArgs e) {
285      EvalBestKnownSolution();
286    }
287    void DistanceFactorParameter_ValueChanged(object sender, EventArgs e) {
288      DistanceFactorParameter.Value.ValueChanged += DistanceFactor_ValueChanged;
289      EvalBestKnownSolution();
290    }
291    void DistanceFactor_ValueChanged(object sender, EventArgs e) {
292      EvalBestKnownSolution();
293    }
294    void FleetUsageFactorParameter_ValueChanged(object sender, EventArgs e) {
295      FleetUsageFactorParameter.Value.ValueChanged += FleetUsageFactor_ValueChanged;
296      EvalBestKnownSolution();
297    }
298    void FleetUsageFactor_ValueChanged(object sender, EventArgs e) {
299      EvalBestKnownSolution();
300    }
301    void DistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
302      if (DistanceMatrix != null) {
303        DistanceMatrix.ItemChanged += DistanceMatrix_ItemChanged;
304        DistanceMatrix.Reset += DistanceMatrix_Reset;
305      }
306      distanceMatrix = DistanceMatrix;
307      EvalBestKnownSolution();
308    }
309    void DistanceMatrix_Reset(object sender, EventArgs e) {
310      EvalBestKnownSolution();
311    }
312    void DistanceMatrix_ItemChanged(object sender, EventArgs<int, int> e) {
313      distanceMatrix = DistanceMatrix;
314      EvalBestKnownSolution();
315    }
316    void UseDistanceMatrixParameter_ValueChanged(object sender, EventArgs e) {
317      UseDistanceMatrix.ValueChanged += UseDistanceMatrix_ValueChanged;
318      if (!UseDistanceMatrix.Value)
319        distanceMatrix = null;
320      EvalBestKnownSolution();
321    }
322    void UseDistanceMatrix_ValueChanged(object sender, EventArgs e) {
323      if (!UseDistanceMatrix.Value)
324        distanceMatrix = null;
325      EvalBestKnownSolution();
326    }
327    #endregion
328  }
329}
Note: See TracBrowser for help on using the repository browser.