Free cookie consent management tool by TermsFeed Policy Generator

Changeset 4376


Ignore:
Timestamp:
09/09/10 16:24:09 (14 years ago)
Author:
svonolfe
Message:

Added Potvin encoding (#1177)

Location:
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4
Files:
12 added
14 edited
2 copied
3 moved

Legend:

Unmodified
Added
Removed

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Analyzer/BestAverageWorstTours/Capacitated/BestAverageWorstCapacitatedVRPToursAnalyzer.cs

    r4374 r4376  
    3939  [Item("BestAverageWorstCapaciatatedVRPToursAnalyzer", "An operator which analyzes the best, average and worst properties of the VRP tours in the scope tree.")]
    4040  [StorableClass]
    41   public sealed class BestAverageWorstCapaciatatedVRPToursAnalyzer : AlgorithmOperator, IAnalyzer, ICapacitatedOperator {
     41  public sealed class BestAverageWorstCapaciatatedVRPToursAnalyzer : AlgorithmOperator, IAnalyzer, IHomogenousCapacitatedOperator {
    4242    #region Parameter properties
    4343    public ILookupParameter<IVRPProblemInstance> ProblemInstanceParameter {

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

    r4365 r4376  
    2828using HeuristicLab.Problems.VehicleRouting.Encodings.General;
    2929using HeuristicLab.Problems.VehicleRouting.Interfaces;
     30using HeuristicLab.Problems.VehicleRouting.Variants;
    3031
    3132namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    3233  [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.")]
    3334  [StorableClass]
    34   public class AlbaEncoding : PermutationEncoding {   
     35  public class AlbaEncoding : PermutationEncoding, ISingleDepotEncoding, ITimeWindowedEncoding, IHeterogenousCapacitatedEncoding {   
    3536    #region IVRPEncoding Members
    3637    public override List<Tour> GetTours() {
    … …  
    6061    #endregion
    6162
     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
    6283    public override IDeepCloneable Clone(HeuristicLab.Common.Cloner cloner) {
    6384      AlbaEncoding clone = new AlbaEncoding(
    64         new Permutation(this.PermutationType, this.array),
    65         (IVRPProblemInstance)cloner.Clone(ProblemInstance));
     85        new Permutation(this.PermutationType, this.array), ProblemInstance);
    6686      cloner.RegisterClonedObject(this, clone);
    6787      clone.readOnly = readOnly;
    … …  
    103123        instance);
    104124    }
     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    }
    105173  }
    106174}

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Crossovers/AlbaCrossover.cs

    r4369 r4376  
    5353        IVRPEncoding solution = ParentsParameter.ActualValue[i];
    5454
    55         /*if (!(solution is AlbaEncoding)) {
    56           parents[i] = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value,
    57             DistanceMatrixParameter);
    58         } else*/ {
     55        if (!(solution is AlbaEncoding)) {
     56          parents[i] = AlbaEncoding.ConvertFrom(solution, ProblemInstance);
     57        } else {
    5958          parents[i] = solution;
    6059        }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Manipulators/AlbaManipulator.cs

    r4369 r4376  
    6262      IVRPEncoding solution = VRPToursParameter.ActualValue;
    6363      if (!(solution is AlbaEncoding)) {
    64         //VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value, DistanceMatrixParameter);
     64        VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, ProblemInstance);
    6565      }
    6666

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Moves/AlbaMoveGenerator.cs

    r4369 r4376  
    4343      IVRPEncoding solution = VRPToursParameter.ActualValue;
    4444      if (!(solution is AlbaEncoding)) {
    45         //VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value,
    46         //  DistanceMatrixParameter);
     45        VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, ProblemInstance);
    4746      }
    4847     

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs

    r4365 r4376  
    7171    protected IVRPProblemInstance ProblemInstance { get; set; }
    7272
    73     public override IDeepCloneable Clone(Cloner cloner) {
    74       TourEncoding clone = (TourEncoding)base.Clone(cloner);
    75 
    76       clone.ProblemInstance = (IVRPProblemInstance)cloner.Clone(ProblemInstance);
    77 
    78       return clone;
    79     }
    80 
    8173    public TourEncoding(IVRPProblemInstance problemInstance) {
    8274      Tours = new ItemList<Tour>();
    … …  
    8779    [StorableConstructor]
    8880    protected TourEncoding(bool serializing)
    89       : base() {
     81      : base(serializing) {
     82    }
     83
     84    public static void ConvertFrom(IVRPEncoding encoding, TourEncoding solution, IVRPProblemInstance problemInstance) {
     85      solution.Tours = new ItemList<Tour>(encoding.GetTours());
     86    }
     87
     88    public static void ConvertFrom(List<int> route, TourEncoding solution) {
     89      solution.Tours = new ItemList<Tour>();
     90
     91      Tour tour = new Tour();
     92      for (int i = 0; i < route.Count; i++) {
     93        if (route[i] == 0) {
     94          if (tour.Stops.Count > 0) {
     95            solution.Tours.Add(tour);
     96            tour = new Tour();
     97          }
     98        } else {
     99          tour.Stops.Add(route[i]);
     100        }
     101      }
    90102    }
    91103  }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

    r4374 r4376  
    179179    <Compile Include="Encodings\General\PermutationEncoding.cs" />
    180180    <Compile Include="Encodings\General\TourEncoding.cs" />
     181    <Compile Include="Encodings\Potvin\Crossovers\PotvinCrossover.cs" />
     182    <Compile Include="Encodings\Potvin\Crossovers\PotvinRouteBasedCrossover.cs" />
     183    <Compile Include="Encodings\Potvin\Crossovers\PotvinSequenceBasedCrossover.cs" />
     184    <Compile Include="Encodings\Potvin\IPotvinOperator.cs" />
     185    <Compile Include="Encodings\Potvin\Manipulators\PotvinLocalSearchManipulator.cs" />
     186    <Compile Include="Encodings\Potvin\Manipulators\PotvinManipulator.cs" />
     187    <Compile Include="Encodings\Potvin\Manipulators\PotvinOneLevelExchangeManipulator.cs" />
     188    <Compile Include="Encodings\Potvin\Manipulators\PotvinTwoLevelExchangeManipulator.cs" />
     189    <Compile Include="Encodings\Potvin\PotvinEncoding.cs" />
    181190    <Compile Include="Encodings\VRPOperator.cs" />
    182191    <Compile Include="Interfaces\IMultiVRPOperator.cs" />
    … …  
    192201    <Compile Include="Variants\Capacitated\Heterogenous\IHeterogenousCapacitatedOperator.cs" />
    193202    <Compile Include="Variants\Capacitated\Heterogenous\IHeterogenousCapacitatedEncoding.cs" />
    194     <Compile Include="Variants\Capacitated\Homogenous\ICapacitatedEncoding.cs" />
    195     <Compile Include="Variants\Capacitated\Homogenous\ICapacitatedOperator.cs" />
    196     <Compile Include="Variants\Capacitated\Homogenous\ICapacitatedProblemInstance.cs" />
     203    <Compile Include="Variants\Capacitated\Homogenous\IHomogenousCapacitatedEncoding.cs" />
     204    <Compile Include="Variants\Capacitated\Homogenous\IHomogenousCapacitatedOperator.cs" />
     205    <Compile Include="Variants\Capacitated\Homogenous\IHomogenousCapacitatedProblemInstance.cs" />
     206    <Compile Include="Variants\Capacitated\ICapacitatedProblemInstance.cs" />
     207    <Compile Include="Variants\Capacitated\ICapacitatedOperator.cs" />
    197208    <Compile Include="Variants\General\IGeneralVRPOperator.cs" />
    198209    <Compile Include="Variants\SingleDepot\ISingleDepotOperator.cs" />

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs

    r4363 r4376  
    4949      base.EvaluateTour(eval, instance, tour);
    5050
    51       ICapacitatedProblemInstance cvrpInstance = instance as ICapacitatedProblemInstance;
     51      IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
    5252
    5353      double delivered = 0.0;
    … …  
    5555
    5656      for (int i = 0; i < tour.Stops.Count; i++) {
    57         delivered += instance.Demand[i];
     57        delivered += instance.Demand[tour.Stops[i]];
    5858      }
    5959
    60       double capacity = (instance as ICapacitatedProblemInstance).Capacity.Value;
     60      double capacity = cvrpInstance.Capacity.Value;
    6161      if (delivered > capacity) {
    6262        overweight = delivered - capacity;

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPProblemInstance.cs

    r4374 r4376  
    3636  [Item("CVRPProblemInstance", "Represents a single depot CVRP instance.")]
    3737  [StorableClass]
    38   public class CVRPProblemInstance: SingleDepotVRPProblemInstance, ICapacitatedProblemInstance {
     38  public class CVRPProblemInstance: SingleDepotVRPProblemInstance, IHomogenousCapacitatedProblemInstance {
    3939    protected IValueParameter<DoubleValue> CapacityParameter {
    4040      get { return (IValueParameter<DoubleValue>)Parameters["Capacity"]; }
    … …  
    5555    protected override IEnumerable<IOperator> GetOperators() {
    5656        return base.GetOperators()
    57           .Where(o => o is ICapacitatedOperator).Cast<IOperator>();
     57          .Where(o => o is IHomogenousCapacitatedOperator).Cast<IOperator>();
    5858    }
    5959

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluator.cs

    r4365 r4376  
    106106
    107107    public bool Feasible(IVRPProblemInstance instance, Tour tour) {
    108       return EvaluateTour(instance, tour).Penalty == 0;
     108      return EvaluateTour(instance, tour).Penalty < double.Epsilon;
    109109    }
    110110

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs

    r4374 r4376  
    150150      } else {
    151151        distance = CalculateDistance(start, end);
    152       }
     152      } 
    153153
    154154      return distance;

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Variants/Capacitated/Heterogenous/IHeterogenousCapacitatedEncoding.cs

    r4363 r4376  
    2626
    2727namespace HeuristicLab.Problems.VehicleRouting.Variants {
    28   public interface IHeterogenousCapacitatedEncoding: ICapacitatedEncoding {
    29     List<int> GetVehicleAssignment();
     28  public interface IHeterogenousCapacitatedEncoding : IHomogenousCapacitatedEncoding {
     29    int GetVehicleAssignment(int tour);
    3030  }
    3131}

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Variants/Capacitated/Heterogenous/IHeterogenousCapacitatedOperator.cs

    r4363 r4376  
    2626
    2727namespace HeuristicLab.Problems.VehicleRouting.Variants {
    28   public interface IHeterogenousCapacitatedOperator: ICapacitatedOperator {
     28  public interface IHeterogenousCapacitatedOperator: IHomogenousCapacitatedOperator {
    2929  }
    3030}

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Variants/Capacitated/Heterogenous/IHeterogenousCapacitatedProblemInstance.cs

    r4363 r4376  
    2424using System.Linq;
    2525using System.Text;
     26using HeuristicLab.Data;
    2627
    2728namespace HeuristicLab.Problems.VehicleRouting.Variants {
    2829  public interface IHeterogenousCapacitatedProblemInstance : ICapacitatedProblemInstance {
     30    DoubleArray Capacity { get; }
    2931  }
    3032}

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Variants/Capacitated/Homogenous/IHomogenousCapacitatedEncoding.cs

    r4374 r4376  
    2727
    2828namespace HeuristicLab.Problems.VehicleRouting.Variants {
    29   public interface ICapacitatedEncoding: IVRPEncoding {
     29  public interface IHomogenousCapacitatedEncoding : IVRPEncoding {
    3030  }
    3131}

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Variants/Capacitated/Homogenous/IHomogenousCapacitatedOperator.cs

    r4374 r4376  
    2727
    2828namespace HeuristicLab.Problems.VehicleRouting.Variants {
    29   public interface ICapacitatedOperator: IVRPOperator {
     29  public interface IHomogenousCapacitatedOperator : ICapacitatedOperator {
    3030  }
    3131}

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Variants/Capacitated/Homogenous/IHomogenousCapacitatedProblemInstance.cs

    r4374 r4376  
    2828
    2929namespace HeuristicLab.Problems.VehicleRouting.Variants {
    30   public interface ICapacitatedProblemInstance: IVRPProblemInstance {
     30  public interface IHomogenousCapacitatedProblemInstance: ICapacitatedProblemInstance {
    3131    DoubleValue Capacity { get; }
    32     DoubleValue OverloadPenalty { get; }
    3332  }
    3433}

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Variants/Capacitated/ICapacitatedOperator.cs

    r4374 r4376  
    2727
    2828namespace HeuristicLab.Problems.VehicleRouting.Variants {
    29   public interface ICapacitatedOperator: IVRPOperator {
     29  public interface ICapacitatedOperator : IVRPOperator {
    3030  }
    3131}

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Variants/Capacitated/ICapacitatedProblemInstance.cs

    r4374 r4376  
    2929namespace HeuristicLab.Problems.VehicleRouting.Variants {
    3030  public interface ICapacitatedProblemInstance: IVRPProblemInstance {
    31     DoubleValue Capacity { get; }
    3231    DoubleValue OverloadPenalty { get; }
    3332  }
Note: See TracChangeset for help on using the changeset viewer.