Free cookie consent management tool by TermsFeed Policy Generator

Changeset 7822


Ignore:
Timestamp:
05/15/12 12:14:47 (13 years ago)
Author:
svonolfe
Message:

Worked on VRP path relinking (#1331)

Location:
branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinCrossover.cs

    r7259 r7822  
    7474    }
    7575
    76     protected Tour FindRoute(PotvinEncoding solution, int city) {
     76    protected static Tour FindRoute(PotvinEncoding solution, int city) {
    7777      Tour found = null;
    7878

  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs

    r7259 r7822  
    4040      : base() { }
    4141
    42     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;
     42    public static PotvinEncoding Apply(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2, bool allowInfeasible,
     43      DoubleArray dueTimeArray, DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
     44      DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
     45      PotvinEncoding child = parent2.Clone() as PotvinEncoding;
    5146
    52       bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
    53 
    54       PotvinEncoding child = parent2.Clone() as PotvinEncoding;
     47      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, distanceMatrix, useDistanceMatrix);
    5548
    5649      int tourParent1 = random.Next(parent1.Tours.Count);
    … …  
    6760          child.Unrouted.Add(city);
    6861
    69       if (Repair(random, child, replacing, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible) || allowInfeasible)
     62      if (Repair(random, child, replacing, distMatrix, dueTimeArray, readyTimeArray, serviceTimeArray,
     63        demandArray, capacity, allowInfeasible) || allowInfeasible)
    7064        return child;
    7165      else {
    … …  
    7367          return parent1.Clone() as PotvinEncoding;
    7468        else
    75           return parent2.Clone() as PotvinEncoding;   
     69          return parent2.Clone() as PotvinEncoding;
    7670      }
     71    }
     72
     73    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
     74      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
     75      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     76      DoubleArray dueTime = DueTimeParameter.ActualValue;
     77      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
     78      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
     79      DoubleArray demand = DemandParameter.ActualValue;
     80      DoubleValue capacity = CapacityParameter.ActualValue;
     81
     82      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     83
     84      return Apply(random, parent1, parent2,
     85        allowInfeasible, dueTime, serviceTime, readyTime,
     86        demand, capacity, coordinates, DistanceMatrixParameter, useDistanceMatrix);
    7787    }
    7888  }

  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs

    r7259 r7822  
    4141      : base() { }
    4242
    43     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;
     43    public static PotvinEncoding Apply(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2, bool allowInfeasible,
     44      DoubleArray dueTimeArray, DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
     45      DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
     46      PotvinEncoding child = parent1.Clone() as PotvinEncoding;
    5247
    53       bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     48      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, distanceMatrix, useDistanceMatrix);
     49      int cities = coordinates.Rows - 1;
    5450
    55       PotvinEncoding child = parent1.Clone() as PotvinEncoding;
    5651      Tour newTour = new Tour();
    5752
    58       int breakPoint1 = random.Next(1, Cities + 1);
     53      int breakPoint1 = random.Next(1, cities + 1);
    5954      Tour tour1 = FindRoute(child, breakPoint1);
    6055      breakPoint1 = tour1.Cities.IndexOf(breakPoint1);
    … …  
    6358        newTour.Cities.Add(tour1.Cities[i]);
    6459
    65       int breakPoint2 = random.Next(1, Cities + 1);
     60      int breakPoint2 = random.Next(1, cities + 1);
    6661      Tour tour2 = FindRoute(parent2, breakPoint2);
    6762      breakPoint2 = tour2.Cities.IndexOf(breakPoint2);
    … …  
    8176          child.Unrouted.Add(city);
    8277
    83       if (Repair(random, child, newTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible) || allowInfeasible) {
     78      if (Repair(random, child, newTour, distMatrix, dueTimeArray, readyTimeArray, serviceTimeArray,
     79        demandArray, capacity, allowInfeasible) || allowInfeasible) {
    8480        return child;
    8581      } else {
    86          if (random.NextDouble() < 0.5)
     82        if (random.NextDouble() < 0.5)
    8783          return parent1.Clone() as PotvinEncoding;
    8884        else
    89           return parent2.Clone() as PotvinEncoding;   
    90       }
     85          return parent2.Clone() as PotvinEncoding;
     86      }
     87    }
     88
     89    protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
     90      BoolValue useDistanceMatrix = UseDistanceMatrixParameter.ActualValue;
     91      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     92      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, DistanceMatrixParameter, useDistanceMatrix);
     93      DoubleArray dueTime = DueTimeParameter.ActualValue;
     94      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
     95      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
     96      DoubleArray demand = DemandParameter.ActualValue;
     97      DoubleValue capacity = CapacityParameter.ActualValue;
     98
     99      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     100
     101      return Apply(random, parent1, parent2,
     102        allowInfeasible, dueTime, serviceTime, readyTime,
     103        demand, capacity, coordinates, DistanceMatrixParameter, useDistanceMatrix);
    91104    }
    92105  }

  • branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/PathRelinkers/VRPPathRelinker.cs

    r7821 r7822  
    208208
    209209    #region moves
     210    public static PotvinEncoding RouteBasedXOver(PotvinEncoding initiator, PotvinEncoding guide, IRandom random,
     211      IntValue vehicles, DoubleArray dueTimeArray,
     212      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
     213      DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
     214        return PotvinRouteBasedCrossover.Apply(random, initiator, guide, false,
     215          dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
     216          capacity, coordinates, distanceMatrix, useDistanceMatrix);
     217    }
     218
     219    public static PotvinEncoding SequenceBasedXOver(PotvinEncoding initiator, PotvinEncoding guide, IRandom random,
     220     IntValue vehicles, DoubleArray dueTimeArray,
     221     DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
     222     DoubleMatrix coordinates, IParameter distanceMatrix, BoolValue useDistanceMatrix) {
     223      return PotvinSequenceBasedCrossover.Apply(random, initiator, guide, false,
     224        dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
     225        capacity, coordinates, distanceMatrix, useDistanceMatrix);
     226    }
     227
     228
    210229    public static void GuidedRelocateMove(PotvinEncoding initiator, PotvinEncoding guide, IRandom random) {
    211230      List<int> cities = new List<int>();
    … …  
    468487            PotvinEncoding next = current.Clone() as PotvinEncoding;
    469488
    470             int neighborhood = rand.Next(2);
     489            int neighborhood = rand.Next(4);
    471490            switch (neighborhood) {
    472               case 0: GuidedRelocateMove(next, guide, rand);
     491              case 0: next = RouteBasedXOver(next, guide, rand,
     492                vehicles, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
     493                capacity, coordinates, distanceMatrix, useDistanceMatrix);
    473494                break;
    474               case 1: TwoOptMove(next, rand);
     495              case 1: next = SequenceBasedXOver(next, guide, rand,
     496                vehicles, dueTimeArray, serviceTimeArray, readyTimeArray, demandArray,
     497                capacity, coordinates, distanceMatrix, useDistanceMatrix);
     498                  break;
     499              case 2: TwoOptMove(next, rand);
    475500                break;
    476               case 2: TwoOptStarMove(next, rand);
    477                 break;
    478               case 3: OrOptMove(next, rand);
    479                 break;
    480               case 4: ExchangeMove(next, rand);
     501              case 3: GuidedRelocateMove(next, guide, rand);
    481502                break;
    482503            }
Note: See TracChangeset for help on using the changeset viewer.