Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
08/04/10 16:11:59 (14 years ago)
Author:
svonolfe
Message:

Refactored VRP, added Potvin encoding (WIP) (#1039)

Location:
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Alba
Files:
2 added
5 edited

Legend:

Unmodified
Added
Removed

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

    r4068 r4150  
    2525using HeuristicLab.Encodings.PermutationEncoding;
    2626using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     27using System.Collections.Generic;
    2728
    2829namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    … …  
    3031  [StorableClass]
    3132  class AlbaEncoding : Permutation, IVRPEncoding {
    32     #region IVRPEncoding Members
    3333    [Storable]
    3434    private int cities;
     35   
     36    #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.Count > 0) {
     45              result.Add(tour);
     46
     47              tour = new Tour();
     48            }
     49          } else {
     50            tour.Add(new IntValue(this.array[i] + 1));
     51          }
     52        }
     53
     54        if (tour.Count > 0) {
     55          result.Add(tour);
     56        }
     57
     58        return result;
     59      }
     60    }
     61
     62    public int Cities {
     63      get { return cities; }
     64    }
     65
     66    public int MaxVehicles {
     67      get { return Length - Cities;  }
     68    }
     69
     70    #endregion
    3571
    3672    public override IDeepCloneable Clone(HeuristicLab.Common.Cloner cloner) {
    … …  
    4379
    4480    public AlbaEncoding(Permutation permutation, int cities)
    45       : base(PermutationTypes.RelativeDirected) {
     81      : base(PermutationTypes.RelativeUndirected) {
    4682      this.array = new int[permutation.Length];
    4783      for (int i = 0; i < array.Length; i++)
    … …  
    5692    }
    5793
    58     public ItemList<Tour> Tours {
    59       get {
    60         ItemList<Tour> result = new ItemList<Tour>();
    61         Tour tour = new Tour();
    62         tour.Add(new IntValue(0));
    63 
    64         for (int i = 0; i < this.array.Length; i++) {
    65           if (this.array[i] >= cities) {
    66             if (tour.Count > 1) {
    67               tour.Add(new IntValue(0));
    68               result.Add(tour);
    69 
    70               tour = new Tour();
    71               tour.Add(new IntValue(0));
    72             }
    73           } else {
    74             tour.Add(new IntValue(this.array[i] + 1));
    75           }
    76         }
    77 
    78         if (tour.Count > 1) {
    79           tour.Add(new IntValue(0));
    80           result.Add(tour);
    81         }
    82 
    83         return result;
    84       }
    85     }
    86 
    87     public int Cities {
    88       get { return cities; }
    89     }
    90 
    91     #endregion
    92 
    93     public static AlbaEncoding ConvertFrom(IVRPEncoding encoding) {
     94    public static AlbaEncoding ConvertFrom(IVRPEncoding encoding, int vehicles) {
    9495      ItemList<Tour> tours = encoding.Tours;
    9596
    … …  
    9899        cities += tour.Count;
    99100      }
    100       int[] array = new int[cities + tours.Count - 2];
     101
     102      int emptyVehicles = vehicles - tours.Count;
     103
     104      int[] array = new int[cities + tours.Count + emptyVehicles - 1];
    101105      int delimiter = cities;
    102106      int arrayIndex = 0;
    … …  
    104108      foreach (Tour tour in tours) {
    105109        foreach (IntValue city in tour) {
    106           array[arrayIndex] = city.Value;
    107 
    108           arrayIndex++;
     110            array[arrayIndex] = city.Value - 1;
     111            arrayIndex++;
    109112        }
    110113
    … …  
    116119      }
    117120
    118       AlbaEncoding solution = new AlbaEncoding(new Permutation(PermutationTypes.RelativeUndirected), cities);
     121      for (int i = 0; i < emptyVehicles - 1; i++) {
     122        array[arrayIndex] = delimiter;
     123        delimiter++;
     124        arrayIndex++;
     125      }
     126           
     127      AlbaEncoding solution = new AlbaEncoding(new Permutation(PermutationTypes.RelativeUndirected, new IntArray(array)), cities);
    119128
    120129      return solution;
    121130    }
    122131
     132    public static AlbaEncoding ConvertFrom(List<int> routeParam) {
     133      List<int> route = new List<int>(routeParam);
     134     
     135      int cities = 0;
     136      for (int i = 0; i < route.Count; i++) {
     137        if (route[i] != 0) {
     138          cities++;
     139        }
     140      }
    123141
     142      int vehicle = cities;
     143      for (int i = 0; i < route.Count; i++) {
     144        if (route[i] == 0) {
     145          route[i] = vehicle;
     146          vehicle++;
     147        } else {
     148          route[i] = route[i] - 1;
     149        }
     150      }
    124151
     152      return new AlbaEncoding(
     153        new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()),
     154        cities);
     155    }
    125156  }
    126157}

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

    r4068 r4150  
    3232  [Item("AlbaPushForwardCreator", "An operator which creates a new alba VRP representation using the push forward insertion heuristic.")]
    3333  [StorableClass]
    34   public sealed class AlbaPushForwardCreator : VRPCreator, IStochasticOperator {
    35     #region IStochasticOperator Members
    36     public ILookupParameter<IRandom> RandomParameter {
    37       get { return (LookupParameter<IRandom>)Parameters["Random"]; }
    38     }
    39     #endregion
    40 
    41     public IValueParameter<DoubleValue> Alpha {
    42       get { return (IValueParameter<DoubleValue>)Parameters["Alpha"]; }
    43     }
    44     public IValueParameter<DoubleValue> AlphaVariance {
    45       get { return (IValueParameter<DoubleValue>)Parameters["AlphaVariance"]; }
    46     }
    47     public IValueParameter<DoubleValue> Beta {
    48       get { return (IValueParameter<DoubleValue>)Parameters["Beta"]; }
    49     }
    50     public IValueParameter<DoubleValue> BetaVariance {
    51       get { return (IValueParameter<DoubleValue>)Parameters["BetaVariance"]; }
    52     }
    53     public IValueParameter<DoubleValue> Gamma {
    54       get { return (IValueParameter<DoubleValue>)Parameters["Gamma"]; }
    55     }
    56     public IValueParameter<DoubleValue> GammaVariance {
    57       get { return (IValueParameter<DoubleValue>)Parameters["GammaVariance"]; }
    58     }
    59 
    60     public AlbaPushForwardCreator()
    61       : base() {
    62       Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
    63       Parameters.Add(new ValueParameter<DoubleValue>("Alpha", "The alpha value.", new DoubleValue(0.7)));
    64       Parameters.Add(new ValueParameter<DoubleValue>("AlphaVariance", "The alpha variance.", new DoubleValue(0.5)));
    65       Parameters.Add(new ValueParameter<DoubleValue>("Beta", "The beta value.", new DoubleValue(0.1)));
    66       Parameters.Add(new ValueParameter<DoubleValue>("BetaVariance", "The beta variance.", new DoubleValue(0.07)));
    67       Parameters.Add(new ValueParameter<DoubleValue>("Gamma", "The gamma value.", new DoubleValue(0.2)));
    68       Parameters.Add(new ValueParameter<DoubleValue>("GammaVariance", "The gamma variance.", new DoubleValue(0.14)));
    69     }
    70 
    71     public override IOperation Apply() {
    72       VRPSolutionParameter.ActualValue = new AlbaEncoding(CreateSolution(), CitiesParameter.ActualValue.Value);
    73 
    74       return base.Apply();
    75     }
    76 
    77     // use the Box-Mueller transform in the polar form to generate a N(0,1) random variable out of two uniformly distributed random variables
    78     private double Gauss(IRandom random) {
    79       double u = 0.0, v = 0.0, s = 0.0;
    80       do {
    81         u = (random.NextDouble() * 2) - 1;
    82         v = (random.NextDouble() * 2) - 1;
    83         s = Math.Sqrt(u * u + v * v);
    84       } while (s < Double.Epsilon || s > 1);
    85       return u * Math.Sqrt((-2.0 * Math.Log(s)) / s);
    86     }
    87 
    88     private double N(double mu, double sigma, IRandom random) {
    89       return mu + (sigma * Gauss(random)); // transform the random variable sampled from N(0,1) to N(mu,sigma)
    90     }
    91 
    92     private double CalculateDistance(int start, int end) {
    93       double distance = 0.0;
    94       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
    95 
    96       distance =
    97           Math.Sqrt(
    98             Math.Pow(coordinates[start, 0] - coordinates[end, 0], 2) +
    99             Math.Pow(coordinates[start, 1] - coordinates[end, 1], 2));
    100 
    101       return distance;
    102     }
    103 
    104     private DoubleMatrix CreateDistanceMatrix() {
    105       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
    106       DoubleMatrix distanceMatrix = new DoubleMatrix(coordinates.Rows, coordinates.Rows);
    107 
    108       for (int i = 0; i < distanceMatrix.Rows; i++) {
    109         for (int j = i; j < distanceMatrix.Columns; j++) {
    110           double distance = CalculateDistance(i, j);
    111 
    112           distanceMatrix[i, j] = distance;
    113           distanceMatrix[j, i] = distance;
    114         }
    115       }
    116 
    117       return distanceMatrix;
    118     }
    119 
    120     private double Distance(int start, int end) {
    121       double distance = 0.0;
    122 
    123       if (UseDistanceMatrixParameter.ActualValue.Value) {
    124         if (DistanceMatrixParameter.ActualValue == null) {
    125           DistanceMatrixParameter.ActualValue = CreateDistanceMatrix();
    126         }
    127 
    128         distance = DistanceMatrixParameter.ActualValue[start, end];
    129       } else {
    130         distance = CalculateDistance(start, end);
    131       }
    132 
    133       return distance;
    134     }
    135 
    136     private double TravelDistance(List<int> route, int begin) {
    137       double distance = 0;
    138       for (int i = begin; i < route.Count - 1 && (i == begin || route[i] != 0); i++) {
    139         distance += Distance(route[i], route[i + 1]);
    140       }
    141       return distance;
    142     }
    143 
    144     private bool SubrouteConstraintsOK(List<int> route, int begin) {
    145       double t = 0.0, o = 0.0;
    146       for (int i = begin + 1; i < route.Count; i++) {
    147         t += Distance(route[i - 1], route[i]);
    148         if (route[i] == 0) return (t < DueTimeParameter.ActualValue[0]); // violation on capacity constraint is handled below
    149         else {
    150           if (t > DueTimeParameter.ActualValue[route[i]]) return false;
    151           t = Math.Max(ReadyTimeParameter.ActualValue[route[i]], t);
    152           t += ServiceTimeParameter.ActualValue[route[i]];
    153           o += DemandParameter.ActualValue[route[i]];
    154           if (o > CapacityParameter.ActualValue.Value) return false; // premature exit on capacity constraint violation
    155         }
    156       }
    157       return true;
    158     }
    159 
    160     private bool SubrouteTardinessOK(List<int> route, int begin) {
    161       double t = 0.0;
    162       for (int i = begin + 1; i < route.Count; i++) {
    163         t += Distance(route[i - 1], route[i]);
    164         if (route[i] == 0) {
    165           if (t < DueTimeParameter.ActualValue[0]) return true;
    166           else return false;
    167         } else {
    168           if (t > DueTimeParameter.ActualValue[route[i]]) return false;
    169           t = Math.Max(ReadyTimeParameter.ActualValue[route[i]], t);
    170           t += ServiceTimeParameter.ActualValue[route[i]];
    171         }
    172       }
    173       return true;
    174     }
    175 
    176     private bool SubrouteLoadOK(List<int> route, int begin) {
    177       double o = 0.0;
    178       for (int i = begin + 1; i < route.Count; i++) {
    179         if (route[i] == 0) return (o < CapacityParameter.ActualValue.Value);
    180         else {
    181           o += DemandParameter.ActualValue[route[i]];
    182         }
    183       }
    184       return (o < CapacityParameter.ActualValue.Value);
    185     }
    186 
    187     private Permutation CreateSolution() {
    188       double alpha, beta, gamma;
    189       alpha = N(Alpha.Value.Value, Math.Sqrt(AlphaVariance.Value.Value), RandomParameter.ActualValue);
    190       beta = N(Beta.Value.Value, Math.Sqrt(BetaVariance.Value.Value), RandomParameter.ActualValue);
    191       gamma = N(Gamma.Value.Value, Math.Sqrt(GammaVariance.Value.Value), RandomParameter.ActualValue);
    192 
    193       double x0 = CoordinatesParameter.ActualValue[0, 0];
    194       double y0 = CoordinatesParameter.ActualValue[0, 1];
    195       double distance = 0;
    196       double cost = 0;
    197       double minimumCost = double.MaxValue;
    198       List<int> unroutedList = new List<int>();
    199       List<double> costList = new List<double>();
    200       int index;
    201       int indexOfMinimumCost = -1;
    202       int indexOfCustomer = -1;
    203 
    204       /*-----------------------------------------------------------------------------
    205        * generate cost list
    206        *-----------------------------------------------------------------------------
    207        */
    208       for (int i = 1; i <= CitiesParameter.ActualValue.Value; i++) {
    209         distance = Distance(i, 0);
    210         if (CoordinatesParameter.ActualValue[i, 0] < x0) distance = -distance;
    211         cost = -alpha * distance + // distance 0 <-> City[i]
    212                  beta * (DueTimeParameter.ActualValue[i]) + // latest arrival time
    213                  gamma * (Math.Asin((CoordinatesParameter.ActualValue[i, 1] - y0) / distance) / 360 * distance); // polar angle
    214 
    215         index = 0;
    216         while (index < costList.Count && costList[index] < cost) index++;
    217         costList.Insert(index, cost);
    218         unroutedList.Insert(index, i);
    219       }
    220 
    221       /*------------------------------------------------------------------------------
    222        * route customers according to cost list
    223        *------------------------------------------------------------------------------
    224        */
    225       int routeIndex = 0;
    226       int currentRoute = 0;
    227       int c;
    228       int customer = -1;
    229       int subTourCount = 1;
    230       List<int> route = new List<int>(CitiesParameter.ActualValue.Value + VehiclesParameter.ActualValue.Value - 1);
    231       minimumCost = double.MaxValue;
    232       indexOfMinimumCost = -1;
    233       route.Add(0);
    234       route.Add(0);
    235       route.Insert(1, unroutedList[0]);
    236       unroutedList.RemoveAt(0);
    237       currentRoute = routeIndex;
    238       routeIndex++;
    239 
    240       do {
    241         for (c = 0; c < unroutedList.Count; c++) {
    242           for (int i = currentRoute + 1; i < route.Count; i++) {
    243             route.Insert(i, (int)unroutedList[c]);
    244             if (route[currentRoute] != 0) { throw new Exception("currentRoute not depot"); }
    245             cost = TravelDistance(route, currentRoute);
    246             if (cost < minimumCost && SubrouteConstraintsOK(route, currentRoute)) {
    247               minimumCost = cost;
    248               indexOfMinimumCost = i;
    249               customer = (int)unroutedList[c];
    250               indexOfCustomer = c;
    251             }
    252             route.RemoveAt(i);
    253           }
    254         }
    255         // insert customer if found
    256         if (indexOfMinimumCost != -1) {
    257           route.Insert(indexOfMinimumCost, customer);
    258           routeIndex++;
    259           unroutedList.RemoveAt(indexOfCustomer);
    260           costList.RemoveAt(indexOfCustomer);
    261         } else { // no feasible customer found
    262           routeIndex++;
    263           route.Insert(routeIndex, 0);
    264           currentRoute = routeIndex;
    265           route.Insert(route.Count - 1, (int)unroutedList[0]);
    266           unroutedList.RemoveAt(0);
    267           routeIndex++;
    268           subTourCount++;
    269         }
    270         // reset minimum   
    271         minimumCost = double.MaxValue;
    272         indexOfMinimumCost = -1;
    273         indexOfCustomer = -1;
    274         customer = -1;
    275       } while (unroutedList.Count > 0);
    276       while (route.Count < CitiesParameter.ActualValue.Value + VehiclesParameter.ActualValue.Value - 1)
    277         route.Add(0);
    278 
    279       int vehicle = CitiesParameter.ActualValue.Value;
    280       for (int i = 0; i < route.Count; i++) {
    281         if (route[i] == 0) {
    282           route[i] = vehicle;
    283           vehicle++;
    284         } else {
    285           route[i] = route[i] - 1;
    286         }
    287       }
    288 
    289       return new Permutation(PermutationTypes.RelativeDirected, route.ToArray());
     34  public sealed class AlbaPushForwardCreator : PushForwardCreator {
     35    protected override IVRPEncoding CreateEncoding(List<int> route) {
     36      return AlbaEncoding.ConvertFrom(route);
    29037    }
    29138  }

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

    r4068 r4150  
    2828  [Item("AlbaPermutationCrossover", "An operator which crosses two alba VRP representations.")]
    2929  [StorableClass]
    30   public sealed class AlbaPermutationCrossover : VRPCrossover {
     30  public sealed class AlbaPermutationCrossover : AlbaCrossover {
    3131    public IValueLookupParameter<IPermutationCrossover> PermutationCrossoverParameter {
    3232      get { return (IValueLookupParameter<IPermutationCrossover>)Parameters["PermutationCrossover"]; }
    … …  
    3838    }
    3939
    40     public override IOperation Apply() {
    41       int cities = 0;
    42 
    43       for (int i = 0; i < ParentsParameter.ActualValue.Length; i++) {
    44         IVRPEncoding solution = ParentsParameter.ActualValue[i];
    45         cities = solution.Cities;
    46         if (!(solution is AlbaEncoding)) {
    47           ParentsParameter.ActualValue[i] = AlbaEncoding.ConvertFrom(solution);
    48         }
    49       }
     40    protected override void Crossover() {
     41      int cities = ParentsParameter.ActualValue[0].Cities;
    5042
    5143      PermutationCrossoverParameter.ActualValue.ParentsParameter.ActualName = ParentsParameter.ActualName;
    52       IAtomicOperation op = this.ExecutionContext.CreateOperation(PermutationCrossoverParameter.ActualValue);
     44      IAtomicOperation op = this.ExecutionContext.CreateOperation(
     45        PermutationCrossoverParameter.ActualValue, this.ExecutionContext.Scope);
    5346      op.Operator.Execute((IExecutionContext)op);
    5447
    55       if (ExecutionContext.Scope.Variables.ContainsKey("Permutation")) {
    56         Permutation permutation = ExecutionContext.Scope.Variables["Permutation"].Value as Permutation;
    57         ExecutionContext.Scope.Variables.Remove("Permutation");
     48      string childName = PermutationCrossoverParameter.ActualValue.ChildParameter.ActualName;
     49      if (ExecutionContext.Scope.Variables.ContainsKey(childName)) {
     50        Permutation permutation = ExecutionContext.Scope.Variables[childName].Value as Permutation;
     51        ExecutionContext.Scope.Variables.Remove(childName);
    5852
    5953        ChildParameter.ActualValue = new AlbaEncoding(permutation, cities);
    6054      } else
    6155        ChildParameter.ActualValue = null;
    62 
    63       return base.Apply();
    6456    }
    6557  }

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

    r4068 r4150  
    2828  [Item("AlbaPermutationManipulator", "An operator which manipulates an alba VRP representation.")]
    2929  [StorableClass]
    30   public sealed class AlbaPermutationManipulator : VRPManipulator {
     30  public sealed class AlbaPermutationManipulator : AlbaManipulator {
    3131    public IValueLookupParameter<IPermutationManipulator> PermutationManipulatorParameter {
    3232      get { return (IValueLookupParameter<IPermutationManipulator>)Parameters["PermutationManipulator"]; }
    … …  
    3939
    4040    public override IOperation Apply() {
    41       IVRPEncoding solution = VRPSolutionParameter.ActualValue;
    42       if (!(solution is AlbaEncoding)) {
    43         VRPSolutionParameter.ActualValue = AlbaEncoding.ConvertFrom(solution);
    44       }
    45 
    4641      OperationCollection next = new OperationCollection(base.Apply());
    4742      IPermutationManipulator op = PermutationManipulatorParameter.ActualValue;

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

    r4068 r4150  
    2323using HeuristicLab.Encodings.PermutationEncoding;
    2424using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     25using HeuristicLab.Data;
     26using HeuristicLab.Parameters;
    2527
    2628namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
    … …  
    2830  [StorableClass]
    2931  public abstract class AlbaMoveOperator : VRPMoveOperator {
     32    public ILookupParameter<IntValue> VehiclesParameter {
     33      get { return (ILookupParameter<IntValue>)Parameters["Vehicles"]; }
     34    }
     35
     36    public AlbaMoveOperator()
     37      : base() {
     38      Parameters.Add(new LookupParameter<IntValue>("Vehicles", "The vehicles count."));
     39    }
     40   
    3041    [Storable]
    3142    protected abstract IPermutationMoveOperator PermutationMoveOperatorParameter { get; set; }
    … …  
    3445      IVRPEncoding solution = VRPSolutionParameter.ActualValue;
    3546      if (!(solution is AlbaEncoding)) {
    36         VRPSolutionParameter.ActualValue = AlbaEncoding.ConvertFrom(solution);
     47        VRPSolutionParameter.ActualValue = AlbaEncoding.ConvertFrom(solution, VehiclesParameter.ActualValue.Value);
    3748      }
    3849
Note: See TracChangeset for help on using the changeset viewer.