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