Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HLScript/HeuristicLab.Problems.VehicleRouting/3.4/PathRelinkers/VRPPathRelinker.cs @ 10331

Last change on this file since 10331 was 9456, checked in by swagner, 12 years ago

Updated copyright year and added some missing license headers (#1889)

File size: 13.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Optimization;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
33using HeuristicLab.Problems.VehicleRouting.Interfaces;
34using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
35using HeuristicLab.Problems.VehicleRouting.Variants;
36
37namespace HeuristicLab.Problems.VehicleRouting {
38  /// <summary>
39  /// An operator which relinks paths between VRP solutions.
40  /// </summary>
41  [Item("VRPPathRelinker", "An operator which relinks paths between VRP solutions.")]
42  [StorableClass]
43  public sealed class VRPPathRelinker : SingleObjectivePathRelinker, IGeneralVRPOperator, IStochasticOperator {
44    #region Parameter properties
45    public IValueParameter<IntValue> IterationsParameter {
46      get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
47    }
48    public ILookupParameter<IVRPProblemInstance> ProblemInstanceParameter {
49      get { return (ILookupParameter<IVRPProblemInstance>)Parameters["ProblemInstance"]; }
50    }
51    public ILookupParameter<IRandom> RandomParameter {
52      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
53    }
54    public IValueParameter<IntValue> SampleSizeParameter {
55      get { return (IValueParameter<IntValue>)Parameters["SampleSize"]; }
56    }
57    #endregion
58
59    [StorableConstructor]
60    private VRPPathRelinker(bool deserializing) : base(deserializing) { }
61    private VRPPathRelinker(VRPPathRelinker original, Cloner cloner) : base(original, cloner) { }
62    public VRPPathRelinker()
63      : base() {
64      Parameters.Add(new ValueParameter<IntValue>("Iterations", "The number of iterations the operator should perform.", new IntValue(50)));
65      Parameters.Add(new LookupParameter<IVRPProblemInstance>("ProblemInstance", "The VRP problem instance"));
66      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
67      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "The number of moves that should be executed.", new IntValue(10)));
68    }
69
70    public override IDeepCloneable Clone(Cloner cloner) {
71      return new VRPPathRelinker(this, cloner);
72    }
73
74    public static ItemArray<IItem> Apply(PotvinEncoding initiator, PotvinEncoding guide, PercentValue n, int sampleSize, int iterations, IRandom rand, IVRPProblemInstance problemInstance) {
75      if (initiator == null || guide == null)
76        throw new ArgumentException("Cannot relink path because one of the provided solutions or both are null.");
77
78      double sigma = 1.5;
79      double minPenalty = 0.001;
80      double maxPenalty = 1000000000;
81
82      var originalOverloadPenalty = new DoubleValue();
83      if (problemInstance is IHomogenousCapacitatedProblemInstance)
84        originalOverloadPenalty.Value = (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value;
85      var originalTardinessPenalty = new DoubleValue();
86      if (problemInstance is ITimeWindowedProblemInstance)
87        originalTardinessPenalty.Value = (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value;
88
89      PotvinEncoding current = MatchTours(initiator, guide, problemInstance);
90      double currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
91
92      IList<PotvinEncoding> solutions = new List<PotvinEncoding>();
93      int i = 0;
94      while (i < iterations && !currentSimilarity.IsAlmost(1.0)) {
95        var currentEval = problemInstance.Evaluate(current);
96        currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
97
98        if (currentSimilarity < 1.0) {
99          for (int sample = 0; sample < sampleSize; sample++) {
100            var next = current.Clone() as PotvinEncoding;
101
102            int neighborhood = rand.Next(3);
103            switch (neighborhood) {
104              case 0: next = RouteBasedXOver(next, guide, rand,
105                problemInstance);
106                break;
107              case 1: next = SequenceBasedXOver(next, guide, rand,
108                problemInstance);
109                break;
110              case 2: GuidedRelocateMove(next, guide, rand);
111                break;
112            }
113
114            next = MatchTours(next, guide, problemInstance);
115
116            var nextEval = problemInstance.Evaluate(next);
117            if ((nextEval.Quality < currentEval.Quality)) {
118              current = next;
119              solutions.Add(current);
120              break;
121            }
122          }
123
124          if (problemInstance is IHomogenousCapacitatedProblemInstance) {
125            if (((CVRPEvaluation)currentEval).Overload > 0) {
126              (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value =
127                Math.Min(maxPenalty,
128                (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value * sigma);
129            } else {
130              (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value =
131                Math.Max(minPenalty,
132                (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value * sigma);
133            }
134          }
135
136
137          if (problemInstance is ITimeWindowedProblemInstance) {
138            if (((CVRPTWEvaluation)currentEval).Tardiness > 0) {
139              (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value =
140                Math.Min(maxPenalty,
141              (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value * sigma);
142            } else {
143              (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value =
144                Math.Max(minPenalty,
145                (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value / sigma);
146            }
147          }
148
149          i++;
150        }
151      }
152
153      if (problemInstance is IHomogenousCapacitatedProblemInstance)
154        (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value = originalOverloadPenalty.Value;
155      if (problemInstance is ITimeWindowedProblemInstance)
156        (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value = originalTardinessPenalty.Value;
157
158      return new ItemArray<IItem>(ChooseSelection(solutions, n));
159    }
160
161    private static IList<IItem> ChooseSelection(IList<PotvinEncoding> solutions, PercentValue n) {
162      IList<IItem> selection = new List<IItem>();
163      if (solutions.Count > 0) {
164        int noSol = (int)(solutions.Count * n.Value);
165        if (noSol <= 0) noSol++;
166        double stepSize = (double)solutions.Count / (double)noSol;
167        for (int i = 0; i < noSol; i++)
168          selection.Add(solutions.ElementAt((int)((i + 1) * stepSize - stepSize * 0.5)));
169      }
170
171      return selection;
172    }
173
174    protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {
175      if (parents.Length != 2)
176        throw new ArgumentException("The number of parents is not equal to 2.");
177
178      if (!(parents[0] is PotvinEncoding))
179        parents[0] = PotvinEncoding.ConvertFrom(parents[0] as IVRPEncoding, ProblemInstanceParameter.ActualValue);
180      if (!(parents[1] is PotvinEncoding))
181        parents[1] = PotvinEncoding.ConvertFrom(parents[1] as IVRPEncoding, ProblemInstanceParameter.ActualValue);
182
183      return Apply(parents[0] as PotvinEncoding, parents[1] as PotvinEncoding, n,
184        SampleSizeParameter.Value.Value, IterationsParameter.Value.Value, RandomParameter.ActualValue, ProblemInstanceParameter.ActualValue);
185    }
186
187    private static int MatchingCities(Tour tour1, Tour tour2) {
188      return tour1.Stops.Intersect(tour2.Stops).Count();
189    }
190
191    private static PotvinEncoding MatchTours(PotvinEncoding initiator, PotvinEncoding guide, IVRPProblemInstance problemInstance) {
192      var result = new PotvinEncoding(problemInstance);
193
194      var used = new List<bool>();
195      for (int i = 0; i < initiator.Tours.Count; i++) {
196        used.Add(false);
197      }
198
199      for (int i = 0; i < guide.Tours.Count; i++) {
200        int bestMatch = -1;
201        int bestTour = -1;
202
203        for (int j = 0; j < initiator.Tours.Count; j++) {
204          if (!used[j]) {
205            int match = MatchingCities(guide.Tours[i], initiator.Tours[j]);
206            if (match > bestMatch) {
207              bestMatch = match;
208              bestTour = j;
209            }
210          }
211        }
212
213        if (bestTour != -1) {
214          result.Tours.Add(initiator.Tours[bestTour]);
215          used[bestTour] = true;
216        }
217      }
218
219      for (int i = 0; i < initiator.Tours.Count; i++) {
220        if (!used[i])
221          result.Tours.Add(initiator.Tours[i]);
222      }
223
224      return result;
225    }
226
227    #region moves
228    public static PotvinEncoding RouteBasedXOver(PotvinEncoding initiator, PotvinEncoding guide, IRandom random, IVRPProblemInstance problemInstance) {
229      return PotvinRouteBasedCrossover.Apply(random, initiator, guide, problemInstance, false);
230    }
231
232    public static PotvinEncoding SequenceBasedXOver(PotvinEncoding initiator, PotvinEncoding guide, IRandom random, IVRPProblemInstance problemInstance) {
233      return PotvinSequenceBasedCrossover.Apply(random, initiator, guide, problemInstance, false);
234    }
235
236    public static void GuidedRelocateMove(PotvinEncoding initiator, PotvinEncoding guide, IRandom random) {
237      List<int> cities = new List<int>();
238      foreach (Tour tour in initiator.Tours) {
239        foreach (int city in tour.Stops) {
240          Tour guideTour = guide.Tours.First(t => t.Stops.Contains(city));
241          if (guide.Tours.IndexOf(guideTour) != initiator.Tours.IndexOf(tour)) {
242            cities.Add(city);
243          }
244        }
245      }
246
247      if (cities.Count == 0) {
248        RelocateMove(initiator, random);
249      } else {
250        int city = cities[random.Next(cities.Count)];
251        Tour tour = initiator.Tours.First(t => t.Stops.Contains(city));
252        tour.Stops.Remove(city);
253
254        Tour guideTour = guide.Tours.First(t => t.Stops.Contains(city));
255        int guideTourIndex = guide.Tours.IndexOf(guideTour);
256
257        if (guideTourIndex < initiator.Tours.Count) {
258          Tour tour2 = initiator.Tours[guideTourIndex];
259
260          int guideIndex = guideTour.Stops.IndexOf(city);
261          if (guideIndex == 0) {
262            tour2.Stops.Insert(0, city);
263          } else {
264            int predecessor = guideTour.Stops[guideIndex - 1];
265            int initIndex = tour2.Stops.IndexOf(predecessor);
266            if (initIndex != -1) {
267              tour2.Stops.Insert(initIndex + 1, city);
268            } else {
269              if (guideIndex == guideTour.Stops.Count - 1) {
270                tour2.Stops.Insert(tour2.Stops.Count, city);
271              } else {
272                int sucessor = guideTour.Stops[guideIndex + 1];
273                initIndex = tour2.Stops.IndexOf(sucessor);
274                if (initIndex != -1) {
275                  tour2.Stops.Insert(initIndex, city);
276                } else {
277                  tour2.Stops.Insert(random.Next(tour2.Stops.Count + 1), city);
278                }
279              }
280            }
281          }
282        } else {
283          Tour tour2 = new Tour();
284          tour2.Stops.Add(city);
285          initiator.Tours.Add(tour2);
286        }
287
288        if (tour.Stops.Count == 0)
289          initiator.Tours.Remove(tour);
290      }
291    }
292
293    public static void RelocateMove(PotvinEncoding individual, IRandom random) {
294      int cities = individual.Cities;
295      int city = 1 + random.Next(cities);
296      Tour originalTour = individual.Tours.Find(t => t.Stops.Contains(city));
297      //consider creating new route
298      individual.Tours.Add(new Tour());
299
300      int position = 1 + random.Next(cities + individual.Tours.Count - 1);
301      if (position >= city) {
302        position++;
303      }
304
305      int originalPosition = originalTour.Stops.IndexOf(city);
306      originalTour.Stops.RemoveAt(originalPosition);
307
308      Tour insertionTour;
309      int insertionPosition;
310      if (position <= cities) {
311        insertionTour = individual.Tours.Find(t => t.Stops.Contains(position));
312        insertionPosition = insertionTour.Stops.IndexOf(position) + 1;
313      } else {
314        insertionTour = individual.Tours[position - cities - 1];
315        insertionPosition = 0;
316      }
317
318      insertionTour.Stops.Insert(insertionPosition, city);
319
320      individual.Tours.RemoveAll(t => t.Stops.Count == 0);
321    }
322    #endregion
323  }
324}
Note: See TracBrowser for help on using the repository browser.