1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022010 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.Data;


25  using HeuristicLab.Encodings.PermutationEncoding;


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


27  using System.Collections.Generic;


28  using HeuristicLab.Problems.VehicleRouting.Encodings.General;


29  using HeuristicLab.Problems.VehicleRouting.Interfaces;


30  using HeuristicLab.Problems.VehicleRouting.Variants;


31 


32  namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {


33  [Item("AlbaEncoding", "Represents an Alba encoding of VRP solutions. It is implemented as described in Alba, E. and Dorronsoro, B. (2004). Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms.")]


34  [StorableClass]


35  public class AlbaEncoding : PermutationEncoding, ISingleDepotEncoding, ITimeWindowedEncoding, IHeterogenousCapacitatedEncoding {


36  #region IVRPEncoding Members


37  public override List<Tour> GetTours() {


38  List<Tour> result = new List<Tour>();


39 


40  int cities = ProblemInstance.Cities.Value;


41 


42  Tour tour = new Tour();


43  for (int i = 0; i < this.array.Length; i++) {


44  if (this.array[i] >= cities) {


45  if (tour.Stops.Count > 0) {


46  result.Add(tour);


47 


48  tour = new Tour();


49  }


50  } else {


51  tour.Stops.Add(this.array[i] + 1);


52  }


53  }


54 


55  if (tour.Stops.Count > 0) {


56  result.Add(tour);


57  }


58 


59  return result;


60  }


61  #endregion


62 


63  #region IHeterogenousCapacitatedEncoding Members


64 


65  public int GetVehicleAssignment(int tour) {


66  int vehicleAssignment = 1;


67  Tour currentTour = GetTours()[tour];


68 


69  int lastStop = currentTour.Stops[


70  currentTour.Stops.Count  1]  1;


71 


72  int lastStopIndex = this.IndexOf(lastStop);


73 


74  if (lastStopIndex == this.Length  1)


75  vehicleAssignment = this.ProblemInstance.Vehicles.Value  1;


76  else


77  vehicleAssignment = this[lastStopIndex + 1]  this.ProblemInstance.Cities.Value;


78 


79  return vehicleAssignment;


80  }


81  #endregion


82 


83  public override IDeepCloneable Clone(HeuristicLab.Common.Cloner cloner) {


84  AlbaEncoding clone = new AlbaEncoding(


85  new Permutation(this.PermutationType, new IntArray(this.array)), ProblemInstance);


86  cloner.RegisterClonedObject(this, clone);


87  clone.readOnly = readOnly;


88  return clone;


89  }


90 


91  public AlbaEncoding(Permutation permutation, IVRPProblemInstance instance)


92  : base(permutation, instance) {


93  }


94 


95  [StorableConstructor]


96  private AlbaEncoding(bool serializing)


97  : base(serializing) {


98  }


99 


100  public static AlbaEncoding ConvertFrom(List<int> routeParam, IVRPProblemInstance instance) {


101  List<int> route = new List<int>(routeParam);


102  route.RemoveAt(routeParam.Count  1);


103 


104  int cities = 0;


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


106  if (route[i] != 0) {


107  cities++;


108  }


109  }


110 


111  int vehicle = cities;


112  for (int i = 0; i < route.Count; i++) {


113  if (route[i] == 0) {


114  route[i] = vehicle;


115  vehicle++;


116  } else {


117  route[i] = route[i]  1;


118  }


119  }


120 


121  return new AlbaEncoding(


122  new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()),


123  instance);


124  }


125 


126  public static AlbaEncoding ConvertFrom(IVRPEncoding encoding, IVRPProblemInstance instance) {


127  List<Tour> tours = encoding.GetTours();


128 


129  int cities = 0;


130  foreach (Tour tour in tours) {


131  cities += tour.Stops.Count;


132  }


133 


134  int emptyVehicles = instance.Vehicles.Value  tours.Count;


135 


136  int[] array = new int[cities + tours.Count + emptyVehicles  1];


137  int delimiter = 0;


138  int arrayIndex = 0;


139 


140  foreach (Tour tour in tours) {


141  foreach (int city in tour.Stops) {


142  array[arrayIndex] = city  1;


143  arrayIndex++;


144  }


145 


146  if (arrayIndex != array.Length) {


147  if (encoding is IHeterogenousCapacitatedEncoding) {


148  array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);


149  } else {


150  array[arrayIndex] = cities + delimiter;


151  }


152 


153  delimiter++;


154  arrayIndex++;


155  }


156  }


157 


158  for (int i = 0; i < emptyVehicles  1; i++) {


159  if (encoding is IHeterogenousCapacitatedEncoding) {


160  array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);


161  } else {


162  array[arrayIndex] = cities + delimiter;


163  }


164 


165  delimiter++;


166  arrayIndex++;


167  }


168 


169  AlbaEncoding solution = new AlbaEncoding(new Permutation(PermutationTypes.RelativeUndirected, new IntArray(array)), instance);


170 


171  return solution;


172  }


173  }


174  }

