Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
06/21/11 10:27:03 (13 years ago)
Author:
svonolfe
Message:

Added possibility to allow infeasible solutions (#1561)

Location:
trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Potvin/Crossovers
Files:
4 edited

Legend:

Unmodified
Added
Removed

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

    r6455 r6459  
    3636    }
    3737
     38    public IValueParameter<BoolValue> AllowInfeasibleSolutions {
     39      get { return (IValueParameter<BoolValue>)Parameters["AllowInfeasibleSolutions"]; }
     40    }
     41
     42    [StorableHook(HookType.AfterDeserialization)]
     43    private void AfterDeserialization() {
     44      // BackwardsCompatibility3.3
     45      #region Backwards compatible code (remove with 3.4)
     46      if (!Parameters.ContainsKey("AllowInfeasibleSolutions")) {
     47        Parameters.Add(new ValueParameter<BoolValue>("AllowInfeasibleSolutions", "Indicates if infeasible solutions should be allowed.", new BoolValue(false)));
     48      }
     49      #endregion
     50    }
     51
    3852    [StorableConstructor]
    3953    protected PotvinCrossover(bool deserializing) : base(deserializing) { }
    … …  
    4458    public PotvinCrossover() {
    4559      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
     60      Parameters.Add(new ValueParameter<BoolValue>("AllowInfeasibleSolutions", "Indicates if infeasible solutions should be allowed.", new BoolValue(false)));
    4661    }
    4762
    … …  
    5065    protected static bool FindInsertionPlace(PotvinEncoding individual, int city,
    5166      DoubleArray dueTime, DoubleArray serviceTime, DoubleArray readyTime, DoubleArray demand,
    52       DoubleValue capacity, DistanceMatrix distMatrix,
     67      DoubleValue capacity, DistanceMatrix distMatrix, bool allowInfeasible,
    5368      out int route, out int place) {
    5469      return individual.FindInsertionPlace(
    5570        dueTime, serviceTime, readyTime,
    5671        demand, capacity, distMatrix,
    57         city, -1, out route, out place);
     72        city, -1, allowInfeasible,
     73        out route, out place);
    5874    }
    5975
    … …  
    7288
    7389    protected static bool RouteUnrouted(PotvinEncoding solution, DistanceMatrix distMatrix,
    74       DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity) {
     90      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity, bool allowInfeasible) {
    7591      bool success = true;
    7692      int index = 0;
    … …  
    8197        if (FindInsertionPlace(solution, unrouted,
    8298          dueTime, serviceTime, readyTime, demand, capacity,
    83           distMatrix,
     99          distMatrix, allowInfeasible,
    84100          out route, out place)) {
    85101          solution.Tours[route].Cities.Insert(place, unrouted);
    … …  
    98114
    99115    protected static bool Repair(IRandom random, PotvinEncoding solution, Tour newTour, DistanceMatrix distmatrix,
    100       DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity) {
     116      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity,
     117      bool allowInfeasible) {
    101118      bool success = true;
    102119
    … …  
    134151      }
    135152
    136       if (!newTour.Feasible(
     153      if (!allowInfeasible && !newTour.Feasible(
    137154        dueTime, serviceTime, readyTime, demand, capacity, distmatrix))
    138155        return false;
    139156
    140157      //route unrouted vehicles
    141       success = RouteUnrouted(solution, distmatrix, dueTime, readyTime, serviceTime, demand, capacity);
     158      success = RouteUnrouted(solution, distmatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible);
    142159
    143160      return success;

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

    r6455 r6459  
    157157      DoubleArray dueTimeArray,
    158158      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
    159       DistanceMatrix distMatrix,
    160       int city, out int place) {
     159      DistanceMatrix distMatrix, int city, bool allowInfeasible, out int place) {
    161160      place = -1;
    162161      bool bestFeasible = false;
    … …  
    171170          capacity, distMatrix);
    172171
    173         if (!bestFeasible || feasible) {
     172        if ((!allowInfeasible && feasible) || (allowInfeasible && (!bestFeasible || feasible))) {
    174173          double newLength = tour.GetLength(distMatrix);
    175174          double detour = newLength - length;
    176175
    177           if (place <= 0 || (!(bestFeasible && !feasible)) && detour < minDetour || (feasible && !bestFeasible)) {
     176          if (place <= 0 || detour < minDetour ||
     177                (allowInfeasible && ((!(bestFeasible && !feasible)) && detour < minDetour || (feasible && !bestFeasible)))) {
    178178            place = i;
    179179            minDetour = detour;
    … …  
    203203      DoubleValue capacity = CapacityParameter.ActualValue;
    204204
     205      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     206
    205207      List<Tour> R1 = new List<Tour>();
    206208      PotvinEncoding p1Clone = parent1.Clone() as PotvinEncoding;
    … …  
    247249
    248250          int place = -1;
    249           if(FindRouteInsertionPlace(childTour, dueTime, serviceTime, readyTime, 
    250             demand, capacity, distMatrix, city, out place)) {
     251          if(FindRouteInsertionPlace(childTour, dueTime, serviceTime, readyTime,
     252            demand, capacity, distMatrix, city, allowInfeasible, out place)) {
    251253            childTour.Cities.Insert(place, city);
    252254
    253             if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
     255            if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {
    254256              childTour.Cities.RemoveAt(place);
    255257              insertSuccess = false;
    … …  
    261263
    262264        child.Tours.Add(childTour);
    263         if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
     265        if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {
    264266          /*success = false;
    265267          break;*/
    … …  
    271273          Tour childTour = p1Clone.Tours[i].Clone() as Tour;
    272274          child.Tours.Add(childTour);
    273           if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
     275          if (!Repair(random, child, childTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {
    274276            /*success = false;
    275277            break;*/
    … …  
    285287        }
    286288
    287         if (!RouteUnrouted(child, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
     289        if (!RouteUnrouted(child, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {
    288290          success = false;
    289291        }
    290292      }
    291293
    292       if (success)
     294      if (success || allowInfeasible)
    293295        return child;
    294296      else {

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

    r6449 r6459  
    5050      DoubleValue capacity = CapacityParameter.ActualValue;
    5151
     52      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     53
    5254      PotvinEncoding child = parent2.Clone() as PotvinEncoding;
    5355
    … …  
    6567          child.Unrouted.Add(city);
    6668
    67       if (Repair(random, child, replacing, distMatrix, dueTime, readyTime, serviceTime, demand, capacity))
     69      if (Repair(random, child, replacing, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible) || allowInfeasible)
    6870        return child;
    6971      else {

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

    r6449 r6459  
    5151      DoubleValue capacity = CapacityParameter.ActualValue;
    5252
     53      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     54
    5355      PotvinEncoding child = parent1.Clone() as PotvinEncoding;
    5456      Tour newTour = new Tour();
    … …  
    7981          child.Unrouted.Add(city);
    8082
    81       if (Repair(random, child, newTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
     83      if (Repair(random, child, newTour, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible) || allowInfeasible) {
    8284        return child;
    8385      } else {
Note: See TracChangeset for help on using the changeset viewer.