dijkstra (#16) - Route Cost problems (#239) - Message List

Route Cost problems

I'm having problems putting weightings on roads. For this task I've selected a small area of my road network.

I put a weighting of 1000 on one of the roads and the alternative route was not taken.

SQL code for the table can be found here:  http://www.oconnorwebsites.net/newbridge.sql

There is a costing of 1000 on gid:15521 but is still routing right through it.

Edit: This problem is with the algorithms dijkstra_sp_delta, astar_sp_delta and shootingstar_sp

Thanks!

soconnor
04/04/09 00:45:10 (20 months ago)
Tree View Flat View (newer first) Flat View (older first)
  • Message #842

    Could you also post the SQL query with start point and end point, which doesn't work as expected?

    If this would be only the case for Dijkstra and A*, the reason could be that you have two (or more) possible links between two points A and B. The algorithm will always choose the first one no matter the cost you assign to the other one. This is not an issue with Shooting Star though.

    Another question: do you get correct results if you use the length as cost without weighting?

    One more idea as your file is called "newbridge": If you have a very sparse network (for example you want to route from one side of the river to the other side and not many bridges available), the bounding box value to select an area from the database might be too small, so the alternate bridge is not available in the area that the algorithm takes into account.

    daniel
    04/04/09 16:10:59 (20 months ago)
    • Message #854

      Could you also post the SQL query with start point and end point, which doesn't work as expected?

      SELECT rt.gid, AsText?(rt.the_geom) AS wkt,

      cost AS length, newbridge.id

      FROM newbridge,

      (SELECT gid, the_geom

      FROM shootingstar_sp(

      'newbridge', 15517, 14984, 5000, 'length', true, true)

      ) as rt

      WHERE newbridge.gid=rt.gid;

      Results of the above query are as follows:

      [GID ] [WKT ] [LENGTH ]

      15517 MULTILINESTRING....

      15490 MULTILINESTRING....

      15221 MULTILINESTRING.... 1000

      15206 MULTILINESTRING....

      14984 MULTILINESTRING....

      If this would be only the case for Dijkstra and A*, the reason could be that you have two (or more) possible links between two points A and B. The algorithm will always choose the first one no matter the cost you assign to the other one. This is not an issue with Shooting Star though.

      The issue is with all the algorithms

      Another question: do you get correct results if you use the length as cost without weighting?

      It's routing fine in terms of the shortest path in terms of length, but when I replaced the cost from length to my own values then the route has not changed and is still taking the shortest path. The cost seems to be irrelevant.

      One more idea as your file is called "newbridge": If you have a very sparse network (for example you want to route from one side of the river to the other side and not many bridges available), the bounding box value to select an area from the database might be too small, so the alternate bridge is not available in the area that the algorithm takes into account.

      Just to clarify no bridges are involved with the file supplied. Thats the name of a townland in Ireland! I hand picked the area myself, so as to provide alternative routes of a route!

      soconnor
      04/05/09 23:40:32 (20 months ago)
      • Message #856

        Hi, your query is correct but you take just the length as cost.

        You could do something like this: 

        SELECT rt.gid, AsText(rt.the_geom) AS wkt, cost AS mycost, newbridge.id
    FROM newbridge,
        (SELECT gid, the_geom
            FROM shootingstar_sp(
                'newbridge', 15517, 14984, 5000, '2*length+(somecost/2)', true, true)
        ) as rt
    WHERE newbridge.gid=rt.gid;

        Instead of '2*length+(somecost/2)' you can do any maths or even do a subselect.
        We often take length in our examples, because it is usually available with even simple data and it returns a reasonable route. But you can mix the cost parameter as you like.

        daniel
        04/06/09 14:13:58 (20 months ago)
        • Message #858

          I still get the same route. Maybe its due to the length of the roads? It seems like its just selecting the one road, whereas is should select the other road and come back in on the main road.

          soconnor
          04/07/09 19:35:15 (20 months ago)
          • Message #859

            Can you post your query?

            daniel
            04/07/09 19:47:35 (20 months ago)
            • Message #860

              SELECT rt.gid, AsText?(rt.the_geom) AS wkt, cost AS mycost, newbridge.id

              FROM newbridge,

              (SELECT gid, the_geom

              FROM shootingstar_sp(

              'newbridge', 15517, 14984, 5000, '2*length+(1000/2)', true, true)

              ) as rt

              WHERE newbridge.gid=rt.gid;

              soconnor
              04/07/09 19:51:58 (20 months ago)
              • Message #861

                I think you get this result, because it's correct. In your cost calculation still the only one parameter that matters is "length".

                Let's say you have an attribute "speed" for each road link (high for highways and low for residential roads).You could then calculate your cost as 'length*speed' ... just an example.

                If you had an attribute describing the road safety you could calculate the most safe route for example with 'length*(safety/speed)'. Probably makes no sense, just an example.

                daniel
                04/07/09 19:59:05 (20 months ago)
Tree View Flat View (newer first) Flat View (older first)