Changeset 6851 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings

Timestamp:

09/29/11 15:51:56 (13 years ago)

Author:

svonolfe

Message:

Added support for multi depot CVRP instances (#1177)

Location:

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

Files:

• Alba/AlbaEncoding.cs (modified) (8 diffs)
• Alba/Creators/AlbaCreator.cs (modified) (1 diff)
• Alba/Crossovers/AlbaCrossover.cs (modified) (1 diff)
• Alba/IAlbaOperator.cs (modified) (1 diff)
• Alba/Manipulators/AlbaManipulator.cs (modified) (1 diff)
• ExtendedPotvin (added)
• ExtendedPotvin/Creators (added)
• ExtendedPotvin/Creators/ExtendedPotvinCreator.cs (added)
• ExtendedPotvin/Creators/IterativeInsertionCreator.cs (moved) (moved from branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/IterativeInsertionCreator.cs) (6 diffs)
• ExtendedPotvin/Creators/PushForwardInsertionCreator.cs (moved) (moved from branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/PushForwardInsertionCreator.cs) (4 diffs)
• ExtendedPotvin/Crossovers (added)
• ExtendedPotvin/Crossovers/ExtendedPotvinCrossover.cs (added)
• ExtendedPotvin/ExtendedPotvinEncoding.cs (added)
• ExtendedPotvin/IExtendedPotvinOperator.cs (added)
• ExtendedPotvin/Manipulators (added)
• ExtendedPotvin/Manipulators/ExtendedPotvinManipulator.cs (added)
• GVR/Crossovers/GVRCrossover.cs (modified) (1 diff)
• GVR/GVREncoding.cs (modified) (3 diffs)
• General/Crossovers/BiasedMultiVRPSolutionCrossover.cs (modified) (1 diff)
• General/Manipulators/BiasedMultiVRPSolutionManipulator.cs (modified) (1 diff)
• General/PermutationEncoding.cs (modified) (1 diff)
• General/TourEncoding.cs (modified) (2 diffs)
• Potvin/Crossovers/PotvinInsertionBasedCrossover.cs (modified) (12 diffs)
• Potvin/Crossovers/PotvinRouteBasedCrossover.cs (modified) (2 diffs)
• Potvin/Crossovers/PotvinSequenceBasedCrossover.cs (modified) (1 diff)
• Potvin/Manipulators/PotvinCustomerRelocationManipulator.cs (modified) (2 diffs)
• Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeExhaustiveMoveGenerator.cs (modified) (1 diff)
• Potvin/Moves/PickupDelivery/PDExchange/PotvinPDExchangeSingleMoveGenerator.cs (modified) (2 diffs)
• Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeExhaustiveMoveGenerator.cs (modified) (1 diff)
• Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeMoveMaker.cs (modified) (1 diff)
• Potvin/Moves/PickupDelivery/PDRearrange/PotvinPDRearrangeSingleMoveGenerator.cs (modified) (1 diff)
• Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftExhaustiveMoveGenerator.cs (modified) (1 diff)
• Potvin/Moves/PickupDelivery/PDShift/PotvinPDShiftSingleMoveGenerator.cs (modified) (1 diff)
• Potvin/PotvinEncoding.cs (modified) (4 diffs)
• Tour.cs (modified) (3 diffs)
• Zhu/Crossovers/ZhuHeuristicCrossover1.cs (modified) (1 diff)
• Zhu/Crossovers/ZhuHeuristicCrossover2.cs (modified) (1 diff)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs

@@ -33 +33 @@
   [Item("AlbaEncoding", "Represents an Alba encoding of VRP solutions. It is implemented as described in Alba, E. and Dorronsoro, B. (2004). Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms.")]
   [StorableClass]
-  public class AlbaEncoding : PermutationEncoding, IHeterogenousCapacitatedEncoding  {   
+  public class AlbaEncoding : PermutationEncoding  {   
     #region IVRPEncoding Members
     public override List<Tour> GetTours() {
+      Repair();
       List<Tour> result = new List<Tour>();
 
@@ -55 +56 @@
       if (tour.Stops.Count > 0) {
         result.Add(tour);
-      }   
+      }
 
       return result;
     }
-    #endregion
 
-    #region IHeterogenousCapacitatedEncoding Members
-
-    public int GetVehicleAssignment(int tour) {
+    public override int GetVehicleAssignment(int tour) {
       int vehicleAssignment = -1;
       Tour currentTour = GetTours()[tour];
@@ -72 +70 @@
       int lastStopIndex = this.IndexOf(lastStop);
 
-      if (lastStopIndex == this.Length - 1)
-        vehicleAssignment = this.ProblemInstance.Vehicles.Value - 1;
+      if (lastStopIndex == this.Length - 1) {
+        int i = this.Length - 1;
+
+        while (vehicleAssignment == -1) {
+          if (this.array[i] >= ProblemInstance.Cities.Value) {
+            vehicleAssignment = this.array[i] - ProblemInstance.Cities.Value;
+          }
+          
+          i--;
+        }
+      }
       else
         vehicleAssignment = this[lastStopIndex + 1] - this.ProblemInstance.Cities.Value;
@@ -80 +87 @@
     }
     #endregion
+
+    public void Repair() {
+      int cities = ProblemInstance.Cities.Value;
+
+      if (this[this.Length - 1] < cities) {
+        int index = this.Length - 2;
+        while (this[index] < cities) {
+          index--;
+        }
+
+        int vehicle = this[index];
+        for (int i = index; i < this.Length - 1; i++)
+          this[i] = this[i + 1];
+        this[Length - 1] = vehicle;
+      }
+    }
 
     public AlbaEncoding(Permutation permutation, IVRPProblemInstance instance)
@@ -100 +123 @@
     public static AlbaEncoding ConvertFrom(List<int> routeParam, IVRPProblemInstance instance) {
       List<int> route = new List<int>(routeParam);
-      route.RemoveAt(routeParam.Count - 1);
       
       int cities = instance.Cities.Value;
@@ -129 +151 @@
       int emptyVehicles = instance.Vehicles.Value - tours.Count;
 
-      int[] array = new int[cities + tours.Count + emptyVehicles - 1];
+      int[] array = new int[cities + tours.Count + emptyVehicles];
       int delimiter = 0;
       int arrayIndex = 0;
@@ -140 +162 @@
 
         if (arrayIndex != array.Length) {
-          if (encoding is IHeterogenousCapacitatedEncoding) {
-            array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
-          } else {
-            array[arrayIndex] = cities + delimiter;
-          }
+          array[arrayIndex] = cities + encoding.GetVehicleAssignment(delimiter);
           
           delimiter++;
@@ -151 +169 @@
       }
 
-      for (int i = 0; i < emptyVehicles - 1; i++) {
-        if (encoding is IHeterogenousCapacitatedEncoding) {
-          array[arrayIndex] = cities + (encoding as IHeterogenousCapacitatedEncoding).GetVehicleAssignment(delimiter);
-        } else {
-          array[arrayIndex] = cities + delimiter;
-        }
+      for (int i = 0; i < emptyVehicles; i++) {
+        array[arrayIndex] = cities + encoding.GetVehicleAssignment(delimiter);
 
         delimiter++;

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

@@ -47 +47 @@
       : base(original, cloner) {
     }
+
+    public override IOperation Apply() {
+      (VRPToursParameter.ActualValue as AlbaEncoding).Repair();
+
+      return base.Apply();
+    }
   }
 }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Crossovers/AlbaCrossover.cs

@@ -67 +67 @@
 
       ChildParameter.ActualValue = 
-        Crossover(RandomParameter.ActualValue, parents[0] as AlbaEncoding, parents[1] as AlbaEncoding);  
+        Crossover(RandomParameter.ActualValue, parents[0] as AlbaEncoding, parents[1] as AlbaEncoding);
+      (ChildParameter.ActualValue as AlbaEncoding).Repair();
 
       return base.Apply();

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/IAlbaOperator.cs

@@ -32 +32 @@
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Alba {
-  public interface IAlbaOperator: 
-    ISingleDepotOperator, IHeterogenousCapacitatedOperator, ITimeWindowedOperator {    
+  public interface IAlbaOperator:
+    ISingleDepotOperator, IHeterogenousCapacitatedOperator, IMultiDepotOperator, ITimeWindowedOperator {    
   }
 }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/Manipulators/AlbaManipulator.cs

@@ -71 +71 @@
 
       Manipulate(RandomParameter.ActualValue, VRPToursParameter.ActualValue as AlbaEncoding);
+      (VRPToursParameter.ActualValue as AlbaEncoding).Repair();
 
       return base.Apply();

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

@@ -33 +33 @@
 using HeuristicLab.Problems.VehicleRouting.Variants;
 
-namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.ExtendedPotvin {
   [Item("IterativeInsertionCreator", "Creates a randomly initialized VRP solution.")]
   [StorableClass]
-  public sealed class IterativeInsertionCreator : PotvinCreator, IStochasticOperator {
+  public sealed class IterativeInsertionCreator : ExtendedPotvinCreator, IStochasticOperator {
     #region IStochasticOperator Members
     public ILookupParameter<IRandom> RandomParameter {
@@ -65 +65 @@
 
     private static double CalculateAngleToDepot(IVRPProblemInstance instance, int city) {
-      double dx = instance.Coordinates[0, 0];
-      double dy = instance.Coordinates[0, 1];
+      double dx = instance.GetCoordinates(0)[0];
+      double dy = instance.GetCoordinates(0)[1];
 
-      double cx = instance.Coordinates[city, 0];
-      double cy = instance.Coordinates[city, 1];
+      double cx = instance.GetCoordinates(city)[0];
+      double cy = instance.GetCoordinates(city)[1];
 
       double alpha = Math.Atan((cx - dx) / (dy - cy)) * (180.0 / Math.PI);
@@ -82 +82 @@
     }
 
-    private static PotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, bool adhereTimeWindows) {
-      PotvinEncoding result = new PotvinEncoding(instance);
+    private static ExtendedPotvinEncoding CreateSolution(IVRPProblemInstance instance, IRandom random, bool adhereTimeWindows) {
+      ExtendedPotvinEncoding result = new ExtendedPotvinEncoding(instance);
 
       IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance; 
@@ -89 +89 @@
       List<int> customers = new List<int>();
       for (int i = 1; i <= instance.Cities.Value; i++)
-        if(pdp == null || pdp.Demand[i] >= 0)
+        if(pdp == null || pdp.GetDemand(i) >= 0)
           customers.Add(i);
 
@@ -107 +107 @@
         int index = (i + j) % customers.Count;
 
-        int stopIdx = result.FindBestInsertionPlace(currentTour, customers[index]);
+        int stopIdx = 0;
+        if(currentTour.Stops.Count > 0)
+          result.FindBestInsertionPlace(currentTour, customers[index]);
         currentTour.Stops.Insert(stopIdx, customers[index]);
 
@@ -122 +124 @@
               currentTour.Stops.Remove(pdp.PickupDeliveryLocation[customers[index]]);
 
-          if(currentTour.Stops.Count > 0)
-            result.Tours.Add(currentTour);
+          if (currentTour.Stops.Count == 0)
+            result.Tours.Remove(currentTour);
           currentTour = new Tour();
+          result.Tours.Add(currentTour);
           
           currentTour.Stops.Add(customers[index]);

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

@@ -33 +33 @@
 using HeuristicLab.Problems.VehicleRouting.Variants;
 
-namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
+namespace HeuristicLab.Problems.VehicleRouting.Encodings.ExtendedPotvin {
   [Item("PushForwardInsertionCreator", "Creates a randomly initialized VRP solution.")]
   [StorableClass]
-  public sealed class PushForwardInsertionCreator : PotvinCreator, IStochasticOperator {
+  public sealed class PushForwardInsertionCreator : ExtendedPotvinCreator, IStochasticOperator {
     #region IStochasticOperator Members
     public ILookupParameter<IRandom> RandomParameter {
@@ -99 +99 @@
     }
 
-    private static double Distance(IVRPProblemInstance problemInstance, int start, int end) {
-      return problemInstance.GetDistance(start, end);
-    }
-
-    private static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
+    private static double GetDistance(int start, int end, IVRPProblemInstance problemInstance) {
+      double distance = 0.0;
+
+      double startX = problemInstance.Coordinates[start, 0];
+      double startY = problemInstance.Coordinates[start, 1];
+
+      double endX = problemInstance.Coordinates[end, 0];
+      double endY = problemInstance.Coordinates[end, 1];
+
+      distance =
+          Math.Sqrt(
+            Math.Pow(startX - endX, 2) +
+            Math.Pow(startY - endY, 2));
+
+      return distance;
+    }
+
+    private static ExtendedPotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
       double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
       double alphaVariance = 0.5, double betaVariance = 0.07, double gammaVariance = 0.14) {
-      PotvinEncoding result = new PotvinEncoding(problemInstance);
+      ExtendedPotvinEncoding result = new ExtendedPotvinEncoding(problemInstance);
 
       double alpha, beta, gamma;
@@ -113 +126 @@
       gamma = N(gammaValue, Math.Sqrt(gammaVariance), random);
 
-      double x0 = problemInstance.Coordinates[0, 0];
-      double y0 = problemInstance.Coordinates[0, 1];
+      int totalTours = 0;
+
       double distance = 0;
       double cost = 0;
@@ -121 +134 @@
 
       IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
-
-      /*-----------------------------------------------------------------------------
-       * generate cost list
-       *-----------------------------------------------------------------------------
-       */
-      for (int i = 1; i <= problemInstance.Cities.Value; 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
-
-          int index = 0;
-          while (index < costList.Count && costList[index] < cost) index++;
-
-          costList.Insert(index, cost);
-
-          unroutedList.Insert(index, i);
-        }
+      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
+
+      int depots = 1;
+      if (mdp != null) {
+        depots = mdp.Depots.Value;
+        for (int i = 0; i < result.VehicleAssignment.Length; i++)
+          result.VehicleAssignment[i] = -1;
       }
 
-      double minimumCost = double.MaxValue;
-      int indexOfMinimumCost = -1;
-      int indexOfMinimumCost2 = -1;
-      int indexOfCustomer = -1;
-
-      Tour tour = new Tour();
-      result.Tours.Add(tour);
-
-      tour.Stops.Add(unroutedList[0]);
-
-      if (pdp != null) {
-        tour.Stops.Add(pdp.PickupDeliveryLocation[unroutedList[0]]);
-      }
-
-      unroutedList.RemoveAt(0);
-
-      while (unroutedList.Count > 0) {
-        for (int c = 0; c < unroutedList.Count; c++) {
-          VRPEvaluation eval =
-          problemInstance.EvaluateTour(tour, result);
-          double originalCosts = eval.Quality;
-          int customer = unroutedList[c];
-
-          for (int i = 0; i <= tour.Stops.Count; i++) {
-            tour.Stops.Insert(i, customer);
-            eval = problemInstance.EvaluateTour(tour, result);
-            double tourCost = eval.Quality - originalCosts;
-
-            if (pdp != null) {
-              for (int j = i + 1; j <= tour.Stops.Count; j++) {
-                bool feasible;
-                cost = tourCost +
-                  problemInstance.GetInsertionCosts(eval, pdp.PickupDeliveryLocation[unroutedList[c]], 0, j, out feasible);
+      List<int> unrouted = new List<int>();
+      for (int i = 1; i <= problemInstance.Cities.Value; i++)
+        if (pdp == null || problemInstance.GetDemand(i) >= 0)
+          unrouted.Add(i);
+
+      for (int depot = 0; depot < depots; depot++) {
+        int vehicleCount = problemInstance.Vehicles.Value;
+        List<int> vehicles = new List<int>();
+        if (mdp != null) {
+          vehicleCount = 0;
+          for (int i = 0; i < mdp.VehicleDepotAssignment.Length; i++) {
+            if (mdp.VehicleDepotAssignment[i] == depot) {
+              vehicleCount++;
+              vehicles.Add(i);
+            }
+          }
+        } else {
+          for (int i = 0; i < problemInstance.Vehicles.Value; i++)
+            vehicles.Add(i);
+        }
+
+        costList.Clear();
+        unroutedList.Clear();
+
+        double x0 = problemInstance.Coordinates[depot, 0];
+        double y0 = problemInstance.Coordinates[depot, 1];
+
+        /*-----------------------------------------------------------------------------
+        * generate cost list
+        *-----------------------------------------------------------------------------
+        */
+        for (int i = 1; i <= problemInstance.Cities.Value; i++) {
+          //only insert sources
+          if (unrouted.Contains(i) && (pdp == null || problemInstance.GetDemand(i) >= 0)) {
+            distance = GetDistance(i + depots - 1, depot, problemInstance);
+            if (problemInstance.Coordinates[i + depots - 1, 0] < x0) distance = -distance;
+
+            double dueTime = 0;
+            if (problemInstance is ITimeWindowedProblemInstance)
+              dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[i];
+
+            cost = -alpha * distance + // distance 0 <-> City[i]
+                   beta * dueTime + // latest arrival time
+                   gamma * (Math.Asin((problemInstance.Coordinates[i + depots - 1, 0] - y0) / distance) / 360 * distance); // polar angle
+
+            int index = 0;
+            while (index < costList.Count && costList[index] < cost) index++;
+
+            costList.Insert(index, cost);
+
+            unroutedList.Insert(index, i);
+          }
+        }
+
+        int tours = 0;
+        double minimumCost = double.MaxValue;
+        int indexOfMinimumCost = -1;
+        int indexOfMinimumCost2 = -1;
+        int indexOfCustomer = -1;
+
+        Tour tour = new Tour();
+        result.Tours.Add(tour);
+        result.VehicleAssignment[totalTours] = vehicles[0];
+        vehicles.RemoveAt(0);
+        tours++;
+        totalTours++;
+
+        tour.Stops.Add(unroutedList[0]);
+
+        if (pdp != null) {
+          tour.Stops.Add(pdp.PickupDeliveryLocation[unroutedList[0]]);
+        }
+
+        unrouted.Remove(unroutedList[0]);
+        unroutedList.RemoveAt(0);
+
+        while (unroutedList.Count > 0 && (tours < vehicleCount || depot == depots - 1)) {
+          for (int c = 0; c < unroutedList.Count; c++) {
+            VRPEvaluation eval = problemInstance.EvaluateTour(tour, result);
+            double originalCosts = eval.Quality;
+            int customer = unroutedList[c];
+
+            for (int i = 0; i <= tour.Stops.Count; i++) {
+              tour.Stops.Insert(i, customer);
+              eval = problemInstance.EvaluateTour(tour, result);
+              double tourCost = eval.Quality - originalCosts;
+
+              if (pdp != null) {
+                for (int j = i + 1; j <= tour.Stops.Count; j++) {
+                  bool feasible;
+                  cost = tourCost +
+                    problemInstance.GetInsertionCosts(eval, result, pdp.PickupDeliveryLocation[unroutedList[c]], 0, j, out feasible);
+                  if (cost < minimumCost && feasible) {
+                    minimumCost = cost;
+                    indexOfMinimumCost = i;
+                    indexOfMinimumCost2 = j;
+                    indexOfCustomer = c;
+                  }
+                }
+              } else {
+                cost = tourCost;
+                bool feasible = problemInstance.Feasible(eval);
                 if (cost < minimumCost && feasible) {
                   minimumCost = cost;
                   indexOfMinimumCost = i;
-                  indexOfMinimumCost2 = j;
                   indexOfCustomer = c;
                 }
               }
-            } else {
-              cost = tourCost;
-              bool feasible = problemInstance.Feasible(eval);
-              if (cost < minimumCost && feasible) {
-                minimumCost = cost;
-                indexOfMinimumCost = i;
-                indexOfCustomer = c;
-              }
+
+              tour.Stops.RemoveAt(i);
             }
-
-            tour.Stops.RemoveAt(i);            
-          }
-        }
-
-        // insert customer if found
-        if (indexOfMinimumCost != -1) {
-          tour.Stops.Insert(indexOfMinimumCost, unroutedList[indexOfCustomer]);
-          if (pdp != null) {
-            tour.Stops.Insert(indexOfMinimumCost2, pdp.PickupDeliveryLocation[unroutedList[indexOfCustomer]]);
-          }
-
-          unroutedList.RemoveAt(indexOfCustomer);
-        } else { // no feasible customer found
-          tour = new Tour();
-          result.Tours.Add(tour);
-
-          tour.Stops.Add(unroutedList[0]);
-          if (pdp != null) {
-            tour.Stops.Add(pdp.PickupDeliveryLocation[unroutedList[0]]);
-          }
-
-          unroutedList.RemoveAt(0);
-        }
-        // reset minimum    
-        minimumCost = double.MaxValue;
-        indexOfMinimumCost = -1;
-        indexOfMinimumCost2 = -1;
-        indexOfCustomer = -1;
+          }
+
+          // insert customer if found
+          if (indexOfMinimumCost != -1) {
+            tour.Stops.Insert(indexOfMinimumCost, unroutedList[indexOfCustomer]);
+            if (pdp != null) {
+              tour.Stops.Insert(indexOfMinimumCost2, pdp.PickupDeliveryLocation[unroutedList[indexOfCustomer]]);
+            }
+
+            unrouted.Remove(unroutedList[indexOfCustomer]);
+            unroutedList.RemoveAt(indexOfCustomer);
+          } else if (tours < vehicleCount || depot == depots - 1) { // no feasible customer found
+            tour = new Tour();
+            result.Tours.Add(tour);
+            result.VehicleAssignment[totalTours] = vehicles[0];
+            vehicles.RemoveAt(0);
+            tours++;
+            totalTours++;
+
+            tour.Stops.Add(unroutedList[0]);
+            if (pdp != null) {
+              tour.Stops.Add(pdp.PickupDeliveryLocation[unroutedList[0]]);
+            }
+
+            unrouted.Remove(unroutedList[0]);
+            unroutedList.RemoveAt(0);
+          }
+          // reset minimum    
+          minimumCost = double.MaxValue;
+          indexOfMinimumCost = -1;
+          indexOfMinimumCost2 = -1;
+          indexOfCustomer = -1;
+        }
+      }
+
+      if (mdp != null) {
+        List<int> availableVehicles = new List<int>();
+        for (int i = 0; i < mdp.Vehicles.Value; i++)
+          availableVehicles.Add(i);
+
+        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
+          if (result.VehicleAssignment[i] != -1)
+            availableVehicles.Remove(result.VehicleAssignment[i]);
+        }
+
+        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
+          if (result.VehicleAssignment[i] == -1) {
+            result.VehicleAssignment[i] = availableVehicles[0];
+            availableVehicles.RemoveAt(0);
+          }
+        }
       }
 

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/GVR/Crossovers/GVRCrossover.cs

@@ -82 +82 @@
       for (int i = 1; i <= ProblemInstance.Cities.Value; i++) {
         if (!subroute.Contains(i)) {
-          double distance = ProblemInstance.GetDistance(subroute[0], i);
+          double distance = ProblemInstance.GetDistance(subroute[0], i, child);
 
           if (customer == -1 || distance < minDistance) {

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/GVR/GVREncoding.cs

@@ -42 +42 @@
         double currentDemand = 0;
 
-        DoubleArray demand = ProblemInstance.Demand;
         DoubleValue capacity = new DoubleValue(double.MaxValue);
         if (ProblemInstance is IHomogenousCapacitatedProblemInstance) {
@@ -50 +49 @@
 
         foreach (int city in tour.Stops) {
-          currentDemand += demand[city];
+          currentDemand += ProblemInstance.GetDemand(city);
 
           if (currentDemand > capacity.Value) {
@@ -58 +57 @@
             newTour = new Tour();
             newTour.Stops.Add(city);
-            currentDemand = demand[city];
+            currentDemand = ProblemInstance.GetDemand(city);
           } else {
             newTour.Stops.Add(city);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Crossovers/BiasedMultiVRPSolutionCrossover.cs

@@ -160 +160 @@
       OperationCollection next = new OperationCollection(successorOp);
       if (successor != null) {
-        SelectedOperatorParameter.ActualValue = new StringValue(successor.GetType().Name);
+        SelectedOperatorParameter.ActualValue = new StringValue(successor.Name);
 
         if (CreateChildOperation)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Manipulators/BiasedMultiVRPSolutionManipulator.cs

@@ -160 +160 @@
       OperationCollection next = new OperationCollection(successorOp);
       if (successor != null) {
-        SelectedOperatorParameter.ActualValue = new StringValue(successor.GetType().Name);
+        SelectedOperatorParameter.ActualValue = new StringValue(successor.Name);
 
         if (CreateChildOperation)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/PermutationEncoding.cs

@@ -35 +35 @@
     #region IVRPEncoding Members
     public abstract List<Tour> GetTours();
+
+    public int GetTourIndex(Tour tour) {
+      int index = -1;
+
+      List<Tour> tours = GetTours();
+      for (int i = 0; i < tours.Count; i++) {
+        if (tours[i].IsEqual(tour)) {
+          index = i;
+          break;
+        }
+      }
+
+      return index;
+    }
+
+    public virtual int GetVehicleAssignment(int tour) {
+      return tour;
+    }
     #endregion
 

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs

@@ -38 +38 @@
     
     #region IVRPEncoding Members
-    public void Repair() {
+    public virtual void Repair() {
       List<Tour> toBeRemoved = new List<Tour>();
       foreach (Tour tour in Tours) {
@@ -62 +62 @@
 
      return result;
+    }
+
+    public int GetTourIndex(Tour tour) {
+      int index = -1;
+
+      for (int i = 0; i < Tours.Count; i++) {
+        if (Tours[i].IsEqual(tour)) {
+          index = i;
+          break;
+        }
+      }
+
+      return index;
+    }
+
+    public virtual int GetVehicleAssignment(int tour) {
+      return tour;
     }
 

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

@@ -28 +28 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
+using HeuristicLab.Problems.VehicleRouting.Interfaces;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -74 +75 @@
     }
 
-    private double CalculateCentroidDistance(Tour t1, Tour t2, DoubleMatrix coordinates) {
+    private double CalculateCentroidDistance(Tour t1, Tour t2, IVRPProblemInstance instance) {
       double xSum = 0;
       double ySum = 0;
@@ -80 +81 @@
 
       for (int i = 0; i < t1.Stops.Count; i++) {
-        xSum += coordinates[t1.Stops[i], 0];
-        ySum += coordinates[t1.Stops[i], 1];
+        xSum += instance.GetCoordinates(t1.Stops[i])[0];
+        ySum += instance.GetCoordinates(t1.Stops[i])[1];
       }
       c1X = xSum / t1.Stops.Count;
@@ -87 +88 @@
 
       for (int i = 0; i < t2.Stops.Count; i++) {
-        xSum += coordinates[t2.Stops[i], 0];
-        ySum += coordinates[t2.Stops[i], 1];
+        xSum += instance.GetCoordinates(t2.Stops[i])[0];
+        ySum += instance.GetCoordinates(t2.Stops[i])[1];
       }
       c2X = xSum / t1.Stops.Count;
@@ -98 +99 @@
     }
 
-    private double CalculateMeanCentroidDistance(Tour t1, IList<Tour> tours, DoubleMatrix coordinates) {
+    private double CalculateMeanCentroidDistance(Tour t1, IList<Tour> tours, IVRPProblemInstance instance) {
       double sum = 0;
 
       for (int i = 0; i < tours.Count; i++) {
-        sum += CalculateCentroidDistance(t1, tours[i], coordinates);
+        sum += CalculateCentroidDistance(t1, tours[i], instance);
       }
 
@@ -108 +109 @@
     }
 
-    private int SelectCityBiasedByNeighborDistance(IRandom random, Tour tour) {
+    private int SelectCityBiasedByNeighborDistance(IRandom random, Tour tour, IVRPEncoding solution) {
       int cityIndex = -1;
 
@@ -120 +121 @@
           next = tour.Stops[i + 1];
         double distance = ProblemInstance.GetDistance(
-          tour.Stops[i], next);
+          tour.Stops[i], next, solution);
 
         int prev;
@@ -128 +129 @@
           prev = tour.Stops[i - 1];
         distance += ProblemInstance.GetDistance(
-          tour.Stops[i], prev);
+          tour.Stops[i], prev, solution);
 
         probabilities[i] = distance;
@@ -168 +169 @@
       for (int i = 0; i <= tour.Stops.Count; i++) {
         bool feasible;
-        double detour = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);
+        double detour = ProblemInstance.GetInsertionCosts(eval, individual, city, 0, i, out feasible);
         if (feasible || allowInfeasible) {
           if (place < 0 || detour < minDetour) {
@@ -195 +196 @@
 
     protected override PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2) {
-      PotvinEncoding child = new PotvinEncoding(ProblemInstance);
+      PotvinEncoding child = parent1.Clone() as PotvinEncoding;
+      child.Tours.Clear();
 
       bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
@@ -213 +215 @@
         List<int> R2 = new List<int>();
 
-        double r = CalculateMeanCentroidDistance(r1, parent2.Tours, ProblemInstance.Coordinates);
+        double r = CalculateMeanCentroidDistance(r1, parent2.Tours, ProblemInstance);
         foreach (Tour tour in parent2.Tours) {
-          if (CalculateCentroidDistance(r1, tour, ProblemInstance.Coordinates) <= r) {
+          if (CalculateCentroidDistance(r1, tour, ProblemInstance) <= r) {
             R2.AddRange(tour.Stops);
           }
@@ -227 +229 @@
         int removed = random.Next(1, r1.Stops.Count + 1);
         for (int i = 0; i < removed; i++) {
-          childTour.Stops.RemoveAt(SelectCityBiasedByNeighborDistance(random, childTour));
+          childTour.Stops.RemoveAt(SelectCityBiasedByNeighborDistance(random, childTour, child));
         }
 
         //REPAIR - add cities from R2
-        int maxCount = random.Next(1, Math.Min(5, R2.Count));
+        int maxCount = 1;
+        if(R2.Count > 1)
+          maxCount = random.Next(1, Math.Min(5, R2.Count));
         int count = 0;
 

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

@@ -26 +26 @@
 using HeuristicLab.Data;
 using HeuristicLab.Common;
+using HeuristicLab.Problems.VehicleRouting.Encodings.ExtendedPotvin;
 
 namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
@@ -57 +58 @@
 
       child.Tours.Remove(replaced);
-      child.Tours.Add(replacing);
+      child.Tours.Insert(tourParent2, replacing);
+
+      if (parent1 is ExtendedPotvinEncoding && child is ExtendedPotvinEncoding) {
+        Permutation vehicleAssignment = (child as ExtendedPotvinEncoding).VehicleAssignment;
+
+        int vehicle = vehicleAssignment[tourParent2];
+        int vehicle2 = (parent1 as ExtendedPotvinEncoding).VehicleAssignment[tourParent1];
+        vehicleAssignment[tourParent2] = vehicle2;
+
+        for (int i = 0; i < vehicleAssignment.Length; i++) {
+          if (vehicleAssignment[i] == vehicle2 && i != tourParent2) {
+            vehicleAssignment[i] = vehicle;
+            break;
+          }
+        }        
+      }
 
       foreach (int city in replaced.Stops)

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

@@ -67 +67 @@
         newTour.Stops.Add(tour2.Stops[i]);
 
+      int tour1Index = child.Tours.IndexOf(tour1);
       child.Tours.Remove(tour1);
-      child.Tours.Add(newTour);
+      child.Tours.Insert(tour1Index, newTour);
 
       foreach (int city in tour1.Stops)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinCustomerRelocationManipulator.cs

@@ -67 +67 @@
         for (int i = 0; i < route1.Stops.Count; i++) {
           int stop = route1.Stops[i];
-          if (ProblemInstance.Demand[stop] < 0) {
+          if (ProblemInstance.GetDemand(stop) < 0) {
             int source = pdp.PickupDeliveryLocation[stop];
 
@@ -158 +158 @@
 
             //drive there
-            double currentDistace = vrptw.GetDistance(start, end);
+            double currentDistace = vrptw.GetDistance(start, end, individual);
             time += currentDistace;
 

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

@@ -62 +62 @@
             if (k != i) {
               int city1 = individual.Tours[i].Stops[j];
-              if (pdp == null || pdp.Demand[city1] >= 0) {
+              if (pdp == null || pdp.GetDemand(city1) >= 0) {
                 for (int l = 0; l < individual.Tours[k].Stops.Count; l++) {
                   int city2 = individual.Tours[k].Stops[l];
-                  if (pdp == null || pdp.Demand[city2] >= 0) {
+                  if (pdp == null || pdp.GetDemand(city2) >= 0) {
                     bool valid = pdp == null ||
                       (pdp.PickupDeliveryLocation[city2] != pdp.PickupDeliveryLocation[city1] &&

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

@@ -62 +62 @@
       IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
       for (int i = 1; i <= individual.Cities; i++) {
-        if (pdp == null || pdp.Demand[i] >= 0)
+        if (pdp == null || pdp.GetDemand(i) >= 0)
           cities.Add(i);
       }
@@ -84 +84 @@
         foreach (int stop in newTour.Stops) {
           if (pdp == null ||
-            (pdp.Demand[stop] >= 0 &&
+            (pdp.GetDemand(stop) >= 0 &&
              pdp.PickupDeliveryLocation[stop] != pdp.PickupDeliveryLocation[city] &&
              pdp.PickupDeliveryLocation[stop] != city &&

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

@@ -54 +54 @@
 
       for (int i = 1; i <= problemInstance.Cities.Value; i++) {
-        if (pdp == null || pdp.Demand[i] >= 0) {
+        if (pdp == null || pdp.GetDemand(i) >= 0) {
           int tour = individual.Tours.FindIndex(t => t.Stops.Contains(i));
 

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

@@ -74 +74 @@
           if (positionToAvoid != i || positionToAvoid2 != j || stops == 0) {
             bool feasible;
-            double targetCosts = problemInstance.GetInsertionCosts(tourEval, target, 0, j, out feasible);
+            double targetCosts = problemInstance.GetInsertionCosts(tourEval, solution, target, 0, j, out feasible);
 
             double costs = sourceCosts + targetCosts;

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

@@ -62 +62 @@
       IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
       for (int i = 1; i <= individual.Cities; i++) {
-        if(pdp == null || pdp.Demand[i] >= 0)
+        if(pdp == null || pdp.GetDemand(i) >= 0)
           cities.Add(i);
       }

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

@@ -62 +62 @@
             if (k != i) {
               int city = individual.Tours[i].Stops[j];
-              if (pdp == null || pdp.Demand[city] >= 0) {
+              if (pdp == null || pdp.GetDemand(city) >= 0) {
                 PotvinPDShiftMove move = new PotvinPDShiftMove(
                   city, i, k, individual);

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

@@ -62 +62 @@
       IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
       for (int i = 1; i <= individual.Cities; i++) {
-        if(pdp == null || pdp.Demand[i] >= 0)
+        if(pdp == null || pdp.GetDemand(i) >= 0)
           cities.Add(i);
       }

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

@@ -45 +45 @@
 
     [StorableConstructor]
-    private PotvinEncoding(bool serializing)
+    protected PotvinEncoding(bool serializing)
       : base(serializing) {
     }
@@ -75 +75 @@
 
     public double GetTourLength(Tour tour) {
-      return tour.GetTourLength(ProblemInstance);
+      return tour.GetTourLength(ProblemInstance, this);
     }
 
@@ -87 +87 @@
         if (positionToAvoid != i) {
           bool feasible;
-          double quality = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);
+          double quality = ProblemInstance.GetInsertionCosts(eval, this, city, 0, i, out feasible);
           if (place < 0 || quality < minQuality) {
             place = i;
@@ -115 +115 @@
           for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
             bool feasible;
-            double detour = ProblemInstance.GetInsertionCosts(eval, city, tour, i, out feasible);
-            
+            double detour = ProblemInstance.GetInsertionCosts(eval, this, city, tour, i, out feasible);
+
             if (feasible || allowInfeasible) {
               if (route < 0 || detour < minDetour) {

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

@@ -48 +48 @@
     }
 
-    public double GetTourLength(IVRPProblemInstance instance) {
+    public double GetTourLength(IVRPProblemInstance instance, IVRPEncoding solution) {
       double length = 0;
 
@@ -60 +60 @@
 
         for (int i = 1; i < cities.Count; i++) {
-          length += instance.GetDistance(cities[i - 1], cities[i]);
+          length += instance.GetDistance(cities[i - 1], cities[i], solution);
         }
       }
@@ -66 +66 @@
       return length;
     }
+
+    public bool IsEqual(Tour tour) {
+      bool equal = (tour != null) && (tour.Stops.Count == Stops.Count);
+      int index = 0;
+
+      while (equal && index < Stops.Count) {
+        equal = equal && tour.Stops[index] == Stops[index];
+        index++;
+      }      
+
+      return equal;
+    }
   }
 }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Zhu/Crossovers/ZhuHeuristicCrossover1.cs

@@ -77 +77 @@
 
         if (ProblemInstance.GetDistance(
-          child[i] + 1, parent1[(i + 1) % child.Length] + 1)
+          child[i] + 1, parent1[(i + 1) % child.Length] + 1, child)
           <
           ProblemInstance.GetDistance(
-          child[i] + 1, parent2[(i + 1) % child.Length] + 1)) {
+          child[i] + 1, parent2[(i + 1) % child.Length] + 1, child)) {
           child[(i + 1) % child.Length] = parent1[(i + 1) % child.Length];
           Swap(parent2, parent2[(i + 1) % child.Length], parent1[(i + 1) % child.Length]);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Zhu/Crossovers/ZhuHeuristicCrossover2.cs

@@ -79 +79 @@
 
         if (ProblemInstance.GetDistance(
-         child[i] + 1, p1[parent1Index] + 1)
+         child[i] + 1, p1[parent1Index] + 1, child)
          <
          ProblemInstance.GetDistance(
-         child[i] + 1, p2[parent2Index] + 1)) {
+         child[i] + 1, p2[parent2Index] + 1, child)) {
           child[(i + 1) % child.Length] = p1[parent1Index];
         } else {