Changeset 8462 for branches/RoutePlanning

Timestamp:

08/09/12 16:20:19 (12 years ago)

Author:

spimming

Message:

#1894:

• calculate distance in kilometers for two locations
• generate IGraph from a datasource
• adapted test program

Location:

branches/RoutePlanning

Files:

• HeuristicLab.Problems.RoutePlanning.Test/Program.cs (modified) (4 diffs)
• HeuristicLab.Problems.RoutePlanning/3.3/Graph/OsmGraph.cs (modified) (2 diffs)
• HeuristicLab.Problems.RoutePlanning/3.3/Osm.Data/XmlDataSource.cs (modified) (3 diffs)
• HeuristicLab.Problems.RoutePlanning/3.3/Osm/IDataSource.cs (modified) (2 diffs)
• HeuristicLab.Problems.RoutePlanning/3.3/Osm/Utils.cs (modified) (1 diff)

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning.Test/Program.cs

@@ -21 +21 @@
       string file5 = @"..\..\OsmTestFiles\test_mid.osm";
       string file6 = @"C:\dev\osmfiles\oberosterreich.highway.osm";
+      string file7 = @"C:\dev\osmfiles\austria.highway.osm";
 
-      IDataSource ds = TestLoad(file6);
+      IDataSource ds = TestLoad(file5);
       OsmGraph graph = new OsmGraph(ds);
-      TestRouter(new DijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
-      TestRouter(new AStarAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
-      TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
-      TestRouter(new BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
+      IGraph graphNew = TestGetRoutingGraph(ds);
+      TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
+      TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 1001363194, true);
+      //TestRouter(new DijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
+      //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
+      //TestRouter(new AStarAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
+      //TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
+      //TestRouter(new BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
+
+      //TestRouter(new AStarAlgorithmV2(graph), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
 
       //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 31372732, false, false); // inz - hgb
@@ -33 +40 @@
       //TestLoadAndRouter(file6, typeof(AStarAlgorithmV2), 529102170, 31372732, false, true); // inz - hgb
 
+      //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
       //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
       //TestLoadAndRouter(file6, typeof(AStarAlgorithm), 529102170, 1001363194, true, false);
@@ -41 +49 @@
       //TestLoadAndRouter(file5, typeof(BidrectionalDijkstraAlgorithm), 529102170, 1001363194, true, true);
       //TestLoadAndRouter(file6, typeof(BidrectionalDijkstraAlgorithm), 529102170, 31372732, false, true); // inz - hgb
+
+
+
+
 
       System.Console.Read();
@@ -167 +179 @@
       }
     }
+
+    private static IGraph TestGetRoutingGraph(IDataSource ds) {
+      Console.WriteLine("Test GetRoutingGraph BEGIN ------------------------");
+      Console.WriteLine();
+      Console.Write("Construct graph ... ");
+      var sw = Stopwatch.StartNew();
+      IGraph graph = ds.GetRoutingGraph();
+      sw.Stop();
+      Console.WriteLine("done.");
+      Console.WriteLine("Time: {0}", sw.Elapsed);
+      Console.WriteLine();
+      Console.WriteLine("===================================================");
+      Console.WriteLine();
+      return graph;
+    }
   }
 }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/OsmGraph.cs

@@ -71 +71 @@
     public float GetWeight(Way edge, OsmVertex<Node> source, OsmVertex<Node> target) {
       double distance = Utils.Distance(source.Node.Point, target.Node.Point);
+      //double distance = Utils.LocationDistance(source.Node.Point, target.Node.Point);
       int speed = edge.GetMaxSpeed();
       double weight = (distance / speed) * 3.6;
+      //double weight = (distance / speed);
       return (float)weight;
     }
@@ -84 +86 @@
     public float EstimatedCosts(OsmVertex<Node> source, OsmVertex<Node> target) {
       double distance = Utils.Distance(source.Node.Point, target.Node.Point);
+      //double distance = Utils.LocationDistance(source.Node.Point, target.Node.Point);
       int speed = 130;
       double costs = (distance / speed) * 3.6;
+      //double costs = (distance / speed);
       return (float)costs;
     }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm.Data/XmlDataSource.cs

@@ -1 +1 @@
 
+using System;
 using System.Collections.Generic;
 using System.IO;
 using System.Xml;
+using HeuristicLab.Problems.RoutePlanning.Graph;
 namespace HeuristicLab.Problems.RoutePlanning.Osm.Data {
   public class XmlDataSource : IDataSource {
@@ -82 +84 @@
     }
 
-    #endregion
+    public IGraph GetRoutingGraph() {
+      IGraph graph = new Graph.Graph();
+      foreach (Way way in ways.Values) {
+        List<Node> nodes = way.Nodes;
+        for (int i = 0; i < way.Nodes.Count - 1; i++) {
+          Vertex v1 = new Vertex(nodes[i].Id, nodes[i].Longitude, nodes[i].Latitude);
+          graph.AddVertex(v1);
+          Vertex v2 = new Vertex(nodes[i + 1].Id, nodes[i + 1].Longitude, nodes[i + 1].Latitude);
+          if (v1.Id == 370626403) {
+            Console.WriteLine();
+          }
+          graph.AddVertex(v2);
+          if (way.OneWay) {
+            Edge<Vertex> edge = new Edge<Vertex>(v1, v2);
+            edge.Category = (short)way.HighwayTag;
+            graph.AddEdge(edge);
+          } else {
+            Edge<Vertex> edgeForward = new Edge<Vertex>(v1, v2);
+            edgeForward.Category = (short)way.HighwayTag;
+            graph.AddEdge(edgeForward);
+
+            Edge<Vertex> edgeBackward = new Edge<Vertex>(v2, v1);
+            edgeForward.Category = (short)way.HighwayTag;
+            graph.AddEdge(edgeBackward);
+          }
+
+        }
+      }
+      return graph;
+    }
+
+    #endregion
+
+    #region Private Methods
 
     private void ReadData() {
@@ -214 +249 @@
       }
     }
+
+    #endregion
   }
 }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm/IDataSource.cs

@@ -1 +1 @@
 
 using System.Collections.Generic;
+using HeuristicLab.Problems.RoutePlanning.Graph;
 namespace HeuristicLab.Problems.RoutePlanning.Osm {
   public interface IDataSource {
@@ -8 +9 @@
     List<Way> GetWays(Node node);
     Relation GetRelation(long relationId);
+    IGraph GetRoutingGraph();
   }
 }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm/Utils.cs

@@ -8 +8 @@
       double dy = p2.Y - p1.Y;
       return Math.Sqrt(dx * dx + dy * dy);
+    }
+
+    public static double LocationDistance(PointD p1, PointD p2) {
+      // The Haversine formula
+      /* dlon = lon2 - lon1
+            dlat = lat2 - lat1
+            a = (sin(dlat/2))^2 + cos(lat1) * cos(lat2) * (sin(dlon/2))^2
+            c = 2 * atan2(sqrt(a), sqrt(1-a)) 
+            d = R * c
+       */
+
+      double lat1Rad = p1.Y * (Math.PI / 180.0);
+      double long1Rad = p1.X * (Math.PI / 180.0);
+      double lat2Rad = p2.Y * (Math.PI / 180.0);
+      double long2Rad = p2.X * (Math.PI / 180.0);
+
+      double longitude = long2Rad - long1Rad;
+      double latitude = lat2Rad - lat1Rad;
+
+      double a = Math.Pow(Math.Sin(latitude / 2.0), 2.0) +
+                   Math.Cos(lat1Rad) * Math.Cos(lat2Rad) *
+                   Math.Pow(Math.Sin(longitude / 2.0), 2.0);
+
+      double c = 2.0 * Math.Asin(Math.Sqrt(a));
+
+      const double earthRadiusKms = 6376.5;
+      double distance = earthRadiusKms * c;
+
+      return distance;
     }