1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Linq;
|
---|
4 | using System.Text;
|
---|
5 | using System.IO;
|
---|
6 |
|
---|
7 | namespace VRPProblemAnalyzer {
|
---|
8 | public static class Maths {
|
---|
9 | public static double StandardDeviation(this IEnumerable<double> data) {
|
---|
10 | double average = data.Average();
|
---|
11 | var individualDeviations = data.Select(num => Math.Pow(num - average, 2.0));
|
---|
12 | return Math.Sqrt(individualDeviations.Average());
|
---|
13 | }
|
---|
14 | }
|
---|
15 |
|
---|
16 | class Program {
|
---|
17 | private static string InstancePath = @"C:\Users\svonolfen\Desktop\Instances\Augerat";
|
---|
18 |
|
---|
19 | private static double GetDistance(double[,] vertices, int source, int target) {
|
---|
20 | return Math.Sqrt(
|
---|
21 | Math.Pow((vertices[source, 0] - vertices[target, 0]), 2) +
|
---|
22 | Math.Pow((vertices[source, 1] - vertices[target, 1]), 2));
|
---|
23 | }
|
---|
24 |
|
---|
25 | private static double[] GetDistances(double[,] vertices) {
|
---|
26 | List<double> result = new List<double>();
|
---|
27 |
|
---|
28 | int cities = vertices.Length / 2;
|
---|
29 | for (int i = 0; i < cities; i++) {
|
---|
30 | for (int j = 0; j < cities; j++) {
|
---|
31 | if (i != j) {
|
---|
32 | result.Add(GetDistance(vertices, i, j));
|
---|
33 | }
|
---|
34 | }
|
---|
35 | }
|
---|
36 |
|
---|
37 | return result.ToArray();
|
---|
38 | }
|
---|
39 |
|
---|
40 | private static double[] GetAverageDistances(double[,] vertices) {
|
---|
41 | int cities = vertices.Length / 2;
|
---|
42 | double[] result = new double[cities];
|
---|
43 |
|
---|
44 | for (int i = 0; i < cities; i++) {
|
---|
45 | double distance = 0;
|
---|
46 | for (int j = 0; j < cities; j++) {
|
---|
47 | if (i != j) {
|
---|
48 | distance += GetDistance(vertices, i, j);
|
---|
49 | }
|
---|
50 | }
|
---|
51 | result[i] = distance / (cities - 1);
|
---|
52 | }
|
---|
53 |
|
---|
54 | return result;
|
---|
55 | }
|
---|
56 |
|
---|
57 | private static double GetAverageDistance(TSPLIBParser instance) {
|
---|
58 | double result = 0;
|
---|
59 |
|
---|
60 | double[] distances = GetDistances(instance.Vertices);
|
---|
61 | result = distances.Average();
|
---|
62 |
|
---|
63 | return result;
|
---|
64 | }
|
---|
65 |
|
---|
66 | private static double GetDistanceHeterogenity(TSPLIBParser instance) {
|
---|
67 | double result = 0;
|
---|
68 |
|
---|
69 | result = GetAverageDistances(instance.Vertices).StandardDeviation();
|
---|
70 |
|
---|
71 | return result;
|
---|
72 | }
|
---|
73 |
|
---|
74 | private static double GetDistance(double[] cust1, double[] cust2) {
|
---|
75 | return Math.Sqrt(
|
---|
76 | Math.Pow((cust1[0] - cust2[0]), 2) +
|
---|
77 | Math.Pow((cust1[1] - cust2[1]), 2));
|
---|
78 | }
|
---|
79 |
|
---|
80 | private static double GetDistance(Cluster cluster1, Cluster cluster2) {
|
---|
81 | List<double> distances = new List<double>();
|
---|
82 | foreach (double[] cust1 in cluster1.Items) {
|
---|
83 | foreach (double[] cust2 in cluster2.Items) {
|
---|
84 | distances.Add(GetDistance(cust1, cust2));
|
---|
85 | }
|
---|
86 | }
|
---|
87 |
|
---|
88 | return distances.Min();
|
---|
89 |
|
---|
90 | //return GetDistance(cluster1.Center, cluster2.Center);
|
---|
91 | }
|
---|
92 |
|
---|
93 | private static double GetDistance(List<Cluster> clusters, Cluster cluster) {
|
---|
94 | List<double> distances = new List<double>();
|
---|
95 | foreach (Cluster other in clusters) {
|
---|
96 | if (other != cluster) {
|
---|
97 | distances.Add(GetDistance(cluster, other));
|
---|
98 | }
|
---|
99 | }
|
---|
100 |
|
---|
101 | if (distances.Count > 0)
|
---|
102 | return distances.Min();
|
---|
103 | else
|
---|
104 | return 0;
|
---|
105 | }
|
---|
106 |
|
---|
107 | private static double GetCohesion(Cluster cluster) {
|
---|
108 | double cohesion = 0;
|
---|
109 |
|
---|
110 | List<double> distances = new List<double>();
|
---|
111 | foreach (double[] cust1 in cluster.Items) {
|
---|
112 | //option 1
|
---|
113 | foreach (double[] cust2 in cluster.Items) {
|
---|
114 | if (cust1 != cust2) {
|
---|
115 | distances.Add(GetDistance(cust1, cust2));
|
---|
116 | }
|
---|
117 | }
|
---|
118 |
|
---|
119 | //option2
|
---|
120 | //distances.Add(GetDistance(cluster.Center, cust1));
|
---|
121 | }
|
---|
122 |
|
---|
123 | if (distances.Count > 0)
|
---|
124 | cohesion = distances.Average();
|
---|
125 |
|
---|
126 | return cohesion;
|
---|
127 | }
|
---|
128 |
|
---|
129 | private static double GetClustering(TSPLIBParser instance) {
|
---|
130 | double result = 0;
|
---|
131 |
|
---|
132 | int cities = instance.Vertices.Length / 2 - 1;
|
---|
133 | double[,] coordinates = new double[cities, 2];
|
---|
134 | for (int i = 1; i <= cities; i++) {
|
---|
135 | coordinates[i - 1, 0] = instance.Vertices[i, 0];
|
---|
136 | coordinates[i - 1, 1] = instance.Vertices[i, 1];
|
---|
137 | }
|
---|
138 |
|
---|
139 | double clusterFactor = 0;
|
---|
140 | double couplingFactor = 1;
|
---|
141 | double cohesionFactor = 1;
|
---|
142 |
|
---|
143 | double maxQuality = double.MinValue;
|
---|
144 |
|
---|
145 | int clusters = -1;
|
---|
146 | for (int i = 1; i <= cities; i++) {
|
---|
147 | List<Cluster> collection = KMeansClustering.Cluster(coordinates, i, 9);
|
---|
148 |
|
---|
149 | if (collection.Count > 0) {
|
---|
150 | List<double> distances = new List<double>();
|
---|
151 | List<double> cohesions = new List<double>();
|
---|
152 | foreach (Cluster cluster in collection) {
|
---|
153 | distances.Add(GetDistance(collection, cluster));
|
---|
154 | cohesions.Add(GetCohesion(cluster));
|
---|
155 | }
|
---|
156 |
|
---|
157 | double distance = distances.Average();
|
---|
158 | double cohesion = cohesions.Average();
|
---|
159 |
|
---|
160 | double quality = clusterFactor * (distances.Count / (double)cities) + couplingFactor * distance - cohesionFactor * cohesion;
|
---|
161 | if (quality > maxQuality) {
|
---|
162 | maxQuality = quality;
|
---|
163 | clusters = distances.Count;
|
---|
164 | }
|
---|
165 | }
|
---|
166 | }
|
---|
167 |
|
---|
168 | if (clusters != 0)
|
---|
169 | result = (cities / (double)clusters) / cities;
|
---|
170 |
|
---|
171 | return result;
|
---|
172 | }
|
---|
173 |
|
---|
174 | private static double GetDemandSize(TSPLIBParser instance) {
|
---|
175 | double result = 0;
|
---|
176 |
|
---|
177 | result = instance.Demands.Average();
|
---|
178 |
|
---|
179 | return result;
|
---|
180 | }
|
---|
181 |
|
---|
182 | private static double GetDemandHeterogenity(TSPLIBParser instance) {
|
---|
183 | double result = 0;
|
---|
184 |
|
---|
185 | result = instance.Demands.StandardDeviation();
|
---|
186 |
|
---|
187 | return result;
|
---|
188 | }
|
---|
189 |
|
---|
190 | private static void Normalize(TSPLIBParser instance) {
|
---|
191 | //normalize demands
|
---|
192 | for (int i = 0; i < instance.Demands.Length; i++) {
|
---|
193 | instance.Demands[i] = instance.Demands[i] / instance.Capacity;
|
---|
194 | }
|
---|
195 |
|
---|
196 | //normalize coordinates
|
---|
197 | //-find bounds
|
---|
198 | double maxX = double.MinValue;
|
---|
199 | double maxY = double.MinValue;
|
---|
200 |
|
---|
201 | int cities = instance.Vertices.Length / 2;
|
---|
202 | for (int i = 0; i < cities; i++) {
|
---|
203 | if (instance.Vertices[i, 0] > maxX)
|
---|
204 | maxX = instance.Vertices[i, 0];
|
---|
205 |
|
---|
206 | if (instance.Vertices[i, 1] > maxY)
|
---|
207 | maxY = instance.Vertices[i, 1];
|
---|
208 | }
|
---|
209 |
|
---|
210 | //-normalize
|
---|
211 | double factorX = 1;
|
---|
212 | double factorY = 1;
|
---|
213 | if (maxX > maxY) {
|
---|
214 | factorX = 1 / maxX;
|
---|
215 | factorY = (maxY / maxX) / maxY;
|
---|
216 | } else {
|
---|
217 | factorX = (maxX / maxY) / maxX;
|
---|
218 | factorY = 1 / maxY;
|
---|
219 | }
|
---|
220 |
|
---|
221 | for (int i = 0; i < cities; i++) {
|
---|
222 | instance.Vertices[i, 0] *= factorX;
|
---|
223 | instance.Vertices[i, 1] *= factorY;
|
---|
224 | }
|
---|
225 | }
|
---|
226 |
|
---|
227 | static void Main(string[] args) {
|
---|
228 | using (StreamWriter sw = new StreamWriter(InstancePath + Path.DirectorySeparatorChar + "analysis.csv")) {
|
---|
229 | sw.WriteLine("Instance;Customers;Clustering;DistanceAvg;DistanceStdev;DemandAvg;DemandStdev");
|
---|
230 |
|
---|
231 | string[] instances = Directory.GetFiles(InstancePath, "*.vrp", SearchOption.AllDirectories);
|
---|
232 | foreach (string instance in instances) {
|
---|
233 | TSPLIBParser parser = new TSPLIBParser(instance);
|
---|
234 | parser.Parse();
|
---|
235 | Normalize(parser);
|
---|
236 |
|
---|
237 | sw.Write(Path.GetFileNameWithoutExtension(instance));
|
---|
238 | sw.Write(';');
|
---|
239 | sw.Write(parser.Vertices.Length / 2 - 1);
|
---|
240 | sw.Write(';');
|
---|
241 | sw.Write(GetClustering(parser));
|
---|
242 | sw.Write(';');
|
---|
243 | sw.Write(GetAverageDistance(parser));
|
---|
244 | sw.Write(';');
|
---|
245 | sw.Write(GetDistanceHeterogenity(parser));
|
---|
246 | sw.Write(';');
|
---|
247 | sw.Write(GetDemandSize(parser));
|
---|
248 | sw.Write(';');
|
---|
249 | sw.Write(GetDemandHeterogenity(parser));
|
---|
250 | sw.Write(';');
|
---|
251 | sw.WriteLine();
|
---|
252 | }
|
---|
253 | }
|
---|
254 | }
|
---|
255 | }
|
---|
256 | }
|
---|