1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022011 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 


22  using HeuristicLab.Common;


23  using HeuristicLab.Core;


24  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


25  using System.Collections.Generic;


26  using HeuristicLab.Data;


27  using System;


28  using HeuristicLab.Parameters;


29  using HeuristicLab.Problems.VehicleRouting.ProblemInstances;


30 


31  namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {


32  [Item("PotvinInsertionBasedCrossover", "The IBX crossover for VRP representations. It is implemented as described in Berger, J and Solois, M and Begin, R (1998). A hybrid genetic algorithm for the vehicle routing problem with time windows. LNCS 1418. Springer, London 114127.")]


33  [StorableClass]


34  public sealed class PotvinInsertionBasedCrossover : PotvinCrossover {


35  public IValueParameter<IntValue> Length {


36  get { return (IValueParameter<IntValue>)Parameters["Length"]; }


37  }


38 


39  [StorableConstructor]


40  private PotvinInsertionBasedCrossover(bool deserializing) : base(deserializing) { }


41  private PotvinInsertionBasedCrossover(PotvinInsertionBasedCrossover original, Cloner cloner)


42  : base(original, cloner) {


43  }


44  public override IDeepCloneable Clone(Cloner cloner) {


45  return new PotvinInsertionBasedCrossover(this, cloner);


46  }


47  public PotvinInsertionBasedCrossover()


48  : base() {


49  Parameters.Add(new ValueParameter<IntValue>("Length", "The maximum length of the replaced route.", new IntValue(1)));


50  }


51 


52  private static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {


53  int tourIndex = 1;


54 


55  double sum = 0.0;


56  double[] probabilities = new double[individual.Tours.Count];


57  for (int i = 0; i < individual.Tours.Count; i++) {


58  probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)individual.Cities);


59  sum += probabilities[i];


60  }


61 


62  double rand = random.NextDouble() * sum;


63  double cumulatedProbabilities = 0.0;


64  int index = 0;


65  while (tourIndex == 1 && index < probabilities.Length) {


66  if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])


67  tourIndex = index;


68 


69  cumulatedProbabilities += probabilities[index];


70  index++;


71  }


72 


73  return tourIndex;


74  }


75 


76  private double CalculateCentroidDistance(Tour t1, Tour t2, DoubleMatrix coordinates) {


77  double xSum = 0;


78  double ySum = 0;


79  double c1X, c1Y, c2X, c2Y;


80 


81  for (int i = 0; i < t1.Stops.Count; i++) {


82  xSum += coordinates[t1.Stops[i], 0];


83  ySum += coordinates[t1.Stops[i], 1];


84  }


85  c1X = xSum / t1.Stops.Count;


86  c1Y = ySum / t1.Stops.Count;


87 


88  for (int i = 0; i < t2.Stops.Count; i++) {


89  xSum += coordinates[t2.Stops[i], 0];


90  ySum += coordinates[t2.Stops[i], 1];


91  }


92  c2X = xSum / t1.Stops.Count;


93  c2Y = ySum / t1.Stops.Count;


94 


95  return Math.Sqrt(


96  (c1X  c2X) * (c1X  c2X) +


97  (c1Y  c2Y) * (c1Y  c2Y));


98  }


99 


100  private double CalculateMeanCentroidDistance(Tour t1, IList<Tour> tours, DoubleMatrix coordinates) {


101  double sum = 0;


102 


103  for (int i = 0; i < tours.Count; i++) {


104  sum += CalculateCentroidDistance(t1, tours[i], coordinates);


105  }


106 


107  return sum / tours.Count;


108  }


109 


110  private int SelectCityBiasedByNeighborDistance(IRandom random, Tour tour) {


111  int cityIndex = 1;


112 


113  double sum = 0.0;


114  double[] probabilities = new double[tour.Stops.Count];


115  for (int i = 0; i < tour.Stops.Count; i++) {


116  int next;


117  if (i + 1 >= tour.Stops.Count)


118  next = 0;


119  else


120  next = tour.Stops[i + 1];


121  double distance = ProblemInstance.GetDistance(


122  tour.Stops[i], next);


123 


124  int prev;


125  if (i  1 < 0)


126  prev = 0;


127  else


128  prev = tour.Stops[i  1];


129  distance += ProblemInstance.GetDistance(


130  tour.Stops[i], prev);


131 


132  probabilities[i] = distance;


133  sum += probabilities[i];


134  }


135 


136  double rand = random.NextDouble() * sum;


137  double cumulatedProbabilities = 0.0;


138  int index = 0;


139  while (cityIndex == 1 && index < probabilities.Length) {


140  if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])


141  cityIndex = index;


142 


143  cumulatedProbabilities += probabilities[index];


144  index++;


145  }


146 


147  return cityIndex;


148  }


149 


150  private bool FindRouteInsertionPlace(


151  Tour tour,


152  int city, bool allowInfeasible, out int place) {


153  place = 1;


154 


155  if (tour.Stops.Contains(city))


156  return false;


157 


158  if (tour.Stops.Count == 0) {


159  place = 0;


160  return true;


161  }


162 


163  double minDetour = 0;


164  VRPEvaluation eval = ProblemInstance.Evaluate(tour);


165  bool originalFeasible = ProblemInstance.Feasible(eval);


166 


167  for (int i = 0; i <= tour.Stops.Count; i++) {


168  bool feasible;


169  double detour = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);


170  if (feasible  allowInfeasible) {


171  if (place < 0  detour < minDetour) {


172  place = i;


173  minDetour = detour;


174  }


175  }


176  }


177 


178  return place >= 0;


179  }


180 


181  private ICollection<int> GetUnrouted(PotvinEncoding solution, int cities) {


182  HashSet<int> undiscovered = new HashSet<int>();


183  for (int i = 1; i <= cities; i++) {


184  undiscovered.Add(i);


185  }


186 


187  foreach (Tour tour in solution.Tours) {


188  foreach (int city in tour.Stops)


189  undiscovered.Remove(city);


190  }


191 


192  return undiscovered;


193  }


194 


195  protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {


196  PotvinEncoding child = new PotvinEncoding(ProblemInstance);


197 


198  bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;


199 


200  List<Tour> R1 = new List<Tour>();


201  PotvinEncoding p1Clone = parent1.Clone() as PotvinEncoding;


202 


203  int length = Math.Min(Length.Value.Value, parent1.Tours.Count) + 1;


204  int k = random.Next(1, length);


205  for (int i = 0; i < k; i++) {


206  int index = SelectRandomTourBiasedByLength(random, p1Clone);


207  R1.Add(p1Clone.Tours[index]);


208  p1Clone.Tours.RemoveAt(index);


209  }


210 


211  foreach (Tour r1 in R1) {


212  List<int> R2 = new List<int>();


213 


214  double r = CalculateMeanCentroidDistance(r1, parent2.Tours, ProblemInstance.Coordinates);


215  foreach (Tour tour in parent2.Tours) {


216  if (CalculateCentroidDistance(r1, tour, ProblemInstance.Coordinates) <= r) {


217  R2.AddRange(tour.Stops);


218  }


219  }


220 


221  Tour childTour = new Tour();


222  childTour.Stops.AddRange(r1.Stops);


223 


224  //DESTROY  remove cities from r1


225  int removed = random.Next(1, r1.Stops.Count + 1);


226  for (int i = 0; i < removed; i++) {


227  childTour.Stops.RemoveAt(SelectCityBiasedByNeighborDistance(random, childTour));


228  }


229 


230  //REPAIR  add cities from R2


231  int maxCount = random.Next(1, Math.Min(5, R2.Count));


232  int count = 0;


233 


234  while (count < maxCount && R2.Count != 0) {


235  PotvinEncoding newChild = child.Clone() as PotvinEncoding;


236  newChild.Tours.Add(childTour);


237 


238  int index = random.Next(R2.Count);


239  int city = R2[index];


240  R2.RemoveAt(index);


241 


242  int place = 1;


243  bool found = FindRouteInsertionPlace(childTour, city, allowInfeasible, out place);


244  if (found) {


245  childTour.Stops.Insert(place, city);


246 


247  if (!Repair(random, child, childTour, ProblemInstance, allowInfeasible)) {


248  childTour.Stops.RemoveAt(place);


249  } else {


250  count++;


251  }


252  }


253  }


254 


255  child.Tours.Add(childTour);


256  Repair(random, child, childTour, ProblemInstance, allowInfeasible);


257  }


258 


259  for (int i = 0; i < p1Clone.Tours.Count; i++) {


260  Tour childTour = p1Clone.Tours[i].Clone() as Tour;


261  child.Tours.Add(childTour);


262  Repair(random, child, childTour, ProblemInstance, allowInfeasible);


263  }


264 


265  //route unrouted customers


266  child.Unrouted.AddRange(GetUnrouted(child, ProblemInstance.Cities.Value));


267  bool success = RouteUnrouted(child, allowInfeasible);


268 


269  if (success  allowInfeasible)


270  return child;


271  else {


272  if (random.NextDouble() < 0.5)


273  return parent1.Clone() as PotvinEncoding;


274  else


275  return parent2.Clone() as PotvinEncoding;


276  }


277  }


278  }


279  }

