Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I'm developing an application for academic purposes that mainly gives to the user a recommended itinerary for a previously introduced preferences (Gastronomy, Leisure,etc.).

For this purpose, I use osm data in a PostgreSQL database imported with osm2po (routable network) and with osmosis for the interest points (POI). Furthermore I use the PgRouting and PostGist extensions for this database, that let me perform shortest paths between vertex.

Briefly, the procedure is as follows: I obtain a set of POIs near a certain localization accordingto the user preferences (maybe 100 or 200) I filter them according to their score and then I construct the distances matrix (I use this structure MultikeyMap, to store pairs of POIs and the cost related to go to one to each other).

Constructing this matrix is a critical proccess because I must to perform shortest paths (Dijkstra in PgRouting PgRouting_Dijkstra) to each POI to each others and store this information in the structure previously mentioned (MultikeyMap).

Finally, I send this matrix to an algorith that calculates the best itinerary according to these POIs - costs and maximizing the score as maximum as possible.

The problem I've found is that sometimes, I've pairs of POIs with no cost, namely a POI that is reached for some other POIs, but not for all of them. I've checked this issue with the JOSM tool, and I've realized that the problematic POI is unconnected with the other ones.

Is there a way to check if a vertex is disconnected or unreachable? Should I check it before doing the distances matrix or before sending to the Route Algorithm?

Thanks in advance!

Excuse my english :(


For example, if we go to A->B with a cost of 0.3, I would store (A,B,0.3) in the MultikeyMap. The reason is to have an structure to store the overall information about the POIs an their costs for go to one to each others and then that let me access them in a efficiently way. Maybe there were other better and more efficient alternatives :(.

In my case I faced the problem of the time response, the calculation of the distances matrix for a set of 75 or 100 POIs is really expensive, PgRouting dijkstra takes a few on seconds in each one. For Dijstra query, I use this function: dijkstra_sp_delta_directed() with the directed parameter set to true.

Thereby I consider the cost of go to A->B is the same to B->A, I construct a triangular matrix (maybe my problem comes for this...).

Then I send the MultiKeyMap to the route algoritm. I've done two implementations for this. The first one based on the heuristic of I-Ming Chao, Bruce L. Golden and Edward A. Wasil, this implementation have the following steps: Initilization, Two-points-exchange, One-point-movement, Clean-up and Reinitialization. We can summarize it in the steps of Initialization-Improvement-Reinitialization (exchange and movement belong to the Improvement step).

The second implementation is a GRASP with Path Relinking, based on the paper of Vicente Campos and Rafael Martí and it has similar steps: Initialization-Improvement-PathRelinking.

Finally, this implementations give a path that, in theory, contains the best POIs to visit according to the preferences and the time limit. This path will be sent to a client (handheld device) and this device will plot the route (mapsforge-library).

Before sending the optimal path to de client device, I need to perform several checkings in order to send a correct path (set of LINESTRINGS) to the mobile-device. This implies checking the LINESTRINGS before send them and reorder its coordinates so that the final coordinate match with the first one of the following edge and so on.

Another factor that may influence is the calculation of the nearest POIs. I perform this query:

  SELECT node_id, ST_ASTEXT(geom) as the_geom, score
FROM nodes, node_tags
WHERE node_id=id AND <setOfTags> AND ST_DWithin (geom,'SRID=4326;POINT(lon lat)'::geography,radius)

Note that setOfTags will include the preferences of the user (Gastronomy, Leisure, etc.) With these POIs, I would find their nearest vertex (source/target in osm2po generated table) and then I would calculate the distances between them as I explained before.

I hope I've explained clearly the problem and how I'm working.

Excuse again for any mistake with my english and thanks for your patience.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Actually, osm contains disconnected nodes. Additionally there are nodes which can only be reached from one direction but not reverse. This is the case where oneways have been clipped at border regions of your extract. You see, there is no guarantee for A->B => B->A. Nevertheless, the routing itself should give you the answer whether a route is valid or not. Hence, I do not see any reason to check this in a preprocessing step. If I understood you correctly, you are going to build up a distance matrix. But what do you need a MultiKeyMap for? This is an NxN-Matrix and it can be calculated in linear time (not in N^2). Another question: Which Algo are you using? One of the lin2/3opt-family?

share|improve this answer
1  
Did you really mean to say "NxN" matrix? If that refers to a full distance matrix among N points, then--unless the points fall into disconnected groups lying along nonbranching lines--it requires at least O(N^2) time to compute, if only because it potentially contains O(N^2) independent coefficients! –  whuber Mar 20 '13 at 20:18
    
Indeed, if you call Dijkstra for each pair in the matrix you'll end up with an O(N^2)-Problem. But this is not needed and not the case. A Dijkstra is not goal directed, hence you can exploit its nature to get a result in linear time. Meaning, calling it once from a given source without valid target calculates all shortest path to all other nodes (targets). To be more precise: One full Dijkstra-traversal calculates one matrix-row. –  Carsten Mar 21 '13 at 18:10
    
Right: and because you describe this as an "NxN" matrix, that says you are considering N such rows. In general, each requires a separate O(N) calculation, giving O(N^2) total effort. –  whuber Mar 21 '13 at 18:54
    
I did not say a single row calculation needs O(N) ;-) –  Carsten Mar 21 '13 at 19:15
    
"All shortest path[s] to all other nodes" involves N outputs, whence it is at least O(N)--unless you meant for "N" to refer to something other than the number of nodes or points. –  whuber Mar 21 '13 at 19:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.