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 


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


31  [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.")]


32  [StorableClass]


33  public sealed class PotvinInsertionBasedCrossover : PotvinCrossover {


34  public IValueParameter<IntValue> Length {


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


36  }


37 


38  [StorableConstructor]


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


40  private PotvinInsertionBasedCrossover(PotvinInsertionBasedCrossover original, Cloner cloner)


41  : base(original, cloner) {


42  }


43  public override IDeepCloneable Clone(Cloner cloner) {


44  return new PotvinInsertionBasedCrossover(this, cloner);


45  }


46  public PotvinInsertionBasedCrossover()


47  : base() {


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


49  }


50 


51  protected static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {


52  int tourIndex = 1;


53 


54  double sum = 0.0;


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


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


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


58  sum += probabilities[i];


59  }


60 


61  for (int i = 0; i < probabilities.Length; i++)


62  probabilities[i] = probabilities[i] / sum;


63 


64  double rand = random.NextDouble();


65  double cumulatedProbabilities = 0.0;


66  int index = 0;


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


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


69  tourIndex = index;


70 


71  cumulatedProbabilities += probabilities[index];


72  index++;


73  }


74 


75  return tourIndex;


76  }


77 


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


79  double xSum = 0;


80  double ySum = 0;


81  double c1X, c1Y, c2X, c2Y;


82 


83  for (int i = 0; i < t1.Cities.Count; i++) {


84  xSum += coordinates[t1.Cities[i], 0];


85  ySum += coordinates[t1.Cities[i], 0];


86  }


87  c1X = xSum / t1.Cities.Count;


88  c1Y = ySum / t1.Cities.Count;


89 


90  for (int i = 0; i < t2.Cities.Count; i++) {


91  xSum += coordinates[t2.Cities[i], 0];


92  ySum += coordinates[t2.Cities[i], 0];


93  }


94  c2X = xSum / t1.Cities.Count;


95  c2Y = ySum / t1.Cities.Count;


96 


97  return Math.Sqrt(


98  Math.Pow(c1X  c2X, 2) +


99  Math.Pow(c1Y  c2Y, 2));


100  }


101 


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


103  double sum = 0;


104 


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


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


107  }


108 


109  return sum / tours.Count;


110  }


111 


112  private int SelectCityBiasedByNeighborDistance(IRandom random, Tour tour, DistanceMatrix distMatrix) {


113  int cityIndex = 1;


114 


115  double sum = 0.0;


116  double[] probabilities = new double[tour.Cities.Count];


117  for (int i = 0; i < tour.Cities.Count; i++) {


118  int next = i + 1;


119  if (next >= tour.Cities.Count)


120  next = 0;


121  else


122  next = tour.Cities[next];


123  double distance = VRPUtilities.GetDistance(


124  tour.Cities[i], next, distMatrix);


125 


126  int prev = i  1;


127  if (prev < 0)


128  prev = 0;


129  else


130  prev = tour.Cities[prev];


131  distance += VRPUtilities.GetDistance(


132  tour.Cities[i], prev, distMatrix);


133 


134  probabilities[i] = distance;


135  sum += probabilities[i];


136  }


137 


138  for (int i = 0; i < probabilities.Length; i++)


139  probabilities[i] = probabilities[i] / sum;


140 


141  double rand = random.NextDouble();


142  double cumulatedProbabilities = 0.0;


143  int index = 0;


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


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


146  cityIndex = index;


147 


148  cumulatedProbabilities += probabilities[index];


149  index++;


150  }


151 


152  return cityIndex;


153  }


154 


155  private bool FindRouteInsertionPlace(


156  Tour tour,


157  DoubleArray dueTimeArray,


158  DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,


159  DistanceMatrix distMatrix, int city, bool allowInfeasible, out int place) {


160  place = 1;


161  bool bestFeasible = false;


162  double minDetour = 0;


163 


164  for (int i = 0; i <= tour.Cities.Count; i++) {


165  double length = tour.GetLength(distMatrix);


166 


167  tour.Cities.Insert(i, city);


168 


169  bool feasible = tour.Feasible(dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,


170  capacity, distMatrix);


171 


172  if ((!allowInfeasible && feasible)  (allowInfeasible && (!bestFeasible  feasible))) {


173  double newLength = tour.GetLength(distMatrix);


174  double detour = newLength  length;


175 


176  if (place <= 0  detour < minDetour 


177  (allowInfeasible && ((!(bestFeasible && !feasible)) && detour < minDetour  (feasible && !bestFeasible)))) {


178  place = i;


179  minDetour = detour;


180 


181  if (feasible)


182  bestFeasible = true;


183  }


184  }


185 


186  tour.Cities.RemoveAt(i);


187  }


188 


189  return place >= 0;


190  }


191 


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


193  PotvinEncoding child = new PotvinEncoding();


194  bool success = true;


195 


196  BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;


197  DoubleMatrix coordinates = CoordinatesParameter.ActualValue;


198  DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);


199  DoubleArray dueTime = DueTimeParameter.ActualValue;


200  DoubleArray readyTime = ReadyTimeParameter.ActualValue;


201  DoubleArray serviceTime = ServiceTimeParameter.ActualValue;


202  DoubleArray demand = DemandParameter.ActualValue;


203  DoubleValue capacity = CapacityParameter.ActualValue;


204 


205  bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;


206 


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


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


209 


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


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


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


213  int index = SelectRandomTourBiasedByLength(random, p1Clone);


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


215  p1Clone.Tours.RemoveAt(index);


216  }


217 


218  foreach (Tour r1 in R1) {


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


220 


221  double r = CalculateMeanCentroidDistance(r1, parent2.Tours, coordinates);


222  foreach (Tour tour in parent2.Tours) {


223  if (CalculateCentroidDistance(r1, tour, coordinates) <= r) {


224  R2.AddRange(tour.Cities);


225  }


226  }


227 


228  Tour childTour = new Tour();


229  childTour.Cities.AddRange(r1.Cities);


230 


231  //DESTROY  remove cities from r1


232  int removed = random.Next(1, r1.Cities.Count + 1);


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


234  childTour.Cities.RemoveAt(SelectCityBiasedByNeighborDistance(random, childTour, distMatrix));


235  }


236 


237  //REPAIR  add cities from R2


238  bool insertSuccess = true;


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


240  int count = 0;


241 


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


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


244  newChild.Tours.Add(childTour);


245 


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


247  int city = R2[index];


248  R2.RemoveAt(index);


249 


250  int place = 1;


251  if(FindRouteInsertionPlace(childTour, dueTime, serviceTime, readyTime,


252  demand, capacity, distMatrix, city, allowInfeasible, out place)) {


253  childTour.Cities.Insert(place, city);


254 


255  if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {


256  childTour.Cities.RemoveAt(place);


257  insertSuccess = false;


258  } else {


259  count++;


260  }


261  }


262  }


263 


264  child.Tours.Add(childTour);


265  if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {


266  /*success = false;


267  break;*/


268  }


269  }


270 


271  if (success) {


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


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


274  child.Tours.Add(childTour);


275  if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {


276  /*success = false;


277  break;*/


278  }


279  }


280  }


281 


282  if (success) {


283  //route unrouted customers


284  for (int i = 1; i <= parent1.Cities; i++) {


285  if (FindRoute(child, i) == null)


286  child.Unrouted.Add(i);


287  }


288 


289  if (!RouteUnrouted(child, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {


290  success = false;


291  }


292  }


293 


294  if (success  allowInfeasible)


295  return child;


296  else {


297  if (random.NextDouble() < 0.5)


298  return parent1.Clone() as PotvinEncoding;


299  else


300  return parent2.Clone() as PotvinEncoding;


301  }


302  }


303  }


304  }

