Changeset 6870 for branches/VRP

Timestamp:

10/05/11 15:54:51 (13 years ago)

Author:

svonolfe

Message:

Improved the performance of the PFIH for multi depot problem instances (#1177)

File:

• branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/PushForwardInsertionCreator.cs (modified) (2 diffs)

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

@@ -116 +116 @@
     }
 
-    private static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
+    private static int GetNearestDepot(IVRPProblemInstance problemInstance, List<int> depots, int customer, 
+      double alpha, double beta, double gamma, out double minCost) {
+      int nearest = -1;
+      minCost = double.MaxValue;
+
+      int depotCount = 1;
+      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
+      if (mdp != null) {
+        depotCount = mdp.Depots.Value;
+      }
+
+      foreach (int depot in depots) {
+        double x0 = problemInstance.Coordinates[depot, 0];
+        double y0 = problemInstance.Coordinates[depot, 1];
+
+        double distance = GetDistance(customer + depotCount - 1, depot, problemInstance);
+       
+        double dueTime = 0;
+        if (problemInstance is ITimeWindowedProblemInstance)
+          dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[customer + depotCount - 1];
+        if (dueTime == double.MaxValue)
+          dueTime = 0;
+
+        double dist;
+        if (problemInstance.Coordinates[customer + depotCount - 1, 0] < x0)
+          dist = -distance;
+        else
+          dist = distance;
+
+        double cost = alpha * distance + // distance 0 <-> City[i]
+                   -beta * dueTime + // latest arrival time
+                   -gamma * (Math.Asin((problemInstance.Coordinates[customer + depotCount - 1, 1] - y0) / dist) / 360 * dist); // polar angle
+
+        if (cost < minCost) {
+          minCost = cost;
+          nearest = depot;
+        }
+      }
+
+      return nearest;
+    }
+
+    private static List<int> SortCustomers(IVRPProblemInstance problemInstance, List<int> customers, List<int> depots, 
+      Dictionary<int, int> depotAssignment, 
+      double alpha, double beta, double gamma) {
+      List<int> sortedCustomers = new List<int>();
+      depotAssignment.Clear();
+
+      List<double> costList = new List<double>();
+
+      for (int i = 0; i < customers.Count; i++) {
+        double cost;
+        int depot = GetNearestDepot(problemInstance, depots, customers[i], 
+          alpha, beta, gamma,
+          out cost);
+        depotAssignment[customers[i]] = depot;
+
+        int index = 0;
+        while (index < costList.Count && costList[index] < cost) index++;
+        costList.Insert(index, cost);
+        sortedCustomers.Insert(index, customers[i]);
+      }
+
+      return sortedCustomers;
+    }
+
+    private static bool RemoveUnusedDepots(List<int> depots, Dictionary<int, List<int>> vehicles) {
+      List<int> toBeRemoved = new List<int>();
+
+      foreach (int depot in depots) {
+        if (vehicles[depot].Count == 0)
+          toBeRemoved.Add(depot);
+      }
+
+      foreach (int depot in toBeRemoved) {
+        depots.Remove(depot);
+        vehicles.Remove(depot);
+      }
+
+      return toBeRemoved.Count > 0;
+    }
+
+    public static PotvinEncoding 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);
+
+      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
+      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
 
       double alpha, beta, gamma;
@@ -126 +211 @@
       gamma = N(gammaValue, Math.Sqrt(gammaVariance), random);
 
-      int totalTours = 0;
-
-      double distance = 0;
-      double cost = 0;
-      List<int> unroutedList = new List<int>();
-      List<double> costList = new List<double>();
-
-      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
-      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
-
-      int depots = 1;
+      List<int> unroutedCustomers = new List<int>();
+      for (int i = 1; i <= problemInstance.Cities.Value; i++) {
+        if (pdp == null ||
+           (problemInstance.GetDemand(i) >= 0 ||
+            pdp.GetPickupDeliveryLocation(i) <= 0))
+          unroutedCustomers.Add(i);
+      }
+
+      List<int> depots = new List<int>();
       if (mdp != null) {
-        depots = mdp.Depots.Value;
-        for (int i = 0; i < result.VehicleAssignment.Length; i++)
-          result.VehicleAssignment[i] = -1;
-      }
-
-      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++) {
+        for (int i = 0; i < mdp.Depots.Value; i++) {
+          depots.Add(i);
+        }
+      } else {
+        depots.Add(0);
+      }
+
+      Dictionary<int, List<int>> vehicles = new Dictionary<int, List<int>>();
+      foreach (int depot in depots) {
+        vehicles[depot] = new List<int>();
+
         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);
+          for (int vehicle = 0; vehicle < mdp.VehicleDepotAssignment.Length; vehicle++) {
+            if (mdp.VehicleDepotAssignment[vehicle] == depot) {
+              vehicles[depot].Add(vehicle);
             }
           }
         } 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 + depots - 1];
-
-            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;
+          for (int vehicle = 0; vehicle < vehicleCount; vehicle++) {
+            vehicles[depot].Add(vehicle);
+          }
+        }
+      }
+
+      RemoveUnusedDepots(depots, vehicles);
+      Dictionary<int, int> depotAssignment = new Dictionary<int, int>();
+
+      unroutedCustomers = SortCustomers(
+        problemInstance, unroutedCustomers, depots, depotAssignment,
+        alpha, beta, gamma);
+
+      /////////
+      Tour tour = new Tour();
+      result.Tours.Add(tour);
+      int currentCustomer = unroutedCustomers[0];
+      unroutedCustomers.RemoveAt(0);
+
+      int currentDepot = depotAssignment[currentCustomer];
+      int currentVehicle = vehicles[currentDepot][0];
+      vehicles[currentDepot].RemoveAt(0);
+      if (RemoveUnusedDepots(depots, vehicles)) {
+        unroutedCustomers = SortCustomers(
+        problemInstance, unroutedCustomers, depots, depotAssignment,
+        alpha, beta, gamma);
+      }
+
+      result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
+
+      tour.Stops.Add(currentCustomer);
+      if (pdp != null && pdp.GetPickupDeliveryLocation(currentCustomer) > 0) {
+        tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));
+      }
+      ////////
+
+      while (unroutedCustomers.Count > 0) {
         double minimumCost = double.MaxValue;
+        int customer = -1;
         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.GetPickupDeliveryLocation(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.GetPickupDeliveryLocation(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);
+
+        foreach (int unrouted in unroutedCustomers) {
+          VRPEvaluation eval = problemInstance.EvaluateTour(tour, result);
+          double originalCosts = eval.Quality;
+
+          for (int i = 0; i <= tour.Stops.Count; i++) {
+            tour.Stops.Insert(i, unrouted);
+            eval = problemInstance.EvaluateTour(tour, result);
+            double tourCost = eval.Quality - originalCosts;
+
+            if (pdp != null && pdp.GetPickupDeliveryLocation(unrouted) > 0) {
+              for (int j = i + 1; j <= tour.Stops.Count; j++) {
+                bool feasible;
+                double cost = tourCost +
+                  problemInstance.GetInsertionCosts(eval, result, pdp.GetPickupDeliveryLocation(unrouted), 0, j, out feasible);
                 if (cost < minimumCost && feasible) {
+                  customer = unrouted;
                   minimumCost = cost;
                   indexOfMinimumCost = i;
-                  indexOfCustomer = c;
+                  indexOfMinimumCost2 = j;
                 }
               }
-
-              tour.Stops.RemoveAt(i);
+            } else {
+              double cost = tourCost;
+              bool feasible = problemInstance.Feasible(eval);
+              if (cost < minimumCost && feasible) {
+                customer = unrouted;
+                minimumCost = cost;
+                indexOfMinimumCost = i;
+              }
             }
-          }
-
-          // insert customer if found
-          if (indexOfMinimumCost != -1) {
-            tour.Stops.Insert(indexOfMinimumCost, unroutedList[indexOfCustomer]);
-            if (pdp != null) {
-              tour.Stops.Insert(indexOfMinimumCost2, pdp.GetPickupDeliveryLocation(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.GetPickupDeliveryLocation(unroutedList[0]));
-            }
-
-            unrouted.Remove(unroutedList[0]);
-            unroutedList.RemoveAt(0);
-          }
-          // reset minimum    
-          minimumCost = double.MaxValue;
-          indexOfMinimumCost = -1;
-          indexOfMinimumCost2 = -1;
-          indexOfCustomer = -1;
+
+            tour.Stops.RemoveAt(i);
+          }
+        }
+
+        if (indexOfMinimumCost == -1 && vehicles.Count == 0) {
+          indexOfMinimumCost = tour.Stops.Count;
+          indexOfMinimumCost2 = tour.Stops.Count + 1;
+          customer = unroutedCustomers[0];
+        }
+
+        // insert customer if found
+        if (indexOfMinimumCost != -1) {
+          tour.Stops.Insert(indexOfMinimumCost, customer);
+          if (pdp != null && pdp.GetPickupDeliveryLocation(customer) > 0) {
+            tour.Stops.Insert(indexOfMinimumCost2, pdp.GetPickupDeliveryLocation(customer));
+          }
+
+          unroutedCustomers.Remove(customer);
+        } else { // no feasible customer found
+          tour = new Tour();
+          result.Tours.Add(tour);
+          currentCustomer = unroutedCustomers[0];
+          unroutedCustomers.RemoveAt(0);
+
+          currentDepot = depotAssignment[currentCustomer];
+          currentVehicle = vehicles[currentDepot][0];
+          vehicles[currentDepot].RemoveAt(0);
+          if (RemoveUnusedDepots(depots, vehicles)) {
+            unroutedCustomers = SortCustomers(
+            problemInstance, unroutedCustomers, depots, depotAssignment,
+            alpha, beta, gamma);
+          }
+
+          result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
+
+          tour.Stops.Add(currentCustomer);
+          if (pdp != null && pdp.GetPickupDeliveryLocation(currentCustomer) > 0) {
+            tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));
+          }
         }
       }