Changeset 6960

Timestamp:

11/08/11 09:47:31 (12 years ago)

Author:

svonolfe

Message:

Added pairwise manipulators, removed relocation manipulator (#1177)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4

Files:

• Encodings/Potvin/Crossovers/PotvinCrossover.cs (modified) (1 diff)
• Encodings/Potvin/Manipulators/PotvinCustomerRelocationManipulator.cs (deleted)
• Encodings/Potvin/Manipulators/PotvinPairwiseOneLevelExchangeManipulator.cs (added)
• Encodings/Potvin/Manipulators/PotvinPairwiseTwoLevelExchangeManipulator.cs (added)
• Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeMoveMaker.cs (modified) (1 diff)
• Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveMaker.cs (modified) (2 diffs)
• Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveMaker.cs (modified) (1 diff)
• Encodings/Potvin/PotvinEncoding.cs (modified) (1 diff)
• HeuristicLab.Problems.VehicleRouting-3.4.csproj (modified) (1 diff)

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

@@ -136 +136 @@
       }
 
-      if (!allowInfeasible && !instance.TourFeasible(newTour, solution))
+      if (newTour.Stops.Count > 0 && !allowInfeasible && !instance.TourFeasible(newTour, solution))
         return false;
 

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeMoveMaker.cs

@@ -80 +80 @@
         tour.Stops.Remove(move.Replaced);
 
-        PotvinPDRearrangeMoveMaker.InsertPair(solution, tour, move.City, pdp.GetPickupDeliveryLocation(move.City), problemInstance);
-        PotvinPDRearrangeMoveMaker.InsertPair(solution, oldTour, move.Replaced, pdp.GetPickupDeliveryLocation(move.Replaced), problemInstance);
+        solution.InsertPair(tour, move.City, pdp.GetPickupDeliveryLocation(move.City), problemInstance);
+        solution.InsertPair(oldTour, move.Replaced, pdp.GetPickupDeliveryLocation(move.Replaced), problemInstance);
       } else {
         tour.Stops.Remove(move.Replaced);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveMaker.cs

@@ -59 +59 @@
     }
 
-    public static void InsertPair(PotvinEncoding solution, Tour tour, int source, int target, IVRPProblemInstance problemInstance, int positionToAvoid = -1, int positionToAvoid2 = -1) {
-      int stops = tour.Stops.Count;
-      VRPEvaluation eval = problemInstance.EvaluateTour(tour, solution);
-      double minCosts = double.MaxValue;
-      int sourceLocation = -1;
-      int targetLocation = -1;
-
-      for (int i = 0; i <= stops; i++) {
-        tour.Stops.Insert(i, source);
-        VRPEvaluation tourEval = problemInstance.EvaluateTour(tour, solution);
-        double sourceCosts = tourEval.Quality - eval.Quality;
-
-        for (int j = i + 1; j <= stops + 1; j++) {
-          if (positionToAvoid != i || positionToAvoid2 != j || stops == 0) {
-            bool feasible;
-            double targetCosts = problemInstance.GetInsertionCosts(tourEval, solution, target, 0, j, out feasible);
-
-            double costs = sourceCosts + targetCosts;
-            if (costs < minCosts) {
-              minCosts = costs;
-              sourceLocation = i;
-              targetLocation = j;
-            }
-          }
-        }
-        tour.Stops.Remove(source);
-      }
-
-      tour.Stops.Insert(sourceLocation, source);
-      tour.Stops.Insert(targetLocation, target);
-    }
-
     public static void Apply(PotvinEncoding solution, PotvinPDRearrangeMove move, IVRPProblemInstance problemInstance) {
       Tour tour = solution.Tours[move.Tour];
@@ -104 +72 @@
         tour2.Stops.Remove(location);
 
-        PotvinPDRearrangeMoveMaker.InsertPair(solution, tour, move.City, location, problemInstance, position, position2);
+        solution.InsertPair(tour, move.City, location, problemInstance, position, position2);
       } else {
         tour.Stops.Remove(move.City);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftMoveMaker.cs

@@ -74 +74 @@
         oldTour2.Stops.Remove(location);
 
-        PotvinPDRearrangeMoveMaker.InsertPair(solution, tour, move.City, location, problemInstance);
+        solution.InsertPair(tour, move.City, location, problemInstance);
       } else {
         int place = solution.FindBestInsertionPlace(tour, move.City);

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

@@ -165 +165 @@
     }
 
+    public void InsertPair(Tour tour, int source, int target, IVRPProblemInstance problemInstance, int positionToAvoid = -1, int positionToAvoid2 = -1) {
+      int stops = tour.Stops.Count;
+      VRPEvaluation eval = problemInstance.EvaluateTour(tour, this);
+      double minCosts = double.MaxValue;
+      int sourceLocation = -1;
+      int targetLocation = -1;
+
+      for (int i = 0; i <= stops; i++) {
+        tour.Stops.Insert(i, source);
+        VRPEvaluation tourEval = problemInstance.EvaluateTour(tour, this);
+        double sourceCosts = tourEval.Quality - eval.Quality;
+
+        for (int j = i + 1; j <= stops + 1; j++) {
+          if (positionToAvoid != i || positionToAvoid2 != j || stops == 0) {
+            bool feasible;
+            double targetCosts = problemInstance.GetInsertionCosts(tourEval, this, target, 0, j, out feasible);
+
+            double costs = sourceCosts + targetCosts;
+            if (costs < minCosts) {
+              minCosts = costs;
+              sourceLocation = i;
+              targetLocation = j;
+            }
+          }
+        }
+        tour.Stops.Remove(source);
+      }
+
+      tour.Stops.Insert(sourceLocation, source);
+      tour.Stops.Insert(targetLocation, target);
+    }
+
     public bool FindInsertionPlace(int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
       route = -1;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

@@ -210 +210 @@
     <Compile Include="Encodings\Potvin\Crossovers\PotvinSequenceBasedCrossover.cs" />
     <Compile Include="Encodings\Potvin\IPotvinOperator.cs" />
+    <Compile Include="Encodings\Potvin\Manipulators\PotvinPairwiseTwoLevelExchangeManipulator.cs" />
+    <Compile Include="Encodings\Potvin\Manipulators\PotvinPairwiseOneLevelExchangeManipulator.cs" />
     <Compile Include="Encodings\Potvin\Manipulators\PotvinVehicleAssignmentManipulator.cs" />
-    <Compile Include="Encodings\Potvin\Manipulators\PotvinCustomerRelocationManipulator.cs" />
     <Compile Include="Encodings\Potvin\Manipulators\PotvinLocalSearchManipulator.cs" />
     <Compile Include="Encodings\Potvin\Manipulators\PotvinManipulator.cs" />