Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs	(revision 6752)
@@ -38,20 +38,30 @@
     
     #region IVRPEncoding Members
-    public virtual List<Tour> GetTours() {
-      List<Tour> result = new List<Tour>();
-
-      foreach(Tour tour in Tours) {
-        if (tour.Stops.Count > 0)
-          result.Add(tour.Clone() as Tour);
+    public void Repair() {
+      List<Tour> toBeRemoved = new List<Tour>();
+      foreach (Tour tour in Tours) {
+        if (tour.Stops.Count == 0)
+          toBeRemoved.Add(tour);
       }
 
-     while (result.Count > ProblemInstance.Vehicles.Value) {
-        Tour tour = result[result.Count - 1];
-        result[result.Count - 2].Stops.AddRange(tour.Stops);
+      foreach (Tour tour in toBeRemoved)
+        Tours.Remove(tour);
 
-        result.Remove(tour);
-      }   
+      while (Tours.Count > ProblemInstance.Vehicles.Value) {
+        Tour tour = Tours[Tours.Count - 1];
+        Tours[Tours.Count - 2].Stops.AddRange(tour.Stops);
 
-      return result;
+        Tours.Remove(tour);
+      } 
+    }
+
+    public virtual List<Tour> GetTours() {
+     Repair();
+      
+     List<Tour> result = new List<Tour>();
+     foreach (Tour tour in Tours)
+       result.Add(tour.Clone() as Tour);
+
+     return result;
     }
 
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs	(revision 6752)
@@ -156,29 +156,22 @@
         return false;
 
-      bool bestFeasible = false;
+      if (tour.Stops.Count == 0) {
+        place = 0;
+        return true;
+      }
+
       double minDetour = 0;
-
       VRPEvaluation eval = ProblemInstance.Evaluate(tour);
-      double length = eval.Quality;
+      bool originalFeasible = ProblemInstance.Feasible(eval);
+
       for (int i = 0; i <= tour.Stops.Count; i++) {
-        tour.Stops.Insert(i, city);
-
-        eval = ProblemInstance.Evaluate(tour);
-        bool feasible = ProblemInstance.Feasible(eval);
-
-        if (feasible || allowInfeasible && !bestFeasible) {
-          double newLength = eval.Quality;
-          double detour = newLength - length;
-
-          if (place < 0 || detour < minDetour || feasible && !bestFeasible) {
+        bool feasible;
+        double detour = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);
+        if (feasible || allowInfeasible) {
+          if (place < 0 || detour < minDetour) {
             place = i;
             minDetour = detour;
-
-            if (feasible)
-              bestFeasible = true;
           }
         }
-
-        tour.Stops.RemoveAt(i);
       }
 
@@ -248,5 +241,6 @@
 
           int place = -1;
-          if (FindRouteInsertionPlace(childTour, city, allowInfeasible, out place)) {
+          bool found = FindRouteInsertionPlace(childTour, city, allowInfeasible, out place); 
+          if (found) {
             childTour.Stops.Insert(place, city);
 
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs	(revision 6752)
@@ -39,11 +39,7 @@
     public List<int> Unrouted { get; set; }
 
-    [Storable]
-    public double PenaltyFactor { get; set; }
-
     public PotvinEncoding(IVRPProblemInstance instance)
       : base(instance) {
       Unrouted = new List<int>();
-      PenaltyFactor = 1;
     }
 
@@ -60,5 +56,4 @@
       : base(original, cloner) {
         this.Unrouted = new List<int>(original.Unrouted);
-        this.PenaltyFactor = original.PenaltyFactor;
     }
 
@@ -87,16 +82,13 @@
       double minQuality = -1;
 
+      VRPEvaluation eval = ProblemInstance.Evaluate(tour);
+
       for (int i = 0; i <= tour.Stops.Count; i++) {
-        tour.Stops.Insert(i, city);
-
-        VRPEvaluation eval = ProblemInstance.Evaluate(tour);
-        double quality = eval.Quality + eval.Penalty * (PenaltyFactor - 1.0);
-
+        bool feasible;
+        double quality = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);
         if (place < 0 || quality < minQuality) {
           place = i;
           minQuality = quality;
         }
-
-        tour.Stops.RemoveAt(i);
       }
 
@@ -110,33 +102,24 @@
       route = -1;
       place = -1;
-      bool bestFeasible = false;
       double minDetour = double.MaxValue;
+
+      VRPEvaluation eval = ProblemInstance.Evaluate(this);
+      bool originalFeasible = ProblemInstance.Feasible(eval);
 
       for (int tour = 0; tour < Tours.Count; tour++) {
         if (tour != routeToAvoid) {
-          VRPEvaluation eval = ProblemInstance.Evaluate(Tours[tour]);
           double length = eval.Quality;
 
           for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
-            Tours[tour].Stops.Insert(i, city);
-
-            eval = ProblemInstance.Evaluate(Tours[tour]);
-            bool feasible = ProblemInstance.Feasible(eval);
-
-            if (feasible || allowInfeasible && !bestFeasible) {
-              double newLength = eval.Quality;
-              double detour = newLength - length;
-
-              if (route < 0 || detour < minDetour || feasible && !bestFeasible) {
+            bool feasible;
+            double detour = ProblemInstance.GetInsertionCosts(eval, city, tour, i, out feasible);
+            
+            if (feasible || allowInfeasible) {
+              if (route < 0 || detour < minDetour) {
                 route = tour;
                 place = i;
                 minDetour = detour;
-
-                if (feasible)
-                  bestFeasible = true;
               }
             }
-
-            Tours[tour].Stops.RemoveAt(i);
           }
         }
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPEvaluator.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPEvaluator.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPEvaluator.cs	(revision 6752)
@@ -35,4 +35,5 @@
     VRPEvaluation Evaluate(IVRPProblemInstance instance, Tour tour);
     bool Feasible(VRPEvaluation evaluation);
+    double GetInsertionCosts(IVRPProblemInstance instance, VRPEvaluation eval, int customer, int tour, int index, out bool feasible);
   }
 }
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPProblemInstance.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPProblemInstance.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPProblemInstance.cs	(revision 6752)
@@ -54,4 +54,5 @@
     VRPEvaluation Evaluate(Tour tour);
     bool Feasible(VRPEvaluation eval);
+    double GetInsertionCosts(VRPEvaluation eval, int customer, int tour, int index, out bool feasible);
   }
 }
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluation.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluation.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluation.cs	(revision 6752)
@@ -24,6 +24,22 @@
 using System.Linq;
 using System.Text;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Core;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
+  public class CVRPInsertionInfo : StopInsertionInfo {
+    private double spareCapacity;
+
+    public double SpareCapacity {
+      get { return spareCapacity; }
+    }
+
+    public CVRPInsertionInfo(int start, int end, double spareCapacity)
+      : base(start, end) {
+      this.spareCapacity = spareCapacity;
+    }
+  }
+  
   public class CVRPEvaluation: VRPEvaluation {
     public double Overload { get; set; }
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs	(revision 6752)
@@ -48,4 +48,7 @@
 
     protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) {
+      TourInsertionInfo tourInfo = new TourInsertionInfo();
+      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
+      
       IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
       DoubleArray demand = instance.Demand;
@@ -54,4 +57,15 @@
       double overweight = 0.0;
       double distance = 0.0;
+
+      double capacity = cvrpInstance.Capacity.Value;
+      for (int i = 0; i <= tour.Stops.Count; i++) {
+        int end = 0;
+        if (i < tour.Stops.Count)
+          end = tour.Stops[i];
+
+        delivered += demand[end];
+      }
+
+      double spareCapacity = capacity - delivered;
 
       //simulate a tour, start and end at depot
@@ -68,5 +82,6 @@
         distance += currentDistace;
 
-        delivered += demand[end];
+        CVRPInsertionInfo stopInfo = new CVRPInsertionInfo(start, end, spareCapacity);
+        tourInfo.AddStopInsertionInfo(stopInfo);
       }
 
@@ -77,5 +92,4 @@
       eval.VehicleUtilization += 1;
 
-      double capacity = cvrpInstance.Capacity.Value;
       if (delivered > capacity) {
         overweight = delivered - capacity;
@@ -86,4 +100,34 @@
       eval.Penalty += penalty;
       eval.Quality += penalty;
+      tourInfo.Penalty = penalty;
+    }
+
+    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer, 
+      out bool feasible) {
+      CVRPInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPInsertionInfo;
+      
+      double costs = 0;
+      feasible = tourInsertionInfo.Penalty < double.Epsilon;
+
+      ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;
+      double overloadPenalty = cvrp.OverloadPenalty.Value;
+
+      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
+      double newDistance =
+        instance.GetDistance(insertionInfo.Start, customer) +
+        instance.GetDistance(customer, insertionInfo.End);
+      costs += instance.DistanceFactor.Value * (newDistance - distance);
+
+      double demand = instance.Demand[customer];
+      if (demand > insertionInfo.SpareCapacity) {
+        feasible = false;
+
+        if(insertionInfo.SpareCapacity >= 0)
+          costs += (demand - insertionInfo.SpareCapacity) * overloadPenalty;
+        else
+          costs += demand * overloadPenalty;
+      }
+      
+      return costs;
     }
 
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluation.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluation.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluation.cs	(revision 6752)
@@ -24,6 +24,28 @@
 using System.Linq;
 using System.Text;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
+  public class CVRPPDTWInsertionInfo : CVRPTWInsertionInfo {
+    private List<int> visited;
+
+    public List<int> Visited {
+      get { return visited; }
+    }
+
+    private double arrivalSpareCapacity;
+
+    public double ArrivalSpareCapacity {
+      get { return arrivalSpareCapacity;  }
+    }
+
+    public CVRPPDTWInsertionInfo(int start, int end, double spareCapacity, double arrivalTime, double leaveTime, double spareTime, double waitingTime, List<int> visited, double arrivalSpareCapacity)
+      : base(start, end, spareCapacity, arrivalTime, leaveTime, spareTime, waitingTime) {
+        this.visited = visited;
+        this.arrivalSpareCapacity = arrivalSpareCapacity;
+    }
+  }
+  
   public class CVRPPDTWEvaluation: CVRPTWEvaluation {
     public int PickupViolations { get; set; }
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluator.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluator.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluator.cs	(revision 6752)
@@ -48,4 +48,7 @@
 
     protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) {
+      TourInsertionInfo tourInfo = new TourInsertionInfo();
+      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
+
       IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
       DoubleArray demand = instance.Demand;
@@ -86,4 +89,6 @@
         distance += currentDistace;
 
+        double arrivalTime = time;
+
         //check if it was serviced on time
         if (time > dueTime[end])
@@ -94,6 +99,11 @@
         if (time < readyTime[end])
           currentWaitingTime = readyTime[end] - time;
+
+        double waitTime = readyTime[end] - time;
+
         waitingTime += currentWaitingTime;
         time += currentWaitingTime;
+
+        double spareTime = dueTime[end] - time;
 
         //service
@@ -103,4 +113,6 @@
 
         //Pickup / deliver
+        double arrivalSpareCapacity = capacity - currentLoad;
+
         bool validPickupDelivery = 
           validPickupDelivery =
@@ -110,10 +122,14 @@
         if (validPickupDelivery) {
           currentLoad += demand[end];
-
-          if (currentLoad > capacity)
-            overweight += currentLoad - capacity;
         } else {
           pickupViolations++;
         }
+
+        if (currentLoad > capacity)
+          overweight += currentLoad - capacity;
+
+        double spareCapacity = capacity - currentLoad;
+        CVRPPDTWInsertionInfo stopInfo = new CVRPPDTWInsertionInfo(start, end, spareCapacity, arrivalTime, time, spareTime, waitTime, new List<int>(stops.Keys), arrivalSpareCapacity);
+        tourInfo.AddStopInsertionInfo(stopInfo);
 
         stops.Add(end, true);
@@ -126,7 +142,9 @@
 
       (eval as CVRPEvaluation).Overload += overweight;
+      double tourPenalty = 0;
       double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
       eval.Penalty += penalty;
       eval.Quality += penalty;
+      tourPenalty += penalty;
 
       (eval as CVRPTWEvaluation).Tardiness += tardiness;
@@ -136,11 +154,137 @@
       eval.Penalty += penalty;
       eval.Quality += penalty;
+      tourPenalty += penalty;
 
       (eval as CVRPPDTWEvaluation).PickupViolations += pickupViolations;
       penalty = pickupViolations * pdp.PickupViolationPenalty.Value;
       eval.Penalty += penalty;
+      tourPenalty += penalty;
 
       eval.Quality += penalty;
       eval.Quality += time * vrptw.TimeFactor.Value;
+      tourInfo.Penalty = tourPenalty;
+    }
+
+    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer, 
+      out bool feasible) {
+      CVRPPDTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPPDTWInsertionInfo;
+
+      double costs = 0;
+      feasible = tourInsertionInfo.Penalty < double.Epsilon;
+      bool tourFeasible = true;
+
+      ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;
+      double overloadPenalty = cvrp.OverloadPenalty.Value;
+
+      ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
+      DoubleArray dueTime = vrptw.DueTime;
+      DoubleArray readyTime = vrptw.ReadyTime;
+      DoubleArray serviceTimes = vrptw.ServiceTime;
+      double tardinessPenalty = vrptw.TardinessPenalty.Value;
+
+      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
+      IntArray pickupDeliveryLocation = pdp.PickupDeliveryLocation;
+      double pickupPenalty = pdp.PickupViolationPenalty.Value;
+
+      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
+      double newDistance =
+        instance.GetDistance(insertionInfo.Start, customer) +
+        instance.GetDistance(customer, insertionInfo.End);
+      costs += instance.DistanceFactor.Value * (newDistance - distance);
+
+      double demand = instance.Demand[customer];
+      if (demand > insertionInfo.ArrivalSpareCapacity) {
+        tourFeasible = feasible = false;
+        if (insertionInfo.ArrivalSpareCapacity >= 0)
+          costs += (demand - insertionInfo.ArrivalSpareCapacity) * overloadPenalty;
+        else
+          costs += demand * overloadPenalty;
+      }
+      int destination = pickupDeliveryLocation[customer];
+
+      bool validPickup = true;
+      if (demand < 0 && !insertionInfo.Visited.Contains(destination)) {
+        tourFeasible = feasible = false;
+        validPickup = false;
+        costs += pickupPenalty;
+      }
+
+      double time = 0;
+      double tardiness = 0;
+
+      if (index > 0)
+        time = (tourInsertionInfo.GetStopInsertionInfo(index - 1) as CVRPTWInsertionInfo).LeaveTime;
+      time += instance.GetDistance(insertionInfo.Start, customer);
+      if (time > dueTime[customer]) {
+        tardiness += time - dueTime[customer];
+      }
+      if (time < readyTime[customer])
+        time += readyTime[customer] - time;
+      time += serviceTimes[customer];
+      time += instance.GetDistance(customer, insertionInfo.End);
+
+      double additionalTime = time - (tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo).ArrivalTime;
+      for (int i = index; i < tourInsertionInfo.GetStopCount(); i++) {
+        CVRPTWInsertionInfo nextStop = tourInsertionInfo.GetStopInsertionInfo(i) as CVRPTWInsertionInfo;
+
+        if (demand >= 0) {
+          if (nextStop.End == destination) {
+            demand = 0;
+            costs -= pickupPenalty;
+            if (tourInsertionInfo.Penalty == pickupPenalty && tourFeasible)
+              feasible = true;
+          } else if (nextStop.SpareCapacity < 0) {
+            costs += demand * overloadPenalty;
+          } else if (nextStop.SpareCapacity < demand) {
+            tourFeasible = feasible = false;
+            costs += (demand - nextStop.SpareCapacity) * overloadPenalty;
+          }
+        } else if (validPickup) {
+          if (nextStop.SpareCapacity < 0) {
+            costs += Math.Max(demand, nextStop.SpareCapacity) * overloadPenalty;
+          }
+        }
+
+        if (additionalTime < 0) {
+          //arrive earlier than before
+          //wait probably
+          if (nextStop.WaitingTime < 0) {
+            double wait = nextStop.WaitingTime - additionalTime;
+            if (wait > 0)
+              additionalTime += wait;
+          } else {
+            additionalTime = 0;
+          }
+
+          //check due date, decrease tardiness
+          if (nextStop.SpareTime < 0) {
+            costs += Math.Max(nextStop.SpareTime, additionalTime) * tardinessPenalty;
+          }
+        } else {
+          //arrive later than before, probably don't have to wait
+          if (nextStop.WaitingTime > 0) {
+            additionalTime -= Math.Min(additionalTime, nextStop.WaitingTime);
+          }
+
+          //check due date
+          if (nextStop.SpareTime > 0) {
+            double spare = nextStop.SpareTime - additionalTime;
+            if (spare < 0)
+              tardiness += -spare;
+          } else {
+            tardiness += additionalTime;
+          }
+        }
+      }
+
+      costs += additionalTime * vrptw.TimeFactor.Value;
+
+      if (tardiness > 0) {
+        tourFeasible = feasible = false;
+      }
+
+      costs += tardiness * tardinessPenalty;
+
+      return costs;
     }
 
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluation.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluation.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluation.cs	(revision 6752)
@@ -24,6 +24,42 @@
 using System.Linq;
 using System.Text;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
+  public class CVRPTWInsertionInfo : CVRPInsertionInfo {
+    private double arrivalTime;
+
+    public double ArrivalTime {
+      get { return arrivalTime; }
+    }
+
+    private double leaveTime;
+
+    public double LeaveTime {
+      get { return leaveTime; }
+    }
+
+    private double spareTime;
+
+    public double SpareTime {
+      get { return spareTime; }
+    }
+
+    private double waitingTime;
+
+    public double WaitingTime {
+      get { return waitingTime; }
+    }
+
+    public CVRPTWInsertionInfo(int start, int end, double spareCapacity, double arrivalTime, double leaveTime, double spareTime, double waitingTime)
+      : base(start, end, spareCapacity) {
+        this.arrivalTime = arrivalTime;
+        this.leaveTime = leaveTime;
+        this.spareTime = spareTime;
+        this.waitingTime = waitingTime;
+    }
+  }
+  
   public class CVRPTWEvaluation: CVRPEvaluation {
     public double Tardiness { get; set; }
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluator.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluator.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluator.cs	(revision 6752)
@@ -52,4 +52,7 @@
 
     protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) {
+      TourInsertionInfo tourInfo = new TourInsertionInfo();
+      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
+      
       IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
       DoubleArray demand = instance.Demand;
@@ -67,4 +70,15 @@
       double overweight = 0.0;
       double distance = 0.0;
+
+      double capacity = cvrpInstance.Capacity.Value;
+      for (int i = 0; i <= tour.Stops.Count; i++) {
+        int end = 0;
+        if (i < tour.Stops.Count)
+          end = tour.Stops[i];
+
+        delivered += demand[end];
+      }
+
+      double spareCapacity = capacity - delivered;
 
       //simulate a tour, start and end at depot
@@ -82,4 +96,6 @@
         distance += currentDistace;
 
+        double arrivalTime = time;
+
         //check if it was serviced on time
         if (time > dueTime[end])
@@ -90,6 +106,11 @@
         if (time < readyTime[end])
           currentWaitingTime = readyTime[end] - time;
+
+        double waitTime = readyTime[end]-time;
+
         waitingTime += currentWaitingTime;
         time += currentWaitingTime;
+
+        double spareTime = dueTime[end] - time;
 
         //service
@@ -97,5 +118,7 @@
         serviceTime += currentServiceTime;
         time += currentServiceTime;
-        delivered += demand[end];
+
+        CVRPTWInsertionInfo stopInfo = new CVRPTWInsertionInfo(start, end, spareCapacity, arrivalTime, time, spareTime, waitTime);
+        tourInfo.AddStopInsertionInfo(stopInfo);
       }
 
@@ -105,5 +128,4 @@
       eval.VehicleUtilization += 1;
 
-      double capacity = cvrpInstance.Capacity.Value;
       if (delivered > capacity) {
         overweight = delivered - capacity;
@@ -111,7 +133,9 @@
 
       (eval as CVRPEvaluation).Overload += overweight;
+      double tourPenalty = 0;
       double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
       eval.Penalty += penalty;
       eval.Quality += penalty;
+      tourPenalty += penalty;
 
       (eval as CVRPTWEvaluation).Tardiness += tardiness;
@@ -121,5 +145,99 @@
       eval.Penalty += penalty;
       eval.Quality += penalty;
+      tourPenalty += penalty;
       eval.Quality += time * vrptw.TimeFactor.Value;
+      tourInfo.Penalty = tourPenalty;
+    }
+
+    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,
+      out bool feasible) {
+      CVRPTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo;
+
+      double costs = 0;
+      feasible = tourInsertionInfo.Penalty < double.Epsilon;
+
+      ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;
+      double overloadPenalty = cvrp.OverloadPenalty.Value;
+
+      ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
+      DoubleArray dueTime = vrptw.DueTime;
+      DoubleArray readyTime = vrptw.ReadyTime;
+      DoubleArray serviceTimes = vrptw.ServiceTime;
+      double tardinessPenalty = vrptw.TardinessPenalty.Value;
+
+      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
+      double newDistance =
+        instance.GetDistance(insertionInfo.Start, customer) +
+        instance.GetDistance(customer, insertionInfo.End);
+      costs += instance.DistanceFactor.Value * (newDistance - distance);
+
+      double demand = instance.Demand[customer];
+      if (demand > insertionInfo.SpareCapacity) {
+        feasible = false;
+        if (insertionInfo.SpareCapacity >= 0)
+          costs += (demand - insertionInfo.SpareCapacity) * overloadPenalty;
+        else
+          costs += demand * overloadPenalty;
+      }
+
+      double time = 0;
+      double tardiness = 0;
+
+      if (index > 0)
+        time = (tourInsertionInfo.GetStopInsertionInfo(index - 1) as CVRPTWInsertionInfo).LeaveTime;
+      time += instance.GetDistance(insertionInfo.Start, customer);
+      if (time > dueTime[customer]) {
+        tardiness += time - dueTime[customer];
+      }
+      if (time < readyTime[customer])
+        time += readyTime[customer] - time;
+      time += serviceTimes[customer];
+      time += instance.GetDistance(customer, insertionInfo.End);
+
+      double additionalTime = time - (tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo).ArrivalTime;
+      for (int i = index; i < tourInsertionInfo.GetStopCount(); i++) {
+        CVRPTWInsertionInfo nextStop = tourInsertionInfo.GetStopInsertionInfo(i) as CVRPTWInsertionInfo;
+
+        if (additionalTime < 0) {
+          //arrive earlier than before
+          //wait probably
+          if (nextStop.WaitingTime < 0) {
+            double wait = nextStop.WaitingTime - additionalTime;
+            if (wait > 0)
+              additionalTime += wait;
+          } else {
+            additionalTime = 0;
+          }
+
+          //check due date, decrease tardiness
+          if (nextStop.SpareTime < 0) {
+            costs += Math.Max(nextStop.SpareTime, additionalTime) * tardinessPenalty;
+          }
+        } else {
+          //arrive later than before, probably don't have to wait
+          if (nextStop.WaitingTime > 0) {
+            additionalTime -= Math.Min(additionalTime, nextStop.WaitingTime);            
+          }
+
+          //check due date
+          if (nextStop.SpareTime > 0) {
+            double spare = nextStop.SpareTime - additionalTime;
+            if (spare < 0)
+              tardiness += -spare; 
+          } else {
+            tardiness += additionalTime;
+          }
+        }
+      }
+
+      costs += additionalTime * vrptw.TimeFactor.Value;
+
+      if (tardiness > 0) {
+        feasible = false;
+      }
+
+      costs += tardiness * tardinessPenalty;
+
+      return costs;
     }
 
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/SingleDepotVRPEvaluator.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/SingleDepotVRPEvaluator.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/SingleDepotVRPEvaluator.cs	(revision 6752)
@@ -41,4 +41,7 @@
   public class SingleDepotVRPEvaluator: VRPEvaluator {
     protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) {
+      TourInsertionInfo tourInfo = new TourInsertionInfo();
+      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
+      
       double distance = 0.0;
       double quality = 0.0;
@@ -56,4 +59,7 @@
         double currentDistace = instance.GetDistance(start, end);
         distance += currentDistace;
+
+        StopInsertionInfo stopInfo = new StopInsertionInfo(start, end);
+        tourInfo.AddStopInsertionInfo(stopInfo);
       }
 
@@ -67,4 +73,21 @@
 
       eval.Quality += quality;
+    }
+
+    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,
+      out bool feasible) {
+      StopInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index);
+      
+      double costs = 0;
+      feasible = true;
+
+      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
+      double newDistance =
+        instance.GetDistance(insertionInfo.Start, customer) +
+        instance.GetDistance(customer, insertionInfo.End);
+
+      costs += instance.DistanceFactor.Value * (newDistance - distance);
+
+      return costs;
     }
     
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluation.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluation.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluation.cs	(revision 6752)
@@ -24,12 +24,80 @@
 using System.Linq;
 using System.Text;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Core;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
+  public class StopInsertionInfo {   
+    private int start;
+
+    public int Start {
+      get { return start; }
+    }
+
+    private int end;
+
+    public int End {
+      get { return end; }
+    }
+        
+    public StopInsertionInfo(int start, int end)
+      : base() {
+        this.start = start;
+        this.end = end;
+    }
+  }
+
+  public class TourInsertionInfo {
+    public double Penalty { get; set; }
+
+    private List<StopInsertionInfo> stopInsertionInfos;
+
+    public TourInsertionInfo()
+      : base() {
+      stopInsertionInfos = new List<StopInsertionInfo>();
+    }
+
+    public void AddStopInsertionInfo(StopInsertionInfo info) {
+      stopInsertionInfos.Add(info);
+    }
+
+   public StopInsertionInfo GetStopInsertionInfo(int stop) {
+      return stopInsertionInfos[stop];
+    } 
+
+    public int GetStopCount() {
+      return stopInsertionInfos.Count;
+    }
+  }
+
+  public class InsertionInfo {
+    private List<TourInsertionInfo> tourInsertionInfos;
+    
+    public InsertionInfo()
+      : base() {
+        tourInsertionInfos = new List<TourInsertionInfo>();
+    }
+
+    public void AddTourInsertionInfo(TourInsertionInfo info) {     
+      tourInsertionInfos.Add(info);
+    }
+
+    public TourInsertionInfo GetTourInsertionInfo(int tour) {
+      return tourInsertionInfos[tour];
+    }
+  }
+  
   public class VRPEvaluation {
     public double Quality { get; set; }
     public double Distance { get; set; }
     public int VehicleUtilization { get; set; }
+    public InsertionInfo InsertionInfo { get; set; }
 
     public double Penalty { get; set; }
+
+    public VRPEvaluation() {
+      InsertionInfo = new InsertionInfo();
+    }
   }
 }
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluator.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluator.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluator.cs	(revision 6752)
@@ -109,4 +109,18 @@
     }
 
+    protected abstract double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer, out bool feasible);
+
+    public double GetInsertionCosts(IVRPProblemInstance instance, VRPEvaluation eval, int customer, int tour, int index, out bool feasible) {
+      bool tourFeasible;
+      double costs = GetTourInsertionCosts(
+        instance,
+        eval.InsertionInfo.GetTourInsertionInfo(tour), index,
+        customer, out tourFeasible);
+
+      feasible = tourFeasible;
+
+      return costs;
+    }
+
     public VRPEvaluation Evaluate(IVRPProblemInstance instance, IVRPEncoding solution) {
       VRPEvaluation evaluation = CreateTourEvaluation();
Index: /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs
===================================================================
--- /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs	(revision 6751)
+++ /branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs	(revision 6752)
@@ -230,4 +230,8 @@
     }
 
+    public double GetInsertionCosts(VRPEvaluation eval, int customer, int tour, int index, out bool feasible) {
+      return evaluator.GetInsertionCosts(this, eval, customer, tour, index, out feasible);
+    }
+
     protected void EvalBestKnownSolution() {
       if (BestKnownSolution != null) {
