Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14492 was 14186, checked in by swagner, 8 years ago

#2526: Updated year of copyrights in license headers

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