Forum #18 - Topic #23 - Message List
First of all thank for your great work.
I would like to describe the situation (I'm sorry for my pure english) I have downloaded 1.0.0a win 32 version. I have used some sample data for routing CREATE TABLE "map_polish"."rtest" (
"gid" SERIAL,
"source" INTEGER NOT NULL,
"target" INTEGER NOT NULL,
"cost" DOUBLE PRECISION DEFAULT 0 NOT NULL,
"rcost" DOUBLE PRECISION DEFAULT 0 NOT NULL,
"x1" DOUBLE PRECISION DEFAULT 0 NOT NULL,
"y1" DOUBLE PRECISION NOT NULL,
"x2" DOUBLE PRECISION NOT NULL,
"y2" DOUBLE PRECISION NOT NULL,
"rule" TEXT,
"to_cost" DOUBLE PRECISION NOT NULL,
CONSTRAINT "rtest_pkey" PRIMARY KEY("gid")
) WITH OIDS;
CREATE INDEX "rtest_idx" ON "map_polish"."rtest"
USING btree ("source", "target");
INSERT INTO "map_polish"."rtest" ("gid", "source", "target", "cost", "rcost", "x1", "y1", "x2", "y2", "rule", "to_cost") VALUES
(1, 1, 2, 1, 0, 1, 1, 2, 2, NULL, 100),
(2, 3, 2, 1, 0, 3, 3, 2, 2, NULL, 100),
(3, 2, 4, 1, 0, 2, 2, 4, 4, NULL, 100),
(4, 4, 5, 1, 0, 4, 4, 5, 5, '3', 100),
(5, 3, 5, 1, 0, 3, 3, 5, 5, NULL, 100),
(36, 5, 3, 1, 0, 5, 5, 3, 3, '4', 555);
Then I run query: SELECT * FROM shortest_path_shooting_star('SELECT gid AS id,source::int4,
target::int4, cost::double precision, rcost::double precision AS reverse_cost, x1,y1,x2,y2,rule,to_cost FROM map_polish.rtest order by gid',1,5,true,false);
And sometimes I get error (Postgresql process terminates). But in most cases the result is:
vertex_id edge_id cost
0 1 1
1 3 1
4 4 1
6 36 1
2 5 1
1)Edges where found correctly
2)In my opinion vertices are not correct
3)In data there are 2 turn restriction for edges 3->4, 4->36. But in result they do not influence on resulting costs
I use it with postgresql 8.2.3 and postgis 1.2.1 Win XP.
Thanks in advance.
-
Message #79
Hello,
Thank you, we are really glad to know that our project is useful!
1) Hooray!
2) Yeah, that's my fault. Shooting* is an edge-based algorithm, so I thought that vertices are not so important. Well, I think we can fix it if you really need correct vertices.
3)You are calling Shooting* with 'true,false'. It means that you want to have your road network directed, without reverse cost. Thus there is no other way from edge 1 to 5, 'cause it cannot pass edge 2. Yes, there are turn restrictions and they rise a cost of passage by a value of 'to_cost' field. So, in your case it is still possible to pass from edge 1 to 5, but the cost is high. You can try to add one more edge between vertices 4 and 3 with a high cost (let's say 10) and the algorithm will choose this one.
anton06/28/07 11:52:37 -
Message #80
Thanks for your quick reply, Anton.
But I didn't understand the reply on 3-rd question:
3)You are calling Shooting* with 'true,false'. It means that you want to have your road network directed, without reverse cost. Thus there is no other way from edge 1 to 5, 'cause it cannot pass edge 2. Yes, there are turn restrictions and they rise a cost of passage by a value of 'to_cost' field. So, in your case it is still possible to pass from edge 1 to 5, but the cost is high. You can try to add one more edge between vertices 4 and 3 with a high cost (let's say 10) and the algorithm will choose this one.
The matter is that in my test data I have directed edge(id=36) for vertices (5->3)
(36, 5, 3, 1, 0, 5, 5, 3, 3, '4', 555);
The result of shooting* algorithm of the shortest path from edge 1 to edge 5 was: 1->3->4->36->5. It is correct result, but the costs where wrong because I have turn restriction 3->4 (turn cost is 100) and 4->36 (turn cost is 555). In the result all costs are 1. Please correct me if I miss something.
And It may be off topic: I didn't understand from the documentation of using shooting* algorithm.
To describe turn restrictions:
gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
12 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 14
means that the cost of going from edge 14 to edge 12 is 1000, and
gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
12 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 14, 4
means that the cost of going from edge 14 to edge 12 through edge 4 is 1000.
The question is: how to describe rule - edge 12 has turn restriction cost from edge 14 and turn restriction cost from edge 4? Edges 14,4 and 12 have only 1 common vertex.
siarhei06/28/07 15:45:27 -
Message #81
The result of shooting* algorithm of the shortest path from edge 1 to edge 5 was: 1->3->4->36->5. It is correct result, but the costs where wrong because I have turn restriction 3->4 (turn cost is 100) and 4->36 (turn cost is 555). In the result all costs are 1. Please correct me if I miss something.
No, you're right!
I thought that normaly you shouldn't get any restricted turns in a result, 'cause in a real world there should be other way. That's why I put edge cost to the result without adding a cost of restricted turns.
Also, cost usualy means length. Probably, it can be pretty confusing to add some fictional value to a length.
Well, I think it will be better not to return a path at all if it contains restricted turns. Or, if you wish, I can add 'to_cost' value. What do you think?
The question is: how to describe rule - edge 12 has turn restriction cost from edge 14 and turn restriction cost from edge 4? Edges 14,4 and 12 have only 1 common vertex.
In this case you need to make two entries for edge 12 - one with 'rule' value '14' and another one with '4'.
The function will combine them into one edge. In this case it is important to use 'order by gid' in the main query.
anton06/28/07 17:14:02 -
Message #82
I thought that normaly you shouldn't get any restricted turns in a result, 'cause in a real world there should be other way. That's why I put edge cost to the result without adding a cost of restricted turns. Also, cost usualy means length. Probably, it can be pretty confusing to add some fictional value to a length. Well, I think it will be better not to return a path at all if it contains restricted turns. Or, if you wish, I can add 'to_cost' value. What do you think?
I think that to_cost value can be spent time on passing through the edges. So as to restrictions if to_cost value is positive (as in documentation it can be traffic light ) it can take part in calculating shortest path( with to_cost values).
But if to_cost value is negative (-1) then restriction turn must not appear in shortest path result
siarhei06/28/07 17:38:56 -
Message #84siarhei06/28/07 18:11:41
-
Message #85siarhei06/28/07 18:12:07

