Re: [OSRM-talk] Shortest route given start and end point
Hi, I have used a strategy close to what is described in the mentioned ticket (see my comment there). It did work for another project to add this specific feature to an existing TSP solver. As for the "computationally expensive" side, it is all a matter of trade-off between computing time and solution quality. My experience is that 1000's can still be tackled in a matter of seconds with very decent results. Hope this can help, Julien Le 09/12/2015 22:32, Patrick Niklaus a écrit : Hey, no sadly we don't support this yet. Corresponding ticket is here [1]. Chau suggests a approach in the ticket, but we never investigated if its actually viable/correct. Let me know if you want to give this a spin. Cheers, Patrick [1] https://github.com/Project-OSRM/osrm-backend/issues/1623 On Wed, Dec 9, 2015 at 11:38 AM, Kieran Caplice wrote: Hello, At the moment we're using the MapQuest Optimize Route API (http://www.mapquestapi.com/directions/#optimized), which given a list of points, computes the shortest route, using the first point as the start and the last point as the end. This is the exactly the functionality we're looking for, but MapQuest is quite expensive, slow, and doesn't support large batches (we need to support a couple of thousand points). From what I've been told, OSRM doesn't support this - it only supports travelling salesman (trip), using the same start and end point, or viaroute, which doesn't do any optimisation. I'm wondering how easy/possible would it be to implement in OSRM, or is there any pre/post processing that we can do to achieve this? Thanks in advance. Kind regards, Kieran Caplice ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] Shortest route given start and end point
Hi Kieran, You're correct, OSRM doesn't currently implement the query you want. All the data you need to answer the question is in the response of the `/table` API. In theory, supporting this exact situation (fixed start/end nodes) should be a fairly simple change to the trip plugin. With the addition of a URL parameter to indicate that it's not a round-trip, we could insert a dummy node between the start/end points with 0 weight, and this should find a path with the properties you want, once we discard the dummy node at the end. Changes here should be mostly limited to the `plugins/trip.cpp` file, adding some entries to the distance table before performing the TSP search. Even without this feature, you could test OSRM with a couple of thousand points for a full round-trip. Performance for the query would be roughly the same, and I have no idea how it would handle 1000's. It's absolutely unfeasible for a brute-force search, that is limited to 10 nodes inside OSRM, so it would use the Farthest Insertion algorithm, which we've had good results with with 10's to 100's of points, but I don't know if it's been tested to 1000's. I suspect it's probably still going to be slow, you're asking some pretty computationally expensive questions here. daniel > On Dec 9, 2015, at 2:38 AM, Kieran Caplice wrote: > > Hello, > > At the moment we're using the MapQuest Optimize Route API > (http://www.mapquestapi.com/directions/#optimized), which given a list of > points, computes the shortest route, using the first point as the start and > the last point as the end. This is the exactly the functionality we're > looking for, but MapQuest is quite expensive, slow, and doesn't support large > batches (we need to support a couple of thousand points). > > From what I've been told, OSRM doesn't support this - it only supports > travelling salesman (trip), using the same start and end point, or viaroute, > which doesn't do any optimisation. I'm wondering how easy/possible would it > be to implement in OSRM, or is there any pre/post processing that we can do > to achieve this? > > Thanks in advance. > > Kind regards, > Kieran Caplice > > > ___ > OSRM-talk mailing list > OSRM-talk@openstreetmap.org > https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] Shortest route given start and end point
Hey, no sadly we don't support this yet. Corresponding ticket is here [1]. Chau suggests a approach in the ticket, but we never investigated if its actually viable/correct. Let me know if you want to give this a spin. Cheers, Patrick [1] https://github.com/Project-OSRM/osrm-backend/issues/1623 On Wed, Dec 9, 2015 at 11:38 AM, Kieran Caplice wrote: > Hello, > > At the moment we're using the MapQuest Optimize Route API > (http://www.mapquestapi.com/directions/#optimized), which given a list of > points, computes the shortest route, using the first point as the start and > the last point as the end. This is the exactly the functionality we're > looking for, but MapQuest is quite expensive, slow, and doesn't support > large batches (we need to support a couple of thousand points). > > From what I've been told, OSRM doesn't support this - it only supports > travelling salesman (trip), using the same start and end point, or viaroute, > which doesn't do any optimisation. I'm wondering how easy/possible would it > be to implement in OSRM, or is there any pre/post processing that we can do > to achieve this? > > Thanks in advance. > > Kind regards, > Kieran Caplice > > > ___ > OSRM-talk mailing list > OSRM-talk@openstreetmap.org > https://lists.openstreetmap.org/listinfo/osrm-talk ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
[OSRM-talk] Order of via_points in /trip response
Firing a query like:
http://
{IP_ADDRESS}:5000/trip?loc=18.9457243,72.8237605&loc=18.9457243,72.8237605&loc=18.9414821,72.8284626&loc=18.9457243,72.8237605&loc=18.9629992,72.8175748&loc=18.9352599,72.8371511&loc=19.1227498,72.8932321
The order of the points in the response in via_points object was:
1. 19.123192,72.892303
2. 18.935261,72.837151
3. 18.941444,72.828468
4. 18.945871,72.82399
5. 18.945871,72.82399
6. 18.945871,72.82399
7. 18.962875,72.817871
8. 19.123192,72.892303
Why don't the points follow the order in which they were input in the
query? Why are the points changed in via_points and appear slightly
different than the original ones supplied in the query?
Also, is the last loc (in the query) always the first and last via_point?
The same issue I have posted on osrm github[1].
[1]: https://github.com/Project-OSRM/osrm-backend/issues/1806
--
Prateek Sachan
Indian Institute of Technology Delhi, 2014
___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk
[OSRM-talk] Shortest route given start and end point
Hello, At the moment we're using the MapQuest Optimize Route API (http://www.mapquestapi.com/directions/#optimized), which given a list of points, computes the shortest route, using the first point as the start and the last point as the end. This is the exactly the functionality we're looking for, but MapQuest is quite expensive, slow, and doesn't support large batches (we need to support a couple of thousand points). From what I've been told, OSRM doesn't support this - it only supports travelling salesman (trip), using the same start and end point, or viaroute, which doesn't do any optimisation. I'm wondering how easy/possible would it be to implement in OSRM, or is there any pre/post processing that we can do to achieve this? Thanks in advance. Kind regards, Kieran Caplice ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
