[14586] | 1 | using System;
|
---|
[14653] | 2 | using System.Collections.Generic;
|
---|
[14604] | 3 | using System.IO;
|
---|
[14586] | 4 | using System.Linq;
|
---|
[14653] | 5 | using HeuristicLab.Data;
|
---|
[14586] | 6 | using HeuristicLab.Problems.TravelingSalesman;
|
---|
| 7 |
|
---|
[14601] | 8 | namespace HeuristicLab.Networks.IntegratedOptimization.TravelingThief {
|
---|
[14586] | 9 | public static class TtpUtils {
|
---|
[14604] | 10 | public enum DistanceType {
|
---|
| 11 | Unknown = int.MinValue,
|
---|
| 12 | CEIL_2D = 0,
|
---|
| 13 | EUC_2D = 1,
|
---|
| 14 | }
|
---|
| 15 |
|
---|
| 16 | public static void Import(string filePath, out double[,] tspCoordinates,
|
---|
| 17 | out DistanceType distanceType,
|
---|
| 18 | out int kspCapacity,
|
---|
| 19 | out int[] kspItemValues,
|
---|
| 20 | out int[] kspItemWeights,
|
---|
| 21 | out int[] ttpAvailability,
|
---|
| 22 | out double ttpMinSpeed,
|
---|
| 23 | out double ttpMaxSpeed,
|
---|
| 24 | out double ttpRentingRatio) {
|
---|
| 25 | int nrOfCities = 0, nrOfItems = 0; kspCapacity = 0;
|
---|
| 26 | ttpMinSpeed = 0.0; ttpMaxSpeed = 0.0; ttpRentingRatio = 0.0;
|
---|
| 27 | distanceType = DistanceType.Unknown;
|
---|
| 28 |
|
---|
| 29 | using (var fs = new FileStream(filePath, FileMode.Open))
|
---|
| 30 | using (var sr = new StreamReader(fs)) {
|
---|
| 31 | string input;
|
---|
| 32 | while ((input = sr.ReadLine()) != null && !input.Contains("NODE_COORD_SECTION")) {
|
---|
| 33 | if (input.Contains("DIMENSION:")) int.TryParse(input.Replace("DIMENSION:", string.Empty), out nrOfCities);
|
---|
| 34 | if (input.Contains("NUMBER OF ITEMS:")) int.TryParse(input.Replace("NUMBER OF ITEMS:", string.Empty), out nrOfItems);
|
---|
| 35 | if (input.Contains("CAPACITY OF KNAPSACK:")) int.TryParse(input.Replace("CAPACITY OF KNAPSACK:", string.Empty), out kspCapacity);
|
---|
| 36 | if (input.Contains("MIN SPEED:")) double.TryParse(input.Replace("MIN SPEED:", string.Empty), out ttpMinSpeed);
|
---|
| 37 | if (input.Contains("MAX SPEED:")) double.TryParse(input.Replace("MAX SPEED:", string.Empty), out ttpMaxSpeed);
|
---|
| 38 | if (input.Contains("RENTING RATIO:")) double.TryParse(input.Replace("RENTING RATIO:", string.Empty), out ttpRentingRatio);
|
---|
| 39 | if (input.Contains("EDGE_WEIGHT_TYPE:")) Enum.TryParse(input.Replace("EDGE_WEIGHT_TYPE:", string.Empty), out distanceType);
|
---|
| 40 | }
|
---|
| 41 |
|
---|
| 42 | tspCoordinates = new double[nrOfCities, 2];
|
---|
| 43 | kspItemValues = new int[nrOfItems];
|
---|
| 44 | kspItemWeights = new int[nrOfItems];
|
---|
| 45 | ttpAvailability = new int[nrOfItems];
|
---|
| 46 |
|
---|
| 47 | // read cities
|
---|
| 48 | while ((input = sr.ReadLine()) != null && !input.Contains("ITEMS SECTION")) {
|
---|
| 49 | string[] data = input.Split('\t');
|
---|
| 50 | int index; double x, y;
|
---|
| 51 | int.TryParse(data[0], out index);
|
---|
| 52 | double.TryParse(data[1], out x);
|
---|
| 53 | double.TryParse(data[2], out y);
|
---|
| 54 | tspCoordinates[index - 1, 0] = x;
|
---|
| 55 | tspCoordinates[index - 1, 1] = y;
|
---|
| 56 | }
|
---|
| 57 | // read items
|
---|
| 58 | while ((input = sr.ReadLine()) != null) {
|
---|
| 59 | string[] data = input.Split('\t');
|
---|
| 60 | int index, value, weight, city;
|
---|
| 61 | int.TryParse(data[0], out index);
|
---|
| 62 | int.TryParse(data[1], out value);
|
---|
| 63 | int.TryParse(data[2], out weight);
|
---|
| 64 | int.TryParse(data[3], out city);
|
---|
| 65 | kspItemValues[index - 1] = value;
|
---|
| 66 | kspItemWeights[index - 1] = weight;
|
---|
| 67 | ttpAvailability[index - 1] = city - 1;
|
---|
| 68 | }
|
---|
| 69 | }
|
---|
| 70 | }
|
---|
| 71 |
|
---|
[14653] | 72 | public static double Evaluate(TravelingSalesmanProblem tsp, int[] tour, BinaryKnapsackProblem ksp, bool[] loot, Dictionary<int, int[]> availability, double rentingRatio, double minSpeed, double maxSpeed) {
|
---|
[14586] | 73 | double collectedWeight = 0.0;
|
---|
| 74 | double objectiveValue = 0.0;
|
---|
| 75 | double infeasibleBaseLine = -1000000.0;
|
---|
| 76 | double speedCoefficient = (maxSpeed - minSpeed) / ksp.KnapsackCapacity.Value;
|
---|
| 77 |
|
---|
| 78 | int hideoutIdx = 0;
|
---|
| 79 | while (tour[hideoutIdx] != 0) hideoutIdx++;
|
---|
| 80 | int cityIdx = (hideoutIdx + 1) % tour.Length;
|
---|
| 81 | int lastCityIdx = hideoutIdx;
|
---|
| 82 |
|
---|
| 83 | while (cityIdx != hideoutIdx) {
|
---|
| 84 | double oldCollectedWeight = collectedWeight;
|
---|
| 85 |
|
---|
[14653] | 86 | foreach (var itemIdx in availability[tour[cityIdx]]) {
|
---|
| 87 | if (!loot[itemIdx]) continue;
|
---|
| 88 | collectedWeight += ksp.Weights[itemIdx];
|
---|
| 89 | objectiveValue += ksp.Values[itemIdx];
|
---|
[14586] | 90 | }
|
---|
| 91 |
|
---|
[14653] | 92 | objectiveValue -= tsp.DistanceMatrix[tour[lastCityIdx], tour[cityIdx]] * rentingRatio / (maxSpeed - speedCoefficient * oldCollectedWeight);
|
---|
[14586] | 93 | lastCityIdx = cityIdx;
|
---|
| 94 | cityIdx = (cityIdx + 1) % tour.Length;
|
---|
| 95 | }
|
---|
| 96 |
|
---|
[14653] | 97 | objectiveValue -= tsp.DistanceMatrix[tour[lastCityIdx], tour[hideoutIdx]] * rentingRatio / (maxSpeed - speedCoefficient * collectedWeight);
|
---|
[14586] | 98 |
|
---|
[14653] | 99 | bool feasible = collectedWeight <= ksp.KnapsackCapacity.Value;
|
---|
[14586] | 100 | if (!feasible) objectiveValue = infeasibleBaseLine - collectedWeight;
|
---|
| 101 |
|
---|
| 102 | return objectiveValue;
|
---|
| 103 | }
|
---|
| 104 |
|
---|
[14653] | 105 | public static Dictionary<int, int[]> GetAvailability(int[] availability) {
|
---|
| 106 | return availability.Select((c, i) => Tuple.Create(c, i)).GroupBy(x => x.Item1).ToDictionary(k => k.Key, v => v.Select(x => x.Item2).ToArray());
|
---|
| 107 | }
|
---|
| 108 |
|
---|
| 109 | public static double[,] GetDistances(DoubleMatrix coordinates, DistanceType distanceType) {
|
---|
| 110 | int nrOfNodes = coordinates.Rows;
|
---|
| 111 | var distances = new double[nrOfNodes, nrOfNodes];
|
---|
| 112 |
|
---|
| 113 | for (int i = 1; i < nrOfNodes; i++)
|
---|
| 114 | for (int j = 0; j < i; j++)
|
---|
| 115 | distances[i, j] = distances[j, i] = Distance(coordinates, i, j, distanceType);
|
---|
| 116 |
|
---|
| 117 | return distances;
|
---|
| 118 | }
|
---|
| 119 |
|
---|
| 120 | private static double Distance(DoubleMatrix coordinates, int fromIdx, int toIdx, DistanceType distanceType) {
|
---|
| 121 | double fromX = coordinates[fromIdx, 0];
|
---|
| 122 | double fromY = coordinates[fromIdx, 1];
|
---|
| 123 | double toX = coordinates[toIdx, 0];
|
---|
| 124 | double toY = coordinates[toIdx, 1];
|
---|
| 125 |
|
---|
[14604] | 126 | double distance = Math.Sqrt((toX - fromX) * (toX - fromX) + (toY - fromY) * (toY - fromY));
|
---|
[14653] | 127 |
|
---|
[14604] | 128 | switch (distanceType) {
|
---|
| 129 | case DistanceType.CEIL_2D: return (int)Math.Ceiling(distance);
|
---|
| 130 | case DistanceType.EUC_2D: return distance;
|
---|
[14653] | 131 | default: return double.NaN;
|
---|
[14604] | 132 | }
|
---|
[14586] | 133 | }
|
---|
| 134 | }
|
---|
| 135 | }
|
---|