6

I do not know much about GIS and I do not know much of the jargon. Hopefully you can help me a bit here because I am really unaware of the services and software available.

My problem is as follows: I need to get a distance matrix for a large set of points (up to ~1000 points) all within one city. I need the driving distance (the driving time would be useful as well) between all pairs of such points (so can be up to a million pairs.) Moreover, I need to do this within seconds.

I am not sure if this is actually possible, if it is not then I'll have to reduce the set of points. I do know what the city is in advance, but I do not know in advance what the set of points are. Once the set of points are input into the system, I want to be able to get the distance matrix within seconds (~1-2 seconds).

Some ideas I had so far:

  • Use an API. I did find Google's Distance Matrix API and MapQuest directions API, but neither can handle over 25 locations.

Maybe there are APIs which can handle this?

  • Store the road network ahead of time and calculate the distance matrix locally. This seems like a more feasible solution.

But where do I get that data and what software/libraries can I use to generate the distance matrix from that data?

closed as too broad by PolyGeo Jun 1 '17 at 20:50

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • Always the same city or where on the Earth are you? What is the typical size of city? (population-wise) – Uffe Kousgaard Apr 6 '15 at 16:30
  • Right now I'd like to use it for some of the main cities in Australia: Melbourne, Sydney, Brisbane. But later I'd like to be able to extend it to any city in the world pretty much. – fiftyeight Apr 7 '15 at 1:54
  • I have run a test here with 1000 points and can do it in about 6 seconds, faster if using multiple cores. But this is with a street network of 20,000 links, which equals a city of about 250,000 inhabitants to give you an idea. The same matrix calculated in a much bigger street network would be slower. In fact it may be worthwhile to extract the relevant part on the fly and then rebuild the topology, if the matrix has enough elements, like in this case. This is a test run with our commercially available RWNet4 library. Data was also a subset of OSM. – Uffe Kousgaard Apr 7 '15 at 9:45
2

Open Source Routing Machine is a project of Open Street Map (OSM) also provides distance matrix results although you may find that a 1k x 1k matrix is pushing it. You can build and install locally or use use their API for small sets of points. I believe that there is even a docker instance for the OSRM which you can populate with OpenStreetMap data. I would also suggest looking at GraphHopper ( I have no affiliation ) but can thoroughly recommend it.

0

Please feel free to try out our api. The TravelTime Platform.

We allow 2 main events on our API (The TravelTime Platform)

TimeFilter - allows you to receive time from one origin to 1000's of lat / lngs by any mode of transport in under a second.

TimeMap - Show the catchment area by polygon - use for display or database search.

enter link description here

0

You could use the open source GraphHopper routing library. Very easy to setup and query via HTTP. (Note: I'm the author)

We also offer a commercial Matrix API based on GraphHopper making such queries very fast. Also you could use the Isochrone API.

  • Can you clarify what format for the road-data I need to get for inputting into the routing library? and could you estimate how long it would take to calculate a 1000 x 1000 distance matrix? thank you for your answer – fiftyeight Apr 7 '15 at 1:59
  • GraphHopper uses OpenStreetMap, but you can use other formats with custom import procedure like ordnance survey has done. The speed of the Matrix API heavily depends on the distance of the locations itself, like 1 to 20 minutes – Karussell Apr 7 '15 at 7:48
  • Cool, thank you for the answer. I'd also like to ask, do I need to download the OpenStreetMap data from somewhere and input it into the software, or does it pull it itself once I query the software? – fiftyeight Apr 7 '15 at 7:50
  • You'll need to take care that it downloaded the area before you query it with this. Automatic download could work too but will make the first queries extremely slow – Karussell Apr 7 '15 at 8:07

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