Changeset 6854 for branches/VRP/HeuristicLab.Problems.VehicleRouting

Timestamp:

09/30/11 11:36:05 (13 years ago)

Author:

svonolfe

Message:

Added support for the multi depot CVRP with time windows (#1177)

Location:

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4

Files:

• Encodings/ExtendedPotvin/Creators/PushForwardInsertionCreator.cs (modified) (1 diff)
• Encodings/Potvin/Manipulators/PotvinCustomerRelocationManipulator.cs (modified) (3 diffs)
• HeuristicLab.Problems.VehicleRouting-3.4.csproj (modified) (1 diff)
• Interfaces/IVRPProblemInstance.cs (modified) (1 diff)
• Parsers/CordeauParser.cs (modified) (3 diffs)
• ProblemInstances/MultiDepotVRP/MDCVRP/MDCVRPEvaluator.cs (modified) (1 diff)
• ProblemInstances/MultiDepotVRP/MDCVRP/MDCVRPTW (added)
• ProblemInstances/MultiDepotVRP/MDCVRP/MDCVRPTW/MDCVRPTWEvaluator.cs (added)
• ProblemInstances/MultiDepotVRP/MDCVRP/MDCVRPTW/MDCVRPTWProblemInstance.cs (added)
• ProblemInstances/MultiDepotVRP/MultiDepotVRPEvaluator.cs (modified) (1 diff)
• ProblemInstances/MultiDepotVRP/MultiDepotVRPProblemInstance.cs (modified) (2 diffs)
• ProblemInstances/VRPProblemInstance.cs (modified) (1 diff)
• VehicleRoutingProblem.cs (modified) (2 diffs)

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

@@ -182 +182 @@
             double dueTime = 0;
             if (problemInstance is ITimeWindowedProblemInstance)
-              dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[i];
+              dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[i + depots - 1];
 
             cost = -alpha * distance + // distance 0 <-> City[i]

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

@@ -146 +146 @@
           DoubleArray serviceTimes = vrptw.ServiceTime;
 
+          int depot = 0;
+          int depots = 1;
+
+          int tourIndex = individual.GetTourIndex(route1);
+          int vehicle = individual.GetVehicleAssignment(tourIndex);
+
+          if (ProblemInstance is IMultiDepotProblemInstance) {
+            depots = (ProblemInstance as IMultiDepotProblemInstance).Depots.Value;
+            depot = (ProblemInstance as IMultiDepotProblemInstance).VehicleDepotAssignment[vehicle];
+          }
+
           List<int> timeWindowViolations = new List<int>();
           double time = 0;
 
           for (int i = 0; i < route1.Stops.Count; i++) {
-            int start = 0;
-            if (i > 0)
-              start = route1.Stops[i - 1];
-            int end = 0;
-            if (i < route1.Stops.Count)
-              end = route1.Stops[i];
+            int start = route1.Stops[i - 1];
+            int end = route1.Stops[i];
 
             //drive there
@@ -161 +168 @@
             time += currentDistace;
 
+            int endIndex = end + depots - 1;
+
             //check if it was serviced on time
-            if (time > dueTime[end]) {
+            if (time > dueTime[endIndex]) {
               timeWindowViolations.Add(end);
             }
@@ -168 +177 @@
             //wait
             double currentWaitingTime = 0.0;
-            if (time < readyTime[end])
-              currentWaitingTime = readyTime[end] - time;
+            if (time < readyTime[endIndex])
+              currentWaitingTime = readyTime[endIndex] - time;
             time += currentWaitingTime;
 
             //service
-            double currentServiceTime = serviceTimes[end];
+            double currentServiceTime = serviceTimes[end - 1];
             time += currentServiceTime;
           }

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

@@ -301 +301 @@
     <Compile Include="ProblemInstances\MultiDepotVRP\MDCVRP\MDCVRPEvaluator.cs" />
     <Compile Include="ProblemInstances\MultiDepotVRP\MDCVRP\MDCVRPProblemInstance.cs" />
+    <Compile Include="ProblemInstances\MultiDepotVRP\MDCVRP\MDCVRPTW\MDCVRPTWEvaluator.cs" />
+    <Compile Include="ProblemInstances\MultiDepotVRP\MDCVRP\MDCVRPTW\MDCVRPTWProblemInstance.cs" />
     <Compile Include="ProblemInstances\MultiDepotVRP\MultiDepotVRPProblemInstance.cs" />
     <Compile Include="ProblemInstances\MultiDepotVRP\MultiDepotVRPEvaluator.cs" />

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPProblemInstance.cs

@@ -51 +51 @@
     double GetDemand(int city);
     double GetDistance(int start, int end, IVRPEncoding solution);
-    double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution);
+    double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution, out double startDistance, out double endDistance);
     bool Feasible(IVRPEncoding solution);
     bool TourFeasible(Tour tour, IVRPEncoding solution);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Parsers/CordeauParser.cs

@@ -132 +132 @@
         throw new InvalidDataException("File has wrong format!");
 
+      bool timeWindows = int.Parse(m[0].Value) == 6;
       vehicles = int.Parse(m[3].Value);
       line = reader.ReadLine();
@@ -146 +147 @@
       List<double> depotXcoord = new List<double>();
       List<double> depotYcoord = new List<double>();
+      List<double> depotReadyTime = new List<double>();
+      List<double> depotDueTime = new List<double>();
+
       while ((line != null)) {
         m = reg.Matches(line);
 
-        if (m.Count == 11) {
+        if (m.Count >= 11) {
           xCoord.Add(double.Parse(m[1].Value, System.Globalization.CultureInfo.InvariantCulture));
           yCoord.Add(double.Parse(m[2].Value, System.Globalization.CultureInfo.InvariantCulture));
           demand.Add((double)int.Parse(m[4].Value, System.Globalization.CultureInfo.InvariantCulture));
-        } else if (m.Count == 7) {
+
+          if (timeWindows) {
+            serviceTime.Add(int.Parse(m[3].Value));
+            readyTime.Add(int.Parse(m[m.Count - 2].Value));
+            dueTime.Add(int.Parse(m[m.Count - 1].Value));
+          } else {
+            serviceTime.Add(0);
+            readyTime.Add(0);
+            dueTime.Add(double.MaxValue);
+          }
+        } else if (m.Count >= 7) {
           depotXcoord.Add(double.Parse(m[1].Value, System.Globalization.CultureInfo.InvariantCulture));
           depotYcoord.Add(double.Parse(m[2].Value, System.Globalization.CultureInfo.InvariantCulture));
+
+          if (timeWindows) {
+            depotReadyTime.Add(int.Parse(m[m.Count - 2].Value));
+            depotDueTime.Add(int.Parse(m[m.Count - 1].Value));
+          } else {
+            depotReadyTime.Add(0);
+            depotDueTime.Add(double.MaxValue);
+          }
         }
                
@@ -163 +185 @@
       xCoord.InsertRange(0, depotXcoord);
       yCoord.InsertRange(0, depotYcoord);
+      readyTime.InsertRange(0, depotReadyTime);
+      dueTime.InsertRange(0, depotDueTime);
 
       cities = demand.Count;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/MultiDepotVRP/MDCVRP/MDCVRPEvaluator.cs

@@ -111 +111 @@
       double overloadPenalty = cvrp.OverloadPenalty.Value;
 
-      costs += instance.GetInsertionDistance(insertionInfo.Start, customer, insertionInfo.End, solution);
+      double startDistance, endDistance;
+      costs += instance.GetInsertionDistance(insertionInfo.Start, customer, insertionInfo.End, solution, out startDistance, out endDistance);
 
       double demand = instance.GetDemand(customer);

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/MultiDepotVRP/MultiDepotVRPEvaluator.cs

@@ -81 +81 @@
       double costs = 0;
       feasible = true;
+      double startDistance, endDistance;
 
-      costs += instance.GetInsertionDistance(insertionInfo.Start, customer, insertionInfo.End, solution);
+      costs += instance.GetInsertionDistance(insertionInfo.Start, customer, insertionInfo.End, solution, out startDistance, out endDistance);
 
       return costs;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/MultiDepotVRP/MultiDepotVRPProblemInstance.cs

@@ -150 +150 @@
     }
 
-    public override double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution) {
+    public override double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution, 
+      out double startDistance, out double endDistance) {
       if (start == 0) {
         start = GetDepot(end, solution);
@@ -164 +165 @@
       
       double distance = base.GetDistance(start, end, solution);
-      double newDistance =
-        base.GetDistance(start, customer, solution) +
-        base.GetDistance(customer, end, solution);
+
+      startDistance = base.GetDistance(start, customer, solution);
+      endDistance = base.GetDistance(customer, end, solution);
+
+      double newDistance = startDistance + endDistance;
 
       return newDistance - distance;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs

@@ -220 +220 @@
     }
 
-    public virtual double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution) {
+    public virtual double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution,
+      out double startDistance, out double endDistance) {
       double distance = GetDistance(start, end, solution);
-      double newDistance =
-        GetDistance(start, customer, solution) +
-        GetDistance(customer, end, solution);
+
+      startDistance = GetDistance(start, customer, solution);
+      endDistance = GetDistance(customer, end, solution);
+      
+      double newDistance = startDistance + endDistance;
 
       return newDistance - distance;

branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/VehicleRoutingProblem.cs

@@ -247 +247 @@
       parser.Parse();
 
-      MDCVRPProblemInstance problem = new MDCVRPProblemInstance();
+      MDCVRPTWProblemInstance problem = new MDCVRPTWProblemInstance();
 
       problem.Coordinates = new DoubleMatrix(parser.Coordinates);
@@ -255 +255 @@
       problem.Depots.Value = parser.Depots;
       problem.VehicleDepotAssignment = new IntArray(parser.Vehicles);
+      problem.ReadyTime = new DoubleArray(parser.Readytimes);
+      problem.ServiceTime = new DoubleArray(parser.Servicetimes);
+      problem.DueTime = new DoubleArray(parser.Duetimes);
+
       int depot = 0;
       int i = 0;