Changeset 14604 for branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpUtils.cs

Timestamp:

01/25/17 14:30:18 (7 years ago)

Author:

jkarder

Message:

#2205: worked on optimization networks

• updated ttp networks (1, 2, 3)
• added lrp network (1)
• fixed plugin dependencies

File:

• branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpUtils.cs (modified) (5 diffs)

branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpUtils.cs

@@ -1 +1 @@
 using System;
+using System.IO;
 using System.Linq;
 using HeuristicLab.Problems.TravelingSalesman;
@@ -5 +6 @@
 namespace HeuristicLab.Networks.IntegratedOptimization.TravelingThief {
   public static class TtpUtils {
-    public static double EvaluateTtp(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, int[] availability, double rentingRatio, double minSpeed, double maxSpeed) {
-      bool feasible;
-      return EvaluateTtp(tsp, tour, ksp, loot, availability, rentingRatio, minSpeed, maxSpeed, out feasible);
+    public enum DistanceType {
+      Unknown = int.MinValue,
+      CEIL_2D = 0,
+      EUC_2D = 1,
     }
 
-    public static double EvaluateTtp(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, int[] availability, double rentingRatio, double minSpeed, double maxSpeed, out bool feasible) {
+    public static void Import(string filePath, out double[,] tspCoordinates,
+                                               out DistanceType distanceType,
+                                               out int kspCapacity,
+                                               out int[] kspItemValues,
+                                               out int[] kspItemWeights,
+                                               out int[] ttpAvailability,
+                                               out double ttpMinSpeed,
+                                               out double ttpMaxSpeed,
+                                               out double ttpRentingRatio) {
+      int nrOfCities = 0, nrOfItems = 0; kspCapacity = 0;
+      ttpMinSpeed = 0.0; ttpMaxSpeed = 0.0; ttpRentingRatio = 0.0;
+      distanceType = DistanceType.Unknown;
+
+      using (var fs = new FileStream(filePath, FileMode.Open))
+      using (var sr = new StreamReader(fs)) {
+        string input;
+        while ((input = sr.ReadLine()) != null && !input.Contains("NODE_COORD_SECTION")) {
+          if (input.Contains("DIMENSION:")) int.TryParse(input.Replace("DIMENSION:", string.Empty), out nrOfCities);
+          if (input.Contains("NUMBER OF ITEMS:")) int.TryParse(input.Replace("NUMBER OF ITEMS:", string.Empty), out nrOfItems);
+          if (input.Contains("CAPACITY OF KNAPSACK:")) int.TryParse(input.Replace("CAPACITY OF KNAPSACK:", string.Empty), out kspCapacity);
+          if (input.Contains("MIN SPEED:")) double.TryParse(input.Replace("MIN SPEED:", string.Empty), out ttpMinSpeed);
+          if (input.Contains("MAX SPEED:")) double.TryParse(input.Replace("MAX SPEED:", string.Empty), out ttpMaxSpeed);
+          if (input.Contains("RENTING RATIO:")) double.TryParse(input.Replace("RENTING RATIO:", string.Empty), out ttpRentingRatio);
+          if (input.Contains("EDGE_WEIGHT_TYPE:")) Enum.TryParse(input.Replace("EDGE_WEIGHT_TYPE:", string.Empty), out distanceType);
+        }
+
+        tspCoordinates = new double[nrOfCities, 2];
+        kspItemValues = new int[nrOfItems];
+        kspItemWeights = new int[nrOfItems];
+        ttpAvailability = new int[nrOfItems];
+
+        // read cities
+        while ((input = sr.ReadLine()) != null && !input.Contains("ITEMS SECTION")) {
+          string[] data = input.Split('\t');
+          int index; double x, y;
+          int.TryParse(data[0], out index);
+          double.TryParse(data[1], out x);
+          double.TryParse(data[2], out y);
+          tspCoordinates[index - 1, 0] = x;
+          tspCoordinates[index - 1, 1] = y;
+        }
+        // read items
+        while ((input = sr.ReadLine()) != null) {
+          string[] data = input.Split('\t');
+          int index, value, weight, city;
+          int.TryParse(data[0], out index);
+          int.TryParse(data[1], out value);
+          int.TryParse(data[2], out weight);
+          int.TryParse(data[3], out city);
+          kspItemValues[index - 1] = value;
+          kspItemWeights[index - 1] = weight;
+          ttpAvailability[index - 1] = city - 1;
+        }
+      }
+    }
+
+    public static double Evaluate(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, int[] availability, double rentingRatio, double minSpeed, double maxSpeed, DistanceType distanceType) {
+      bool feasible;
+      return Evaluate(tsp, tour, ksp, loot, availability, rentingRatio, minSpeed, maxSpeed, distanceType, out feasible);
+    }
+
+    public static double Evaluate(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, int[] availability, double rentingRatio, double minSpeed, double maxSpeed, DistanceType distanceType, out bool feasible) {
       double collectedWeight = 0.0;
       double objectiveValue = 0.0;
@@ -31 +94 @@
         }
 
-        objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[cityIdx]) * rentingRatio /
+        objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[cityIdx], distanceType) * rentingRatio /
                           (maxSpeed - speedCoefficient * oldCollectedWeight);
         lastCityIdx = cityIdx;
@@ -37 +100 @@
       }
 
-      objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[hideoutIdx]) * rentingRatio /
+      objectiveValue -= Distance(tsp.Coordinates.CloneAsMatrix(), tour[lastCityIdx], tour[hideoutIdx], distanceType) * rentingRatio /
                         (maxSpeed - speedCoefficient * collectedWeight);
 
@@ -46 +109 @@
     }
 
-    private static double Distance(double[,] coords, int fromIdx, int toIdx) {
+    private static double Distance(double[,] coords, int fromIdx, int toIdx, DistanceType distanceType) {
       double fromX = coords[fromIdx, 0], fromY = coords[fromIdx, 1],
              toX = coords[toIdx, 0], toY = coords[toIdx, 1];
-      return (int)Math.Ceiling(Math.Sqrt((toX - fromX) * (toX - fromX) + (toY - fromY) * (toY - fromY)));
+      double distance = Math.Sqrt((toX - fromX) * (toX - fromX) + (toY - fromY) * (toY - fromY));
+      switch (distanceType) {
+        case DistanceType.CEIL_2D: return (int)Math.Ceiling(distance);
+        case DistanceType.EUC_2D: return distance;
+        default: return 0.0;
+      }
     }
   }