Changeset 6752 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs

Timestamp:

09/13/11 16:00:19 (13 years ago)

Author:

svonolfe

Message:

Added support for incremental evaluation to improve performance (#1177)

File:

• branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs (modified) (5 diffs)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs

@@ -48 +48 @@
 
     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 +57 @@
       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 +82 @@
         distance += currentDistace;
 
-        delivered += demand[end];
+        CVRPInsertionInfo stopInfo = new CVRPInsertionInfo(start, end, spareCapacity);
+        tourInfo.AddStopInsertionInfo(stopInfo);
       }
 
@@ -77 +92 @@
       eval.VehicleUtilization += 1;
 
-      double capacity = cvrpInstance.Capacity.Value;
       if (delivered > capacity) {
         overweight = delivered - capacity;
@@ -86 +100 @@
       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;
     }