Changeset 10460


Ignore:
Timestamp:
02/18/14 08:57:37 (6 years ago)
Author:
svonolfe
Message:

added static apply methods to VRP operators (#2152)

Location:
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinLocalSearchManipulator.cs

    r9456 r10460  
    5252    }
    5353
    54     private bool FindBetterInsertionPlace(
    55       PotvinEncoding individual, int tour, int city, int length,
     54    private static bool FindBetterInsertionPlace(
     55      PotvinEncoding individual, IVRPProblemInstance instance, int tour, int city, int length,
    5656      out int insertionTour, out int insertionPlace) {
    5757      bool insertionFound = false;
     
    7070          distance = individual.GetTourLength(individual.Tours[currentTour]);
    7171          individual.Tours[currentTour].Stops.InsertRange(currentCity, toBeDeleted);
    72           if (ProblemInstance.TourFeasible(individual.Tours[currentTour], individual)) {
     72          if (instance.TourFeasible(individual.Tours[currentTour], individual)) {
    7373            double lengthIncrease =
    7474              individual.GetTourLength(individual.Tours[currentTour]) - distance;
     
    9292    }
    9393
    94     protected override void Manipulate(IRandom random, PotvinEncoding individual) {
     94    public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, int maxIterations) {
    9595      //only apply to feasible individuals
    96       if (ProblemInstance.Feasible(individual)) {
     96      if (instance.Feasible(individual)) {
    9797        bool insertionFound;
    9898        int iterations = 0;
     
    107107              while (city <= individual.Tours[tour].Stops.Count - length && !insertionFound) {
    108108                int insertionTour, insertionPlace;
    109                 if (FindBetterInsertionPlace(individual, tour, city, length,
     109                if (FindBetterInsertionPlace(individual, instance, tour, city, length,
    110110                 out insertionTour, out insertionPlace)) {
    111111                  insertionFound = true;
     
    126126          iterations++;
    127127        } while (insertionFound &&
    128           iterations < Iterations.Value.Value);
     128          iterations < maxIterations);
    129129
    130130        IList<Tour> toBeRemoved = new List<Tour>();
     
    139139      }
    140140    }
     141 
     142
     143    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
     144      ApplyManipulation(random, individual, ProblemInstance, Iterations.Value.Value);     
     145    }
    141146  }
    142147}
  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinManipulator.cs

    r10298 r10460  
    5555    protected abstract void Manipulate(IRandom random, PotvinEncoding individual);
    5656
    57     protected int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
     57    protected static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance) {
    5858      int tourIndex = -1;
    5959
     
    6161      double[] probabilities = new double[individual.Tours.Count];
    6262      for (int i = 0; i < individual.Tours.Count; i++) {
    63         probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)ProblemInstance.Cities.Value);
     63        probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)instance.Cities.Value);
    6464        sum += probabilities[i];
    6565      }
     
    8282    }
    8383
    84     protected bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
     84    protected static bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
    8585      return individual.FindInsertionPlace(
    8686        city, routeToAvoid, allowInfeasible, out route, out place);
  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinOneLevelExchangeManipulator.cs

    r9456 r10460  
    2323using HeuristicLab.Core;
    2424using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     25using HeuristicLab.Problems.VehicleRouting.Interfaces;
    2526
    2627namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     
    4142    }
    4243
    43     protected override void Manipulate(IRandom random, PotvinEncoding individual) {
    44       bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
    45 
    46       int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
     44    public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, bool allowInfeasible) {
     45      int selectedIndex = SelectRandomTourBiasedByLength(random, individual, instance);
    4746      if (selectedIndex >= 0) {
    4847        Tour route1 =
     
    6867      }
    6968    }
     69
     70    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
     71      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     72      ApplyManipulation(random, individual, ProblemInstance, allowInfeasible);     
     73    }
    7074  }
    7175}
  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseOneLevelExchangeManipulator.cs

    r9456 r10460  
    2525using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
    2626using HeuristicLab.Problems.VehicleRouting.Variants;
     27using HeuristicLab.Problems.VehicleRouting.Interfaces;
    2728
    2829namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     
    4344    }
    4445
    45     public bool PairwiseMove(PotvinEncoding individual, int city, bool allowInfeasible) {
     46    public static bool PairwiseMove(PotvinEncoding individual, IVRPProblemInstance instance, int city, bool allowInfeasible) {
    4647      bool success;
    4748
    48       IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
     49      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
    4950
    5051      if (pdp != null) {
     
    6465
    6566        int source, target;
    66         if (ProblemInstance.GetDemand(city) >= 0) {
     67        if (instance.GetDemand(city) >= 0) {
    6768          source = city;
    6869          target = dest;
     
    8081          if (tourIdx != routeToAvoid) {
    8182            Tour tour = individual.Tours[tourIdx];
    82             VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);
    83             individual.InsertPair(tour, source, target, ProblemInstance);
    84             VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);
     83            VRPEvaluation eval = instance.EvaluateTour(tour, individual);
     84            individual.InsertPair(tour, source, target, instance);
     85            VRPEvaluation evalNew = instance.EvaluateTour(tour, individual);
    8586
    8687            double delta = evalNew.Quality - eval.Quality;
    8788
    8889            if (delta < bestQuality &&
    89                (ProblemInstance.Feasible(evalNew) || allowInfeasible)) {
     90               (instance.Feasible(evalNew) || allowInfeasible)) {
    9091              bestQuality = delta;
    9192              bestTour = tourIdx;
     
    127128    }
    128129
     130    public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IPickupAndDeliveryProblemInstance pdp, bool allowInfeasible) {
     131      int selectedIndex = SelectRandomTourBiasedByLength(random, individual, pdp);
     132      if (selectedIndex >= 0) {
     133        Tour route1 =
     134          individual.Tours[selectedIndex];
     135
     136        int count = route1.Stops.Count;
     137
     138        if (count > 0) {
     139          int i = random.Next(0, count);
     140          int city = route1.Stops[i];
     141
     142          if (!PairwiseMove(individual, pdp, city, allowInfeasible))
     143            i++;
     144
     145          count = route1.Stops.Count;
     146        }
     147      }
     148    }
     149
     150
    129151    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
    130152      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     153
    131154      IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
    132155
    133156      if (pdp != null) {
    134         int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
    135         if (selectedIndex >= 0) {
    136           Tour route1 =
    137             individual.Tours[selectedIndex];
    138 
    139           int count = route1.Stops.Count;
    140 
    141           if (count > 0) {
    142             int i = random.Next(0, count);
    143             int city = route1.Stops[i];
    144 
    145             if (!PairwiseMove(individual, city, allowInfeasible))
    146               i++;
    147 
    148             count = route1.Stops.Count;
    149           }
    150         }
     157        ApplyManipulation(random, individual, pdp, allowInfeasible);
    151158      }
    152159    }
  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinPairwiseTwoLevelExchangeManipulator.cs

    r9456 r10460  
    2626using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
    2727using HeuristicLab.Problems.VehicleRouting.Variants;
     28using HeuristicLab.Problems.VehicleRouting.Interfaces;
    2829
    2930namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     
    4445    }
    4546
    46     private PotvinEncoding ReplacePair(PotvinEncoding individual, int replaced, int replacing, bool allowInfeasible) {
     47    private static PotvinEncoding ReplacePair(PotvinEncoding individual, IVRPProblemInstance instance, int replaced, int replacing, bool allowInfeasible) {
    4748      individual = individual.Clone() as PotvinEncoding;
    48       IPickupAndDeliveryProblemInstance pdp = ProblemInstance as IPickupAndDeliveryProblemInstance;
     49      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
    4950
    5051      int replacedDest = pdp.GetPickupDeliveryLocation(replaced);
     
    7677
    7778      replacedSourceTour.Stops[replacedSourceTour.Stops.IndexOf(replacedSource)] = replacingSource;
    78       if (!allowInfeasible && !ProblemInstance.TourFeasible(replacedSourceTour, individual))
     79      if (!allowInfeasible && !instance.TourFeasible(replacedSourceTour, individual))
    7980        return null;
    8081
    8182      replacedTargetTour.Stops[replacedTargetTour.Stops.IndexOf(replacedTarget)] = replacingTarget;
    82       if (!allowInfeasible && !ProblemInstance.TourFeasible(replacedTargetTour, individual))
     83      if (!allowInfeasible && !instance.TourFeasible(replacedTargetTour, individual))
    8384        return null;
    8485
     
    9394        if (tourIdx != routeToAvoid) {
    9495          Tour tour = individual.Tours[tourIdx];
    95           VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, individual);
    96           individual.InsertPair(tour, replacedSource, replacedTarget, ProblemInstance);
    97           VRPEvaluation evalNew = ProblemInstance.EvaluateTour(tour, individual);
     96          VRPEvaluation eval = instance.EvaluateTour(tour, individual);
     97          individual.InsertPair(tour, replacedSource, replacedTarget, instance);
     98          VRPEvaluation evalNew = instance.EvaluateTour(tour, individual);
    9899
    99100          double delta = evalNew.Quality - eval.Quality;
    100101
    101102          if (delta < bestQuality &&
    102               (ProblemInstance.Feasible(evalNew) || allowInfeasible)) {
     103              (instance.Feasible(evalNew) || allowInfeasible)) {
    103104            bestQuality = delta;
    104105            bestTour = tourIdx;
     
    127128    }
    128129
     130    public static PotvinEncoding ApplyManipulation(IRandom random, PotvinEncoding individual, IPickupAndDeliveryProblemInstance pdp, bool allowInfeasible) {
     131      PotvinEncoding result = null;
     132     
     133      int selectedIndex = SelectRandomTourBiasedByLength(random, individual, pdp);
     134      if (selectedIndex >= 0) {
     135        bool performed = false;
     136        Tour route1 = individual.Tours[selectedIndex];
     137
     138        if (route1.Stops.Count > 0) {
     139          //randomize customer selection
     140          Permutation perm = new Permutation(PermutationTypes.Absolute, route1.Stops.Count, random);
     141          int customer1Position = 0;
     142
     143          while (customer1Position < route1.Stops.Count) {
     144            performed = false;
     145
     146            int customer1 = route1.Stops[perm[customer1Position]];
     147            int customer2 = -1;
     148
     149            for (int i = 0; i < individual.Tours.Count; i++) {
     150              if (i != selectedIndex) {
     151                Tour tour = individual.Tours[i];
     152                for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) {
     153                  customer2 = tour.Stops[customer2Position];
     154
     155                  if (pdp.GetPickupDeliveryLocation(customer1) != customer2) {
     156                    result = ReplacePair(individual, pdp, customer2, customer1, allowInfeasible);
     157                    if (result != null) {
     158                      individual = result;
     159
     160                      route1 = individual.Tours[selectedIndex];
     161                      performed = true;
     162                      break;
     163                    }
     164                  }
     165                }
     166              }
     167
     168              if (performed) {
     169                break;
     170              }
     171            }
     172
     173            if (!performed)
     174              customer1Position++;
     175            else
     176              break;
     177          }
     178        }
     179      }
     180
     181      return result;
     182    }
     183
    129184    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
    130185      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     
    132187
    133188      if (pdp != null) {
    134         int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
    135         if (selectedIndex >= 0) {
    136           bool performed = false;
    137           Tour route1 = individual.Tours[selectedIndex];
    138 
    139           if (route1.Stops.Count > 0) {
    140             //randomize customer selection
    141             Permutation perm = new Permutation(PermutationTypes.Absolute, route1.Stops.Count, random);
    142             int customer1Position = 0;
    143 
    144             while (customer1Position < route1.Stops.Count) {
    145               performed = false;
    146 
    147               int customer1 = route1.Stops[perm[customer1Position]];
    148               int customer2 = -1;
    149 
    150               for (int i = 0; i < individual.Tours.Count; i++) {
    151                 if (i != selectedIndex) {
    152                   Tour tour = individual.Tours[i];
    153                   for (int customer2Position = 0; customer2Position < tour.Stops.Count; customer2Position++) {
    154                     customer2 = tour.Stops[customer2Position];
    155 
    156                     if (pdp.GetPickupDeliveryLocation(customer1) != customer2) {
    157                       PotvinEncoding result = ReplacePair(individual, customer2, customer1, allowInfeasible);
    158                       if (result != null) {
    159                         VRPToursParameter.ActualValue = result;
    160                         individual = result;
    161 
    162                         route1 = individual.Tours[selectedIndex];
    163                         performed = true;
    164                         break;
    165                       }
    166                     }
    167                   }
    168                 }
    169 
    170                 if (performed) {
    171                   break;
    172                 }
    173               }
    174 
    175               if (!performed)
    176                 customer1Position++;
    177               else
    178                 break;
    179             }
    180           }
    181         }
     189        PotvinEncoding result = ApplyManipulation(random, individual, pdp, allowInfeasible);
     190        if (result != null) {
     191          VRPToursParameter.ActualValue = result;
     192        }       
    182193      }
    183194    }
  • trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinTwoLevelExchangeManipulator.cs

    r9456 r10460  
    2323using HeuristicLab.Core;
    2424using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     25using HeuristicLab.Problems.VehicleRouting.Interfaces;
    2526
    2627namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     
    4142    }
    4243
    43     protected override void Manipulate(IRandom random, PotvinEncoding individual) {
    44       bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
    45 
    46       int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
     44    public static void ApplyManipulation(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance, bool allowInfeasible) {
     45      int selectedIndex = SelectRandomTourBiasedByLength(random, individual, instance);
    4746      if (selectedIndex >= 0) {
    4847        Tour route1 = individual.Tours[selectedIndex];
     
    6362                route1.Stops.RemoveAt(customer1Position);
    6463
    65                 if (ProblemInstance.TourFeasible(tour, individual)) {
     64                if (instance.TourFeasible(tour, individual)) {
    6665                  int routeIdx, place;
    6766                  if (FindInsertionPlace(individual,
     
    9291      }
    9392    }
     93     
     94
     95    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
     96      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     97
     98      ApplyManipulation(random, individual, ProblemInstance, allowInfeasible);
     99    }
    94100  }
    95101}
Note: See TracChangeset for help on using the changeset viewer.