Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2924-dotnet-core/HeuristicLab.Problems.Orienteering/3.3/OrienteeringProblem.cs @ 16123

Last change on this file since 16123 was 15583, checked in by swagner, 7 years ago

#2640: Updated year of copyrights in license headers
File size: 20.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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.IO;
24using System.Linq;
25using HeuristicLab.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.IntegerVectorEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Optimization.Operators;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.Problems.Instances;
35using HeuristicLab.Problems.Instances.Types;
36
37namespace HeuristicLab.Problems.Orienteering {
38  [Item("Orienteering Problem (OP)", "Represents a single-objective Orienteering Problem.")]
39  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 115)]
40  [StorableClass]
41  public sealed class OrienteeringProblem
42    : SingleObjectiveHeuristicOptimizationProblem<IOrienteeringEvaluator, IOrienteeringSolutionCreator>,
43    IStorableContent, IProblemInstanceConsumer<OPData>, IProblemInstanceConsumer<TSPData>, IProblemInstanceConsumer<CVRPData> {
44
45    public string Filename { get; set; }
46
47    #region Parameter Properties
48    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
49      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
50    }
51    public IValueParameter<DistanceMatrix> DistanceMatrixParameter {
52      get { return (IValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
53    }
54
55    public IFixedValueParameter<IntValue> StartingPointParameter {
56      get { return (IFixedValueParameter<IntValue>)Parameters["StartingPoint"]; }
57    }
58    public IFixedValueParameter<IntValue> TerminalPointParameter {
59      get { return (IFixedValueParameter<IntValue>)Parameters["TerminalPoint"]; }
60    }
61    public IFixedValueParameter<DoubleValue> MaximumDistanceParameter {
62      get { return (IFixedValueParameter<DoubleValue>)Parameters["MaximumDistance"]; }
63    }
64    public IValueParameter<DoubleArray> ScoresParameter {
65      get { return (IValueParameter<DoubleArray>)Parameters["Scores"]; }
66    }
67    public IFixedValueParameter<DoubleValue> PointVisitingCostsParameter {
68      get { return (IFixedValueParameter<DoubleValue>)Parameters["PointVisitingCosts"]; }
69    }
70
71    public OptionalValueParameter<IntegerVector> BestKnownSolutionParameter {
72      get { return (OptionalValueParameter<IntegerVector>)Parameters["BestKnownSolution"]; }
73    }
74    #endregion
75
76    #region Properties
77    public DoubleMatrix Coordinates {
78      get { return CoordinatesParameter.Value; }
79      set { CoordinatesParameter.Value = value; }
80    }
81    public DistanceMatrix DistanceMatrix {
82      get { return DistanceMatrixParameter.Value; }
83      set { DistanceMatrixParameter.Value = value; }
84    }
85    public int StartingPoint {
86      get { return StartingPointParameter.Value.Value; }
87      set { StartingPointParameter.Value.Value = value; }
88    }
89    public int TerminalPoint {
90      get { return TerminalPointParameter.Value.Value; }
91      set { TerminalPointParameter.Value.Value = value; }
92    }
93    public double MaximumDistance {
94      get { return MaximumDistanceParameter.Value.Value; }
95      set { MaximumDistanceParameter.Value.Value = value; }
96    }
97    public DoubleArray Scores {
98      get { return ScoresParameter.Value; }
99      set { ScoresParameter.Value = value; }
100    }
101    public double PointVisitingCosts {
102      get { return PointVisitingCostsParameter.Value.Value; }
103      set { PointVisitingCostsParameter.Value.Value = value; }
104    }
105    public IntegerVector BestKnownSolution {
106      get { return BestKnownSolutionParameter.Value; }
107      set { BestKnownSolutionParameter.Value = value; }
108    }
109    private BestOrienteeringSolutionAnalyzer BestOrienteeringSolutionAnalyser {
110      get { return Operators.OfType<BestOrienteeringSolutionAnalyzer>().SingleOrDefault(); }
111    }
112    #endregion
113
114    [StorableConstructor]
115    private OrienteeringProblem(bool deserializing)
116      : base(deserializing) {
117    }
118    private OrienteeringProblem(OrienteeringProblem original, Cloner cloner)
119      : base(original, cloner) {
120      RegisterEventHandlers();
121    }
122    public override IDeepCloneable Clone(Cloner cloner) {
123      return new OrienteeringProblem(this, cloner);
124    }
125    public OrienteeringProblem()
126      : base(new OrienteeringEvaluator(), new GreedyOrienteeringTourCreator()) {
127      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the points."));
128      Parameters.Add(new ValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
129      Parameters.Add(new FixedValueParameter<IntValue>("StartingPoint", "Index of the starting point.", new IntValue(0)));
130      Parameters.Add(new FixedValueParameter<IntValue>("TerminalPoint", "Index of the ending point.", new IntValue(0)));
131      Parameters.Add(new FixedValueParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
132      Parameters.Add(new ValueParameter<DoubleArray>("Scores", "The scores of the points."));
133      Parameters.Add(new FixedValueParameter<DoubleValue>("PointVisitingCosts", "The costs for visiting a point."));
134      Parameters.Add(new OptionalValueParameter<IntegerVector>("BestKnownSolution", "The best known solution of this Orienteering instance."));
135
136      Maximization.Value = true;
137      MaximizationParameter.Hidden = true;
138
139      SolutionCreator.IntegerVectorParameter.ActualName = "OrienteeringSolution";
140
141      InitializeInitialOrienteeringInstance();
142
143      ParameterizeSolutionCreator();
144      ParameterizeEvaluator();
145
146      InitializeOperators();
147      RegisterEventHandlers();
148    }
149
150    #region Events
151    protected override void OnSolutionCreatorChanged() {
152      base.OnSolutionCreatorChanged();
153      SolutionCreator.IntegerVectorParameter.ActualNameChanged += SolutionCreator_IntegerVectorParameter_ActualNameChanged;
154      ParameterizeSolutionCreator();
155      ParameterizeEvaluator();
156      ParameterizeAnalyzer();
157      ParameterizeOperators();
158    }
159    protected override void OnEvaluatorChanged() {
160      base.OnEvaluatorChanged();
161      ParameterizeEvaluator();
162      ParameterizeAnalyzer();
163    }
164    private void SolutionCreator_IntegerVectorParameter_ActualNameChanged(object sender, EventArgs e) {
165      ParameterizeEvaluator();
166      ParameterizeAnalyzer();
167      ParameterizeOperators();
168    }
169    private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
170      if (Coordinates != null) {
171        Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(CoordinatesValue_ItemChanged);
172        Coordinates.Reset += new EventHandler(CoordinatesValue_Reset);
173      }
174      ParameterizeSolutionCreator();
175      UpdateDistanceMatrix();
176      CheckStartingIndex();
177      CheckTerminalIndex();
178    }
179    private void CoordinatesValue_ItemChanged(object sender, EventArgs<int, int> e) {
180      UpdateDistanceMatrix();
181      CheckStartingIndex();
182      CheckTerminalIndex();
183    }
184    private void CoordinatesValue_Reset(object sender, EventArgs e) {
185      ParameterizeSolutionCreator();
186      UpdateDistanceMatrix();
187      CheckStartingIndex();
188      CheckTerminalIndex();
189    }
190    private void StartingPointParameterValue_ValueChanged(object sender, EventArgs e) {
191      CheckStartingIndex();
192    }
193
194    private void TerminalPointParameterValue_ValueChanged(object sender, EventArgs e) {
195      CheckTerminalIndex();
196    }
197    private void MaximumDistanceParameterValue_ValueChanged(object sender, EventArgs e) { }
198    private void ScoresParameter_ValueChanged(object sender, EventArgs e) {
199      ParameterizeEvaluator();
200      ParameterizeAnalyzer();
201      ParameterizeSolutionCreator();
202
203      ScoresParameter.Value.Reset += new EventHandler(ScoresValue_Reset);
204    }
205    private void ScoresValue_Reset(object sender, EventArgs e) {
206      ParameterizeSolutionCreator();
207    }
208    private void PointVisitingCostsParameterValue_ValueChanged(object sender, EventArgs e) { }
209
210    private void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
211      if (BestKnownSolution == null)
212        BestKnownQuality = null;
213    }
214    #endregion
215
216    #region Helpers
217    [StorableHook(HookType.AfterDeserialization)]
218    private void AfterDeserialization() {
219      RegisterEventHandlers();
220    }
221
222    private void RegisterEventHandlers() {
223      SolutionCreator.IntegerVectorParameter.ActualNameChanged += SolutionCreator_IntegerVectorParameter_ActualNameChanged;
224
225      CoordinatesParameter.ValueChanged += CoordinatesParameter_ValueChanged;
226      if (CoordinatesParameter.Value != null) {
227        CoordinatesParameter.Value.ItemChanged += CoordinatesValue_ItemChanged;
228        CoordinatesParameter.Value.Reset += CoordinatesValue_Reset;
229      }
230
231      StartingPointParameter.Value.ValueChanged += StartingPointParameterValue_ValueChanged;
232      TerminalPointParameter.Value.ValueChanged += TerminalPointParameterValue_ValueChanged;
233      MaximumDistanceParameter.Value.ValueChanged += MaximumDistanceParameterValue_ValueChanged;
234      PointVisitingCostsParameter.Value.ValueChanged += PointVisitingCostsParameterValue_ValueChanged;
235
236      ScoresParameter.ValueChanged += ScoresParameter_ValueChanged;
237      ScoresParameter.Value.Reset += ScoresValue_Reset;
238
239      BestKnownSolutionParameter.ValueChanged += BestKnownSolutionParameter_ValueChanged;
240    }
241
242    private void ParameterizeSolutionCreator() {
243      SolutionCreator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
244      SolutionCreator.ScoresParameter.ActualName = ScoresParameter.Name;
245      SolutionCreator.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
246      SolutionCreator.StartingPointParameter.ActualName = StartingPointParameter.Name;
247      SolutionCreator.TerminalPointParameter.ActualName = TerminalPointParameter.Name;
248      SolutionCreator.PointVisitingCostsParameter.ActualName = PointVisitingCostsParameter.Name;
249    }
250    private void ParameterizeEvaluator() {
251      Evaluator.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
252      Evaluator.ScoresParameter.ActualName = ScoresParameter.Name;
253      Evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
254      Evaluator.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
255      Evaluator.PointVisitingCostsParameter.ActualName = PointVisitingCostsParameter.Name;
256    }
257    private void ParameterizeAnalyzer() {
258      if (BestOrienteeringSolutionAnalyser != null) {
259        BestOrienteeringSolutionAnalyser.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
260
261        BestOrienteeringSolutionAnalyser.IntegerVector.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
262        BestOrienteeringSolutionAnalyser.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
263        BestOrienteeringSolutionAnalyser.ScoresParameter.ActualName = ScoresParameter.Name;
264
265        BestOrienteeringSolutionAnalyser.ResultsParameter.ActualName = "Results";
266        BestOrienteeringSolutionAnalyser.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
267        BestOrienteeringSolutionAnalyser.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
268      }
269    }
270    private void InitializeOperators() {
271      Operators.Add(new BestOrienteeringSolutionAnalyzer());
272      ParameterizeAnalyzer();
273
274      Operators.Add(new OrienteeringLocalImprovementOperator());
275      Operators.Add(new OrienteeringShakingOperator());
276      Operators.Add(new QualitySimilarityCalculator());
277      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
278
279      ParameterizeOperators();
280    }
281    private void ParameterizeOperators() {
282      foreach (var op in Operators.OfType<OrienteeringLocalImprovementOperator>()) {
283        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
284        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
285        op.ScoresParameter.ActualName = ScoresParameter.Name;
286        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
287        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
288        op.TerminalPointParameter.ActualName = TerminalPointParameter.Name;
289        op.PointVisitingCostsParameter.ActualName = PointVisitingCostsParameter.Name;
290      }
291      foreach (var op in Operators.OfType<OrienteeringShakingOperator>()) {
292        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
293        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
294        op.ScoresParameter.ActualName = ScoresParameter.Name;
295        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
296        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
297        op.TerminalPointParameter.ActualName = TerminalPointParameter.Name;
298        op.PointVisitingCostsParameter.ActualName = PointVisitingCostsParameter.Name;
299      }
300      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
301        similarityCalculator.SolutionVariableName = SolutionCreator.IntegerVectorParameter.ActualName;
302        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
303      }
304    }
305    #endregion
306
307    private DistanceMatrix CalculateDistanceMatrix(double[,] coordinates) {
308      var distances = DistanceHelper.GetDistanceMatrix(DistanceMeasure.Euclidean, coordinates, null, coordinates.GetLength(0));
309
310      return new DistanceMatrix(distances);
311    }
312    private void UpdateDistanceMatrix() {
313      if (Coordinates == null) {
314        DistanceMatrix = new DistanceMatrix(0, 0);
315        return;
316      }
317
318      var coordinates = Coordinates;
319      int dimension = coordinates.Rows;
320      var distances = new double[dimension, dimension];
321      for (int i = 0; i < dimension - 1; i++) {
322        for (int j = i + 1; j < dimension; j++) {
323          double x1 = coordinates[i, 0];
324          double y1 = coordinates[i, 1];
325          double x2 = coordinates[j, 0];
326          double y2 = coordinates[j, 1];
327          distances[i, j] = Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
328          distances[j, i] = distances[i, j];
329        }
330      }
331      DistanceMatrix = new DistanceMatrix(distances);
332    }
333    private void CheckStartingIndex() {
334      if (StartingPoint < 0) StartingPoint = 0;
335      if (StartingPoint >= DistanceMatrix.Rows) StartingPoint = DistanceMatrix.Rows - 1;
336    }
337    private void CheckTerminalIndex() {
338      if (TerminalPoint < 0) TerminalPoint = 0;
339      if (TerminalPoint >= DistanceMatrix.Rows) TerminalPoint = DistanceMatrix.Rows - 1;
340    }
341
342    private void InitializeInitialOrienteeringInstance() {
343      var coordinates = new double[21, 2] {
344        {  4.60,  7.10 }, {  5.70, 11.40 }, {  4.40, 12.30 }, {  2.80, 14.30 }, {  3.20, 10.30 },
345        {  3.50,  9.80 }, {  4.40,  8.40 }, {  7.80, 11.00 }, {  8.80,  9.80 }, {  7.70,  8.20 },
346        {  6.30,  7.90 }, {  5.40,  8.20 }, {  5.80,  6.80 }, {  6.70,  5.80 }, { 13.80, 13.10 },
347        { 14.10, 14.20 }, { 11.20, 13.60 }, {  9.70, 16.40 }, {  9.50, 18.80 }, {  4.70, 16.80 },
348        {  5.00,  5.60 }
349      };
350      Coordinates = new DoubleMatrix(coordinates);
351      DistanceMatrix = CalculateDistanceMatrix(coordinates);
352
353      StartingPoint = 0;
354      TerminalPoint = 20;
355      MaximumDistance = 30;
356
357      Scores = new DoubleArray(new double[21] { 0, 20, 20, 30, 15, 15, 10, 20, 20, 20, 15, 10, 10, 25, 40, 40, 30, 30, 50, 30, 0 });
358    }
359
360    #region Instance consuming
361    public void Load(OPData data) {
362      if (data.Coordinates == null && data.Distances == null)
363        throw new InvalidDataException("The given instance specifies no coordinates or distance matrix!");
364      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
365        throw new InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates.");
366
367      // Clear old solutions
368      BestKnownSolution = null;
369
370      Name = data.Name;
371      Description = data.Description;
372
373      Coordinates = data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null;
374      if (data.Distances != null)
375        DistanceMatrix = new DistanceMatrix(data.Distances);
376      else
377        DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
378
379      StartingPoint = data.StartingPoint;
380      TerminalPoint = data.TerminalPoint;
381
382      PointVisitingCosts = data.PointVisitingCosts;
383      MaximumDistance = data.MaximumDistance;
384      Scores = new DoubleArray(data.Scores);
385    }
386
387    public void Load(TSPData data) {
388      if (data.Coordinates == null && data.Distances == null)
389        throw new InvalidDataException("The given instance specifies no coordinates or distance matrix!");
390      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
391        throw new InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates.");
392
393      // Clear old solutions
394      BestKnownSolution = null;
395
396      Name = data.Name;
397      Description = data.Description;
398
399      Coordinates = data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null;
400      if (data.Distances != null)
401        DistanceMatrix = new DistanceMatrix(data.Distances);
402      else
403        DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
404
405      StartingPoint = 0; // First city is interpreted as start point
406      TerminalPoint = data.Dimension - 1; // Last city is interpreted als end point
407
408      PointVisitingCosts = 0;
409      MaximumDistance = DistanceMatrix.Average() * 5.0; // distance from start to end first to last city is interpreted as maximum distance
410      Scores = new DoubleArray(Enumerable.Repeat(1.0, data.Dimension).ToArray()); // all scores are 1
411    }
412
413    public void Load(CVRPData data) {
414      if (data.Coordinates == null && data.Distances == null)
415        throw new InvalidDataException("The given instance specifies no coordinates or distance matrix!");
416      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
417        throw new InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates.");
418
419      // Clear old solutions
420      BestKnownSolution = null;
421
422      Name = data.Name;
423      Description = data.Description;
424
425      Coordinates = data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null;
426      DistanceMatrix = data.Distances != null
427        ? new DistanceMatrix(data.Distances)
428        : CalculateDistanceMatrix(data.Coordinates);
429
430      StartingPoint = 0; // Depot is interpreted as start point
431      TerminalPoint = 0; // Depot is interpreted als end point
432
433      PointVisitingCosts = 0;
434      MaximumDistance = data.Capacity * 2; // capacity is interpreted as max distance
435      Scores = new DoubleArray(data.Demands); // demands are interpreted as scores
436    }
437    #endregion
438  }
439}
Note: See TracBrowser for help on using the repository browser.