Changeset 6752 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluator.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/CVRPTW/CVRPPDTW/CVRPPDTWEvaluator.cs (modified) (7 diffs)

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluator.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;
@@ -86 +89 @@
         distance += currentDistace;
 
+        double arrivalTime = time;
+
         //check if it was serviced on time
         if (time > dueTime[end])
@@ -94 +99 @@
         if (time < readyTime[end])
           currentWaitingTime = readyTime[end] - time;
+
+        double waitTime = readyTime[end] - time;
+
         waitingTime += currentWaitingTime;
         time += currentWaitingTime;
+
+        double spareTime = dueTime[end] - time;
 
         //service
@@ -103 +113 @@
 
         //Pickup / deliver
+        double arrivalSpareCapacity = capacity - currentLoad;
+
         bool validPickupDelivery = 
           validPickupDelivery =
@@ -110 +122 @@
         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 +142 @@
 
       (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 +154 @@
       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;
     }