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.