[GraphHopper] distance matrix
Peter K
peathal at yahoo.de
Thu Jul 4 16:52:13 UTC 2013
Hi Laura,
there are lots of tricks which I also will investigate in the near future.
You need to do it this way (n*n) BUT you cache the shortest path tree of
every points. Then (for every bidirectional algorithm like CH) you can
reuse the shortest path tree of a previous calculated point (if it was
already involved in distance calculation). When using CH you can assume
that one shortest path tree is not that big per point so it is ok to
store n SPTs.
Also I think one can somehow use the locality of one point which has
nearly the same shortest path tree as its neighbor (except for the
beginning).
Regards,
Peter.
BTW: would be interesting to know where a maxspeed of 1890 km/h exists ;) <=> IllegalArgumentException: Speed value too large for encoding: 1890
> Hi Peter,
>
> awesome! It works, I can import the latest road network now. And no
> trains blocking my way ;) Thanks.
>
> With regard to my previous question about generating a distance
> matrix. You said I need to take care of the caching myself. If I have
> n locations in my matrix, do I need to perform O(n^2) queries to
> graphhopper or is there a more time-efficient way to do it? n^2 might
> take quite long although graphhopper is nicely fast for point to point
> calculations. What do you think?
>
>
> Best, Laura
>
>
> 2013/7/4 Peter K <peathal at yahoo.de <mailto:peathal at yahoo.de>>
>
> ok, this is also not critical as this is a disconnected way which
> will be removed in the graphHopper.optimize() phase. So we won't
> route over this in any case. But still I'll make sure that the car
> encoder does not accept railway=* ;)
>
>
>> oh, when reading my mail it looks like we shouldn't route over
>> this "road" at all ;)
>> how can that be ... I'll look into it ...
>>
>>> Hi Laura,
>>>
>>> indeed, my integration tests failed too (but the reporting was
>>> improperly scripted ;))
>>>
>>> The real problem was that there are indeed very unrealistic
>>> maxspeed values or some German Spaßvögel :)
>>> http://www.openstreetmap.org/browse/way/204067725
>>>
>>> * /maxspeed
>>> <http://wiki.openstreetmap.org/wiki/DE:Key:maxspeed?uselang=de>//=
>>> 300/
>>>
>>> Fixed now.
>>>
>>> Regards,
>>> Peter.
>>>
>>>> HI Laura,
>>>>
>>>> thanks! I'll investigate. Try 'git checkout <somewhereBefore>'
>>>> for now ;)
>>>>
>>>> Regards,
>>>> Peter.
>>>>
>>>>> Hi,
>>>>>
>>>>> when I try to import the latest germany file, I now get the
>>>>> following error:
>>>>>
>>>>> 2013-07-04 15:05:44,267 [main] INFO graphhopper.reader.OSMReader - 138?326?809, now parsing ways
>>>>> 04.07.2013 15:05:46 com.google.inject.internal.MessageProcessor visit
>>>>> INFO: An exception was caught and reported. Message: java.lang.IllegalArgumentException: Speed value too large for encoding: 1890
>>>>> java.lang.IllegalStateException: Couldn't load graph
>>>>> at com.graphhopper.http.DefaultModule.configure(DefaultModule.java:62)
>>>>> at com.google.inject.AbstractModule.configure(AbstractModule.java:59)
>>>>> at com.google.inject.spi.Elements$RecordingBinder.install(Elements.java:223)
>>>>> at com.google.inject.spi.Elements.getElements(Elements.java:101)
>>>>> at com.google.inject.internal.InjectorShell$Builder.build(InjectorShell.java:133)
>>>>>
>>>>> Might this relate to the speed limit change performed yesterday?
>>>>>
>>>>>
>>>>> Thanks, Laura
>>>>>
>>>>>
>>>>> 2013/7/3 Peter K <peathal at yahoo.de <mailto:peathal at yahoo.de>>
>>>>>
>>>>> Hi Guillaume,
>>>>>
>>>>> did you pull, recreate graphhopper and import the graph
>>>>> again? For the example graphhopper now returns 1h 6min
>>>>>
>>>>> Regards,
>>>>> Peter.
>>>>>
>>>>>> Hi Peter,
>>>>>>
>>>>>> Thanks a lot for your assistance. Unfortunately, it does
>>>>>> not change the driving duration ...
>>>>>>
>>>>>> BR
>>>>>>
>>>>>> Guillaume
>>>>>>
>>>>>> Le 3 juil. 2013 à 16:34, Peter K <peathal at yahoo.de
>>>>>> <mailto:peathal at yahoo.de>> a écrit :
>>>>>>
>>>>>>> fixed a bug where speed limits can now be bigger than
>>>>>>> the speed estimated by the highway tag.
>>>>>>> Please report if this fixes your problems!
>>>>>>>
>>>>>>> Regards,
>>>>>>> Peter.
>>>>>>>
>>>>>>>> Hi Peter,
>>>>>>>>
>>>>>>>> Here is an example where time difference is around +40%
>>>>>>>> . The good duration is 1h05 min
>>>>>>>>
>>>>>>>> http://graphhopper.com/maps/?point=47.87502,-3.92245&point=48.44791,-4.41854&vehicle=car
>>>>>>>>
>>>>>>>> Graphhopper : 1h23 min
>>>>>>>>
>>>>>>>>
>>>>>>>> http://map.project-osrm.org/?hl=fr&loc=47.87502,-3.92245&loc=48.44791,-4.41854
>>>>>>>> OSRM : 01h04 min
>>>>>>>>
>>>>>>>>
>>>>>>>> Thanks for your help
>>>>>>>>
>>>>>>>> Guillaume
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> Le 2 juil. 2013 à 14:37, Peter K <peathal at yahoo.de
>>>>>>>> <mailto:peathal at yahoo.de>> a écrit :
>>>>>>>>
>>>>>>>>> Hi Guillaume,
>>>>>>>>>
>>>>>>>>> I do not know internals from OSRM but GraphHopper
>>>>>>>>> could probably need
>>>>>>>>> some tuning there (e.g. less speed in cities, less
>>>>>>>>> speed for turns, ...).
>>>>>>>>>
>>>>>>>>> Do you have some example links for OSRM where you
>>>>>>>>> encounter big differences?
>>>>>>>>>
>>>>>>>>> Regards,
>>>>>>>>> Peter.
>>>>>>>>>
>>>>>>>>>> Hello,
>>>>>>>>>>
>>>>>>>>>> We are testing Graphhopper and OSRM and we have found
>>>>>>>>>> some differences in routing times :
>>>>>>>>>>
>>>>>>>>>> - Graphhopper returns longer driving time as OSRM
>>>>>>>>>> does (except for very short distance between 2
>>>>>>>>>> cities). It appears that OSRM driving durations are
>>>>>>>>>> closer to the real durations compare to Graphhopper.
>>>>>>>>>> - We have set same speed parameters (when there is
>>>>>>>>>> no max speed) on Graphhopper (carflagencoder.java)
>>>>>>>>>> and OSRM (car profile).
>>>>>>>>>>
>>>>>>>>>> Both Graphhopper and OSRM seems to be using CH.
>>>>>>>>>>
>>>>>>>>>> How to explain these difference in driving time ? Is
>>>>>>>>>> there a way to modify parameters on Graphhopper to
>>>>>>>>>> get driving durations closer to the real ones ?
>>>>>>>>>>
>>>>>>>>>> Thank you
>>>>>>>>>>
>>>>>>>>>> Guillaume
>>>>>
>>>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20130704/063578b0/attachment.html>
More information about the GraphHopper
mailing list