Index: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/PushForwardInsertionCreator.cs
===================================================================
--- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/PushForwardInsertionCreator.cs	(revision 6751)
+++ branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Creators/PushForwardInsertionCreator.cs	(revision 6759)
@@ -31,9 +31,10 @@
 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,7 +63,7 @@
 
     [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,8 +77,8 @@
 
     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,18 +103,4 @@
     }
 
-    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,5 +120,8 @@
       int index;
       int indexOfMinimumCost = -1;
+      int indexOfMinimumCost2 = -1;
       int indexOfCustomer = -1;
+
+      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
 
       /*-----------------------------------------------------------------------------
@@ -140,15 +130,20 @@
        */
       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,24 +158,57 @@
       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,4 +219,10 @@
           route.Insert(indexOfMinimumCost, customer);
           routeIndex++;
+
+          if (pdp != null) {
+            route.Insert(indexOfMinimumCost2, pdp.PickupDeliveryLocation[customer]);
+            routeIndex++;
+          }
+
           unroutedList.RemoveAt(indexOfCustomer);
           costList.RemoveAt(indexOfCustomer);
@@ -198,6 +232,10 @@
           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,4 +243,5 @@
         minimumCost = double.MaxValue;
         indexOfMinimumCost = -1;
+        indexOfMinimumCost2 = -1;
         indexOfCustomer = -1;
         customer = -1;
