Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.VehicleRouting/3.4/VehicleRoutingProblem.cs @ 17699

Last change on this file since 17699 was 17699, checked in by abeham, 4 years ago

#2521: Made encodings non-generic classes (the TEncodedSolution type parameter is not actually used), this will make it considerably easier to port the VRP to the new architecture

File size: 12.6 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.Collections.Generic;
24using System.Drawing;
25using System.Linq;
26using System.Threading;
27using HEAL.Attic;
28using HeuristicLab.Analysis;
29using HeuristicLab.Common;
30using HeuristicLab.Core;
31using HeuristicLab.Data;
32using HeuristicLab.Optimization;
33using HeuristicLab.Optimization.Operators;
34using HeuristicLab.Parameters;
35using HeuristicLab.PluginInfrastructure;
36using HeuristicLab.Problems.Instances;
37using HeuristicLab.Problems.VehicleRouting.Encodings.Alba;
38using HeuristicLab.Problems.VehicleRouting.Interfaces;
39using HeuristicLab.Problems.VehicleRouting.Interpreters;
40using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
41using HeuristicLab.Problems.VehicleRouting.Variants;
42
43namespace HeuristicLab.Problems.VehicleRouting {
44  [Item("Vehicle Routing Problem (VRP)", "Represents a Vehicle Routing Problem.")]
45  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 110)]
46  [StorableType("95137523-AE3B-4638-958C-E86829D54CE3")]
47  public sealed class VehicleRoutingProblem : SingleObjectiveProblem<IVRPEncoding, IVRPEncodedSolution>, IProblemInstanceConsumer<IVRPData> {
48
49    public static new Image StaticItemImage {
50      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
51    }
52
53    #region Parameter Properties
54    public ValueParameter<IVRPProblemInstance> ProblemInstanceParameter {
55      get { return (ValueParameter<IVRPProblemInstance>)Parameters["ProblemInstance"]; }
56    }
57    public OptionalValueParameter<VRPSolution> BestKnownSolutionParameter {
58      get { return (OptionalValueParameter<VRPSolution>)Parameters["BestKnownSolution"]; }
59    }
60    #endregion
61
62    #region Properties
63    public IVRPProblemInstance ProblemInstance {
64      get { return ProblemInstanceParameter.Value; }
65      set { ProblemInstanceParameter.Value = value; }
66    }
67
68    public VRPSolution BestKnownSolution {
69      get { return BestKnownSolutionParameter.Value; }
70      set { BestKnownSolutionParameter.Value = value; }
71    }
72    #endregion
73
74    [StorableConstructor]
75    private VehicleRoutingProblem(StorableConstructorFlag _) : base(_) { }
76    public VehicleRoutingProblem()
77      : base(new AlbaEncoding()) {
78      Parameters.Add(new ValueParameter<IVRPProblemInstance>("ProblemInstance", "The VRP problem instance"));
79      Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
80
81      InitializeRandomVRPInstance();
82      InitializeOperators();
83
84      AttachEventHandlers();
85      AttachProblemInstanceEventHandlers();
86    }
87
88    public override IDeepCloneable Clone(Cloner cloner) {
89      cloner.Clone(ProblemInstance);
90      return new VehicleRoutingProblem(this, cloner);
91    }
92
93    private VehicleRoutingProblem(VehicleRoutingProblem original, Cloner cloner)
94      : base(original, cloner) {
95      this.AttachEventHandlers();
96      this.AttachProblemInstanceEventHandlers();
97    }
98
99    public override ISingleObjectiveEvaluationResult Evaluate(IVRPEncodedSolution solution, IRandom random, CancellationToken cancellationToken) {
100      return new SingleObjectiveEvaluationResult(ProblemInstance.Evaluate(solution).Quality);
101    }
102
103    #region Helpers
104    [StorableHook(HookType.AfterDeserialization)]
105    private void AfterDeserialization() {
106      AttachEventHandlers();
107      AttachProblemInstanceEventHandlers();
108    }
109
110    [Storable(OldName = "operators")]
111    private List<IOperator> StorableOperators {
112      set { Operators.AddRange(value); }
113    }
114
115    private void AttachEventHandlers() {
116      ProblemInstanceParameter.ValueChanged += new EventHandler(ProblemInstanceParameter_ValueChanged);
117      BestKnownSolutionParameter.ValueChanged += new EventHandler(BestKnownSolutionParameter_ValueChanged);
118    }
119
120    private void AttachProblemInstanceEventHandlers() {
121      if (ProblemInstance != null) {
122        ProblemInstance.EvaluationChanged += new EventHandler(ProblemInstance_EvaluationChanged);
123      }
124    }
125
126    private void EvalBestKnownSolution() {
127      if (BestKnownSolution == null) return;
128      try {
129        //call evaluator
130        BestKnownQuality = ProblemInstance.Evaluate(BestKnownSolution.Solution).Quality;
131        BestKnownSolution.Quality = new DoubleValue(BestKnownQuality);
132      } catch {
133        BestKnownQuality = double.NaN;
134        BestKnownSolution = null;
135      }
136    }
137
138    void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
139      EvalBestKnownSolution();
140    }
141
142    void ProblemInstance_EvaluationChanged(object sender, EventArgs e) {
143      BestKnownQuality = double.NaN;
144      if (BestKnownSolution != null) {
145        // the tour is not valid if there are more vehicles in it than allowed
146        if (ProblemInstance.Vehicles.Value < BestKnownSolution.Solution.GetTours().Count) {
147          BestKnownSolution = null;
148        } else EvalBestKnownSolution();
149      }
150    }
151
152    void ProblemInstanceParameter_ValueChanged(object sender, EventArgs e) {
153      InitializeOperators();
154      AttachProblemInstanceEventHandlers();
155
156      OnOperatorsChanged();
157    }
158
159    public void SetProblemInstance(IVRPProblemInstance instance) {
160      ProblemInstanceParameter.ValueChanged -= new EventHandler(ProblemInstanceParameter_ValueChanged);
161
162      ProblemInstance = instance;
163      AttachProblemInstanceEventHandlers();
164
165      ProblemInstanceParameter.ValueChanged += new EventHandler(ProblemInstanceParameter_ValueChanged);
166    }
167
168    private void InitializeOperators() {
169      Operators.Clear();
170
171      if (ProblemInstance != null) {
172        Operators.AddRange(
173        ProblemInstance.Operators.Concat(
174          ApplicationManager.Manager.GetInstances<IGeneralVRPOperator>().Cast<IOperator>()).OrderBy(op => op.Name));
175        Operators.Add(new VRPSimilarityCalculator());
176        Operators.Add(new QualitySimilarityCalculator());
177        Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
178
179        IVRPCreator defaultCreator = null;
180        /*foreach (IVRPCreator creator in Operators.Where(o => o is IVRPCreator)) {
181          solutionCreatorParameter.ValidValues.Add(creator);
182          if (creator is Encodings.Alba.RandomCreator)
183            defaultCreator = creator;
184        }*/
185        Operators.Add(new AlbaLambdaInterchangeLocalImprovementOperator());
186        /*if (defaultCreator != null)
187          solutionCreatorParameter.Value = defaultCreator;*/
188      }
189
190      Parameterize();
191    }
192
193    protected override void ParameterizeOperators() {
194      base.ParameterizeOperators();
195      Parameterize();
196    }
197
198    private void Parameterize() {
199      foreach (IOperator op in Operators.OfType<IOperator>()) {
200        if (op is IMultiVRPOperator) {
201          (op as IMultiVRPOperator).SetOperators(Operators.OfType<IOperator>());
202        }
203      }
204      if (Parameters.ContainsKey("ProblemInstance") && ProblemInstance != null) {
205        foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
206          //op.SolutionParameter.ActualName = SolutionCreator.VRPToursParameter.ActualName;
207          op.SolutionParameter.Hidden = true;
208        }
209        foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
210          //op.ParentsParameter.ActualName = SolutionCreator.VRPToursParameter.ActualName;
211          op.ParentsParameter.Hidden = true;
212        }
213        foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
214          //op.SolutionVariableName = SolutionCreator.VRPToursParameter.ActualName;
215          op.QualityVariableName = ProblemInstance.SolutionEvaluator.QualityParameter.ActualName;
216          var calc = op as VRPSimilarityCalculator;
217          if (calc != null) calc.ProblemInstance = ProblemInstance;
218        }
219      }
220    }
221
222    #endregion
223
224    private void InitializeRandomVRPInstance() {
225      System.Random rand = new System.Random();
226
227      CVRPTWProblemInstance problem = new CVRPTWProblemInstance();
228      int cities = 100;
229
230      problem.Coordinates = new DoubleMatrix(cities + 1, 2);
231      problem.Demand = new DoubleArray(cities + 1);
232      problem.DueTime = new DoubleArray(cities + 1);
233      problem.ReadyTime = new DoubleArray(cities + 1);
234      problem.ServiceTime = new DoubleArray(cities + 1);
235
236      problem.Vehicles.Value = 100;
237      problem.Capacity.Value = 200;
238
239      for (int i = 0; i <= cities; i++) {
240        problem.Coordinates[i, 0] = rand.Next(0, 100);
241        problem.Coordinates[i, 1] = rand.Next(0, 100);
242
243        if (i == 0) {
244          problem.Demand[i] = 0;
245          problem.DueTime[i] = Int16.MaxValue;
246          problem.ReadyTime[i] = 0;
247          problem.ServiceTime[i] = 0;
248        } else {
249          problem.Demand[i] = rand.Next(10, 50);
250          problem.DueTime[i] = rand.Next((int)Math.Ceiling(problem.GetDistance(0, i, null)), 1200);
251          problem.ReadyTime[i] = problem.DueTime[i] - rand.Next(0, 100);
252          problem.ServiceTime[i] = 90;
253        }
254      }
255
256      this.ProblemInstance = problem;
257    }
258
259    public void ImportSolution(string solutionFileName) {
260      SolutionParser parser = new SolutionParser(solutionFileName);
261      parser.Parse();
262
263      HeuristicLab.Problems.VehicleRouting.Encodings.Potvin.PotvinEncodedSolution encoding = new Encodings.Potvin.PotvinEncodedSolution(ProblemInstance);
264
265      int cities = 0;
266      foreach (List<int> route in parser.Routes) {
267        Tour tour = new Tour();
268        tour.Stops.AddRange(route);
269        cities += tour.Stops.Count;
270
271        encoding.Tours.Add(tour);
272      }
273
274      if (cities != ProblemInstance.Coordinates.Rows - 1)
275        ErrorHandling.ShowErrorDialog(new Exception("The optimal solution does not seem to correspond with the problem data"));
276      else {
277        VRPSolution solution = new VRPSolution(ProblemInstance, encoding, new DoubleValue(0));
278        BestKnownSolutionParameter.Value = solution;
279      }
280    }
281
282    #region Instance Consuming
283    public void Load(IVRPData data, IVRPDataInterpreter interpreter) {
284      VRPInstanceDescription instance = interpreter.Interpret(data);
285
286      Name = instance.Name;
287      Description = instance.Description;
288
289      BestKnownQuality = double.NaN;
290      BestKnownSolution = null;
291
292      if (ProblemInstance != null && instance.ProblemInstance != null &&
293        instance.ProblemInstance.GetType() == ProblemInstance.GetType())
294        SetProblemInstance(instance.ProblemInstance);
295      else
296        ProblemInstance = instance.ProblemInstance;
297
298      OnReset();
299
300      if (instance.BestKnownQuality != null) {
301        BestKnownQuality = instance.BestKnownQuality ?? double.NaN;
302      }
303
304      if (instance.BestKnownSolution != null) {
305        VRPSolution solution = new VRPSolution(ProblemInstance, instance.BestKnownSolution, new DoubleValue(0));
306        BestKnownSolution = solution;
307      }
308    }
309    #endregion
310
311    #region IProblemInstanceConsumer<VRPData> Members
312
313    public void Load(IVRPData data) {
314      var interpreterDataType = data.GetType();
315      var interpreterType = typeof(IVRPDataInterpreter<>).MakeGenericType(interpreterDataType);
316
317      var interpreters = ApplicationManager.Manager.GetTypes(interpreterType);
318
319      var concreteInterpreter = interpreters.Single(t => GetInterpreterDataType(t) == interpreterDataType);
320
321      Load(data, (IVRPDataInterpreter)Activator.CreateInstance(concreteInterpreter));
322    }
323
324    private Type GetInterpreterDataType(Type type) {
325      var parentInterfaces = type.BaseType.GetInterfaces();
326      var interfaces = type.GetInterfaces().Except(parentInterfaces);
327
328      var interpreterInterface = interfaces.Single(i => typeof(IVRPDataInterpreter).IsAssignableFrom(i));
329      return interpreterInterface.GetGenericArguments()[0];
330    }
331    #endregion
332  }
333}
Note: See TracBrowser for help on using the repository browser.