Changeset 6607 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin

Timestamp:

07/28/11 14:16:21 (13 years ago)

Author:

svonolfe

Message:

Merged changes from trunk (#1561) into branch (#1177)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin

Files:

• Creators/IterativeInsertionCreator.cs (modified) (2 diffs)
• Crossovers/PotvinCrossover.cs (modified) (5 diffs)
• Crossovers/PotvinRouteBasedCrossover.cs (modified) (2 diffs)
• Crossovers/PotvinSequenceBasedCrossover.cs (modified) (2 diffs)
• Manipulators/PotvinManipulator.cs (modified) (3 diffs)
• Manipulators/PotvinOneLevelExchangeManipulator.cs (modified) (2 diffs)
• Manipulators/PotvinTwoLevelExchangeManipulator.cs (modified) (2 diffs)
• Moves/CustomerRelocation/PotvinCustomerRelocationMoveMaker.cs (modified) (1 diff)
• PotvinEncoding.cs (modified) (3 diffs)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/IterativeInsertionCreator.cs

@@ -83 +83 @@
     private static PotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, bool adhereTimeWindows) {
       PotvinEncoding result = new PotvinEncoding(instance);
-      IVRPEvaluator eval = instance.EvaluatorParameter.Value;
 
       List<int> customers = new List<int>();
@@ -105 +104 @@
         currentTour.Stops.Insert(stopIdx, customers[index]);
 
-        CVRPEvaluation evaluation = eval.Evaluate(instance, currentTour) as CVRPEvaluation;
+        CVRPEvaluation evaluation = instance.Evaluate(currentTour) as CVRPEvaluation;
         if (result.Tours.Count < instance.Vehicles.Value && 
-          ((adhereTimeWindows && !eval.Feasible(evaluation)) || ((!adhereTimeWindows) && evaluation.Overload > double.Epsilon))) {
+          ((adhereTimeWindows && !instance.Feasible(evaluation)) || ((!adhereTimeWindows) && evaluation.Overload > double.Epsilon))) {
           currentTour.Stops.RemoveAt(stopIdx);
 

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinCrossover.cs

@@ -39 +39 @@
     }
 
+    public IValueParameter<BoolValue> AllowInfeasibleSolutions {
+      get { return (IValueParameter<BoolValue>)Parameters["AllowInfeasibleSolutions"]; }
+    }
+
     [StorableConstructor]
     protected PotvinCrossover(bool deserializing) : base(deserializing) { }
@@ -44 +48 @@
     public PotvinCrossover() {
       Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
+      Parameters.Add(new ValueParameter<BoolValue>("AllowInfeasibleSolutions", "Indicates if infeasible solutions should be allowed.", new BoolValue(false)));
     }
 
@@ -52 +57 @@
     protected abstract PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2);
 
-    protected bool FindInsertionPlace(PotvinEncoding individual, int city, out int route, out int place) {
+    protected static bool FindInsertionPlace(PotvinEncoding individual, int city, bool allowInfeasible,
+        out int route, out int place) {
       return individual.FindInsertionPlace(
-        city, -1, out route, out place);
+        city, -1, allowInfeasible,
+        out route, out place);
     }
 
@@ -70 +77 @@
     }
 
-    protected bool Repair(IRandom random, PotvinEncoding solution, Tour newTour) {
+    protected static bool RouteUnrouted(PotvinEncoding solution, bool allowInfeasible) {
       bool success = true;
-      
+      int index = 0;
+      while (index < solution.Unrouted.Count && success) {
+        int unrouted = solution.Unrouted[index];
+
+        int route, place;
+        if (FindInsertionPlace(solution, unrouted, allowInfeasible,
+          out route, out place)) {
+          solution.Tours[route].Stops.Insert(place, unrouted);
+        } else {
+          success = false;
+        }
+
+        index++;
+      }
+
+      for (int i = 0; i < index; i++)
+        solution.Unrouted.RemoveAt(0);
+
+      return success;
+    }
+
+    protected static bool Repair(IRandom random, PotvinEncoding solution, Tour newTour, IVRPProblemInstance instance, bool allowInfeasible) {
+      bool success = true;
+
       //remove duplicates from new tour      
       for (int i = 0; i < newTour.Stops.Count; i++) {
@@ -106 +136 @@
       }
 
+      if (!allowInfeasible && !instance.Feasible(newTour))
+        return false;
+
       //route unrouted vehicles
-      int index = 0;
-      while (index < solution.Unrouted.Count && success) {
-        int unrouted = solution.Unrouted[index];
-
-        int route, place;
-        if(FindInsertionPlace(solution, unrouted, out route, out place)) {
-          solution.Tours[route].Stops.Insert(place, unrouted);
-        } else {
-          success = false;
-        }
-
-        index++;
-      }
-
-      for (int i = 0; i < index; i++)
-        solution.Unrouted.RemoveAt(0);
+      success = RouteUnrouted(solution, allowInfeasible);
 
       return success;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinRouteBasedCrossover.cs

@@ -46 +46 @@
      
     protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+
       PotvinEncoding child = parent2.Clone() as PotvinEncoding;
 
@@ -61 +63 @@
           child.Unrouted.Add(city);
 
-      if (Repair(random, child, replacing))
+      if (Repair(random, child, replacing, ProblemInstance, allowInfeasible) || allowInfeasible)
         return child;
       else {

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinSequenceBasedCrossover.cs

@@ -46 +46 @@
         
     protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+      
       PotvinEncoding child = parent1.Clone() as PotvinEncoding;
       Tour newTour = new Tour();
@@ -76 +78 @@
           child.Unrouted.Add(city);
 
-      if (ProblemInstance.Feasible(newTour) &&
-          Repair(random, child, newTour)) {
+      if (Repair(random, child, newTour, ProblemInstance, allowInfeasible) || allowInfeasible) {
         return child;
       } else {

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinManipulator.cs

@@ -38 +38 @@
     }
 
+    public IValueParameter<BoolValue> AllowInfeasibleSolutions {
+      get { return (IValueParameter<BoolValue>)Parameters["AllowInfeasibleSolutions"]; }
+    }
+
     [StorableConstructor]
     protected PotvinManipulator(bool deserializing) : base(deserializing) { }
@@ -43 +47 @@
     public PotvinManipulator() {
       Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
+      Parameters.Add(new ValueParameter<BoolValue>("AllowInfeasibleSolutions", "Indicates if infeasible solutions should be allowed.", new BoolValue(false)));
     }
 
@@ -78 +83 @@
     }
 
-    protected bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, out int route, out int place) {
+    protected bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
       return individual.FindInsertionPlace(
-        city, routeToAvoid, out route, out place);
+        city, routeToAvoid, allowInfeasible, out route, out place);
     }
     

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinOneLevelExchangeManipulator.cs

@@ -46 +46 @@
     
     protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+      
       int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
       Tour route1 =
@@ -54 +56 @@
         int insertedRoute, insertedPlace;
 
-        if (FindInsertionPlace(individual, route1.Stops[i], selectedIndex, out insertedRoute, out insertedPlace)) {
+        if (FindInsertionPlace(individual, route1.Stops[i], selectedIndex, allowInfeasible, out insertedRoute, out insertedPlace)) {
           individual.Tours[insertedRoute].Stops.Insert(insertedPlace, route1.Stops[i]);
           replaced.Add(route1.Stops[i]);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinTwoLevelExchangeManipulator.cs

@@ -46 +46 @@
 
     protected override void Manipulate(IRandom random, PotvinEncoding individual) {
+      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
+      
       int selectedIndex = SelectRandomTourBiasedByLength(random, individual);
       Tour route1 = individual.Tours[selectedIndex];
@@ -65 +67 @@
                 int routeIdx, place;
                 if (FindInsertionPlace(individual,
-                  customer2, selectedIndex, out routeIdx, out place)) {
+                  customer2, selectedIndex, allowInfeasible, out routeIdx, out place)) {
                   individual.Tours[routeIdx].Stops.Insert(place, customer2);
                   route1.Stops.RemoveAt(customer1Position);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/CustomerRelocation/PotvinCustomerRelocationMoveMaker.cs

@@ -106 +106 @@
 
       //reset move quality
-      VRPEvaluation eval = ProblemInstance.EvaluatorParameter.Value.Evaluate(ProblemInstance, newSolution);
+      VRPEvaluation eval = ProblemInstance.Evaluate(newSolution);
       MoveQualityParameter.ActualValue.Value = eval.Quality;
 
       //update penalty factor
       double sigma = SigmaParameter.Value.Value;
-      if (ProblemInstance.EvaluatorParameter.Value.Feasible(eval)) {
+      if (ProblemInstance.Feasible(eval)) {
         newSolution.PenaltyFactor /= (1 + sigma);
         if (newSolution.PenaltyFactor < MinPenaltyFactorParameter.Value.Value)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs

@@ -80 +80 @@
 
     public double GetTourLength(Tour tour) {
-      double length = 0;
-
-      if (tour.Stops.Count > 0) {
-        List<int> cities = new List<int>();
-        cities.Add(0);
-        foreach (int city in tour.Stops) {
-          cities.Add(city);
-        }
-        cities.Add(0);
-
-        for (int i = 1; i < cities.Count; i++) {
-          length += ProblemInstance.GetDistance(cities[i - 1], cities[i]);
-        }
-      }  
-
-      return length;
+      return tour.GetTourLength(ProblemInstance);
     }
 
@@ -105 +90 @@
         tour.Stops.Insert(i, city);
 
-        VRPEvaluation eval = ProblemInstance.EvaluatorParameter.Value.Evaluate(ProblemInstance, tour);
+        VRPEvaluation eval = ProblemInstance.Evaluate(tour);
         double quality = eval.Quality + eval.Penalty * (PenaltyFactor - 1.0);
 
@@ -122 +107 @@
     }
 
-    public bool FindInsertionPlace(int city, int routeToAvoid, out int route, out int place) {
+    public bool FindInsertionPlace(int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
       route = -1;
       place = -1;
-      double minDetour = 0;
+      bool bestFeasible = false;
+      double minDetour = double.MaxValue;
 
       for (int tour = 0; tour < Tours.Count; tour++) {
         if (tour != routeToAvoid) {
-          double length = GetTourLength(Tours[tour]);
+          for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
+            double length = GetTourLength(Tours[tour]);
 
-          for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
             Tours[tour].Stops.Insert(i, city);
 
-            VRPEvaluation eval = ProblemInstance.EvaluatorParameter.Value.Evaluate(
-              ProblemInstance, Tours[tour]);
-            if (ProblemInstance.EvaluatorParameter.Value.Feasible(eval)) {
-              double newLength = eval.Distance;
+            bool feasible = ProblemInstance.Feasible(Tours[tour]);
 
+            if (feasible || allowInfeasible && !bestFeasible) {
+              double newLength = GetTourLength(Tours[tour]);
               double detour = newLength - length;
 
-              if (route <= 0 || detour < minDetour) {
+              if (route < 0 || detour < minDetour || feasible && !bestFeasible) {
                 route = tour;
                 place = i;
                 minDetour = detour;
+
+                if (feasible)
+                  bestFeasible = true;
               }
             }