locked
Least Cost Routing in SQL 2008 RRS feed

  • Question

  • Anybody tried stuff like least cost routing in sql 2008? I have a small road network represented by linestrings in sql, and I'd like to find the shortest (or any other) route between two points. Anyone have some links to whitepapers... tutorials maybe?
    Monday, May 18, 2009 2:29 PM

Answers

  • Sounds like a reasonable first approach... are you doing this as an academic exercise or do you have a particular real-life application in mind?
    One other link you might find useful is http://www.heyes-jones.com/astar.html. It has a good alternative explanation of the A* algorithm, together with links to download an A* implementation in C++ from google code.
    Beginning Spatial with SQL Server http://www.apress.com/book/view/1430218290
    Tuesday, May 19, 2009 7:02 AM
    Answerer

All replies

  • Yes - I've played around with this a bit - you basically have to write your own routing algorithm in .NET. If you haven't done it before, there's some good examples that come from the world of game programming. Try something like the following link, and look up the A* algorithm or Djekstra (http://theory.stanford.edu/~amitp/GameProgramming/)

    However, to try to get anything above the most basic algorithm involves some pretty serious maths, and a lot of data. If you actually want to find the shortest route between two points via a normal road network, I'd recommend you use something like the Virtual Earth Routing Service instead and import the resulting route into SQL Server.
    Beginning Spatial with SQL Server http://www.apress.com/book/view/1430218290
    Monday, May 18, 2009 2:56 PM
    Answerer
  • Hi...

    The A* and Djikstra stuff looks like it might work... thanks.

    I have a huge dataset, and Djikstra requires that each link between nodes be assigned a cost, in other words the value of the heuristic (if I got it right). Is it viable to use the current node's distance (as the crow flies) to the destination node for this value?

    As I have a start and end node, I'll eliminate the majority of the nodes/links by only using the Djekstra/A* algorithm on the links that seem or will most likely connect the nodes, by say drawing a circle around each node, and then a circle to enclose these two circles. All nodes that fall within this bigger circle will be considered as a path. That sound right?
    Tuesday, May 19, 2009 6:41 AM
  • Sounds like a reasonable first approach... are you doing this as an academic exercise or do you have a particular real-life application in mind?
    One other link you might find useful is http://www.heyes-jones.com/astar.html. It has a good alternative explanation of the A* algorithm, together with links to download an A* implementation in C++ from google code.
    Beginning Spatial with SQL Server http://www.apress.com/book/view/1430218290
    Tuesday, May 19, 2009 7:02 AM
    Answerer
  • Hi GrimSt0ner

    Did you have any more luck with the task? I am looking into implementing something similar. I have a small shapefile - data file with some roads and i would like to get some routing using that data.

    Cheers

    Dan


    Dan
    Tuesday, July 13, 2010 3:54 AM
  • I would like to perform routing in MS SQL 2012 which is going to be similar like pg routing ?

    Actually in pgrouting I'll do the following steps to create a routable network.

    1) create a database routing with template "template_routing"


    2) create table "road_network" with following constraints
    ----------------------------------------------------------------
    CHECK (st_ndims(the_geom) = 2)
    CHECK (geometrytype(the_geom) = 'MULTILINESTRING'::text OR the_geom IS NULL)
    CHECK (st_srid(the_geom) = 4030)

    Then
    -- @ CREATE INDEX FOR THE ROAD TABLE -------------------- IMPORTANT

    CREATE INDEX spatialindex_road
     ON road_network
     USING gist
     (the_geom);

    3) Perform following queries
    -------------------------

    ALTER TABLE road_network ADD COLUMN "source" integer;
    ALTER TABLE road_network ADD COLUMN "target" integer;

    SELECT assign_vertex_id('road_network', 0.00001, 'the_geom', 'gid');

    CREATE INDEX source_idx ON road_network("source");
    CREATE INDEX target_idx ON road_network("target");

    ALTER TABLE road_network  ADD COLUMN length double precision;
    UPDATE road_network  SET length = length(the_geom);


    ALTER TABLE road_network  ADD COLUMN reverse_cost double precision;
    UPDATE road_network  SET reverse_cost = length;

    ALTER TABLE road_network  ADD COLUMN x1 double precision;
    ALTER TABLE road_network  ADD COLUMN y1 double precision;
    ALTER TABLE road_network  ADD COLUMN x2 double precision;
    ALTER TABLE road_network  ADD COLUMN y2 double precision;

    UPDATE road_network  SET x1 = x(ST_PointN(the_geom, 1));
    UPDATE road_network  SET y1 = y(ST_PointN(the_geom, 1));
    UPDATE road_network  SET x2 = x(ST_PointN(the_geom, ST_NumPoints(the_geom)));
    UPDATE road_network  SET y2 = y(ST_PointN(the_geom, ST_NumPoints(the_geom)));
    alter table road_network add column cost double precision default 0;
    update road_network set cost=0.1 where type='NH';
    update road_network set cost=0.2 where type='SH';
    update road_network set cost=0.3 where type='major';
    update road_network set cost=0.4 where type='minor';
    update road_network set cost=1.2 where type='colony';
    update road_network set cost=0.8 where type='third';
    4)

    Now network table created
    To check 

    Run: 
    run this query on ur postgreSQL....
    assign table name name and create a table

    CREATE TABLE shortest_path_astar_table_3(gid int4) with oids;
    SELECT AddGeometryColumn( 'shortest_path_astar_table_3', 'the_geom', 4030, 'MULTILINESTRING', 2 );
    INSERT INTO shortest_path_astar_table_3(the_geom) 
    SELECT the_geom FROM astar_sp_directed('road_network',37,43,true,true);

    Open "shortest_path_astar_table_3" on QGIS and check the path

    Is there any similar way to perform similar queries in SQL ?

    Thursday, May 8, 2014 6:02 AM