Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
06/20/11 13:36:49 (14 years ago)
Author:
svonolfe
Message:

Improved performance of many VRP operators by optimizing the parameter lookup (#1561)

Location:
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings
Files:
15 edited

Legend:

Unmodified
Added
Removed

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

    r5445 r6449  
    4848
    4949    protected override AlbaEncoding Crossover(IRandom random, AlbaEncoding parent1, AlbaEncoding parent2) {
    50       //note - the inner crossover is called here and the result is converted to an alba representation
     50      //note - the inner crossover is called here and the solution is converted to an alba representation
    5151      //some refactoring should be done here in the future - the crossover operation should be called directly
    5252
    53       InnerCrossoverParameter.ActualValue.ParentsParameter.ActualName = ParentsParameter.ActualName;
    54       IAtomicOperation op = this.ExecutionContext.CreateOperation(
    55         InnerCrossoverParameter.ActualValue, this.ExecutionContext.Scope);
    56       op.Operator.Execute((IExecutionContext)op, CancellationToken);
     53      if (parent1.Length == parent2.Length) {
     54        InnerCrossoverParameter.ActualValue.ParentsParameter.ActualName = ParentsParameter.ActualName;
     55        IAtomicOperation op = this.ExecutionContext.CreateOperation(
     56          InnerCrossoverParameter.ActualValue, this.ExecutionContext.Scope);
     57        op.Operator.Execute((IExecutionContext)op, CancellationToken);
    5758
    58       string childName = InnerCrossoverParameter.ActualValue.ChildParameter.ActualName;
    59       if (ExecutionContext.Scope.Variables.ContainsKey(childName)) {
    60         Permutation permutation = ExecutionContext.Scope.Variables[childName].Value as Permutation;
    61         ExecutionContext.Scope.Variables.Remove(childName);
     59        string childName = InnerCrossoverParameter.ActualValue.ChildParameter.ActualName;
     60        if (ExecutionContext.Scope.Variables.ContainsKey(childName)) {
     61          Permutation permutation = ExecutionContext.Scope.Variables[childName].Value as Permutation;
     62          ExecutionContext.Scope.Variables.Remove(childName);
    6263
    63         return new AlbaEncoding(permutation, Cities);
    64       } else
    65         return null;
     64          return new AlbaEncoding(permutation, Cities);
     65        } else
     66          return null;
     67      } else {
     68        return parent1.Clone() as AlbaEncoding;
     69      }
    6670    }
    6771  }

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

    r5445 r6449  
    9191    }
    9292
    93     private double CalculateDistance(int start, int end) {
     93    private double CalculateDistance(int start, int end, DoubleMatrix coordinates) {
    9494      double distance = 0.0;
    95       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
    9695
    9796      distance =
    … …  
    103102    }
    104103
    105     private DoubleMatrix CreateDistanceMatrix() {
    106       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     104    private DoubleMatrix CreateDistanceMatrix(DoubleMatrix coordinates) {
    107105      DoubleMatrix distanceMatrix = new DoubleMatrix(coordinates.Rows, coordinates.Rows);
    108106
    109107      for (int i = 0; i < distanceMatrix.Rows; i++) {
    110108        for (int j = i; j < distanceMatrix.Columns; j++) {
    111           double distance = CalculateDistance(i, j);
     109          double distance = CalculateDistance(i, j, coordinates);
    112110
    113111          distanceMatrix[i, j] = distance;
    … …  
    119117    }
    120118
    121     private double Distance(int start, int end) {
     119    private double Distance(int start, int end, DoubleMatrix coordinates, bool useDistanceMatrix) {
    122120      double distance = 0.0;
    123121
    124       if (UseDistanceMatrixParameter.ActualValue.Value) {
    125         if (DistanceMatrixParameter.ActualValue == null) {
    126           DistanceMatrixParameter.ActualValue = CreateDistanceMatrix();
    127         }
    128 
    129         distance = DistanceMatrixParameter.ActualValue[start, end];
    130       } else {
    131         distance = CalculateDistance(start, end);
     122      if (useDistanceMatrix) {
     123        distance = coordinates[start, end];
     124      } else { 
     125        distance = CalculateDistance(start, end, coordinates);
    132126      }
    133127
    … …  
    135129    }
    136130
    137     private double TravelDistance(List<int> route, int begin) {
     131    private double TravelDistance(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix) {
    138132      double distance = 0;
    139133      for (int i = begin; i < route.Count - 1 && (i == begin || route[i] != 0); i++) {
    140         distance += Distance(route[i], route[i + 1]);
     134        distance += Distance(route[i], route[i + 1], coordinates, useDistanceMatrix);
    141135      }
    142136      return distance;
    143137    }
    144138
    145     private bool SubrouteConstraintsOK(List<int> route, int begin) {
     139    private bool SubrouteConstraintsOK(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix,
     140      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity) {
    146141      double t = 0.0, o = 0.0;
    147142      for (int i = begin + 1; i < route.Count; i++) {
    148         t += Distance(route[i - 1], route[i]);
     143        t += Distance(route[i - 1], route[i], coordinates, useDistanceMatrix);
    149144        if (route[i] == 0) return (t < DueTimeParameter.ActualValue[0]); // violation on capacity constraint is handled below
    150145        else {
    151           if (t > DueTimeParameter.ActualValue[route[i]]) return false;
    152           t = Math.Max(ReadyTimeParameter.ActualValue[route[i]], t);
    153           t += ServiceTimeParameter.ActualValue[route[i]];
    154           o += DemandParameter.ActualValue[route[i]];
    155           if (o > CapacityParameter.ActualValue.Value) return false; // premature exit on capacity constraint violation
     146          if (t > dueTime[route[i]]) return false;
     147          t = Math.Max(readyTime[route[i]], t);
     148          t += serviceTime[route[i]];
     149          o += demand[route[i]];
     150          if (o > capacity.Value) return false; // premature exit on capacity constraint violation
    156151        }
    157152      }
    … …  
    159154    }
    160155
    161     private bool SubrouteTardinessOK(List<int> route, int begin) {
     156    private bool SubrouteTardinessOK(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix,
     157      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime) {
    162158      double t = 0.0;
    163159      for (int i = begin + 1; i < route.Count; i++) {
    164         t += Distance(route[i - 1], route[i]);
     160        t += Distance(route[i - 1], route[i], coordinates, useDistanceMatrix);
    165161        if (route[i] == 0) {
    166           if (t < DueTimeParameter.ActualValue[0]) return true;
     162          if (t < dueTime[0]) return true;
    167163          else return false;
    168164        } else {
    169           if (t > DueTimeParameter.ActualValue[route[i]]) return false;
    170           t = Math.Max(ReadyTimeParameter.ActualValue[route[i]], t);
    171           t += ServiceTimeParameter.ActualValue[route[i]];
     165          if (t > dueTime[route[i]]) return false;
     166          t = Math.Max(readyTime[route[i]], t);
     167          t += serviceTime[route[i]];
    172168        }
    173169      }
    … …  
    175171    }
    176172
    177     private bool SubrouteLoadOK(List<int> route, int begin) {
     173    private bool SubrouteLoadOK(List<int> route, int begin, DoubleValue capacity, DoubleArray demand) {
    178174      double o = 0.0;
    179175      for (int i = begin + 1; i < route.Count; i++) {
    180         if (route[i] == 0) return (o < CapacityParameter.ActualValue.Value);
     176        if (route[i] == 0) return (o < capacity.Value);
    181177        else {
    182           o += DemandParameter.ActualValue[route[i]];
    183         }
    184       }
    185       return (o < CapacityParameter.ActualValue.Value);
     178          o += demand[route[i]];
     179        }
     180      }
     181      return (o < capacity.Value);
    186182    }
    187183
    188184    protected override List<int> CreateSolution() {
    189       double alpha, beta, gamma;
    190       alpha = N(Alpha.Value.Value, Math.Sqrt(AlphaVariance.Value.Value), RandomParameter.ActualValue);
    191       beta = N(Beta.Value.Value, Math.Sqrt(BetaVariance.Value.Value), RandomParameter.ActualValue);
    192       gamma = N(Gamma.Value.Value, Math.Sqrt(GammaVariance.Value.Value), RandomParameter.ActualValue);
     185      //double alpha, beta, gamma;
     186      double alpha = N(Alpha.Value.Value, Math.Sqrt(AlphaVariance.Value.Value), RandomParameter.ActualValue);
     187      double beta = N(Beta.Value.Value, Math.Sqrt(BetaVariance.Value.Value), RandomParameter.ActualValue);
     188      double gamma = N(Gamma.Value.Value, Math.Sqrt(GammaVariance.Value.Value), RandomParameter.ActualValue);
    193189
    194190      double x0 = CoordinatesParameter.ActualValue[0, 0];
    … …  
    203199      int indexOfCustomer = -1;
    204200
     201      int vehicles = VehiclesParameter.ActualValue.Value;
     202      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     203      DoubleArray dueTime = DueTimeParameter.ActualValue;
     204      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
     205      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
     206      DoubleArray demand = DemandParameter.ActualValue;
     207      DoubleValue capacity = CapacityParameter.ActualValue;
     208
     209      bool useDistanceMatrix = UseDistanceMatrixParameter.ActualValue.Value;
     210      if (useDistanceMatrix) {
     211        if (DistanceMatrixParameter.ActualValue == null) {
     212          DistanceMatrixParameter.ActualValue = CreateDistanceMatrix(coordinates);
     213        }
     214
     215        coordinates = DistanceMatrixParameter.ActualValue;
     216      }
     217
    205218      /*-----------------------------------------------------------------------------
    206219       * generate cost list
    … …  
    208221       */
    209222      for (int i = 1; i <= Cities; i++) {
    210         distance = Distance(i, 0);
    211         if (CoordinatesParameter.ActualValue[i, 0] < x0) distance = -distance;
     223        distance = Distance(i, 0, coordinates, useDistanceMatrix);
     224        if (coordinates[i, 0] < x0) distance = -distance;
    212225        cost = -alpha * distance + // distance 0 <-> City[i]
    213226                 beta * (DueTimeParameter.ActualValue[i]) + // latest arrival time
    214                  gamma * (Math.Asin((CoordinatesParameter.ActualValue[i, 1] - y0) / distance) / 360 * distance); // polar angle
     227                 gamma * (Math.Asin((coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
    215228
    216229        index = 0;
    … …  
    229242      int customer = -1;
    230243      int subTourCount = 1;
    231       List<int> route = new List<int>(Cities + VehiclesParameter.ActualValue.Value - 1);
     244
     245      List<int> route = new List<int>(Cities + vehicles - 1);
    232246      minimumCost = double.MaxValue;
    233247      indexOfMinimumCost = -1;
    … …  
    244258            route.Insert(i, (int)unroutedList[c]);
    245259            if (route[currentRoute] != 0) { throw new Exception("currentRoute not depot"); }
    246             cost = TravelDistance(route, currentRoute);
    247             if (cost < minimumCost && SubrouteConstraintsOK(route, currentRoute)) {
     260            cost = TravelDistance(route, currentRoute, coordinates, useDistanceMatrix);
     261            if (cost < minimumCost && SubrouteConstraintsOK(route, currentRoute, coordinates, useDistanceMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
    248262              minimumCost = cost;
    249263              indexOfMinimumCost = i;
    … …  
    275289        customer = -1;
    276290      } while (unroutedList.Count > 0);
    277       while (route.Count < Cities + VehiclesParameter.ActualValue.Value - 1)
     291      while (route.Count < Cities + vehicles)
    278292        route.Add(0);
    279293

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

    r5445 r6449  
    2626using HeuristicLab.Parameters;
    2727using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     28using HeuristicLab.Data;
    2829
    2930namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    … …  
    4748    protected abstract PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2);
    4849
    49     protected bool FindInsertionPlace(PotvinEncoding individual, int city, out int route, out int place) {
     50    protected static bool FindInsertionPlace(PotvinEncoding individual, int city,
     51      DoubleArray dueTime, DoubleArray serviceTime, DoubleArray readyTime, DoubleArray demand,
     52      DoubleValue capacity, DistanceMatrix distMatrix,
     53      out int route, out int place) {
    5054      return individual.FindInsertionPlace(
    51         DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
    52         DemandParameter.ActualValue, CapacityParameter.ActualValue, CoordinatesParameter.ActualValue,
    53         DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue,
     55        dueTime, serviceTime, readyTime,
     56        demand, capacity, distMatrix,
    5457        city, -1, out route, out place);
    5558    }
    … …  
    6871    }
    6972
    70     protected bool Repair(IRandom random, PotvinEncoding solution, Tour newTour) {
     73    protected static bool RouteUnrouted(PotvinEncoding solution, DistanceMatrix distMatrix,
     74      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity) {
     75      bool success = true;
     76      int index = 0;
     77      while (index < solution.Unrouted.Count && success) {
     78        int unrouted = solution.Unrouted[index];
     79
     80        int route, place;
     81        if (FindInsertionPlace(solution, unrouted,
     82          dueTime, serviceTime, readyTime, demand, capacity,
     83          distMatrix,
     84          out route, out place)) {
     85          solution.Tours[route].Cities.Insert(place, unrouted);
     86        } else {
     87          success = false;
     88        }
     89
     90        index++;
     91      }
     92
     93      for (int i = 0; i < index; i++)
     94        solution.Unrouted.RemoveAt(0);
     95
     96      return success;
     97    }
     98
     99    protected static bool Repair(IRandom random, PotvinEncoding solution, Tour newTour, DistanceMatrix distmatrix,
     100      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity) {
    71101      bool success = true;
    72102
    … …  
    84114      while (newTour.Cities.Contains(0))
    85115        newTour.Cities.Remove(0);
     116
     117      if (!newTour.Feasible(
     118        dueTime, serviceTime, readyTime, demand, capacity, distmatrix))
     119              return false;
    86120
    87121      //remove duplicates from old tours
    … …  
    105139
    106140      //route unrouted vehicles
    107       int index = 0;
    108       while (index < solution.Unrouted.Count && success) {
    109         int unrouted = solution.Unrouted[index];
    110 
    111         int route, place;
    112         if (FindInsertionPlace(solution, unrouted, out route, out place)) {
    113           solution.Tours[route].Cities.Insert(place, unrouted);
    114         } else {
    115           success = false;
    116         }
    117 
    118         index++;
    119       }
    120 
    121       for (int i = 0; i < index; i++)
    122         solution.Unrouted.RemoveAt(0);
     141      success = RouteUnrouted(solution, distmatrix, dueTime, readyTime, serviceTime, demand, capacity);
    123142
    124143      return success;

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

    r5445 r6449  
    2323using HeuristicLab.Core;
    2424using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     25using HeuristicLab.Data;
    2526
    2627namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    … …  
    4041
    4142    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
     43      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
     44      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     45      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
     46      DoubleArray dueTime = DueTimeParameter.ActualValue;
     47      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
     48      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
     49      DoubleArray demand = DemandParameter.ActualValue;
     50      DoubleValue capacity = CapacityParameter.ActualValue;
     51
    4252      PotvinEncoding child = parent2.Clone() as PotvinEncoding;
    4353
    … …  
    5565          child.Unrouted.Add(city);
    5666
    57       if (Repair(random, child, replacing))
     67      if (Repair(random, child, replacing, distMatrix, dueTime, readyTime, serviceTime, demand, capacity))
    5868        return child;
    5969      else {
    … …  
    6171          return parent1.Clone() as PotvinEncoding;
    6272        else
    63           return parent2.Clone() as PotvinEncoding;
     73          return parent2.Clone() as PotvinEncoding;   
    6474      }
    6575    }

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

    r5445 r6449  
    2323using HeuristicLab.Core;
    2424using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     25using HeuristicLab.Data;
    2526
    2627namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    … …  
    4142
    4243    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
     44      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
     45      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     46      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
     47      DoubleArray dueTime = DueTimeParameter.ActualValue;
     48      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
     49      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
     50      DoubleArray demand = DemandParameter.ActualValue;
     51      DoubleValue capacity = CapacityParameter.ActualValue;
     52
    4353      PotvinEncoding child = parent1.Clone() as PotvinEncoding;
    4454      Tour newTour = new Tour();
    … …  
    6979          child.Unrouted.Add(city);
    7080
    71       if (Feasible(newTour) &&
    72           Repair(random, child, newTour)) {
     81      if (Repair(random, child, newTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
    7382        return child;
    7483      } else {
    75         if (random.NextDouble() < 0.5)
     84         if (random.NextDouble() < 0.5)
    7685          return parent1.Clone() as PotvinEncoding;
    7786        else
    78           return parent2.Clone() as PotvinEncoding;
     87          return parent2.Clone() as PotvinEncoding;   
    7988      }
    8089    }

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

    r5445 r6449  
    4949
    5050    private bool FindBetterInsertionPlace(
    51       PotvinEncoding individual, int tour, int city, int length,
     51      PotvinEncoding individual, 
     52      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand,
     53      DoubleValue capacity, DistanceMatrix distMatrix,
     54      int tour, int city, int length,
    5255      out int insertionTour, out int insertionPlace) {
    5356      bool insertionFound = false;
    … …  
    5659
    5760      List<int> toBeDeleted = individual.Tours[tour].Cities.GetRange(city, length);
    58       double distance = GetLength(individual.Tours[tour]);
     61      double distance = individual.Tours[tour].GetLength(distMatrix);
    5962      individual.Tours[tour].Cities.RemoveRange(city, length);
    60       double removalBenefit = distance - GetLength(individual.Tours[tour]);
     63      double removalBenefit = distance - individual.Tours[tour].GetLength(distMatrix);
    6164
    6265      int currentTour = 0;
    … …  
    6467        int currentCity = 0;
    6568        while (currentCity <= individual.Tours[currentTour].Cities.Count && !insertionFound) {
    66           distance = GetLength(individual.Tours[currentTour]);
     69          distance = individual.Tours[currentTour].GetLength(distMatrix);
    6770          individual.Tours[currentTour].Cities.InsertRange(currentCity, toBeDeleted);
    68           if (Feasible(individual.Tours[currentTour])) {
     71          if (individual.Tours[currentTour].Feasible(dueTime, serviceTime, readyTime, demand, capacity, distMatrix)) {
    6972            double lengthIncrease =
    70               GetLength(individual.Tours[currentTour]) - distance;
     73              individual.Tours[currentTour].GetLength(distMatrix) - distance;
    7174            if (removalBenefit > lengthIncrease) {
    7275              insertionTour = currentTour;
    … …  
    8386      }
    8487
    85       individual.Tours[tour].Cities.InsertRange(city, toBeDeleted);
     88      individual.Tours[tour].Cities.InsertRange(city, toBeDeleted); 
    8689
    8790      return insertionFound;
    … …  
    8992
    9093    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
     94      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
     95      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     96      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
     97      DoubleArray dueTime = DueTimeParameter.ActualValue;
     98      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
     99      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
     100      DoubleArray demand = DemandParameter.ActualValue;
     101      DoubleValue capacity = CapacityParameter.ActualValue;
     102     
    91103      //only apply to feasible individuals
    92       if (Feasible(individual)) {
     104      bool feasible = true;
     105
     106      foreach (Tour tour in individual.Tours) {
     107        if (!tour.Feasible(dueTime, serviceTime, readyTime, demand, capacity, distMatrix)) {
     108          feasible = false;
     109          break;
     110        }
     111      }
     112
     113      if (feasible) {
    93114        bool insertionFound;
    94115        int iterations = 0;
    … …  
    103124              while (city <= individual.Tours[tour].Cities.Count - length && !insertionFound) {
    104125                int insertionTour, insertionPlace;
    105                 if (FindBetterInsertionPlace(individual, tour, city, length,
     126                if (FindBetterInsertionPlace(individual, dueTime, readyTime, serviceTime, demand, capacity, distMatrix,
     127                  tour, city, length,
    106128                 out insertionTour, out insertionPlace)) {
    107129                  insertionFound = true;

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

    r5445 r6449  
    2525using HeuristicLab.Parameters;
    2626using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     27using HeuristicLab.Data;
    2728
    2829namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    … …  
    4546    protected abstract void Manipulate(IRandom random, PotvinEncoding individual);
    4647
    47     protected int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
     48    protected static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
    4849      int tourIndex = -1;
    4950
    … …  
    5152      double[] probabilities = new double[individual.Tours.Count];
    5253      for (int i = 0; i < individual.Tours.Count; i++) {
    53         probabilities[i] = 1.0 / ((double)individual.Tours[i].Cities.Count / (double)Cities);
     54        probabilities[i] = 1.0 / ((double)individual.Tours[i].Cities.Count / (double)individual.Cities);
    5455        sum += probabilities[i];
    5556      }
    … …  
    7273    }
    7374
    74     protected bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, out int route, out int place) {
     75    protected static bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid,
     76      DoubleArray dueTime, DoubleArray serviceTime, DoubleArray readyTime, DoubleArray demand,
     77      DoubleValue capacity, DistanceMatrix distMatrix,
     78      out int route, out int place) {
    7579      return individual.FindInsertionPlace(
    76         DueTimeParameter.ActualValue, ServiceTimeParameter.ActualValue, ReadyTimeParameter.ActualValue,
    77         DemandParameter.ActualValue, CapacityParameter.ActualValue, CoordinatesParameter.ActualValue,
    78         DistanceMatrixParameter, UseDistanceMatrixParameter.ActualValue,
     80        dueTime, serviceTime, readyTime,
     81        demand, capacity, distMatrix,
    7982        city, routeToAvoid, out route, out place);
    8083    }
     84     
    8185
    8286    public override IOperation Apply() {

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

    r5445 r6449  
    2424using HeuristicLab.Core;
    2525using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     26using HeuristicLab.Data;
    2627
    2728namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    … …  
    3940    public PotvinOneLevelExchangeMainpulator() : base() { }
    4041
    41     protected override void Manipulate(IRandom random, PotvinEncoding individual) {
     42    public static void Apply(IRandom random, PotvinEncoding individual,
     43     DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand,
     44      DoubleValue capacity, DistanceMatrix distMatrix) {
    4245      int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
    4346      Tour route1 =
    … …  
    4851        int insertedRoute, insertedPlace;
    4952
    50         if (FindInsertionPlace(individual, route1.Cities[i], selectedIndex, out insertedRoute, out insertedPlace)) {
     53        if (FindInsertionPlace(individual, route1.Cities[i], selectedIndex,
     54          dueTime, serviceTime, readyTime, demand, capacity,
     55          distMatrix,
     56          out insertedRoute, out insertedPlace)) {
    5157          individual.Tours[insertedRoute].Cities.Insert(insertedPlace, route1.Cities[i]);
    5258          replaced.Add(route1.Cities[i]);
    … …  
    6571        individual.Tours.Remove(route1);
    6672    }
     73
     74    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
     75      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
     76      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     77      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
     78      DoubleArray dueTime = DueTimeParameter.ActualValue;
     79      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
     80      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
     81      DoubleArray demand = DemandParameter.ActualValue;
     82      DoubleValue capacity = CapacityParameter.ActualValue;
     83
     84      Apply(random, individual, dueTime, readyTime, serviceTime, demand, capacity, distMatrix);
     85    }
    6786  }
    6887}

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

    r5445 r6449  
    2323using HeuristicLab.Core;
    2424using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     25using HeuristicLab.Data;
    2526
    2627namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
    … …  
    3637    public PotvinTwoLevelExchangeManipulator() : base() { }
    3738
    38     protected override void Manipulate(IRandom random, PotvinEncoding individual) {
     39    public static void Apply(IRandom random, PotvinEncoding individual,
     40      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand,
     41      DoubleValue capacity, DistanceMatrix distMatrix) {
    3942      int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
    40       Tour route1 = individual.Tours[selectedIndex]; 
     43      Tour route1 = individual.Tours[selectedIndex];
    4144
    4245      bool performed = false;
    … …  
    5356              //customer1 can be feasibly inserted at the location of customer2
    5457              tour.Cities[customer2Position] = customer1;
    55               if (Feasible(tour)) {
     58              if (tour.Feasible(dueTime, serviceTime, readyTime, demand, capacity, distMatrix)) {
    5659                int routeIdx, place;
    5760                if (FindInsertionPlace(individual,
    58                   customer2, selectedIndex, out routeIdx, out place)) {
    59                     individual.Tours[routeIdx].Cities.Insert(place, customer2);
    60                     route1.Cities.RemoveAt(customer1Position);
     61                  customer2, selectedIndex,
     62                  dueTime, serviceTime, readyTime, demand, capacity,
     63                  distMatrix,
     64                  out routeIdx, out place)) {
     65                  individual.Tours[routeIdx].Cities.Insert(place, customer2);
     66                  route1.Cities.RemoveAt(customer1Position);
    6167
    62                     if (route1.Cities.Count == 0)
     68                  if (route1.Cities.Count == 0)
    6369                    individual.Tours.Remove(route1);
    6470
    … …  
    8389      }
    8490    }
     91
     92    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
     93      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
     94      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     95      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
     96      DoubleArray dueTime = DueTimeParameter.ActualValue;
     97      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
     98      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
     99      DoubleArray demand = DemandParameter.ActualValue;
     100      DoubleValue capacity = CapacityParameter.ActualValue;
     101
     102      Apply(random, individual, dueTime, readyTime, serviceTime, demand, capacity, distMatrix);
     103    }
    85104  }
    86105}

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

    r5445 r6449  
    6969      DoubleArray dueTimeArray,
    7070      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
    71       DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix,
     71      DistanceMatrix distMatrix,
    7272      int city, int routeToAvoid, out int route, out int place) {
    7373      route = -1;
    7474      place = -1;
     75      bool bestFeasible = false;
    7576      double minDetour = 0;
    7677
    … …  
    7879        if (tour != routeToAvoid) {
    7980          for (int i = 0; i <= Tours[tour].Cities.Count; i++) {
    80             double length = Tours[tour].GetLength(coordinates, distanceMatrix, useDistanceMatrix);
     81            double length = Tours[tour].GetLength(distMatrix);
    8182
    8283            Tours[tour].Cities.Insert(i, city);
    8384
    84             if (Tours[tour].Feasible(dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
    85               capacity, coordinates, distanceMatrix, useDistanceMatrix)) {
    86               double newLength = Tours[tour].GetLength(coordinates, distanceMatrix, useDistanceMatrix);
     85            bool feasible = Tours[tour].Feasible(dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
     86              capacity, distMatrix);
    8787
     88            if (!bestFeasible || feasible) {
     89              double newLength = Tours[tour].GetLength(distMatrix);
    8890              double detour = newLength - length;
    8991
    90               if (route <= 0 || detour < minDetour) {
     92              if (route <= 0 || detour < minDetour || (!(bestFeasible && !feasible)) && detour < minDetour || (feasible && !bestFeasible)) {
    9193                route = tour;
    9294                place = i;
    9395                minDetour = detour;
     96
     97                if (feasible)
     98                  bestFeasible = true;
    9499              }
    95100            }

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Prins/Crossovers/PrinsPermutationCrossover.cs

    r5445 r6449  
    4646
    4747    protected override PrinsEncoding Crossover(IRandom random, PrinsEncoding parent1, PrinsEncoding parent2) {
    48       //note - the inner crossover is called here and the result is converted to a prins representation
     48      //note - the inner crossover is called here and the solution is converted to a prins representation
    4949      //some refactoring should be done here in the future - the crossover operation should be called directly
    5050
    51       InnerCrossoverParameter.ActualValue.ParentsParameter.ActualName = ParentsParameter.ActualName;
    52       IAtomicOperation op = this.ExecutionContext.CreateOperation(
    53         InnerCrossoverParameter.ActualValue, this.ExecutionContext.Scope);
    54       op.Operator.Execute((IExecutionContext)op, CancellationToken);
     51      if (parent1.Length == parent2.Length) {
     52        InnerCrossoverParameter.ActualValue.ParentsParameter.ActualName = ParentsParameter.ActualName;
     53        IAtomicOperation op = this.ExecutionContext.CreateOperation(
     54          InnerCrossoverParameter.ActualValue, this.ExecutionContext.Scope);
     55        op.Operator.Execute((IExecutionContext)op, CancellationToken);
    5556
    56       string childName = InnerCrossoverParameter.ActualValue.ChildParameter.ActualName;
    57       if (ExecutionContext.Scope.Variables.ContainsKey(childName)) {
    58         Permutation permutation = ExecutionContext.Scope.Variables[childName].Value as Permutation;
    59         ExecutionContext.Scope.Variables.Remove(childName);
     57        string childName = InnerCrossoverParameter.ActualValue.ChildParameter.ActualName;
     58        if (ExecutionContext.Scope.Variables.ContainsKey(childName)) {
     59          Permutation permutation = ExecutionContext.Scope.Variables[childName].Value as Permutation;
     60          ExecutionContext.Scope.Variables.Remove(childName);
    6061
    61         return new PrinsEncoding(permutation, Cities,
    62           DueTimeParameter.ActualValue,
    63             ServiceTimeParameter.ActualValue,
    64             ReadyTimeParameter.ActualValue,
    65             DemandParameter.ActualValue,
    66             CapacityParameter.ActualValue,
    67             FleetUsageFactor.ActualValue,
    68             TimeFactor.ActualValue,
    69             DistanceFactor.ActualValue,
    70             OverloadPenalty.ActualValue,
    71             TardinessPenalty.ActualValue,
    72             CoordinatesParameter.ActualValue,
    73             UseDistanceMatrixParameter.ActualValue);
    74       } else
    75         return null;
     62          return new PrinsEncoding(permutation, Cities,
     63            DueTimeParameter.ActualValue,
     64              ServiceTimeParameter.ActualValue,
     65              ReadyTimeParameter.ActualValue,
     66              DemandParameter.ActualValue,
     67              CapacityParameter.ActualValue,
     68              FleetUsageFactor.ActualValue,
     69              TimeFactor.ActualValue,
     70              DistanceFactor.ActualValue,
     71              OverloadPenalty.ActualValue,
     72              TardinessPenalty.ActualValue,
     73              CoordinatesParameter.ActualValue,
     74              UseDistanceMatrixParameter.ActualValue);
     75        } else
     76          return null;
     77      } else {
     78        return parent1.Clone() as PrinsEncoding;
     79      }
    7680    }
    7781  }

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Prins/PrinsEncoding.cs

    r5445 r6449  
    7575    public override List<Tour> GetTours(ILookupParameter<DoubleMatrix> distanceMatrix, int maxVehicles = int.MaxValue) {
    7676      List<Tour> result = new List<Tour>();
     77
     78      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, distanceMatrix, useDistanceMatrix);
    7779
    7880      //Split permutation into vector P
    … …  
    106108            overloadPenalty,
    107109            tardinessPenalty,
    108             coordinates,
    109             distanceMatrix,
    110             useDistanceMatrix);
     110            distMatrix);
    111111
    112112          double cost = eval.Quality;

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

    r5445 r6449  
    4848    public bool Feasible(DoubleArray dueTimeArray,
    4949      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
    50       DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
     50      DistanceMatrix distMatrix) {
    5151      TourEvaluation eval = VRPEvaluator.EvaluateTour(this,
    5252        dueTimeArray,
    … …  
    6060        new DoubleValue(1),
    6161        new DoubleValue(1),
    62         coordinates,
    63         distanceMatrix,
    64         useDistanceMatrix);
     62        distMatrix);
    6563
    6664      return eval.Overload < double.Epsilon && eval.Tardiness < double.Epsilon;
    6765    }
    6866
    69     public double GetLength(DoubleMatrix coordinates,
    70       ILookupParameter<DoubleMatrix> distanceMatrix,
    71       BoolValue useDistanceMatrix) {
     67    public double GetLength(DistanceMatrix distMatrix) {
    7268      double length = 0;
    7369
    … …  
    8278        for (int i = 1; i < cities.Count; i++) {
    8379          length += VRPUtilities.GetDistance(
    84             cities[i - 1], cities[i], coordinates, distanceMatrix, useDistanceMatrix);
     80            cities[i - 1], cities[i], distMatrix);
    8581        }
    8682      }

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Zhu/Crossovers/ZhuPermutationCrossover.cs

    r5445 r6449  
    4848
    4949    protected override ZhuEncoding Crossover(IRandom random, ZhuEncoding parent1, ZhuEncoding parent2) {
    50       //note - the inner crossover is called here and the result is converted to a prins representation
     50      //note - the inner crossover is called here and the solution is converted to a prins representation
    5151      //some refactoring should be done here in the future - the crossover operation should be called directly
    5252
    53       InnerCrossoverParameter.ActualValue.ParentsParameter.ActualName = ParentsParameter.ActualName;
    54       IAtomicOperation op = this.ExecutionContext.CreateOperation(
    55         InnerCrossoverParameter.ActualValue, this.ExecutionContext.Scope);
    56       op.Operator.Execute((IExecutionContext)op, CancellationToken);
     53      if (parent1.Length == parent2.Length) {
     54        InnerCrossoverParameter.ActualValue.ParentsParameter.ActualName = ParentsParameter.ActualName;
     55        IAtomicOperation op = this.ExecutionContext.CreateOperation(
     56          InnerCrossoverParameter.ActualValue, this.ExecutionContext.Scope);
     57        op.Operator.Execute((IExecutionContext)op, CancellationToken);
    5758
    58       string childName = InnerCrossoverParameter.ActualValue.ChildParameter.ActualName;
    59       if (ExecutionContext.Scope.Variables.ContainsKey(childName)) {
    60         Permutation permutation = ExecutionContext.Scope.Variables[childName].Value as Permutation;
    61         ExecutionContext.Scope.Variables.Remove(childName);
     59        string childName = InnerCrossoverParameter.ActualValue.ChildParameter.ActualName;
     60        if (ExecutionContext.Scope.Variables.ContainsKey(childName)) {
     61          Permutation permutation = ExecutionContext.Scope.Variables[childName].Value as Permutation;
     62          ExecutionContext.Scope.Variables.Remove(childName);
    6263
    63         return new ZhuEncoding(permutation, Cities,
    64           DueTimeParameter.ActualValue,
    65             ServiceTimeParameter.ActualValue,
    66             ReadyTimeParameter.ActualValue,
    67             DemandParameter.ActualValue,
    68             CapacityParameter.ActualValue,
    69             CoordinatesParameter.ActualValue,
    70             UseDistanceMatrixParameter.ActualValue);
    71       } else
    72         return null;
     64          return new ZhuEncoding(permutation, Cities,
     65            DueTimeParameter.ActualValue,
     66              ServiceTimeParameter.ActualValue,
     67              ReadyTimeParameter.ActualValue,
     68              DemandParameter.ActualValue,
     69              CapacityParameter.ActualValue,
     70              CoordinatesParameter.ActualValue,
     71              UseDistanceMatrixParameter.ActualValue);
     72        } else
     73          return null;
     74      } else {
     75        return parent1.Clone() as ZhuEncoding;
     76      }
    7377    }
    7478  }

  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Zhu/ZhuEncoding.cs

    r5445 r6449  
    6363      Tour newTour = new Tour();
    6464
     65      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, distanceMatrix, useDistanceMatrix);
     66
    6567      for (int i = 0; i < this.Length; i++) {
    6668        int city = this[i] + 1;
    … …  
    7274          demandArray,
    7375          capacity,
    74           coordinates,
    75           distanceMatrix,
    76           useDistanceMatrix)) {
     76          distMatrix)) {
    7777          newTour.Cities.Remove(city);
    7878          if (newTour.Cities.Count > 0)
Note: See TracChangeset for help on using the changeset viewer.