Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/12/12 13:32:46 (11 years ago)
Author:
jkarder
Message:

#1331:

  • improved path relinking and improvement operators for the VehicleRouting problem
  • recreated SS VRP sample
  • corrected SS VRP sample test
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/PathRelinkers/VRPPathRelinker.cs

    r8346 r8894  
    3737namespace HeuristicLab.Problems.VehicleRouting {
    3838  /// <summary>
    39   /// An operator that relinks paths between vehicle routing solutions.
     39  /// An operator which relinks paths between VRP solutions.
    4040  /// </summary>
    41   [Item("VRPPathRelinker", "An operator that relinks paths between vehicle routing solutions.")]
     41  [Item("VRPPathRelinker", "An operator which relinks paths between VRP solutions.")]
    4242  [StorableClass]
    4343  public sealed class VRPPathRelinker : SingleObjectivePathRelinker, IGeneralVRPOperator, IStochasticOperator {
    4444    #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    }
    4551    public ILookupParameter<IRandom> RandomParameter {
    4652      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    4753    }
    48     public ILookupParameter<IVRPProblemInstance> ProblemInstanceParameter {
    49       get { return (ILookupParameter<IVRPProblemInstance>)Parameters["ProblemInstance"]; }
    50     }
    5154    public IValueParameter<IntValue> SampleSizeParameter {
    5255      get { return (IValueParameter<IntValue>)Parameters["SampleSize"]; }
    53     }
    54     public IValueParameter<IntValue> IterationsParameter {
    55       get { return (IValueParameter<IntValue>)Parameters["Iterations"]; }
    5656    }
    5757    #endregion
    … …  
    6262    public VRPPathRelinker()
    6363      : 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"));
    6466      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
    65       Parameters.Add(new LookupParameter<IVRPProblemInstance>("ProblemInstance", "The VRP problem instance"));
    6667      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "The number of moves that should be executed.", new IntValue(10)));
    67       Parameters.Add(new ValueParameter<IntValue>("Iterations", "The number of iterations the operator should perform.", new IntValue(50)));
    6868    }
    6969
    … …  
    7272    }
    7373
     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
    74187    private static int MatchingCities(Tour tour1, Tour tour2) {
    75188      return tour1.Stops.Intersect(tour2.Stops).Count();
    … …  
    77190
    78191    private static PotvinEncoding MatchTours(PotvinEncoding initiator, PotvinEncoding guide, IVRPProblemInstance problemInstance) {
    79       PotvinEncoding result = new PotvinEncoding(problemInstance);
    80 
    81       List<bool> used = new List<bool>();
     192      var result = new PotvinEncoding(problemInstance);
     193
     194      var used = new List<bool>();
    82195      for (int i = 0; i < initiator.Tours.Count; i++) {
    83196        used.Add(false);
    … …  
    120233      return PotvinSequenceBasedCrossover.Apply(random, initiator, guide, problemInstance, false);
    121234    }
    122 
    123235
    124236    public static void GuidedRelocateMove(PotvinEncoding initiator, PotvinEncoding guide, IRandom random) {
    … …  
    208320      individual.Tours.RemoveAll(t => t.Stops.Count == 0);
    209321    }
    210 
    211     public static void ExchangeMove(PotvinEncoding individual, IRandom random) {
    212       if (individual.Tours.Count > 1) {
    213         int tour1Idx = random.Next(individual.Tours.Count);
    214         int tour2Idx = random.Next(individual.Tours.Count - 1);
    215         if (tour2Idx >= tour1Idx)
    216           tour2Idx++;
    217 
    218         Tour tour1 = individual.Tours[tour1Idx];
    219         Tour tour2 = individual.Tours[tour2Idx];
    220 
    221         int index1 = random.Next(tour1.Stops.Count);
    222         int city1 = tour1.Stops[index1];
    223 
    224         int index2 = random.Next(tour2.Stops.Count);
    225         int city2 = tour2.Stops[index2];
    226 
    227         tour1.Stops.RemoveAt(index1);
    228         tour1.Stops.Insert(index1, city2);
    229 
    230         tour2.Stops.RemoveAt(index2);
    231         tour2.Stops.Insert(index2, city1);
    232       }
    233     }
    234 
    235     public static void TwoOptMove(PotvinEncoding individual, IRandom random) {
    236       List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 4);
    237 
    238       if (tours.Count > 0) {
    239         int tourIdx = random.Next(tours.Count);
    240         Tour tour = tours[tourIdx];
    241 
    242         int a;
    243         if (tour.Stops.Count == 4) {
    244           a = 0;
    245         } else if (tour.Stops.Count == 5) {
    246           int idx = random.Next(4);
    247           if (idx >= 2)
    248             idx++;
    249           a = idx;
    250         } else {
    251           a = random.Next(tour.Stops.Count);
    252         }
    253 
    254         int b;
    255         List<int> indices = new List<int>();
    256         for (int i = 0; i < tour.Stops.Count; i++) {
    257           if (Math.Abs(i - a) > 2) {
    258             indices.Add(i);
    259           }
    260         }
    261         b = indices[random.Next(indices.Count)];
    262 
    263         if (b < a) {
    264           int tmp = a;
    265           a = b;
    266           b = tmp;
    267         }
    268 
    269         int index = a + 1;
    270         int count = b - a - 1;
    271         List<int> segment = tour.Stops.GetRange(index, count);
    272         tour.Stops.RemoveRange(index, count);
    273         segment.Reverse();
    274         tour.Stops.InsertRange(index, segment);
    275       }
    276     }
    277 
    278     public static void TwoOptStarMove(PotvinEncoding individual, IRandom random) {
    279       //consider creating new tour
    280       individual.Tours.Add(new Tour());
    281 
    282       int route1Idx = random.Next(individual.Tours.Count);
    283       int route2Idx = random.Next(individual.Tours.Count - 1);
    284       if (route2Idx >= route1Idx)
    285         route2Idx++;
    286 
    287       Tour route1 = individual.Tours[route1Idx];
    288       Tour route2 = individual.Tours[route2Idx];
    289 
    290       int x1 = random.Next(route1.Stops.Count + 1);
    291       int x2 = random.Next(route2.Stops.Count + 1);
    292 
    293       int count = route1.Stops.Count - x1;
    294       List<int> segmentX1 = new List<int>();
    295       if (count > 0) {
    296         segmentX1 = route1.Stops.GetRange(x1, count);
    297         route1.Stops.RemoveRange(x1, count);
    298       }
    299 
    300       count = route2.Stops.Count - x2;
    301       List<int> segmentX2 = new List<int>();
    302       if (count > 0) {
    303         segmentX2 = route2.Stops.GetRange(x2, count);
    304         route2.Stops.RemoveRange(x2, count);
    305       }
    306 
    307       route1.Stops.AddRange(segmentX2);
    308       route2.Stops.AddRange(segmentX1);
    309 
    310       individual.Tours.RemoveAll(t => t.Stops.Count == 0);
    311     }
    312 
    313     public static void OrOptMove(PotvinEncoding individual, IRandom random) {
    314       List<Tour> tours = individual.Tours.FindAll(t => t.Stops.Count >= 2);
    315 
    316       if (tours.Count > 0) {
    317         int tourIdx = random.Next(tours.Count);
    318         Tour tour = tours[tourIdx];
    319 
    320         int segmentStart = random.Next(tour.Stops.Count);
    321         int segmentLength;
    322         if (segmentStart == 0) {
    323           segmentLength = 1 + random.Next(tour.Stops.Count - 1);
    324         } else {
    325           segmentLength = 1 + random.Next(tour.Stops.Count - segmentStart);
    326         }
    327 
    328         List<int> segment = tour.Stops.GetRange(segmentStart, segmentLength);
    329         tour.Stops.RemoveRange(segmentStart, segmentLength);
    330         int newPos;
    331         if (tour.Stops.Count == 1)
    332           newPos = 0;
    333         else
    334           newPos = random.Next(tour.Stops.Count - 1);
    335 
    336         if (newPos >= segmentStart)
    337           newPos++;
    338         tour.Stops.InsertRange(newPos, segment);
    339       }
    340     }
    341322    #endregion
    342 
    343     private static IList<IItem> ChooseSelection(IList<PotvinEncoding> solutions, PercentValue n) {
    344       IList<IItem> selection = new List<IItem>();
    345       if (solutions.Count > 0) {
    346         int noSol = (int)(solutions.Count * n.Value);
    347         if (noSol <= 0) noSol++;
    348         double stepSize = (double)solutions.Count / (double)noSol;
    349         for (int i = 0; i < noSol; i++)
    350           selection.Add(solutions.ElementAt((int)((i + 1) * stepSize - stepSize * 0.5)));
    351       }
    352 
    353       return selection;
    354     }
    355 
    356     public static ItemArray<IItem> Apply(PotvinEncoding initiator, PotvinEncoding guide, PercentValue n, int sampleSize, int iterations, IRandom rand, IVRPProblemInstance problemInstance) {
    357 
    358       if (initiator == null || guide == null)
    359         throw new ArgumentException("Cannot relink path because one of the provided solutions or both are null.");
    360 
    361       double sigma = 1.5;
    362 
    363       DoubleValue originalOverloadPenalty = new DoubleValue();
    364       if (problemInstance is IHomogenousCapacitatedProblemInstance)
    365         originalOverloadPenalty.Value = (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value;
    366       DoubleValue originalTardinessPenalty = new DoubleValue();
    367       if (problemInstance is ITimeWindowedProblemInstance)
    368         originalTardinessPenalty.Value = (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value;
    369 
    370       PotvinEncoding current = MatchTours(initiator, guide, problemInstance);
    371       double currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
    372 
    373       IList<PotvinEncoding> solutions = new List<PotvinEncoding>();
    374       int i = 0;
    375       while (i < iterations && currentSimilarity != 1.0) {
    376         VRPEvaluation currentEval = problemInstance.Evaluate(current);
    377         currentSimilarity = VRPSimilarityCalculator.CalculateSimilarity(current, guide);
    378 
    379         if (currentSimilarity < 1.0) {
    380           for (int sample = 0; sample < sampleSize; sample++) {
    381             PotvinEncoding next = current.Clone() as PotvinEncoding;
    382 
    383             int neighborhood = rand.Next(4);
    384             switch (neighborhood) {
    385               case 0: next = RouteBasedXOver(next, guide, rand,
    386                 problemInstance);
    387                 break;
    388               case 1: next = SequenceBasedXOver(next, guide, rand,
    389                 problemInstance);
    390                 break;
    391               case 2: TwoOptMove(next, rand);
    392                 break;
    393               case 3: GuidedRelocateMove(next, guide, rand);
    394                 break;
    395             }
    396 
    397             next = MatchTours(next, guide, problemInstance);
    398 
    399             VRPEvaluation nextEval = problemInstance.Evaluate(next);
    400             double nextSimilarity = VRPSimilarityCalculator.CalculateSimilarity(next, guide);
    401 
    402             if (nextSimilarity > currentSimilarity && nextEval.Quality <= currentEval.Quality) {
    403               current = next;
    404               solutions.Add(current);
    405               break;
    406             }
    407           }
    408 
    409           if (problemInstance is IHomogenousCapacitatedProblemInstance) {
    410             if (((CVRPEvaluation)currentEval).Overload > 0)
    411               (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value *= sigma;
    412             else
    413               (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value /= sigma;
    414           }
    415 
    416 
    417           if (problemInstance is ITimeWindowedProblemInstance) {
    418             if (((CVRPTWEvaluation)currentEval).Tardiness > 0)
    419               (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value *= sigma;
    420             else
    421               (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value /= sigma;
    422           }
    423 
    424           i++;
    425         }
    426       }
    427 
    428       if (problemInstance is IHomogenousCapacitatedProblemInstance)
    429         (problemInstance as IHomogenousCapacitatedProblemInstance).OverloadPenalty.Value = originalOverloadPenalty.Value;
    430       if (problemInstance is ITimeWindowedProblemInstance)
    431         (problemInstance as ITimeWindowedProblemInstance).TardinessPenalty.Value = originalTardinessPenalty.Value;
    432 
    433       return new ItemArray<IItem>(ChooseSelection(solutions, n));
    434     }
    435 
    436     protected override ItemArray<IItem> Relink(ItemArray<IItem> parents, PercentValue n) {
    437       if (parents.Length != 2)
    438         throw new ArgumentException("The number of parents is not equal to 2.");
    439 
    440       if (!(parents[0] is PotvinEncoding))
    441         parents[0] = PotvinEncoding.ConvertFrom(parents[0] as IVRPEncoding, ProblemInstanceParameter.ActualValue);
    442       if (!(parents[1] is PotvinEncoding))
    443         parents[1] = PotvinEncoding.ConvertFrom(parents[1] as IVRPEncoding, ProblemInstanceParameter.ActualValue);
    444 
    445       return Apply(parents[0] as PotvinEncoding, parents[1] as PotvinEncoding, n,
    446         SampleSizeParameter.Value.Value, IterationsParameter.Value.Value, RandomParameter.ActualValue, ProblemInstanceParameter.ActualValue);
    447     }
    448323  }
    449324}
Note: See TracChangeset for help on using the changeset viewer.