Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/OrienteeringProblem.cs @ 11261

Last change on this file since 11261 was 11261, checked in by pfleck, 10 years ago

#2208

  • Added Schilde instances zip
  • Implemented additional InstanceConsumer of OPData in OrienteeringProblem
File size: 16.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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
37  [Item("Orienteering Problem", "Represents a single objective Orienteering Problem.")]
38  [Creatable("Problems")]
39  [StorableClass]
40  public class OrienteeringProblem
41    : SingleObjectiveHeuristicOptimizationProblem<IOrienteeringEvaluator, IIntegerVectorCreator>,
42    IStorableContent, IProblemInstanceConsumer<CVRPData>, IProblemInstanceConsumer<OPData> {
43
44    public string Filename { get; set; }
45
46    #region Parameter Properties
47    public ValueParameter<DoubleMatrix> CoordinatesParameter {
48      get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
49    }
50    public ValueParameter<DistanceMatrix> DistanceMatrixParameter {
51      get { return (ValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
52    }
53
54    public ValueParameter<IntValue> StartingPointParameter {
55      get { return (ValueParameter<IntValue>)Parameters["StartingPoint"]; }
56    }
57    public ValueParameter<IntValue> TerminusPointParameter {
58      get { return (ValueParameter<IntValue>)Parameters["TerminusPoint"]; }
59    }
60    public ValueParameter<DoubleValue> MaximumDistanceParameter {
61      get { return (ValueParameter<DoubleValue>)Parameters["MaximumDistance"]; }
62    }
63    public ValueParameter<DoubleArray> ScoresParameter {
64      get { return (ValueParameter<DoubleArray>)Parameters["Scores"]; }
65    }
66    public ValueParameter<DoubleValue> FixedPenaltyParameter {
67      get { return (ValueParameter<DoubleValue>)Parameters["FixedPenalty"]; }
68    }
69
70    public OptionalValueParameter<IntegerVector> BestKnownSolutionParameter {
71      get { return (OptionalValueParameter<IntegerVector>)Parameters["BestKnownSolution"]; }
72    }
73    #endregion
74
75    #region Properties
76    public DoubleMatrix Coordinates {
77      get { return CoordinatesParameter.Value; }
78      set { CoordinatesParameter.Value = value; }
79    }
80    public DistanceMatrix DistanceMatrix {
81      get { return DistanceMatrixParameter.Value; }
82      set { DistanceMatrixParameter.Value = value; }
83    }
84    public IntValue StartingPoint {
85      get { return StartingPointParameter.Value; }
86      set { StartingPointParameter.Value = value; }
87    }
88    public IntValue TerminusPoint {
89      get { return TerminusPointParameter.Value; }
90      set { TerminusPointParameter.Value = value; }
91    }
92    public DoubleValue MaximumDistance {
93      get { return MaximumDistanceParameter.Value; }
94      set { MaximumDistanceParameter.Value = value; }
95    }
96    public DoubleArray Scores {
97      get { return ScoresParameter.Value; }
98      set { ScoresParameter.Value = value; }
99    }
100    public DoubleValue FixedPenalty {
101      get { return FixedPenaltyParameter.Value; }
102      set { FixedPenaltyParameter.Value = value; }
103    }
104    public IntegerVector BestKnownSolution {
105      get { return BestKnownSolutionParameter.Value; }
106      set { BestKnownSolutionParameter.Value = value; }
107    }
108    private BestOrienteeringSolutionAnalyser BestOrienteeringSolutionAnalyser {
109      get { return Operators.OfType<BestOrienteeringSolutionAnalyser>().SingleOrDefault(); }
110    }
111    #endregion
112
113    [StorableConstructor]
114    private OrienteeringProblem(bool deserializing)
115      : base(deserializing) {
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 ValueParameter<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 ValueParameter<IntValue>("StartingPoint", "Index of the starting point.", new IntValue(0)));
129      Parameters.Add(new ValueParameter<IntValue>("TerminusPoint", "Index of the ending point.", new IntValue(0)));
130      Parameters.Add(new ValueParameter<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 ValueParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
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      CalculateDistanceMatrix();
175    }
176    private void CoordinatesValue_ItemChanged(object sender, EventArgs<int, int> e) {
177      CalculateDistanceMatrix();
178    }
179    private void CoordinatesValue_Reset(object sender, EventArgs e) {
180      ParameterizeSolutionCreator();
181      CalculateDistanceMatrix();
182    }
183    private void StartingPointParameter_ValueChanged(object sender, EventArgs e) {
184      ParameterizeEvaluator();
185      ParameterizeAnalyzer();
186    }
187
188    private void TerminusPointParameter_ValueChanged(object sender, EventArgs e) {
189      ParameterizeEvaluator();
190      ParameterizeAnalyzer();
191    }
192    private void MaximumDistanceParameter_ValueChanged(object sender, EventArgs e) {
193      ParameterizeEvaluator();
194      ParameterizeAnalyzer();
195    }
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 FixedPenaltyParameter_ValueChanged(object sender, EventArgs e) {
207      ParameterizeEvaluator();
208      ParameterizeAnalyzer();
209    }
210    #endregion
211
212    #region Helpers
213    [StorableHook(HookType.AfterDeserialization)]
214    private void AfterDeserialization() {
215      RegisterEventHandlers();
216    }
217
218    private void RegisterEventHandlers() {
219      SolutionCreator.IntegerVectorParameter.ActualNameChanged += SolutionCreator_IntegerVectorParameter_ActualNameChanged;
220
221      CoordinatesParameter.ValueChanged += CoordinatesParameter_ValueChanged;
222      if (CoordinatesParameter.Value != null) {
223        CoordinatesParameter.Value.ItemChanged += CoordinatesValue_ItemChanged;
224        CoordinatesParameter.Value.Reset += CoordinatesValue_Reset;
225      }
226
227      StartingPointParameter.ValueChanged += StartingPointParameter_ValueChanged;
228      TerminusPointParameter.ValueChanged += TerminusPointParameter_ValueChanged;
229      MaximumDistanceParameter.ValueChanged += MaximumDistanceParameter_ValueChanged;
230
231      ScoresParameter.ValueChanged += ScoresParameter_ValueChanged;
232      ScoresParameter.Value.Reset += ScoresValue_Reset;
233      FixedPenaltyParameter.ValueChanged += FixedPenaltyParameter_ValueChanged;
234    }
235
236    private void ParameterizeSolutionCreator() {
237      if (SolutionCreator is GreedyOrienteeringTourCreator) {
238        var creator = (GreedyOrienteeringTourCreator)SolutionCreator;
239        creator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
240        creator.ScoresParameter.ActualName = ScoresParameter.Name;
241        creator.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
242        creator.StartingPointParameter.ActualName = StartingPointParameter.Name;
243        creator.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
244        creator.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
245      }
246    }
247    private void ParameterizeEvaluator() {
248      if (Evaluator is OrienteeringEvaluator) {
249        var evaluator = (OrienteeringEvaluator)Evaluator;
250        evaluator.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
251        evaluator.ScoresParameter.ActualName = ScoresParameter.Name;
252      }
253    }
254    private void ParameterizeAnalyzer() {
255      if (BestOrienteeringSolutionAnalyser != null) {
256        BestOrienteeringSolutionAnalyser.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
257
258        BestOrienteeringSolutionAnalyser.IntegerVector.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
259        BestOrienteeringSolutionAnalyser.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
260        BestOrienteeringSolutionAnalyser.ScoresParameter.ActualName = ScoresParameter.Name;
261
262        BestOrienteeringSolutionAnalyser.ResultsParameter.ActualName = "Results";
263        BestOrienteeringSolutionAnalyser.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
264        BestOrienteeringSolutionAnalyser.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
265      }
266    }
267    private void InitializeOperators() {
268      Operators.Add(new BestOrienteeringSolutionAnalyser());
269      ParameterizeAnalyzer();
270
271      Operators.Add(new OrienteeringLocalImprovementOperator());
272      Operators.Add(new OrienteeringShakingOperator());
273      ParameterizeOperators();
274    }
275    private void ParameterizeOperators() {
276      foreach (var op in Operators.OfType<OrienteeringLocalImprovementOperator>()) {
277        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
278        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
279        op.ScoresParameter.ActualName = ScoresParameter.Name;
280        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
281        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
282        op.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
283        op.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
284      }
285      foreach (var op in Operators.OfType<OrienteeringShakingOperator>()) {
286        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
287        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
288        op.ScoresParameter.ActualName = ScoresParameter.Name;
289        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
290        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
291        op.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
292        op.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
293      }
294    }
295    #endregion
296
297    private void CalculateDistanceMatrix() {
298      var distances = new double[Coordinates.Rows, Coordinates.Rows];
299      for (int i = 0; i < Coordinates.Rows; i++) {
300        for (int j = 0; j < Coordinates.Rows; j++) {
301          double distanceX = Math.Abs(Coordinates[i, 0] - Coordinates[j, 0]);
302          double distanceY = Math.Abs(Coordinates[i, 1] - Coordinates[j, 1]);
303          distances[i, j] = Math.Sqrt(Math.Pow(distanceX, 2) + Math.Pow(distanceY, 2));
304        }
305      }
306      DistanceMatrix = new DistanceMatrix(distances);
307    }
308
309    private void InitializeInitialOrienteeringInstance() {
310      Coordinates = new DoubleMatrix(new double[21, 2] {
311        {  4.60,  7.10 }, {  5.70, 11.40 }, {  4.40, 12.30 }, {  2.80, 14.30 }, {  3.20, 10.30 },
312        {  3.50,  9.80 }, {  4.40,  8.40 }, {  7.80, 11.00 }, {  8.80,  9.80 }, {  7.70,  8.20 },
313        {  6.30,  7.90 }, {  5.40,  8.20 }, {  5.80,  6.80 }, {  6.70,  5.80 }, { 13.80, 13.10 },
314        { 14.10, 14.20 }, { 11.20, 13.60 }, {  9.70, 16.40 }, {  9.50, 18.80 }, {  4.70, 16.80 },
315        {  5.00,  5.60 }
316      });
317      CalculateDistanceMatrix();
318
319      StartingPoint.Value = 0;
320      TerminusPoint.Value = 20;
321      MaximumDistance.Value = 30;
322
323      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 });
324    }
325
326    public void Load(CVRPData data) {
327      if (data.Coordinates == null)
328        throw new InvalidDataException("The given instance specifies no coordinates!");
329      if (data.Coordinates.GetLength(1) != 2)
330        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.");
331
332      // Clear old solutions
333      BestKnownQuality = null;
334      BestKnownSolution = null;
335
336      Name = data.Name;
337      Description = data.Description;
338
339      Coordinates = new DoubleMatrix(data.Coordinates);
340      if (data.Distances != null)
341        DistanceMatrix = new DistanceMatrix(data.Distances);
342      else
343        CalculateDistanceMatrix();
344
345      StartingPoint = new IntValue(0);// Depot is interpreted as start and endpoint (default)
346      TerminusPoint = new IntValue(0);
347
348      MaximumDistance = new DoubleValue(data.Capacity * 2); // capacity is interpreted as max distance
349      Scores = new DoubleArray(data.Demands); // demands are interpreted as scores
350
351
352
353      OnReset();
354    }
355
356    public void Load(OPData data) {
357      if (data.Coordinates == null)
358        throw new InvalidDataException("The given instance specifies no coordinates!");
359      if (data.Coordinates.GetLength(1) != 2)
360        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.");
361
362      // Clear old solutions
363      BestKnownQuality = null;
364      BestKnownSolution = null;
365
366      Name = data.Name;
367      Description = data.Description;
368
369      Coordinates = new DoubleMatrix(data.Coordinates);
370      if (data.Distances != null)
371        DistanceMatrix = new DistanceMatrix(data.Distances);
372      else
373        data.GetDistanceMatrix();
374
375      StartingPoint = new IntValue(data.StartingPoint);
376      TerminusPoint = new IntValue(data.TerminusPoint);
377
378      MaximumDistance = new DoubleValue(data.MaximumDistance);
379      Scores = new DoubleArray(data.Scores);
380    }
381  }
382}
Note: See TracBrowser for help on using the repository browser.