Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.Orienteering/3.3/OrienteeringProblem.cs

Last change on this file was 17181, checked in by swagner, 5 years ago

#2875: Merged r17180 from trunk to stable
File size: 20.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.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 HEAL.Attic;
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  [StorableType("0B8DB4A4-F183-4368-86C6-C51289B183D2")]
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(StorableConstructorFlag _) : base(_) {
116    }
117    private OrienteeringProblem(OrienteeringProblem original, Cloner cloner)
118      : base(original, cloner) {
119      RegisterEventHandlers();
120    }
121    public override IDeepCloneable Clone(Cloner cloner) {
122      return new OrienteeringProblem(this, cloner);
123    }
124    public OrienteeringProblem()
125      : base(new OrienteeringEvaluator(), new GreedyOrienteeringTourCreator()) {
126      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the points."));
127      Parameters.Add(new ValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
128      Parameters.Add(new FixedValueParameter<IntValue>("StartingPoint", "Index of the starting point.", new IntValue(0)));
129      Parameters.Add(new FixedValueParameter<IntValue>("TerminalPoint", "Index of the ending point.", new IntValue(0)));
130      Parameters.Add(new FixedValueParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
131      Parameters.Add(new ValueParameter<DoubleArray>("Scores", "The scores of the points."));
132      Parameters.Add(new FixedValueParameter<DoubleValue>("PointVisitingCosts", "The costs for visiting a point."));
133      Parameters.Add(new OptionalValueParameter<IntegerVector>("BestKnownSolution", "The best known solution of this Orienteering instance."));
134
135      Maximization.Value = true;
136      MaximizationParameter.Hidden = true;
137
138      SolutionCreator.IntegerVectorParameter.ActualName = "OrienteeringSolution";
139
140      InitializeInitialOrienteeringInstance();
141
142      ParameterizeSolutionCreator();
143      ParameterizeEvaluator();
144
145      InitializeOperators();
146      RegisterEventHandlers();
147    }
148
149    #region Events
150    protected override void OnSolutionCreatorChanged() {
151      base.OnSolutionCreatorChanged();
152      SolutionCreator.IntegerVectorParameter.ActualNameChanged += SolutionCreator_IntegerVectorParameter_ActualNameChanged;
153      ParameterizeSolutionCreator();
154      ParameterizeEvaluator();
155      ParameterizeAnalyzer();
156      ParameterizeOperators();
157    }
158    protected override void OnEvaluatorChanged() {
159      base.OnEvaluatorChanged();
160      ParameterizeEvaluator();
161      ParameterizeAnalyzer();
162    }
163    private void SolutionCreator_IntegerVectorParameter_ActualNameChanged(object sender, EventArgs e) {
164      ParameterizeEvaluator();
165      ParameterizeAnalyzer();
166      ParameterizeOperators();
167    }
168    private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
169      if (Coordinates != null) {
170        Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(CoordinatesValue_ItemChanged);
171        Coordinates.Reset += new EventHandler(CoordinatesValue_Reset);
172      }
173      ParameterizeSolutionCreator();
174      UpdateDistanceMatrix();
175      CheckStartingIndex();
176      CheckTerminalIndex();
177    }
178    private void CoordinatesValue_ItemChanged(object sender, EventArgs<int, int> e) {
179      UpdateDistanceMatrix();
180      CheckStartingIndex();
181      CheckTerminalIndex();
182    }
183    private void CoordinatesValue_Reset(object sender, EventArgs e) {
184      ParameterizeSolutionCreator();
185      UpdateDistanceMatrix();
186      CheckStartingIndex();
187      CheckTerminalIndex();
188    }
189    private void StartingPointParameterValue_ValueChanged(object sender, EventArgs e) {
190      CheckStartingIndex();
191    }
192
193    private void TerminalPointParameterValue_ValueChanged(object sender, EventArgs e) {
194      CheckTerminalIndex();
195    }
196    private void MaximumDistanceParameterValue_ValueChanged(object sender, EventArgs e) { }
197    private void ScoresParameter_ValueChanged(object sender, EventArgs e) {
198      ParameterizeEvaluator();
199      ParameterizeAnalyzer();
200      ParameterizeSolutionCreator();
201
202      ScoresParameter.Value.Reset += new EventHandler(ScoresValue_Reset);
203    }
204    private void ScoresValue_Reset(object sender, EventArgs e) {
205      ParameterizeSolutionCreator();
206    }
207    private void PointVisitingCostsParameterValue_ValueChanged(object sender, EventArgs e) { }
208
209    private void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
210      if (BestKnownSolution == null)
211        BestKnownQuality = null;
212    }
213    #endregion
214
215    #region Helpers
216    [StorableHook(HookType.AfterDeserialization)]
217    private void AfterDeserialization() {
218      RegisterEventHandlers();
219    }
220
221    private void RegisterEventHandlers() {
222      SolutionCreator.IntegerVectorParameter.ActualNameChanged += SolutionCreator_IntegerVectorParameter_ActualNameChanged;
223
224      CoordinatesParameter.ValueChanged += CoordinatesParameter_ValueChanged;
225      if (CoordinatesParameter.Value != null) {
226        CoordinatesParameter.Value.ItemChanged += CoordinatesValue_ItemChanged;
227        CoordinatesParameter.Value.Reset += CoordinatesValue_Reset;
228      }
229
230      StartingPointParameter.Value.ValueChanged += StartingPointParameterValue_ValueChanged;
231      TerminalPointParameter.Value.ValueChanged += TerminalPointParameterValue_ValueChanged;
232      MaximumDistanceParameter.Value.ValueChanged += MaximumDistanceParameterValue_ValueChanged;
233      PointVisitingCostsParameter.Value.ValueChanged += PointVisitingCostsParameterValue_ValueChanged;
234
235      ScoresParameter.ValueChanged += ScoresParameter_ValueChanged;
236      ScoresParameter.Value.Reset += ScoresValue_Reset;
237
238      BestKnownSolutionParameter.ValueChanged += BestKnownSolutionParameter_ValueChanged;
239    }
240
241    private void ParameterizeSolutionCreator() {
242      SolutionCreator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
243      SolutionCreator.ScoresParameter.ActualName = ScoresParameter.Name;
244      SolutionCreator.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
245      SolutionCreator.StartingPointParameter.ActualName = StartingPointParameter.Name;
246      SolutionCreator.TerminalPointParameter.ActualName = TerminalPointParameter.Name;
247      SolutionCreator.PointVisitingCostsParameter.ActualName = PointVisitingCostsParameter.Name;
248    }
249    private void ParameterizeEvaluator() {
250      Evaluator.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
251      Evaluator.ScoresParameter.ActualName = ScoresParameter.Name;
252      Evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
253      Evaluator.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
254      Evaluator.PointVisitingCostsParameter.ActualName = PointVisitingCostsParameter.Name;
255    }
256    private void ParameterizeAnalyzer() {
257      if (BestOrienteeringSolutionAnalyser != null) {
258        BestOrienteeringSolutionAnalyser.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
259
260        BestOrienteeringSolutionAnalyser.IntegerVector.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
261        BestOrienteeringSolutionAnalyser.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
262        BestOrienteeringSolutionAnalyser.ScoresParameter.ActualName = ScoresParameter.Name;
263
264        BestOrienteeringSolutionAnalyser.ResultsParameter.ActualName = "Results";
265        BestOrienteeringSolutionAnalyser.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
266        BestOrienteeringSolutionAnalyser.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
267      }
268    }
269    private void InitializeOperators() {
270      Operators.Add(new BestOrienteeringSolutionAnalyzer());
271      ParameterizeAnalyzer();
272
273      Operators.Add(new OrienteeringLocalImprovementOperator());
274      Operators.Add(new OrienteeringShakingOperator());
275      Operators.Add(new QualitySimilarityCalculator());
276      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
277
278      ParameterizeOperators();
279    }
280    private void ParameterizeOperators() {
281      foreach (var op in Operators.OfType<OrienteeringLocalImprovementOperator>()) {
282        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
283        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
284        op.ScoresParameter.ActualName = ScoresParameter.Name;
285        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
286        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
287        op.TerminalPointParameter.ActualName = TerminalPointParameter.Name;
288        op.PointVisitingCostsParameter.ActualName = PointVisitingCostsParameter.Name;
289      }
290      foreach (var op in Operators.OfType<OrienteeringShakingOperator>()) {
291        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
292        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
293        op.ScoresParameter.ActualName = ScoresParameter.Name;
294        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
295        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
296        op.TerminalPointParameter.ActualName = TerminalPointParameter.Name;
297        op.PointVisitingCostsParameter.ActualName = PointVisitingCostsParameter.Name;
298      }
299      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
300        similarityCalculator.SolutionVariableName = SolutionCreator.IntegerVectorParameter.ActualName;
301        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
302      }
303    }
304    #endregion
305
306    private DistanceMatrix CalculateDistanceMatrix(double[,] coordinates) {
307      var distances = DistanceHelper.GetDistanceMatrix(DistanceMeasure.Euclidean, coordinates, null, coordinates.GetLength(0));
308
309      return new DistanceMatrix(distances);
310    }
311    private void UpdateDistanceMatrix() {
312      if (Coordinates == null) {
313        DistanceMatrix = new DistanceMatrix(0, 0);
314        return;
315      }
316
317      var coordinates = Coordinates;
318      int dimension = coordinates.Rows;
319      var distances = new double[dimension, dimension];
320      for (int i = 0; i < dimension - 1; i++) {
321        for (int j = i + 1; j < dimension; j++) {
322          double x1 = coordinates[i, 0];
323          double y1 = coordinates[i, 1];
324          double x2 = coordinates[j, 0];
325          double y2 = coordinates[j, 1];
326          distances[i, j] = Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
327          distances[j, i] = distances[i, j];
328        }
329      }
330      DistanceMatrix = new DistanceMatrix(distances);
331    }
332    private void CheckStartingIndex() {
333      if (StartingPoint < 0) StartingPoint = 0;
334      if (StartingPoint >= DistanceMatrix.Rows) StartingPoint = DistanceMatrix.Rows - 1;
335    }
336    private void CheckTerminalIndex() {
337      if (TerminalPoint < 0) TerminalPoint = 0;
338      if (TerminalPoint >= DistanceMatrix.Rows) TerminalPoint = DistanceMatrix.Rows - 1;
339    }
340
341    private void InitializeInitialOrienteeringInstance() {
342      var coordinates = new double[21, 2] {
343        {  4.60,  7.10 }, {  5.70, 11.40 }, {  4.40, 12.30 }, {  2.80, 14.30 }, {  3.20, 10.30 },
344        {  3.50,  9.80 }, {  4.40,  8.40 }, {  7.80, 11.00 }, {  8.80,  9.80 }, {  7.70,  8.20 },
345        {  6.30,  7.90 }, {  5.40,  8.20 }, {  5.80,  6.80 }, {  6.70,  5.80 }, { 13.80, 13.10 },
346        { 14.10, 14.20 }, { 11.20, 13.60 }, {  9.70, 16.40 }, {  9.50, 18.80 }, {  4.70, 16.80 },
347        {  5.00,  5.60 }
348      };
349      Coordinates = new DoubleMatrix(coordinates);
350      DistanceMatrix = CalculateDistanceMatrix(coordinates);
351
352      StartingPoint = 0;
353      TerminalPoint = 20;
354      MaximumDistance = 30;
355
356      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 });
357    }
358
359    #region Instance consuming
360    public void Load(OPData data) {
361      if (data.Coordinates == null && data.Distances == null)
362        throw new InvalidDataException("The given instance specifies no coordinates or distance matrix!");
363      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
364        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.");
365
366      // Clear old solutions
367      BestKnownSolution = null;
368
369      Name = data.Name;
370      Description = data.Description;
371
372      Coordinates = data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null;
373      if (data.Distances != null)
374        DistanceMatrix = new DistanceMatrix(data.Distances);
375      else
376        DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
377
378      StartingPoint = data.StartingPoint;
379      TerminalPoint = data.TerminalPoint;
380
381      PointVisitingCosts = data.PointVisitingCosts;
382      MaximumDistance = data.MaximumDistance;
383      Scores = new DoubleArray(data.Scores);
384    }
385
386    public void Load(TSPData data) {
387      if (data.Coordinates == null && data.Distances == null)
388        throw new InvalidDataException("The given instance specifies no coordinates or distance matrix!");
389      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
390        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.");
391
392      // Clear old solutions
393      BestKnownSolution = null;
394
395      Name = data.Name;
396      Description = data.Description;
397
398      Coordinates = data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null;
399      if (data.Distances != null)
400        DistanceMatrix = new DistanceMatrix(data.Distances);
401      else
402        DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
403
404      StartingPoint = 0; // First city is interpreted as start point
405      TerminalPoint = data.Dimension - 1; // Last city is interpreted als end point
406
407      PointVisitingCosts = 0;
408      MaximumDistance = DistanceMatrix.Average() * 5.0; // distance from start to end first to last city is interpreted as maximum distance
409      Scores = new DoubleArray(Enumerable.Repeat(1.0, data.Dimension).ToArray()); // all scores are 1
410    }
411
412    public void Load(CVRPData data) {
413      if (data.Coordinates == null && data.Distances == null)
414        throw new InvalidDataException("The given instance specifies no coordinates or distance matrix!");
415      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
416        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.");
417
418      // Clear old solutions
419      BestKnownSolution = null;
420
421      Name = data.Name;
422      Description = data.Description;
423
424      Coordinates = data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null;
425      DistanceMatrix = data.Distances != null
426        ? new DistanceMatrix(data.Distances)
427        : CalculateDistanceMatrix(data.Coordinates);
428
429      StartingPoint = 0; // Depot is interpreted as start point
430      TerminalPoint = 0; // Depot is interpreted als end point
431
432      PointVisitingCosts = 0;
433      MaximumDistance = data.Capacity * 2; // capacity is interpreted as max distance
434      Scores = new DoubleArray(data.Demands); // demands are interpreted as scores
435    }
436    #endregion
437  }
438}
Note: See TracBrowser for help on using the repository browser.