Changeset 7791 for branches/VRP

Timestamp:

05/10/12 15:31:22 (13 years ago)

Author:

svonolfe

Message:

Improved PDP moves (#1177)

Location:

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

Files:

• PDExchange/PotvinPDExchangeMoveTabuCriterion.cs (modified) (1 diff)
• PDExchange/PotvinPDExchangeMoveTabuMaker.cs (modified) (3 diffs)
• PDRearrange/PotvinPDRearrangeMoveTabuCriterion.cs (modified) (1 diff)
• PDRearrange/PotvinPDRearrangeMoveTabuMaker.cs (modified) (3 diffs)
• PDShift/PotvinPDShiftExhaustiveMoveGenerator.cs (modified) (1 diff)
• PDShift/PotvinPDShiftMoveMaker.cs (modified) (3 diffs)
• PDShift/PotvinPDShiftMoveTabuCriterion.cs (modified) (1 diff)
• PDShift/PotvinPDShiftMoveTabuMaker.cs (modified) (3 diffs)
• PDShift/PotvinPDShiftSingleMoveGenerator.cs (modified) (2 diffs)
• PotvinPDRelocateMoveAttribute.cs (modified) (3 diffs)

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

@@ -140 +140 @@
             quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
 
+          IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
+          if (pdp != null)
+            quality += attribute.PickupViolations * pdp.PickupViolationPenalty.Value;
+
           if (!useAspiration || moveQuality >= quality) {
             if ((attribute.City == move.City && attribute.Tour == move.Tour) ||

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

@@ -73 +73 @@
       get { return (ILookupParameter<DoubleValue>)Parameters["Tardiness"]; }
     }
+    public ILookupParameter<IntValue> PickupViolationsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["PickupViolations"]; }
+    }
 
     [StorableConstructor]
@@ -92 +95 @@
         Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload of the individual"));
         Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness of the individual"));
+        Parameters.Add(new LookupParameter<IntValue>("PickupViolations", "The number of pickup violations."));
     }
 
@@ -128 +132 @@
         tardiness = TardinessParameter.ActualValue.Value;
 
-      tabuList.Add(new PotvinPDRelocateMoveAttribute(baseQuality, move.OldTour, move.City, distance, overload, tardiness));
-      tabuList.Add(new PotvinPDRelocateMoveAttribute(baseQuality, move.Tour, move.Replaced, distance, overload, tardiness));
+      int pickupViolations = 0;
+      if (PickupViolationsParameter.ActualValue != null)
+        pickupViolations = PickupViolationsParameter.ActualValue.Value;
+
+      tabuList.Add(new PotvinPDRelocateMoveAttribute(baseQuality, move.OldTour, move.City, distance, overload, tardiness, pickupViolations));
+      tabuList.Add(new PotvinPDRelocateMoveAttribute(baseQuality, move.Tour, move.Replaced, distance, overload, tardiness, pickupViolations));
       return base.Apply();
     }

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

@@ -140 +140 @@
             quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
 
+          IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
+          if (pdp != null)
+            quality += attribute.PickupViolations * pdp.PickupViolationPenalty.Value;
+
           if (!useAspiration || moveQuality >= quality) {
             if (attribute.City == move.City && attribute.Tour == move.Tour) {

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

@@ -55 +55 @@
       get { return (ILookupParameter<DoubleValue>)Parameters["Tardiness"]; }
     }
+    public ILookupParameter<IntValue> PickupViolationsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["PickupViolations"]; }
+    }
 
     [StorableConstructor]
@@ -68 +71 @@
         Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload of the individual"));
         Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness of the individual"));
+        Parameters.Add(new LookupParameter<IntValue>("PickupViolations", "The number of pickup violations."));
     }
 
@@ -91 +95 @@
         tardiness = TardinessParameter.ActualValue.Value;
 
-      return new PotvinPDRelocateMoveAttribute(baseQuality, move.Tour, move.City, distance, overload, tardiness);
+      int pickupViolations = 0;
+      if (PickupViolationsParameter.ActualValue != null)
+        pickupViolations = PickupViolationsParameter.ActualValue.Value;
+
+      return new PotvinPDRelocateMoveAttribute(baseQuality, move.Tour, move.City, distance, overload, tardiness, pickupViolations);
     }
   }

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

@@ -54 +54 @@
 
       int max = individual.Tours.Count;
-      if (individual.Tours.Count < problemInstance.Vehicles.Value)
+      if (individual.Tours.Count >= problemInstance.Vehicles.Value)
         max = max - 1;
 

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

@@ -30 +30 @@
 using HeuristicLab.Problems.VehicleRouting.Interfaces;
 using HeuristicLab.Problems.VehicleRouting.Variants;
+using System.Collections.Generic;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -60 +61 @@
 
     public static void Apply(PotvinEncoding solution, PotvinPDShiftMove move, IVRPProblemInstance problemInstance) {
-      if (move.Tour >= solution.Tours.Count)
+      bool newTour = false;
+
+      if (move.Tour >= solution.Tours.Count) {
         solution.Tours.Add(new Tour());
+        newTour = true;
+      }
       Tour tour = solution.Tours[move.Tour];
 
@@ -80 +85 @@
       }
 
+      if (newTour) {
+        List<int> vehicles = new List<int>();
+        for (int i = move.Tour; i < problemInstance.Vehicles.Value; i++) {
+          vehicles.Add(solution.GetVehicleAssignment(i));
+        }
+
+        double bestQuality = double.MaxValue;
+        int bestVehicle = -1;
+
+        int originalVehicle = solution.GetVehicleAssignment(move.Tour);
+        foreach (int vehicle in vehicles) {
+          solution.VehicleAssignment[move.Tour] = vehicle;
+
+          double quality = problemInstance.EvaluateTour(tour, solution).Quality;
+          if (quality < bestQuality) {
+            bestQuality = quality;
+            bestVehicle = vehicle;
+          }
+        }
+
+        solution.VehicleAssignment[move.Tour] = originalVehicle;
+
+        int index = -1;
+        for (int i = move.Tour; i < solution.VehicleAssignment.Length; i++) {
+          if (solution.VehicleAssignment[i] == bestVehicle) {
+            index = i;
+            break;
+          }
+        }
+        solution.VehicleAssignment[index] = originalVehicle;
+        solution.VehicleAssignment[move.Tour] = bestVehicle;
+      }
+
       solution.Repair();
     }

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

@@ -140 +140 @@
             quality += attribute.Tardiness * vrptw.TardinessPenalty.Value;
 
+          IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
+          if (pdp != null)
+            quality += attribute.PickupViolations * pdp.PickupViolationPenalty.Value;
+
           if (!useAspiration || moveQuality >= quality) {
             if (attribute.City == move.City && attribute.Tour == move.Tour) {

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

@@ -54 +54 @@
       get { return (ILookupParameter<DoubleValue>)Parameters["Tardiness"]; }
     }
+    public ILookupParameter<IntValue> PickupViolationsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["PickupViolations"]; }
+    }
 
     [StorableConstructor]
@@ -67 +70 @@
         Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload of the individual"));
         Parameters.Add(new LookupParameter<DoubleValue>("Tardiness", "The tardiness of the individual"));
+        Parameters.Add(new LookupParameter<IntValue>("PickupViolations", "The number of pickup violations."));
     }
 
@@ -89 +93 @@
       if (TardinessParameter.ActualValue != null)
         tardiness = TardinessParameter.ActualValue.Value;
+
+      int pickupViolations = 0;
+      if (PickupViolationsParameter.ActualValue != null)
+        pickupViolations = PickupViolationsParameter.ActualValue.Value;
       
-      return new PotvinPDRelocateMoveAttribute(baseQuality, move.OldTour, move.City, distance, overload, tardiness);
+      return new PotvinPDRelocateMoveAttribute(baseQuality, move.OldTour, move.City, distance, overload, tardiness, pickupViolations);
     }
   }

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

@@ -66 +66 @@
       }
 
-      if (cities.Count > 1 && individual.Tours.Count > 1) {
+      if (cities.Count >= 1) {
         int city = cities[rand.Next(cities.Count)];
         Tour oldTour = individual.Tours.Find(t => t.Stops.Contains(city));
@@ -72 +72 @@
 
         int max = individual.Tours.Count;
-        if (individual.Tours.Count < problemInstance.Vehicles.Value)
+        if (individual.Tours.Count >= problemInstance.Vehicles.Value)
           max = max - 1;
 

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

@@ -40 +40 @@
     [Storable]
     public double Tardiness { get; private set; }
+    [Storable]
+    public int PickupViolations { get; private set; }
 
     [StorableConstructor]
@@ -50 +52 @@
         this.Overload = original.Overload;
         this.Tardiness = original.Tardiness;
+        this.PickupViolations = original.PickupViolations;
     }
-    public PotvinPDRelocateMoveAttribute(double moveQuality, int tour, int city, 
-      double distance, double overload, double tardiness)
+    public PotvinPDRelocateMoveAttribute(double moveQuality, int tour, int city,
+      double distance, double overload, double tardiness, int pickupViolations)
       : base(moveQuality) {
       Tour = tour;
@@ -59 +62 @@
       Overload = overload;
       Tardiness = tardiness;
+      PickupViolations = pickupViolations;
     }