Distance matrix API

[lokeshlal]

Hi,

As most of you here are working on routing problem. I need a suggestion.

Bing, Google and other APIs are only providing 25x25 origin-destination matrix in one request. (for example: https://developers.google.com/maps/documentation/distance-matrix/usage-limits)

In our case, we have approximately close to 1000 locations. What would be the suggestion? shall we go with Manhattan distance or issue 25*25 request. Or let the distance callback issue request for every single origin-destination pair.

Thanks,

[Mizux]

Usually we limit to ~20 locations to keep the request under few hundred milliseconds.
And I guess the pricing is one count per cell so it can become expensive very quickly for larger matrix !
EDIT: Pricing here
note: AFAIK a direction matrix query n*n count as n*n queries...

You could do several requests then run ortools locally but I think using the manhattan distance as first approximation could be a reasonable choice as first approximation.

note: if you don't have one way road you could only request half part of the matrix since you'll have a symmetric matrix...

[TheCoolRob]

Seems like the OSRM folks are about to pull in distance-table functionality into the main branch. It's not the fastest way to do it but it's publicly available and supported. You can run your own server against a smaller map-set that should give you better performance than the figures quoted in the pull request:
Project-OSRM/osrm-backend#4990
@Mizux is right about potentially halving the payload size if you don't have one-way streets but it's often difficult to know that up front in general (highways are effectively one-ways).

[morruth]

my 5 cents for OSRM
if you need matrix more than 100 locations, you'll need host osrm-routed yourself
manhattan distance and large circle arc distance give far from optimal results if exists long obstacle
like river or railway

[morruth]

»Or let the distance callback issue request for every single origin-destination pair.

Never ever think about it
it'll be flood of requests to service each time you try to solve.
I think service 'll ban you very quickly

[lokeshlal]

Thank you very much all. OSRM was easy to setup and use. I haven’t tried it on a larger set of coordinates. However on a smaller set it works fine.

[jd-20]

@Mizux how do I go about using the API for 100 locations? Even after sending 25 locations in each request how do I take the values from the resultant matrices in a 100x100 matrix?