Changeset 6759

Timestamp:

09/14/11 13:00:09 (13 years ago)

Author:

svonolfe

Message:

Adapted creators to support pickup and delivery constraints (#1177)

Location:

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

Files:

• Alba/Creators/PushForwardInsertionCreator.cs (modified) (10 diffs)
• Potvin/Creators/IterativeInsertionCreator.cs (modified) (3 diffs)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/PushForwardInsertionCreator.cs

@@ -31 +31 @@
 using HeuristicLab.Common;
 using HeuristicLab.Problems.VehicleRouting.Interfaces;
+using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
-  [Item("PushForwardCreator", "The push forward insertion heuristic.  It is implemented as described in Sam, and Thangiah, R. (1999). A Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Practical Handbook of Genetic Algorithms, Volume III, pp 347–381.")]
+  [Item("PushForwardInsertionCreator", "The push forward insertion heuristic.  It is implemented as described in Sam, and Thangiah, R. (1999). A Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Practical Handbook of Genetic Algorithms, Volume III, pp 347–381.")]
   [StorableClass]
-  public sealed class PushForwardCreator : DefaultRepresentationCreator, IStochasticOperator, ITimeWindowedOperator {
+  public sealed class PushForwardInsertionCreator : DefaultRepresentationCreator, IStochasticOperator, ITimeWindowedOperator {
     #region IStochasticOperator Members
     public ILookupParameter<IRandom> RandomParameter {
@@ -62 +63 @@
 
     [StorableConstructor]
-    private PushForwardCreator(bool deserializing) : base(deserializing) { }
-
-    public PushForwardCreator()
+    private PushForwardInsertionCreator(bool deserializing) : base(deserializing) { }
+
+    public PushForwardInsertionCreator()
       : base() {
       Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
@@ -76 +77 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new PushForwardCreator(this, cloner);
-    }
-
-    private PushForwardCreator(PushForwardCreator original, Cloner cloner)
+      return new PushForwardInsertionCreator(this, cloner);
+    }
+
+    private PushForwardInsertionCreator(PushForwardInsertionCreator original, Cloner cloner)
       : base(original, cloner) {
     }
@@ -102 +103 @@
     }
 
-    private static double TravelDistance(IVRPProblemInstance problemInstance, List<int> route, int begin) {
-      double distance = 0;
-      for (int i = begin; i < route.Count - 1 && (i == begin || route[i] != 0); i++) {
-        distance += Distance(problemInstance, route[i], route[i + 1]);
-      }
-      return distance;
-    }
-
-    private static bool SubrouteConstraintsOK(IVRPProblemInstance problemInstance, List<int> route, int begin) {
-      AlbaEncoding solution = AlbaEncoding.ConvertFrom(route, problemInstance);
-
-      return problemInstance.Feasible(solution);
-    }
-
     public static List<int> CreateSolution(IVRPProblemInstance problemInstance, IRandom random, 
       double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
@@ -133 +120 @@
       int index;
       int indexOfMinimumCost = -1;
+      int indexOfMinimumCost2 = -1;
       int indexOfCustomer = -1;
+
+      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
 
       /*-----------------------------------------------------------------------------
@@ -140 +130 @@
        */
       for (int i = 1; i <= problemInstance.Cities.Value; i++) {
-        distance = Distance(problemInstance, i, 0);
-        if (problemInstance.Coordinates[i, 0] < x0) distance = -distance;
-
-        cost = -alpha * distance + // distance 0 <-> City[i]
-               beta * (problemInstance as ITimeWindowedProblemInstance).DueTime[i] + // latest arrival time
-               gamma * (Math.Asin((problemInstance.Coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
-
-        index = 0;
-        while (index < costList.Count && costList[index] < cost) index++;
-        costList.Insert(index, cost);
-        unroutedList.Insert(index, i);
+        //only insert sources
+        if (pdp == null || problemInstance.Demand[i] >= 0) {
+          distance = Distance(problemInstance, i, 0);
+          if (problemInstance.Coordinates[i, 0] < x0) distance = -distance;
+
+          cost = -alpha * distance + // distance 0 <-> City[i]
+                 beta * (problemInstance as ITimeWindowedProblemInstance).DueTime[i] + // latest arrival time
+                 gamma * (Math.Asin((problemInstance.Coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
+
+          index = 0;
+          while (index < costList.Count && costList[index] < cost) index++;
+
+          costList.Insert(index, cost);
+
+          unroutedList.Insert(index, i);
+        }
       }
 
@@ -163 +158 @@
       int subTourCount = 1;
       List<int> route = new List<int>(problemInstance.Cities.Value + problemInstance.Vehicles.Value - 1);
+      currentRoute = routeIndex;
       minimumCost = double.MaxValue;
       indexOfMinimumCost = -1;
+      indexOfMinimumCost2 = -1;
       route.Add(0);
       route.Add(0);
+
+      if (pdp != null) {
+        route.Insert(1, pdp.PickupDeliveryLocation[unroutedList[0]]);
+        routeIndex++;
+      }
+
       route.Insert(1, unroutedList[0]);
+      routeIndex++;
+
       unroutedList.RemoveAt(0);
-      currentRoute = routeIndex;
-      routeIndex++;
 
       while (unroutedList.Count > 0) {
         for (c = 0; c < unroutedList.Count; c++) {
+          Tour tour = new Tour();
+          tour.Stops.AddRange(route.GetRange(currentRoute + 1, route.Count - (currentRoute + 1) - 1));
+          VRPEvaluation eval = problemInstance.Evaluate(tour);
+          double originalCosts = eval.Quality;
+
           for (int i = currentRoute + 1; i < route.Count; i++) {
             route.Insert(i, (int)unroutedList[c]);
-            if (route[currentRoute] != 0) { throw new Exception("currentRoute not depot"); }
-            cost = TravelDistance(problemInstance, route, currentRoute);
-            if (cost < minimumCost && SubrouteConstraintsOK(problemInstance, route, currentRoute)) {
-              minimumCost = cost;
-              indexOfMinimumCost = i;
-              customer = (int)unroutedList[c];
-              indexOfCustomer = c;
+            tour = new Tour();
+            tour.Stops.AddRange(route.GetRange(currentRoute+1, route.Count - (currentRoute+1) - 1));
+            eval = problemInstance.Evaluate(tour);
+            double tourCost = eval.Quality - originalCosts;
+
+            if (pdp != null) {
+              for (int j = i - (currentRoute); j <= tour.Stops.Count; j++) {
+                bool feasible;
+                cost = tourCost +
+                  problemInstance.GetInsertionCosts(eval, pdp.PickupDeliveryLocation[unroutedList[c]], 0, j, out feasible);
+                if (cost < minimumCost && feasible) {
+                  minimumCost = cost;
+                  indexOfMinimumCost = i;
+                  indexOfMinimumCost2 = j + currentRoute + 1;
+                  customer = (int)unroutedList[c];
+                  indexOfCustomer = c;
+                }
+              }
+            } else {
+              cost = tourCost;
+              bool feasible = problemInstance.Feasible(eval);
+              if (cost < minimumCost && feasible) {
+                minimumCost = cost;
+                indexOfMinimumCost = i;
+                customer = (int)unroutedList[c];
+                indexOfCustomer = c;
+              }
             }
             route.RemoveAt(i);
@@ -191 +219 @@
           route.Insert(indexOfMinimumCost, customer);
           routeIndex++;
+
+          if (pdp != null) {
+            route.Insert(indexOfMinimumCost2, pdp.PickupDeliveryLocation[customer]);
+            routeIndex++;
+          }
+
           unroutedList.RemoveAt(indexOfCustomer);
           costList.RemoveAt(indexOfCustomer);
@@ -198 +232 @@
           currentRoute = routeIndex;
           route.Insert(route.Count - 1, (int)unroutedList[0]);
+          routeIndex++;
+          if (pdp != null) {
+            route.Insert(route.Count - 1, (int)pdp.PickupDeliveryLocation[unroutedList[0]]);
+            routeIndex++;
+          }
           unroutedList.RemoveAt(0);
-          routeIndex++;
           subTourCount++;
         }
@@ -205 +243 @@
         minimumCost = double.MaxValue;
         indexOfMinimumCost = -1;
+        indexOfMinimumCost2 = -1;
         indexOfCustomer = -1;
         customer = -1;

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

@@ -31 +31 @@
 using HeuristicLab.Problems.VehicleRouting.Interfaces;
 using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
+using HeuristicLab.Problems.VehicleRouting.Variants;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -84 +85 @@
       PotvinEncoding result = new PotvinEncoding(instance);
 
+      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance; 
+
       List<int> customers = new List<int>();
-      for (int i = 0; i < instance.Cities.Value; i++)
-        customers.Add(i + 1);
+      for (int i = 1; i <= instance.Cities.Value; i++)
+        if(pdp == null || pdp.Demand[i] >= 0)
+          customers.Add(i);
+
       customers.Sort(delegate(int city1, int city2)
           {
@@ -104 +109 @@
         currentTour.Stops.Insert(stopIdx, customers[index]);
 
+        if (pdp != null) {
+          stopIdx = result.FindBestInsertionPlace(currentTour, pdp.PickupDeliveryLocation[customers[index]]);
+          currentTour.Stops.Insert(stopIdx, pdp.PickupDeliveryLocation[customers[index]]);
+        }
+
         CVRPEvaluation evaluation = instance.Evaluate(currentTour) as CVRPEvaluation;
         if (result.Tours.Count < instance.Vehicles.Value && 
           ((adhereTimeWindows && !instance.Feasible(evaluation)) || ((!adhereTimeWindows) && evaluation.Overload > double.Epsilon))) {
-          currentTour.Stops.RemoveAt(stopIdx);
+            currentTour.Stops.Remove(customers[index]);
+            if (pdp != null)
+              currentTour.Stops.Remove(pdp.PickupDeliveryLocation[customers[index]]);
 
           if(currentTour.Stops.Count > 0)