Changeset 17711 for branches/2521_ProblemRefactoring/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWProblemInstance.cs

Timestamp:

08/03/20 18:06:16 (4 years ago)

Author:

abeham

Message:

#2521: working on VRP

File:

• branches/2521_ProblemRefactoring/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWProblemInstance.cs (modified) (2 diffs)

branches/2521_ProblemRefactoring/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWProblemInstance.cs

@@ -23 +23 @@
 using System.Collections.Generic;
 using System.Linq;
+using HEAL.Attic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
-using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
-using HEAL.Attic;
-using HeuristicLab.PluginInfrastructure;
 using HeuristicLab.Problems.VehicleRouting.Interfaces;
 using HeuristicLab.Problems.VehicleRouting.Variants;
@@ -89 +87 @@
     }
 
-    protected override IEnumerable<IOperator> GetOperators() {
-      return base.GetOperators()
-        .Where(o => o is ITimeWindowedOperator).Cast<IOperator>();
-    }
-
-    protected override IEnumerable<IOperator> GetAnalyzers() {
-      return ApplicationManager.Manager.GetInstances<ITimeWindowedOperator>()
-        .Where(o => o is IAnalyzer)
-        .Cast<IOperator>().Union(base.GetAnalyzers());
-    }
-
-    protected override IVRPEvaluator Evaluator {
-      get {
-        return new CVRPTWEvaluator();
-      }
+    public override IEnumerable<IOperator> FilterOperators(IEnumerable<IOperator> operators) {
+      return base.FilterOperators(operators).Where(x => x is ITimeWindowedOperator);
+    }
+
+    protected override VRPEvaluation CreateTourEvaluation() {
+      return new CVRPTWEvaluation();
+    }
+
+    protected override void EvaluateTour(VRPEvaluation eval, Tour tour, IVRPEncodedSolution solution) {
+      TourInsertionInfo tourInfo = new TourInsertionInfo(solution.GetVehicleAssignment(solution.GetTourIndex(tour)));
+      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
+      double originalQuality = eval.Quality;
+
+      double time = 0.0;
+      double waitingTime = 0.0;
+      double serviceTime = 0.0;
+      double tardiness = 0.0;
+      double delivered = 0.0;
+      double overweight = 0.0;
+      double distance = 0.0;
+
+      double capacity = 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;
+
+      double tourStartTime = ReadyTime[0];
+      time = tourStartTime;
+
+      //simulate a tour, start and end at depot
+      for (int i = 0; i <= tour.Stops.Count; i++) {
+        int start = 0;
+        if (i > 0)
+          start = tour.Stops[i - 1];
+        int end = 0;
+        if (i < tour.Stops.Count)
+          end = tour.Stops[i];
+
+        //drive there
+        double currentDistace = GetDistance(start, end, solution);
+        time += currentDistace;
+        distance += currentDistace;
+
+        double arrivalTime = time;
+
+        //check if it was serviced on time
+        if (time > DueTime[end]) {
+          tardiness += time - DueTime[end];
+        }
+
+        //wait
+        double currentWaitingTime = 0.0;
+        if (time < ReadyTime[end])
+          currentWaitingTime = ReadyTime[end] - time;
+
+        double waitTime = ReadyTime[end] - time;
+
+        waitingTime += currentWaitingTime;
+        time += currentWaitingTime;
+
+        double spareTime = DueTime[end] - time;
+
+        //service
+        double currentServiceTime = ServiceTime[end];
+        serviceTime += currentServiceTime;
+        time += currentServiceTime;
+
+        CVRPTWInsertionInfo stopInfo = new CVRPTWInsertionInfo(start, end, spareCapacity, tourStartTime, arrivalTime, time, spareTime, waitTime);
+        tourInfo.AddStopInsertionInfo(stopInfo);
+      }
+
+      eval.Quality += FleetUsageFactor.Value;
+      eval.Quality += DistanceFactor.Value * distance;
+      eval.Distance += distance;
+      eval.VehicleUtilization += 1;
+
+      if (delivered > capacity) {
+        overweight = delivered - capacity;
+      }
+
+      (eval as CVRPEvaluation).Overload += overweight;
+      double tourPenalty = 0;
+      double penalty = overweight * OverloadPenalty.Value;
+      eval.Penalty += penalty;
+      eval.Quality += penalty;
+      tourPenalty += penalty;
+
+      (eval as CVRPTWEvaluation).Tardiness += tardiness;
+      (eval as CVRPTWEvaluation).TravelTime += time;
+
+      penalty = tardiness * TardinessPenalty.Value;
+      eval.Penalty += penalty;
+      eval.Quality += penalty;
+      tourPenalty += penalty;
+      eval.Quality += time * TimeFactor.Value;
+      tourInfo.Penalty = tourPenalty;
+      tourInfo.Quality = eval.Quality - originalQuality;
+
+      eval.IsFeasible = overweight == 0 && tardiness == 0;
+    }
+
+    protected override double GetTourInsertionCosts(IVRPEncodedSolution solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
+      out bool feasible) {
+      CVRPTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo;
+
+      double costs = 0;
+      feasible = tourInsertionInfo.Penalty < double.Epsilon;
+
+      double overloadPenalty = OverloadPenalty.Value;
+      double tardinessPenalty = TardinessPenalty.Value;
+
+      double distance = GetDistance(insertionInfo.Start, insertionInfo.End, solution);
+      double newDistance =
+        GetDistance(insertionInfo.Start, customer, solution) +
+        GetDistance(customer, insertionInfo.End, solution);
+      costs += DistanceFactor.Value * (newDistance - distance);
+
+      double demand = 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;
+      else
+        time = insertionInfo.TourStartTime;
+
+      time += GetDistance(insertionInfo.Start, customer, solution);
+      if (time > DueTime[customer]) {
+        tardiness += time - DueTime[customer];
+      }
+      if (time < ReadyTime[customer])
+        time += ReadyTime[customer] - time;
+      time += ServiceTime[customer];
+      time += GetDistance(customer, insertionInfo.End, solution);
+
+      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 * TimeFactor.Value;
+
+      if (tardiness > 0) {
+        feasible = false;
+      }
+
+      costs += tardiness * tardinessPenalty;
+
+      return costs;
     }