source: branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/TtpUtils.cs @ 14653

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using HeuristicLab.Data;
using HeuristicLab.Problems.TravelingSalesman;

namespace HeuristicLab.Networks.IntegratedOptimization.TravelingThief {
  public static class TtpUtils {
    public enum DistanceType {
      Unknown = int.MinValue,
      CEIL_2D = 0,
      EUC_2D = 1,
    }

    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, Dictionary<int, int[]> availability, double rentingRatio, double minSpeed, double maxSpeed) {
      double collectedWeight = 0.0;
      double objectiveValue = 0.0;
      double infeasibleBaseLine = -1000000.0;
      double speedCoefficient = (maxSpeed - minSpeed) / ksp.KnapsackCapacity.Value;

      int hideoutIdx = 0;
      while (tour[hideoutIdx] != 0) hideoutIdx++;
      int cityIdx = (hideoutIdx + 1) % tour.Length;
      int lastCityIdx = hideoutIdx;

      while (cityIdx != hideoutIdx) {
        double oldCollectedWeight = collectedWeight;

        foreach (var itemIdx in availability[tour[cityIdx]]) {
          if (!loot[itemIdx]) continue;
          collectedWeight += ksp.Weights[itemIdx];
          objectiveValue += ksp.Values[itemIdx];
        }

        objectiveValue -= tsp.DistanceMatrix[tour[lastCityIdx], tour[cityIdx]] * rentingRatio / (maxSpeed - speedCoefficient * oldCollectedWeight);
        lastCityIdx = cityIdx;
        cityIdx = (cityIdx + 1) % tour.Length;
      }

      objectiveValue -= tsp.DistanceMatrix[tour[lastCityIdx], tour[hideoutIdx]] * rentingRatio / (maxSpeed - speedCoefficient * collectedWeight);

      bool feasible = collectedWeight <= ksp.KnapsackCapacity.Value;
      if (!feasible) objectiveValue = infeasibleBaseLine - collectedWeight;

      return objectiveValue;
    }

    public static Dictionary<int, int[]> GetAvailability(int[] availability) {
      return availability.Select((c, i) => Tuple.Create(c, i)).GroupBy(x => x.Item1).ToDictionary(k => k.Key, v => v.Select(x => x.Item2).ToArray());
    }

    public static double[,] GetDistances(DoubleMatrix coordinates, DistanceType distanceType) {
      int nrOfNodes = coordinates.Rows;
      var distances = new double[nrOfNodes, nrOfNodes];

      for (int i = 1; i < nrOfNodes; i++)
        for (int j = 0; j < i; j++)
          distances[i, j] = distances[j, i] = Distance(coordinates, i, j, distanceType);

      return distances;
    }

    private static double Distance(DoubleMatrix coordinates, int fromIdx, int toIdx, DistanceType distanceType) {
      double fromX = coordinates[fromIdx, 0];
      double fromY = coordinates[fromIdx, 1];
      double toX = coordinates[toIdx, 0];
      double toY = coordinates[toIdx, 1];

      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 double.NaN;
      }
    }
  }
}