Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
09/29/11 15:51:56 (13 years ago)
Author:
svonolfe
Message:

Added support for multi depot CVRP instances (#1177)

Location:
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs

    r6710 r6851  
    3333  [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.")]
    3434  [StorableClass]
    35   public class AlbaEncoding : PermutationEncoding, IHeterogenousCapacitatedEncoding  {   
     35  public class AlbaEncoding : PermutationEncoding  {   
    3636    #region IVRPEncoding Members
    3737    public override List<Tour> GetTours() {
     38      Repair();
    3839      List<Tour> result = new List<Tour>();
    3940
     
    5556      if (tour.Stops.Count > 0) {
    5657        result.Add(tour);
    57       }   
     58      }
    5859
    5960      return result;
    6061    }
    61     #endregion
    6262
    63     #region IHeterogenousCapacitatedEncoding Members
    64 
    65     public int GetVehicleAssignment(int tour) {
     63    public override int GetVehicleAssignment(int tour) {
    6664      int vehicleAssignment = -1;
    6765      Tour currentTour = GetTours()[tour];
     
    7270      int lastStopIndex = this.IndexOf(lastStop);
    7371
    74       if (lastStopIndex == this.Length - 1)
    75         vehicleAssignment = this.ProblemInstance.Vehicles.Value - 1;
     72      if (lastStopIndex == this.Length - 1) {
     73        int i = this.Length - 1;
     74
     75        while (vehicleAssignment == -1) {
     76          if (this.array[i] >= ProblemInstance.Cities.Value) {
     77            vehicleAssignment = this.array[i] - ProblemInstance.Cities.Value;
     78          }
     79         
     80          i--;
     81        }
     82      }
    7683      else
    7784        vehicleAssignment = this[lastStopIndex + 1] - this.ProblemInstance.Cities.Value;
     
    8087    }
    8188    #endregion
     89
     90    public void Repair() {
     91      int cities = ProblemInstance.Cities.Value;
     92
     93      if (this[this.Length - 1] < cities) {
     94        int index = this.Length - 2;
     95        while (this[index] < cities) {
     96          index--;
     97        }
     98
     99        int vehicle = this[index];
     100        for (int i = index; i < this.Length - 1; i++)
     101          this[i] = this[i + 1];
     102        this[Length - 1] = vehicle;
     103      }
     104    }
    82105
    83106    public AlbaEncoding(Permutation permutation, IVRPProblemInstance instance)
     
    100123    public static AlbaEncoding ConvertFrom(List<int> routeParam, IVRPProblemInstance instance) {
    101124      List<int> route = new List<int>(routeParam);
    102       route.RemoveAt(routeParam.Count - 1);
    103125     
    104126      int cities = instance.Cities.Value;
     
    129151      int emptyVehicles = instance.Vehicles.Value - tours.Count;
    130152
    131       int[] array = new int[cities + tours.Count + emptyVehicles - 1];
     153      int[] array = new int[cities + tours.Count + emptyVehicles];
    132154      int delimiter = 0;
    133155      int arrayIndex = 0;
     
    140162
    141163        if (arrayIndex != array.Length) {
    142           if (encoding is IHeterogenousCapacitatedEncoding) {
    143             array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
    144           } else {
    145             array[arrayIndex] = cities + delimiter;
    146           }
     164          array[arrayIndex] = cities + encoding.GetVehicleAssignment(delimiter);
    147165         
    148166          delimiter++;
     
    151169      }
    152170
    153       for (int i = 0; i < emptyVehicles - 1; i++) {
    154         if (encoding is IHeterogenousCapacitatedEncoding) {
    155           array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
    156         } else {
    157           array[arrayIndex] = cities + delimiter;
    158         }
     171      for (int i = 0; i < emptyVehicles; i++) {
     172        array[arrayIndex] = cities + encoding.GetVehicleAssignment(delimiter);
    159173
    160174        delimiter++;
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/AlbaCreator.cs

    r4752 r6851  
    4747      : base(original, cloner) {
    4848    }
     49
     50    public override IOperation Apply() {
     51      (VRPToursParameter.ActualValue as AlbaEncoding).Repair();
     52
     53      return base.Apply();
     54    }
    4955  }
    5056}
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Crossovers/AlbaCrossover.cs

    r4752 r6851  
    6767
    6868      ChildParameter.ActualValue =
    69         Crossover(RandomParameter.ActualValue, parents[0] as AlbaEncoding, parents[1] as AlbaEncoding); 
     69        Crossover(RandomParameter.ActualValue, parents[0] as AlbaEncoding, parents[1] as AlbaEncoding);
     70      (ChildParameter.ActualValue as AlbaEncoding).Repair();
    7071
    7172      return base.Apply();
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/IAlbaOperator.cs

    r4369 r6851  
    3232
    3333namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    34   public interface IAlbaOperator: 
    35     ISingleDepotOperator, IHeterogenousCapacitatedOperator, ITimeWindowedOperator {   
     34  public interface IAlbaOperator:
     35    ISingleDepotOperator, IHeterogenousCapacitatedOperator, IMultiDepotOperator, ITimeWindowedOperator {   
    3636  }
    3737}
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Manipulators/AlbaManipulator.cs

    r4752 r6851  
    7171
    7272      Manipulate(RandomParameter.ActualValue, VRPToursParameter.ActualValue as AlbaEncoding);
     73      (VRPToursParameter.ActualValue as AlbaEncoding).Repair();
    7374
    7475      return base.Apply();
Note: See TracChangeset for help on using the changeset viewer.