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

Last change on this file since 11245 was 11245, checked in by pfleck, 7 years ago

#2208

  • Added visualization in the visualization tab of the problem
  • Fixed bug in shaking operator when tour only consists of start and end point
File size: 15.4 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;
33
34namespace HeuristicLab.Problems.Orienteering {
35
36  [Item("Orienteering Problem", "Represents a single objective Orienteering Problem.")]
37  [Creatable("Problems")]
38  [StorableClass]
39  public class OrienteeringProblem
40    : SingleObjectiveHeuristicOptimizationProblem<IOrienteeringEvaluator, IIntegerVectorCreator>,
41    IStorableContent, IProblemInstanceConsumer<CVRPData> {
42
43    public string Filename { get; set; }
44
45    #region Parameter Properties
46    public ValueParameter<DoubleMatrix> CoordinatesParameter {
47      get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
48    }
49    public ValueParameter<DistanceMatrix> DistanceMatrixParameter {
50      get { return (ValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
51    }
52
53    public ValueParameter<IntValue> StartingPointParameter {
54      get { return (ValueParameter<IntValue>)Parameters["StartingPoint"]; }
55    }
56    public ValueParameter<IntValue> TerminusPointParameter {
57      get { return (ValueParameter<IntValue>)Parameters["TerminusPoint"]; }
58    }
59    public ValueParameter<DoubleValue> MaximumDistanceParameter {
60      get { return (ValueParameter<DoubleValue>)Parameters["MaximumDistance"]; }
61    }
62    public ValueParameter<DoubleArray> ScoresParameter {
63      get { return (ValueParameter<DoubleArray>)Parameters["Scores"]; }
64    }
65    public ValueParameter<DoubleValue> FixedPenaltyParameter {
66      get { return (ValueParameter<DoubleValue>)Parameters["FixedPenalty"]; }
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 IntValue StartingPoint {
84      get { return StartingPointParameter.Value; }
85      set { StartingPointParameter.Value = value; }
86    }
87    public IntValue TerminusPoint {
88      get { return TerminusPointParameter.Value; }
89      set { TerminusPointParameter.Value = value; }
90    }
91    public DoubleValue MaximumDistance {
92      get { return MaximumDistanceParameter.Value; }
93      set { MaximumDistanceParameter.Value = value; }
94    }
95    public DoubleArray Scores {
96      get { return ScoresParameter.Value; }
97      set { ScoresParameter.Value = value; }
98    }
99    public DoubleValue FixedPenalty {
100      get { return FixedPenaltyParameter.Value; }
101      set { FixedPenaltyParameter.Value = value; }
102    }
103    public IntegerVector BestKnownSolution {
104      get { return BestKnownSolutionParameter.Value; }
105      set { BestKnownSolutionParameter.Value = value; }
106    }
107    private BestOrienteeringSolutionAnalyser BestOrienteeringSolutionAnalyser {
108      get { return Operators.OfType<BestOrienteeringSolutionAnalyser>().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 ValueParameter<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 ValueParameter<IntValue>("StartingPoint", "Index of the starting point.", new IntValue(0)));
128      Parameters.Add(new ValueParameter<IntValue>("TerminusPoint", "Index of the ending point.", new IntValue(0)));
129      Parameters.Add(new ValueParameter<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 ValueParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
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      CalculateDistanceMatrix();
174    }
175    private void CoordinatesValue_ItemChanged(object sender, EventArgs<int, int> e) {
176      CalculateDistanceMatrix();
177    }
178    private void CoordinatesValue_Reset(object sender, EventArgs e) {
179      ParameterizeSolutionCreator();
180      CalculateDistanceMatrix();
181    }
182    private void StartingPointParameter_ValueChanged(object sender, EventArgs e) {
183      ParameterizeEvaluator();
184      ParameterizeAnalyzer();
185    }
186
187    private void TerminusPointParameter_ValueChanged(object sender, EventArgs e) {
188      ParameterizeEvaluator();
189      ParameterizeAnalyzer();
190    }
191    private void MaximumDistanceParameter_ValueChanged(object sender, EventArgs e) {
192      ParameterizeEvaluator();
193      ParameterizeAnalyzer();
194    }
195    private void ScoresParameter_ValueChanged(object sender, EventArgs e) {
196      ParameterizeEvaluator();
197      ParameterizeAnalyzer();
198      ParameterizeSolutionCreator();
199
200      ScoresParameter.Value.Reset += new EventHandler(ScoresValue_Reset);
201    }
202    private void ScoresValue_Reset(object sender, EventArgs e) {
203      ParameterizeSolutionCreator();
204    }
205    private void FixedPenaltyParameter_ValueChanged(object sender, EventArgs e) {
206      ParameterizeEvaluator();
207      ParameterizeAnalyzer();
208    }
209    #endregion
210
211    #region Helpers
212    [StorableHook(HookType.AfterDeserialization)]
213    private void AfterDeserialization() {
214      RegisterEventHandlers();
215    }
216
217    private void RegisterEventHandlers() {
218      SolutionCreator.IntegerVectorParameter.ActualNameChanged += SolutionCreator_IntegerVectorParameter_ActualNameChanged;
219
220      CoordinatesParameter.ValueChanged += CoordinatesParameter_ValueChanged;
221      if (CoordinatesParameter.Value != null) {
222        CoordinatesParameter.Value.ItemChanged += CoordinatesValue_ItemChanged;
223        CoordinatesParameter.Value.Reset += CoordinatesValue_Reset;
224      }
225
226      StartingPointParameter.ValueChanged += StartingPointParameter_ValueChanged;
227      TerminusPointParameter.ValueChanged += TerminusPointParameter_ValueChanged;
228      MaximumDistanceParameter.ValueChanged += MaximumDistanceParameter_ValueChanged;
229
230      ScoresParameter.ValueChanged += ScoresParameter_ValueChanged;
231      ScoresParameter.Value.Reset += ScoresValue_Reset;
232      FixedPenaltyParameter.ValueChanged += FixedPenaltyParameter_ValueChanged;
233    }
234
235    private void ParameterizeSolutionCreator() {
236      if (SolutionCreator is GreedyOrienteeringTourCreator) {
237        var creator = (GreedyOrienteeringTourCreator)SolutionCreator;
238        creator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
239        creator.ScoresParameter.ActualName = ScoresParameter.Name;
240        creator.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
241        creator.StartingPointParameter.ActualName = StartingPointParameter.Name;
242        creator.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
243        creator.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
244      }
245    }
246    private void ParameterizeEvaluator() {
247      if (Evaluator is OrienteeringEvaluator) {
248        var evaluator = (OrienteeringEvaluator)Evaluator;
249        evaluator.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
250        evaluator.ScoresParameter.ActualName = ScoresParameter.Name;
251      }
252    }
253    private void ParameterizeAnalyzer() {
254      if (BestOrienteeringSolutionAnalyser != null) {
255        BestOrienteeringSolutionAnalyser.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
256
257        BestOrienteeringSolutionAnalyser.IntegerVector.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
258        BestOrienteeringSolutionAnalyser.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
259        BestOrienteeringSolutionAnalyser.ScoresParameter.ActualName = ScoresParameter.Name;
260
261        BestOrienteeringSolutionAnalyser.ResultsParameter.ActualName = "Results";
262        BestOrienteeringSolutionAnalyser.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
263        BestOrienteeringSolutionAnalyser.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
264      }
265    }
266    private void InitializeOperators() {
267      Operators.Add(new BestOrienteeringSolutionAnalyser());
268      ParameterizeAnalyzer();
269
270      Operators.Add(new OrienteeringLocalImprovementOperator());
271      Operators.Add(new OrienteeringShakingOperator());
272      ParameterizeOperators();
273    }
274    private void ParameterizeOperators() {
275      foreach (var op in Operators.OfType<OrienteeringLocalImprovementOperator>()) {
276        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
277        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
278        op.ScoresParameter.ActualName = ScoresParameter.Name;
279        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
280        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
281        op.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
282        op.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
283      }
284      foreach (var op in Operators.OfType<OrienteeringShakingOperator>()) {
285        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
286        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
287        op.ScoresParameter.ActualName = ScoresParameter.Name;
288        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
289        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
290        op.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
291        op.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
292      }
293    }
294    #endregion
295
296    private void CalculateDistanceMatrix() {
297      var distances = new double[Coordinates.Rows, Coordinates.Rows];
298      for (int i = 0; i < Coordinates.Rows; i++) {
299        for (int j = 0; j < Coordinates.Rows; j++) {
300          double distanceX = Math.Abs(Coordinates[i, 0] - Coordinates[j, 0]);
301          double distanceY = Math.Abs(Coordinates[i, 1] - Coordinates[j, 1]);
302          distances[i, j] = Math.Sqrt(Math.Pow(distanceX, 2) + Math.Pow(distanceY, 2));
303        }
304      }
305      DistanceMatrix = new DistanceMatrix(distances);
306    }
307
308    private void InitializeInitialOrienteeringInstance() {
309      Coordinates = new DoubleMatrix(new double[21, 2] {
310        {  4.60,  7.10 }, {  5.70, 11.40 }, {  4.40, 12.30 }, {  2.80, 14.30 }, {  3.20, 10.30 },
311        {  3.50,  9.80 }, {  4.40,  8.40 }, {  7.80, 11.00 }, {  8.80,  9.80 }, {  7.70,  8.20 },
312        {  6.30,  7.90 }, {  5.40,  8.20 }, {  5.80,  6.80 }, {  6.70,  5.80 }, { 13.80, 13.10 },
313        { 14.10, 14.20 }, { 11.20, 13.60 }, {  9.70, 16.40 }, {  9.50, 18.80 }, {  4.70, 16.80 },
314        {  5.00,  5.60 }
315      });
316      CalculateDistanceMatrix();
317
318      StartingPoint.Value = 0;
319      TerminusPoint.Value = 20;
320      MaximumDistance.Value = 30;
321
322      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 });
323    }
324
325    public void Load(CVRPData data) {
326
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}
Note: See TracBrowser for help on using the repository browser.