Free cookie consent management tool by TermsFeed Policy Generator

Changeset 6459


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
Files:
8 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 {

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

    r6449 r6459  
    3535    }
    3636
     37    public IValueParameter<BoolValue> AllowInfeasibleSolutions {
     38      get { return (IValueParameter<BoolValue>)Parameters["AllowInfeasibleSolutions"]; }
     39    }
     40
     41    [StorableHook(HookType.AfterDeserialization)]
     42    private void AfterDeserialization() {
     43      // BackwardsCompatibility3.3
     44      #region Backwards compatible code (remove with 3.4)
     45      if (!Parameters.ContainsKey("AllowInfeasibleSolutions")) {
     46        Parameters.Add(new ValueParameter<BoolValue>("AllowInfeasibleSolutions", "Indicates if infeasible solutions should be allowed.", new BoolValue(false)));
     47      }
     48      #endregion
     49    }
     50
    3751    [StorableConstructor]
    3852    protected PotvinManipulator(bool deserializing) : base(deserializing) { }
    … …  
    4256    public PotvinManipulator() {
    4357      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
     58      Parameters.Add(new ValueParameter<BoolValue>("AllowInfeasibleSolutions", "Indicates if infeasible solutions should be allowed.", new BoolValue(false)));
    4459    }
    4560
    … …  
    7590    protected static bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid,
    7691      DoubleArray dueTime, DoubleArray serviceTime, DoubleArray readyTime, DoubleArray demand,
    77       DoubleValue capacity, DistanceMatrix distMatrix,
     92      DoubleValue capacity, DistanceMatrix distMatrix,  bool allowInfeasible,
    7893      out int route, out int place) {
    7994      return individual.FindInsertionPlace(
    8095        dueTime, serviceTime, readyTime,
    8196        demand, capacity, distMatrix,
    82         city, routeToAvoid, out route, out place);
     97        city, routeToAvoid, allowInfeasible,
     98        out route, out place);
    8399    }
    84100     

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

    r6449 r6459  
    4242    public static void Apply(IRandom random, PotvinEncoding individual,
    4343     DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand,
    44       DoubleValue capacity, DistanceMatrix distMatrix) {
     44      DoubleValue capacity, DistanceMatrix distMatrix, bool allowInfeasible) {
    4545      int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
    4646      Tour route1 =
    … …  
    5353        if (FindInsertionPlace(individual, route1.Cities[i], selectedIndex,
    5454          dueTime, serviceTime, readyTime, demand, capacity,
    55           distMatrix,
     55          distMatrix, allowInfeasible,
    5656          out insertedRoute, out insertedPlace)) {
    5757          individual.Tours[insertedRoute].Cities.Insert(insertedPlace, route1.Cities[i]);
    … …  
    8282      DoubleValue capacity = CapacityParameter.ActualValue;
    8383
    84       Apply(random, individual, dueTime, readyTime, serviceTime, demand, capacity, distMatrix);
     84      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     85
     86      Apply(random, individual, dueTime, readyTime, serviceTime, demand, capacity, distMatrix, allowInfeasible);
    8587    }
    8688  }

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

    r6449 r6459  
    3939    public static void Apply(IRandom random, PotvinEncoding individual,
    4040      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand,
    41       DoubleValue capacity, DistanceMatrix distMatrix) {
     41      DoubleValue capacity, DistanceMatrix distMatrix, bool allowInfeasible) {
    4242      int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
    4343      Tour route1 = individual.Tours[selectedIndex];
    … …  
    6161                  customer2, selectedIndex,
    6262                  dueTime, serviceTime, readyTime, demand, capacity,
    63                   distMatrix,
     63                  distMatrix, allowInfeasible,
    6464                  out routeIdx, out place)) {
    6565                  individual.Tours[routeIdx].Cities.Insert(place, customer2);
    … …  
    100100      DoubleValue capacity = CapacityParameter.ActualValue;
    101101
    102       Apply(random, individual, dueTime, readyTime, serviceTime, demand, capacity, distMatrix);
     102      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
     103
     104      Apply(random, individual, dueTime, readyTime, serviceTime, demand, capacity, distMatrix, allowInfeasible);
    103105    }
    104106  }

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

    r6450 r6459  
    6969      DoubleArray dueTimeArray,
    7070      DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
    71       DistanceMatrix distMatrix,
    72       int city, int routeToAvoid, out int route, out int place) {
     71      DistanceMatrix distMatrix,
     72      int city, int routeToAvoid, bool allowInfeasible,
     73      out int route, out int place) {
    7374      route = -1;
    7475      place = -1;
     76      bool bestFeasible = false;
    7577      double minDetour = 0;
    7678
    … …  
    8587              capacity, distMatrix);
    8688
    87             if (feasible) {
     89            if ((!allowInfeasible && feasible) || (allowInfeasible && (!bestFeasible || feasible))) {
    8890              double newLength = Tours[tour].GetLength(distMatrix);
    8991              double detour = newLength - length;
    9092
    91               if (route <= 0 || detour < minDetour) {
     93              if (route <= 0 || detour < minDetour ||
     94                (allowInfeasible && ((!(bestFeasible && !feasible)) && detour < minDetour || (feasible && !bestFeasible)))) {
    9295                route = tour;
    9396                place = i;
    9497                minDetour = detour;
     98
     99                if (feasible)
     100                  bestFeasible = true;
    95101              }
    96102            }
Note: See TracChangeset for help on using the changeset viewer.