Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
09/01/10 11:13:46 (14 years ago)
Author:
svonolfe
Message:

Merged r4351 of the VRP feature branch into trunk (#1039)

Location:
trunk/sources/HeuristicLab.Problems.VehicleRouting
Files:
35 deleted
17 edited
75 copied

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Problems.VehicleRouting

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/AlbaEncoding.cs

    r4204 r4352  
    2626using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2727using System.Collections.Generic;
     28using HeuristicLab.Problems.VehicleRouting.Encodings.General;
    2829
    2930namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    3031  [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.")]
    3132  [StorableClass]
    32   public class AlbaEncoding : Permutation, IVRPEncoding {
     33  public class AlbaEncoding : PermutationEncoding {
    3334    [Storable]
    3435    private int cities;
    3536   
    3637    #region IVRPEncoding Members
    37     public ItemList<Tour> Tours {
    38       get {
    39         ItemList<Tour> result = new ItemList<Tour>();
    40        
    41         Tour tour = new Tour();
    42         for (int i = 0; i < this.array.Length; i++) {
    43           if (this.array[i] >= cities) {
    44             if (tour.Cities.Count > 0) {
    45               result.Add(tour);
     38    public override List<Tour> GetTours(ILookupParameter<DoubleMatrix> distanceMatrix = null, int maxVehicles = int.MaxValue) {
     39      List<Tour> result = new List<Tour>();
    4640
    47               tour = new Tour();
    48             }
    49           } else {
    50             tour.Cities.Add(this.array[i] + 1);
     41      Tour tour = new Tour();
     42      for (int i = 0; i < this.array.Length; i++) {
     43        if (this.array[i] >= cities) {
     44          if (tour.Cities.Count > 0) {
     45            result.Add(tour);
     46
     47            tour = new Tour();
    5148          }
     49        } else {
     50          tour.Cities.Add(this.array[i] + 1);
    5251        }
     52      }
    5353
    54         if (tour.Cities.Count > 0) {
    55           result.Add(tour);
    56         }
     54      if (tour.Cities.Count > 0) {
     55        result.Add(tour);
     56      }
    5757
    58         return result;
    59       }
     58      return result;
    6059    }
    6160
    … …  
    6564
    6665    public int MaxVehicles {
    67       get { return Length - Cities;  }
     66      get { return Length - Cities + 1;  }
    6867    }
    6968
    … …  
    7978
    8079    public AlbaEncoding(Permutation permutation, int cities)
    81       : base(PermutationTypes.RelativeUndirected) {
    82       this.array = new int[permutation.Length];
    83       for (int i = 0; i < array.Length; i++)
    84         this.array[i] = permutation[i];
    85 
     80      : base(permutation) {
    8681      this.cities = cities;
    8782    }
    … …  
    8984    [StorableConstructor]
    9085    private AlbaEncoding(bool serializing)
    91       : base() {
     86      : base(serializing) {
    9287    }
    9388
    94     public static AlbaEncoding ConvertFrom(IVRPEncoding encoding, int vehicles) {
    95       ItemList<Tour> tours = encoding.Tours;
     89    public static AlbaEncoding ConvertFrom(IVRPEncoding encoding, int vehicles, ILookupParameter<DoubleMatrix> distanceMatrix) {
     90      List<Tour> tours = encoding.GetTours(distanceMatrix, vehicles);
    9691
    9792      int cities = 0;
    … …  
    132127    public static AlbaEncoding ConvertFrom(List<int> routeParam) {
    133128      List<int> route = new List<int>(routeParam);
     129      route.RemoveAt(routeParam.Count - 1);
    134130     
    135131      int cities = 0;
    … …  
    156152
    157153    internal static void RemoveUnusedParameters(ParameterCollection parameters) {
    158       parameters.Remove("DistanceMatrix");
    159154      parameters.Remove("UseDistanceMatrix");
    160155      parameters.Remove("Capacity");

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Crossovers/AlbaCrossover.cs

    r4206 r4352  
    5353
    5454        if (!(solution is AlbaEncoding)) {
    55           parents[i] = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value);
     55          parents[i] = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value,
     56            DistanceMatrixParameter);
    5657        } else {
    5758          parents[i] = solution;

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Manipulators/AlbaManipulator.cs

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

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/AlbaMoveMaker.cs

    r4208 r4352  
    2626
    2727namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    28   [Item("PermutationTranslocationMoveMaker", "An operator which makes translocation moves for the Alba representation.")]
     28  [Item("AlbaTranslocationMoveMaker", "An operator which makes translocation moves for the Alba representation.")]
    2929  [StorableClass]
    3030  public abstract class AlbaMoveMaker : AlbaMoveOperator {

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/AlbaMoveOperator.cs

    r4204 r4352  
    4141      IVRPEncoding solution = VRPToursParameter.ActualValue;
    4242      if (!(solution is AlbaEncoding)) {
    43         VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value);
     43        VRPToursParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value,
     44          DistanceMatrixParameter);
    4445      }
    4546

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/Interfaces/IAlbaIntraRouteInversionMoveOperator.cs

    r4206 r4352  
    2626namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    2727  public interface IAlbaIntraRouteInversionMoveOperator : IVRPMoveOperator {
    28     ILookupParameter<IntraRouteInversionMove> IntraRouteInversionMoveParameter { get; }
     28    ILookupParameter<AlbaIntraRouteInversionMove> IntraRouteInversionMoveParameter { get; }
    2929  }
    3030}

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba/Moves/Interfaces/IAlbaLambdaInterchangeMoveOperator.cs

    r4204 r4352  
    2626namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    2727  public interface IAlbaLambdaInterchangeMoveOperator : IVRPMoveOperator {
    28     ILookupParameter<LambdaInterchangeMove> LambdaInterchangeMoveParameter { get; }
     28    ILookupParameter<AlbaLambdaInterchangeMove> LambdaInterchangeMoveParameter { get; }
    2929  }
    3030}

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Creators/PushForwardInsertionCreator.cs

    r4183 r4352  
    225225      int customer = -1;
    226226      int subTourCount = 1;
    227       List<int> route = new List<int>(CitiesParameter.ActualValue.Value + VehiclesParameter.ActualValue.Value - 1);
     227      List<int> route = new List<int>(Cities + VehiclesParameter.ActualValue.Value - 1);
    228228      minimumCost = double.MaxValue;
    229229      indexOfMinimumCost = -1;
    … …  
    271271        customer = -1;
    272272      } while (unroutedList.Count > 0);
    273       while (route.Count < CitiesParameter.ActualValue.Value + VehiclesParameter.ActualValue.Value - 1)
     273      while (route.Count < Cities + VehiclesParameter.ActualValue.Value - 1)
    274274        route.Add(0);
    275275

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Moves/Interfaces/IVRPMove.cs

    r4205 r4352  
    2727namespace HeuristicLab.Problems.VehicleRouting.Encodings.General {
    2828  public interface IVRPMove : IItem {
    29     TourEvaluation GetMoveQuality(IVRPEncoding individual,
     29    TourEvaluation GetMoveQuality(IntValue vehicles,
    3030        DoubleArray dueTimeArray, DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray,
    3131        DoubleValue capacity,DoubleMatrix coordinates,
    … …  
    3434      ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix);
    3535
    36     void MakeMove(IRandom random, IVRPEncoding individual);
     36    IVRPEncoding MakeMove();
    3737  }
    3838}

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Moves/MultiVRPMoveOperator/MultiVRPMoveEvaluator.cs

    r4205 r4352  
    4646
    4747      return move.GetMoveQuality(
    48         VRPToursParameter.ActualValue,
     48        VehiclesParameter.ActualValue,
    4949        DueTimeParameter.ActualValue,
    5050        ServiceTimeParameter.ActualValue,

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Moves/MultiVRPMoveOperator/MultiVRPMoveGenerator.cs

    r4205 r4352  
    118118      Parameters.Add(new LookupParameter<IVRPMove>("VRPMove", "The generated moves."));
    119119
    120       foreach (Type type in ApplicationManager.Manager.GetTypes(typeof(IMultiVRPMoveGenerator))) {
     120      foreach (Type type in ApplicationManager.Manager.GetTypes(typeof(IMultiVRPMoveGenerator)).OrderBy(op => op.Name)) {
    121121        if (!typeof(MultiOperator<IMultiVRPMoveGenerator>).IsAssignableFrom(type))
    122122          Operators.Add((IMultiVRPMoveGenerator)Activator.CreateInstance(type), true);

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Moves/MultiVRPMoveOperator/MultiVRPMoveMaker.cs

    r4205 r4352  
    114114     
    115115      //perform move
    116       move.MakeMove(RandomParameter.ActualValue, VRPToursParameter.ActualValue);
     116      VRPToursParameter.ActualValue = move.MakeMove();
    117117
    118118      quality.Value = moveQuality.Value;

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinCrossover.cs

    r4206 r4352  
    129129
    130130        if (!(solution is PotvinEncoding)) {
    131           parents[i] = PotvinEncoding.ConvertFrom(solution);
     131          parents[i] = PotvinEncoding.ConvertFrom(solution, DistanceMatrixParameter);
    132132        } else {
    133133          parents[i] = solution;

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Manipulators/PotvinManipulator.cs

    r4206 r4352  
    8282      IVRPEncoding solution = VRPToursParameter.ActualValue;
    8383      if (!(solution is PotvinEncoding)) {
    84         VRPToursParameter.ActualValue = PotvinEncoding.ConvertFrom(solution);
     84        VRPToursParameter.ActualValue = PotvinEncoding.ConvertFrom(solution, DistanceMatrixParameter);
    8585      }
    8686     

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/PotvinEncoding.cs

    r4177 r4352  
    2727using System.Drawing;
    2828using System.Collections.Generic;
     29using HeuristicLab.Problems.VehicleRouting.Encodings.General;
    2930
    3031namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    3132  [Item("PotvinEncoding", "Represents a potvin encoding of VRP solutions. It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.")]
    3233  [StorableClass]
    33   public class PotvinEncoding : Item, IVRPEncoding {
    34     public override Image ItemImage {
    35       get { return HeuristicLab.Common.Resources.VS2008ImageLibrary.Class; }
    36     }
    37    
    38     #region IVRPEncoding Members
    39     [Storable]
    40     public ItemList<Tour> Tours { get; set; }
    41 
    42     public int Cities {
    43       get
    44       {
    45         int cities = 0;
    46 
    47         foreach (Tour tour in Tours) {
    48           cities += tour.Cities.Count;
    49         }
    50 
    51         return cities;
    52       }
    53     }
    54     #endregion
    55 
     34  public class PotvinEncoding : TourEncoding {   
    5635    [Storable]
    5736    public List<int> Unrouted { get; set; }
    … …  
    6544    }
    6645
    67     public PotvinEncoding() {
    68       Tours = new ItemList<Tour>();
     46    public PotvinEncoding(): base() {
    6947      Unrouted = new List<int>();
    7048    }
     49
     50    [StorableConstructor]
     51    private PotvinEncoding(bool serializing)
     52      : base() {
     53    }
    7154   
    72     public static PotvinEncoding ConvertFrom(IVRPEncoding encoding) {
     55    public static PotvinEncoding ConvertFrom(IVRPEncoding encoding, ILookupParameter<DoubleMatrix> distanceMatrix) {
    7356      PotvinEncoding solution = new PotvinEncoding();
    7457
    75       solution.Tours.AddRange(
    76         encoding.Tours);
     58      TourEncoding.ConvertFrom(encoding, solution, distanceMatrix);
    7759
    7860      return solution;
    … …  
    8264      PotvinEncoding solution = new PotvinEncoding();
    8365
    84       Tour tour = new Tour();
    85       for (int i = 0; i < route.Count; i++) {
    86         if (route[i] == 0) {
    87           if (tour.Cities.Count > 0) {
    88             solution.Tours.Add(tour);
    89             tour = new Tour();
    90           }
    91         } else {
    92           tour.Cities.Add(route[i]);
    93         }
    94       }
     66      TourEncoding.ConvertFrom(route, solution);
    9567
    9668      return solution;
    … …  
    11587            if (Tours[tour].Feasible(dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
    11688              capacity, coordinates, distanceMatrix, useDistanceMatrix)) {
    117               double newLength = Tours[tour].GetLength(coordinates, distanceMatrix, useDistanceMatrix);
     89                double newLength = Tours[tour].GetLength(coordinates, distanceMatrix, useDistanceMatrix);
    11890
    11991              double detour = newLength - length;

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/VRPCreator.cs

    r4179 r4352  
    3939    }
    4040   
    41     public IValueLookupParameter<IntValue> CitiesParameter {
    42       get { return (IValueLookupParameter<IntValue>)Parameters["Cities"]; }
    43     }
    44 
    4541    [StorableConstructor]
    4642    protected VRPCreator(bool deserializing) : base(deserializing) { }
Note: See TracChangeset for help on using the changeset viewer.