Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/VehicleRoutingProblem.cs @ 11171

Last change on this file since 11171 was 11171, checked in by ascheibe, 10 years ago

#2115 merged r11170 (copyright update) into trunk

File size: 16.3 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.Collections.Generic;
24using System.Drawing;
25using System.Linq;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34using HeuristicLab.Problems.Instances;
35using HeuristicLab.Problems.VehicleRouting.Interfaces;
36using HeuristicLab.Problems.VehicleRouting.Interpreters;
37using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
38using HeuristicLab.Problems.VehicleRouting.Variants;
39
40namespace HeuristicLab.Problems.VehicleRouting {
41  [Item("Vehicle Routing Problem", "Represents a Vehicle Routing Problem.")]
42  [Creatable("Problems")]
43  [StorableClass]
44  public sealed class VehicleRoutingProblem : Problem, ISingleObjectiveHeuristicOptimizationProblem, IStorableContent, IProblemInstanceConsumer<VRPData> {
45    public string Filename { get; set; }
46
47    public static new Image StaticItemImage {
48      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
49    }
50
51    #region Parameter Properties
52    public ValueParameter<BoolValue> MaximizationParameter {
53      get { return (ValueParameter<BoolValue>)Parameters["Maximization"]; }
54    }
55    IParameter ISingleObjectiveHeuristicOptimizationProblem.MaximizationParameter {
56      get { return MaximizationParameter; }
57    }
58    public ValueParameter<IVRPProblemInstance> ProblemInstanceParameter {
59      get { return (ValueParameter<IVRPProblemInstance>)Parameters["ProblemInstance"]; }
60    }
61    public OptionalValueParameter<DoubleValue> BestKnownQualityParameter {
62      get { return (OptionalValueParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
63    }
64    IParameter ISingleObjectiveHeuristicOptimizationProblem.BestKnownQualityParameter {
65      get { return BestKnownQualityParameter; }
66    }
67    public OptionalValueParameter<VRPSolution> BestKnownSolutionParameter {
68      get { return (OptionalValueParameter<VRPSolution>)Parameters["BestKnownSolution"]; }
69    }
70    public IConstrainedValueParameter<IVRPCreator> SolutionCreatorParameter {
71      get { return (IConstrainedValueParameter<IVRPCreator>)Parameters["SolutionCreator"]; }
72    }
73    IParameter IHeuristicOptimizationProblem.SolutionCreatorParameter {
74      get { return SolutionCreatorParameter; }
75    }
76    public IValueParameter<IVRPEvaluator> EvaluatorParameter {
77      get { return (IValueParameter<IVRPEvaluator>)Parameters["Evaluator"]; }
78    }
79    IParameter IHeuristicOptimizationProblem.EvaluatorParameter {
80      get { return EvaluatorParameter; }
81    }
82    #endregion
83
84    #region Properties
85    public IVRPProblemInstance ProblemInstance {
86      get { return ProblemInstanceParameter.Value; }
87      set { ProblemInstanceParameter.Value = value; }
88    }
89
90    public VRPSolution BestKnownSolution {
91      get { return BestKnownSolutionParameter.Value; }
92      set { BestKnownSolutionParameter.Value = value; }
93    }
94
95    public DoubleValue BestKnownQuality {
96      get { return BestKnownQualityParameter.Value; }
97      set { BestKnownQualityParameter.Value = value; }
98    }
99
100    public ISingleObjectiveEvaluator Evaluator {
101      get { return EvaluatorParameter.Value; }
102    }
103
104    IEvaluator IHeuristicOptimizationProblem.Evaluator {
105      get { return this.Evaluator; }
106    }
107
108    ISolutionCreator IHeuristicOptimizationProblem.SolutionCreator {
109      get { return SolutionCreatorParameter.Value; }
110    }
111    public IVRPCreator SolutionCreator {
112      get { return SolutionCreatorParameter.Value; }
113      set { SolutionCreatorParameter.Value = value; }
114    }
115    private SingleObjectivePopulationDiversityAnalyzer SingleObjectivePopulationDiversityAnalyzer {
116      get { return Operators.OfType<SingleObjectivePopulationDiversityAnalyzer>().FirstOrDefault(); }
117    }
118    #endregion
119
120    [StorableConstructor]
121    private VehicleRoutingProblem(bool deserializing) : base(deserializing) { }
122    public VehicleRoutingProblem()
123      : base() {
124      Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to false as the Vehicle Routing Problem is a minimization problem.", new BoolValue(false)));
125      Parameters.Add(new ValueParameter<IVRPProblemInstance>("ProblemInstance", "The VRP problem instance"));
126      Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this VRP instance."));
127      Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
128
129      Parameters.Add(new ConstrainedValueParameter<IVRPCreator>("SolutionCreator", "The operator which should be used to create new VRP solutions."));
130      Parameters.Add(new ValueParameter<IVRPEvaluator>("Evaluator", "The operator which should be used to evaluate VRP solutions."));
131
132      EvaluatorParameter.Hidden = true;
133
134      InitializeRandomVRPInstance();
135      InitializeOperators();
136
137      AttachEventHandlers();
138      AttachProblemInstanceEventHandlers();
139
140      EvaluatorParameter.Value = ProblemInstance.SolutionEvaluator;
141    }
142
143    public override IDeepCloneable Clone(Cloner cloner) {
144      cloner.Clone(ProblemInstance);
145      return new VehicleRoutingProblem(this, cloner);
146    }
147
148    private VehicleRoutingProblem(VehicleRoutingProblem original, Cloner cloner)
149      : base(original, cloner) {
150      this.AttachEventHandlers();
151      this.AttachProblemInstanceEventHandlers();
152
153      ProblemInstance.SolutionEvaluator = EvaluatorParameter.Value;
154    }
155
156    #region Events
157    public event EventHandler SolutionCreatorChanged;
158    private void OnSolutionCreatorChanged() {
159      EventHandler handler = SolutionCreatorChanged;
160      if (handler != null) handler(this, EventArgs.Empty);
161    }
162    public event EventHandler EvaluatorChanged;
163    private void OnEvaluatorChanged() {
164      EventHandler handler = EvaluatorChanged;
165      if (handler != null) handler(this, EventArgs.Empty);
166    }
167    #endregion
168
169    #region Helpers
170    [StorableHook(HookType.AfterDeserialization)]
171    private void AfterDeserialization() {
172      AttachEventHandlers();
173      AttachProblemInstanceEventHandlers();
174
175      ProblemInstance.SolutionEvaluator = EvaluatorParameter.Value;
176    }
177
178    [Storable(Name = "operators", AllowOneWay = true)]
179    private List<IOperator> StorableOperators {
180      set { Operators.AddRange(value); }
181    }
182
183    private void AttachEventHandlers() {
184      ProblemInstanceParameter.ValueChanged += new EventHandler(ProblemInstanceParameter_ValueChanged);
185      BestKnownSolutionParameter.ValueChanged += new EventHandler(BestKnownSolutionParameter_ValueChanged);
186      EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
187      SolutionCreatorParameter.ValueChanged += new EventHandler(SolutionCreatorParameter_ValueChanged);
188    }
189
190    private void AttachProblemInstanceEventHandlers() {
191      if (ProblemInstance != null) {
192        ProblemInstance.EvaluationChanged += new EventHandler(ProblemInstance_EvaluationChanged);
193      }
194    }
195
196    private void EvalBestKnownSolution() {
197      if (BestKnownSolution != null) {
198        //call evaluator
199        BestKnownQuality = new DoubleValue(ProblemInstance.Evaluate(BestKnownSolution.Solution).Quality);
200        BestKnownSolution.Quality = BestKnownQuality;
201      } else {
202        BestKnownQuality = null;
203      }
204    }
205
206    void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
207      EvalBestKnownSolution();
208    }
209
210    void ProblemInstance_EvaluationChanged(object sender, EventArgs e) {
211      EvalBestKnownSolution();
212    }
213
214    void ProblemInstanceParameter_ValueChanged(object sender, EventArgs e) {
215      InitializeOperators();
216      AttachProblemInstanceEventHandlers();
217
218      EvaluatorParameter.Value = ProblemInstance.SolutionEvaluator;
219
220      OnSolutionCreatorChanged();
221      OnEvaluatorChanged();
222      OnOperatorsChanged();
223    }
224
225    public void SetProblemInstance(IVRPProblemInstance instance) {
226      ProblemInstanceParameter.ValueChanged -= new EventHandler(ProblemInstanceParameter_ValueChanged);
227
228      ProblemInstance = instance;
229      AttachProblemInstanceEventHandlers();
230
231      OnSolutionCreatorChanged();
232      OnEvaluatorChanged();
233
234      ProblemInstanceParameter.ValueChanged += new EventHandler(ProblemInstanceParameter_ValueChanged);
235    }
236
237    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
238      OnSolutionCreatorChanged();
239    }
240    private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
241      if (ProblemInstance != null)
242        ProblemInstance.SolutionEvaluator = EvaluatorParameter.Value;
243      OnEvaluatorChanged();
244    }
245
246    private void InitializeOperators() {
247      var solutionCreatorParameter = SolutionCreatorParameter as ConstrainedValueParameter<IVRPCreator>;
248      solutionCreatorParameter.ValidValues.Clear();
249
250      Operators.Clear();
251
252      if (ProblemInstance != null) {
253        Operators.AddRange(
254        ProblemInstance.Operators.Concat(
255          ApplicationManager.Manager.GetInstances<IGeneralVRPOperator>().Cast<IOperator>()).OrderBy(op => op.Name));
256        Operators.Add(new VRPSimilarityCalculator());
257        Operators.Add(new SingleObjectivePopulationDiversityAnalyzer());
258
259        IVRPCreator defaultCreator = null;
260        foreach (IVRPCreator creator in Operators.Where(o => o is IVRPCreator)) {
261          solutionCreatorParameter.ValidValues.Add(creator);
262          if (creator is Encodings.Alba.RandomCreator)
263            defaultCreator = creator;
264        }
265        if (defaultCreator != null)
266          solutionCreatorParameter.Value = defaultCreator;
267      }
268
269      ParameterizeOperators();
270    }
271
272    private void ParameterizeOperators() {
273      foreach (IOperator op in Operators.OfType<IOperator>()) {
274        if (op is IMultiVRPOperator) {
275          (op as IMultiVRPOperator).SetOperators(Operators.OfType<IOperator>());
276        }
277      }
278      if (ProblemInstance != null) {
279        foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
280          op.SolutionParameter.ActualName = SolutionCreator.VRPToursParameter.ActualName;
281          op.SolutionParameter.Hidden = true;
282        }
283        foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
284          op.ParentsParameter.ActualName = SolutionCreator.VRPToursParameter.ActualName;
285          op.ParentsParameter.Hidden = true;
286        }
287        foreach (VRPSimilarityCalculator op in Operators.OfType<VRPSimilarityCalculator>()) {
288          op.SolutionVariableName = SolutionCreator.VRPToursParameter.ActualName;
289          op.QualityVariableName = ProblemInstance.SolutionEvaluator.QualityParameter.ActualName;
290          op.ProblemInstance = ProblemInstance;
291        }
292        if (SingleObjectivePopulationDiversityAnalyzer != null) {
293          SingleObjectivePopulationDiversityAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
294          SingleObjectivePopulationDiversityAnalyzer.QualityParameter.ActualName = ProblemInstance.SolutionEvaluator.QualityParameter.ActualName;
295          SingleObjectivePopulationDiversityAnalyzer.ResultsParameter.ActualName = "Results";
296          SingleObjectivePopulationDiversityAnalyzer.SimilarityCalculator = Operators.OfType<VRPSimilarityCalculator>().SingleOrDefault();
297        }
298      }
299    }
300
301    #endregion
302
303    private void InitializeRandomVRPInstance() {
304      System.Random rand = new System.Random();
305
306      CVRPTWProblemInstance problem = new CVRPTWProblemInstance();
307      int cities = 100;
308
309      problem.Coordinates = new DoubleMatrix(cities + 1, 2);
310      problem.Demand = new DoubleArray(cities + 1);
311      problem.DueTime = new DoubleArray(cities + 1);
312      problem.ReadyTime = new DoubleArray(cities + 1);
313      problem.ServiceTime = new DoubleArray(cities + 1);
314
315      problem.Vehicles.Value = 100;
316      problem.Capacity.Value = 200;
317
318      for (int i = 0; i <= cities; i++) {
319        problem.Coordinates[i, 0] = rand.Next(0, 100);
320        problem.Coordinates[i, 1] = rand.Next(0, 100);
321
322        if (i == 0) {
323          problem.Demand[i] = 0;
324          problem.DueTime[i] = Int16.MaxValue;
325          problem.ReadyTime[i] = 0;
326          problem.ServiceTime[i] = 0;
327        } else {
328          problem.Demand[i] = rand.Next(10, 50);
329          problem.DueTime[i] = rand.Next((int)Math.Ceiling(problem.GetDistance(0, i, null)), 1200);
330          problem.ReadyTime[i] = problem.DueTime[i] - rand.Next(0, 100);
331          problem.ServiceTime[i] = 90;
332        }
333      }
334
335      this.ProblemInstance = problem;
336    }
337
338    public void ImportSolution(string solutionFileName) {
339      SolutionParser parser = new SolutionParser(solutionFileName);
340      parser.Parse();
341
342      HeuristicLab.Problems.VehicleRouting.Encodings.Potvin.PotvinEncoding encoding = new Encodings.Potvin.PotvinEncoding(ProblemInstance);
343
344      int cities = 0;
345      foreach (List<int> route in parser.Routes) {
346        Tour tour = new Tour();
347        tour.Stops.AddRange(route);
348        cities += tour.Stops.Count;
349
350        encoding.Tours.Add(tour);
351      }
352
353      if (cities != ProblemInstance.Coordinates.Rows - 1)
354        ErrorHandling.ShowErrorDialog(new Exception("The optimal solution does not seem to correspond with the problem data"));
355      else {
356        VRPSolution solution = new VRPSolution(ProblemInstance, encoding, new DoubleValue(0));
357        BestKnownSolutionParameter.Value = solution;
358      }
359    }
360
361    #region Instance Consuming
362    public void Load(IVRPData data, IVRPDataInterpreter interpreter) {
363      VRPInstanceDescription instance = interpreter.Interpret(data);
364
365      Name = instance.Name;
366      Description = instance.Description;
367
368      BestKnownQuality = null;
369      BestKnownSolution = null;
370
371      if (ProblemInstance != null && instance.ProblemInstance != null &&
372        instance.ProblemInstance.GetType() == ProblemInstance.GetType())
373        SetProblemInstance(instance.ProblemInstance);
374      else
375        ProblemInstance = instance.ProblemInstance;
376
377      OnReset();
378
379      if (instance.BestKnownQuality != null) {
380        BestKnownQuality = new DoubleValue((double)instance.BestKnownQuality);
381      }
382
383      if (instance.BestKnownSolution != null) {
384        VRPSolution solution = new VRPSolution(ProblemInstance, instance.BestKnownSolution, new DoubleValue(0));
385        BestKnownSolution = solution;
386      }
387    }
388    #endregion
389
390    #region IProblemInstanceConsumer<VRPData> Members
391
392    public void Load(VRPData data) {
393      var interpreterDataType = data.GetType();
394      var interpreterType = typeof(IVRPDataInterpreter<>).MakeGenericType(interpreterDataType);
395
396      var interpreters = ApplicationManager.Manager.GetTypes(interpreterType);
397
398      var concreteInterpreter = interpreters.Single(t => GetInterpreterDataType(t) == interpreterDataType);
399
400      Load(data, (IVRPDataInterpreter)Activator.CreateInstance(concreteInterpreter));
401    }
402
403    private Type GetInterpreterDataType(Type type) {
404      var parentInterfaces = type.BaseType.GetInterfaces();
405      var interfaces = type.GetInterfaces().Except(parentInterfaces);
406
407      var interpreterInterface = interfaces.Single(i => typeof(IVRPDataInterpreter).IsAssignableFrom(i));
408      return interpreterInterface.GetGenericArguments()[0];
409    }
410
411    #endregion
412  }
413}
Note: See TracBrowser for help on using the repository browser.