Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.VehicleRouting/3.4/VehicleRoutingProblem.cs @ 11289

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

#2208 merged changes from #2225 to enable all CVRP provider for the orienteering problem.

File size: 16.3 KB
RevLine 
[4360]1#region License Information
2/* HeuristicLab
[11185]3 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[4360]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;
[8720]26using HeuristicLab.Analysis;
[4360]27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
[7934]34using HeuristicLab.Problems.Instances;
[4362]35using HeuristicLab.Problems.VehicleRouting.Interfaces;
[7934]36using HeuristicLab.Problems.VehicleRouting.Interpreters;
[4362]37using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
[4365]38using HeuristicLab.Problems.VehicleRouting.Variants;
[4360]39
40namespace HeuristicLab.Problems.VehicleRouting {
41  [Item("Vehicle Routing Problem", "Represents a Vehicle Routing Problem.")]
42  [Creatable("Problems")]
43  [StorableClass]
[11289]44  public sealed class VehicleRoutingProblem : Problem, ISingleObjectiveHeuristicOptimizationProblem, IStorableContent, IProblemInstanceConsumer<IVRPData> {
[4444]45    public string Filename { get; set; }
[7203]46
47    public static new Image StaticItemImage {
[5867]48      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
[4360]49    }
50
[4362]51    #region Parameter Properties
52    public ValueParameter<BoolValue> MaximizationParameter {
53      get { return (ValueParameter<BoolValue>)Parameters["Maximization"]; }
[4360]54    }
[5867]55    IParameter ISingleObjectiveHeuristicOptimizationProblem.MaximizationParameter {
[4362]56      get { return MaximizationParameter; }
[4360]57    }
[4362]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    }
[5867]64    IParameter ISingleObjectiveHeuristicOptimizationProblem.BestKnownQualityParameter {
[4362]65      get { return BestKnownQualityParameter; }
66    }
[4860]67    public OptionalValueParameter<VRPSolution> BestKnownSolutionParameter {
68      get { return (OptionalValueParameter<VRPSolution>)Parameters["BestKnownSolution"]; }
69    }
[8121]70    public IConstrainedValueParameter<IVRPCreator> SolutionCreatorParameter {
71      get { return (IConstrainedValueParameter<IVRPCreator>)Parameters["SolutionCreator"]; }
[4360]72    }
[5867]73    IParameter IHeuristicOptimizationProblem.SolutionCreatorParameter {
[4365]74      get { return SolutionCreatorParameter; }
[4362]75    }
[4365]76    public IValueParameter<IVRPEvaluator> EvaluatorParameter {
77      get { return (IValueParameter<IVRPEvaluator>)Parameters["Evaluator"]; }
78    }
[5867]79    IParameter IHeuristicOptimizationProblem.EvaluatorParameter {
[4365]80      get { return EvaluatorParameter; }
81    }
[4362]82    #endregion
[4360]83
[4362]84    #region Properties
85    public IVRPProblemInstance ProblemInstance {
86      get { return ProblemInstanceParameter.Value; }
87      set { ProblemInstanceParameter.Value = value; }
[4360]88    }
89
[4860]90    public VRPSolution BestKnownSolution {
91      get { return BestKnownSolutionParameter.Value; }
92      set { BestKnownSolutionParameter.Value = value; }
93    }
94
[7852]95    public DoubleValue BestKnownQuality {
96      get { return BestKnownQualityParameter.Value; }
97      set { BestKnownQualityParameter.Value = value; }
98    }
99
[4362]100    public ISingleObjectiveEvaluator Evaluator {
[7852]101      get { return EvaluatorParameter.Value; }
[4360]102    }
103
[5867]104    IEvaluator IHeuristicOptimizationProblem.Evaluator {
[4362]105      get { return this.Evaluator; }
[4360]106    }
107
[8121]108    ISolutionCreator IHeuristicOptimizationProblem.SolutionCreator {
[7852]109      get { return SolutionCreatorParameter.Value; }
[4360]110    }
[8121]111    public IVRPCreator SolutionCreator {
112      get { return SolutionCreatorParameter.Value; }
113      set { SolutionCreatorParameter.Value = value; }
114    }
[8720]115    private SingleObjectivePopulationDiversityAnalyzer SingleObjectivePopulationDiversityAnalyzer {
116      get { return Operators.OfType<SingleObjectivePopulationDiversityAnalyzer>().FirstOrDefault(); }
117    }
[4360]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)));
[4362]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."));
[4860]127      Parameters.Add(new OptionalValueParameter<VRPSolution>("BestKnownSolution", "The best known solution of this VRP instance."));
[4365]128
[7852]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
[4360]134      InitializeRandomVRPInstance();
[4365]135      InitializeOperators();
[4360]136
137      AttachEventHandlers();
[4362]138      AttachProblemInstanceEventHandlers();
[10363]139
140      EvaluatorParameter.Value = ProblemInstance.SolutionEvaluator;
[4360]141    }
142
143    public override IDeepCloneable Clone(Cloner cloner) {
[7906]144      cloner.Clone(ProblemInstance);
[4752]145      return new VehicleRoutingProblem(this, cloner);
[4360]146    }
147
[4752]148    private VehicleRoutingProblem(VehicleRoutingProblem original, Cloner cloner)
149      : base(original, cloner) {
150      this.AttachEventHandlers();
[10360]151      this.AttachProblemInstanceEventHandlers();
[10363]152
153      ProblemInstance.SolutionEvaluator = EvaluatorParameter.Value;
[4752]154    }
155
[4360]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)]
[7934]171    private void AfterDeserialization() {
[4360]172      AttachEventHandlers();
[4362]173      AttachProblemInstanceEventHandlers();
[10363]174
175      ProblemInstance.SolutionEvaluator = EvaluatorParameter.Value;
[4360]176    }
177
[8006]178    [Storable(Name = "operators", AllowOneWay = true)]
179    private List<IOperator> StorableOperators {
180      set { Operators.AddRange(value); }
181    }
182
[4360]183    private void AttachEventHandlers() {
[4362]184      ProblemInstanceParameter.ValueChanged += new EventHandler(ProblemInstanceParameter_ValueChanged);
[7861]185      BestKnownSolutionParameter.ValueChanged += new EventHandler(BestKnownSolutionParameter_ValueChanged);
[8006]186      EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
187      SolutionCreatorParameter.ValueChanged += new EventHandler(SolutionCreatorParameter_ValueChanged);
[4360]188    }
[4362]189
190    private void AttachProblemInstanceEventHandlers() {
191      if (ProblemInstance != null) {
[7852]192        ProblemInstance.EvaluationChanged += new EventHandler(ProblemInstance_EvaluationChanged);
[7934]193      }
[7852]194    }
[4860]195
[7861]196    private void EvalBestKnownSolution() {
[7852]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;
[4362]203      }
[4360]204    }
[4362]205
[7861]206    void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
207      EvalBestKnownSolution();
208    }
209
210    void ProblemInstance_EvaluationChanged(object sender, EventArgs e) {
211      EvalBestKnownSolution();
212    }
213
[4362]214    void ProblemInstanceParameter_ValueChanged(object sender, EventArgs e) {
[7853]215      InitializeOperators();
[4362]216      AttachProblemInstanceEventHandlers();
[4365]217
[10363]218      EvaluatorParameter.Value = ProblemInstance.SolutionEvaluator;
219
[4365]220      OnSolutionCreatorChanged();
221      OnEvaluatorChanged();
222      OnOperatorsChanged();
[4360]223    }
[6907]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
[4362]237    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
238      OnSolutionCreatorChanged();
[4360]239    }
[4362]240    private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
[8006]241      if (ProblemInstance != null)
242        ProblemInstance.SolutionEvaluator = EvaluatorParameter.Value;
[4362]243      OnEvaluatorChanged();
[4360]244    }
[4365]245
246    private void InitializeOperators() {
[8346]247      var solutionCreatorParameter = SolutionCreatorParameter as ConstrainedValueParameter<IVRPCreator>;
248      solutionCreatorParameter.ValidValues.Clear();
249
[8006]250      Operators.Clear();
[4365]251
252      if (ProblemInstance != null) {
[8006]253        Operators.AddRange(
[4365]254        ProblemInstance.Operators.Concat(
255          ApplicationManager.Manager.GetInstances<IGeneralVRPOperator>().Cast<IOperator>()).OrderBy(op => op.Name));
[8346]256        Operators.Add(new VRPSimilarityCalculator());
[8720]257        Operators.Add(new SingleObjectivePopulationDiversityAnalyzer());
[8346]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;
[4365]267      }
268
269      ParameterizeOperators();
270    }
271
272    private void ParameterizeOperators() {
[7999]273      foreach (IOperator op in Operators.OfType<IOperator>()) {
[4365]274        if (op is IMultiVRPOperator) {
[7999]275          (op as IMultiVRPOperator).SetOperators(Operators.OfType<IOperator>());
[4365]276        }
277      }
[8346]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        }
[8720]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        }
[8346]298      }
[4365]299    }
[8346]300
[4360]301    #endregion
302
303    private void InitializeRandomVRPInstance() {
304      System.Random rand = new System.Random();
305
[4362]306      CVRPTWProblemInstance problem = new CVRPTWProblemInstance();
[4360]307      int cities = 100;
[4362]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);
[6851]329          problem.DueTime[i] = rand.Next((int)Math.Ceiling(problem.GetDistance(0, i, null)), 1200);
[4362]330          problem.ReadyTime[i] = problem.DueTime[i] - rand.Next(0, 100);
331          problem.ServiceTime[i] = 90;
332        }
333      }
334
335      this.ProblemInstance = problem;
[4360]336    }
[4860]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));
[7852]357        BestKnownSolutionParameter.Value = solution;
[4860]358      }
359    }
[7871]360
[8905]361    #region Instance Consuming
362    public void Load(IVRPData data, IVRPDataInterpreter interpreter) {
363      VRPInstanceDescription instance = interpreter.Interpret(data);
[7871]364
[8905]365      Name = instance.Name;
366      Description = instance.Description;
[10860]367
368      BestKnownQuality = null;
369      BestKnownSolution = null;
370
[8905]371      if (ProblemInstance != null && instance.ProblemInstance != null &&
372        instance.ProblemInstance.GetType() == ProblemInstance.GetType())
373        SetProblemInstance(instance.ProblemInstance);
374      else
375        ProblemInstance = instance.ProblemInstance;
[7871]376
[8905]377      OnReset();
[7871]378
[8905]379      if (instance.BestKnownQuality != null) {
380        BestKnownQuality = new DoubleValue((double)instance.BestKnownQuality);
381      }
[7871]382
[8905]383      if (instance.BestKnownSolution != null) {
384        VRPSolution solution = new VRPSolution(ProblemInstance, instance.BestKnownSolution, new DoubleValue(0));
385        BestKnownSolution = solution;
[7934]386      }
[7871]387    }
[10435]388    #endregion
[8905]389
[10435]390    #region IProblemInstanceConsumer<VRPData> Members
[8905]391
[11289]392    public void Load(IVRPData data) {
[10651]393      var interpreterDataType = data.GetType();
394      var interpreterType = typeof(IVRPDataInterpreter<>).MakeGenericType(interpreterDataType);
[8905]395
[10651]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));
[8905]401    }
402
[10651]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
[8905]411    #endregion
[4360]412  }
413}
Note: See TracBrowser for help on using the repository browser.