Issue with Trip service

[moeinpaki]

We have an issue on the OSRM routing system which appears to be a bug. We have a set of points on which we'd like to use the optimize: true option in order to achieve the best path.
The problem is that when we position one of these points at the very center of a roundabout, the point is "ignored" and pushed to last in the line even though it is closest to the origin point
how it is supposed to work:

expected result:

actual result:

[danpat]

Can you supply the API calls you're making?

By default, the /trips API calculates a round-trip - it's expected that you'll return to your origin, and it tries to find the best way to do that.

Try adding roundtrip=false&source=first to the API request - this will make the solver start at your first coordinate, but then leave the destination open-ended - it will find the shortest overall path that visits all destinations, ending anywhere.

[moeinpaki]

Hi, I tried roundtrip=false but I got an error

https://router.project-osrm.org/trip/v1/car/51.3919205,35.7006172;51.407668590545654,35.711639291719464;51.3987081,35.7051247;51.41035079956055,35.73369360286466?overview=simplified&source=first&roundtrip=false

[moeinpaki]

I think I should pass this roundtrip=false&source=first&destination=last
and the problem is I don't want to set last destination manually

[murphy-paul]

I'm having a similar issue and wondering how to have roundtrip=false without the need to explicitly specify the destination. This seems to me like a significant limitation of the trip service as realistically roundtrip=false is unusable, no? How can I know what the optimal destination is?

@danpat Is there some work around to figuring out the destination that you can think off? any help would be greatly appreciated.

[danpat]

Someone needs to add this feature to here:

https://github.com/Project-OSRM/osrm-backend/blob/master/src/engine/plugins/trip.cpp#L93

The algorithms used always construct a round-trip. To generate non-round-trips, the we modify the cost table before running the algorithm, then do some extra work to make sure the returned result starts at the expected location.

For the open destination option, what you'd need to do is insert a new fake node into the table. Then set:

1. Fake node -> start node = 0 cost
2. Fake node -> all other nodes = infinite cost (INVALID_EDGE_WEIGHT)
3. All nodes -> fake node = 0 cost

This would ensure that the round trip included the leg "Fake node" -> "start node" - you would then emit results starting at start node, and stopping when "Fake node" is encountered in the round-trip.

This is basically what the above linked function is doing already for fixed start/end, but I think you might need to go to the extra step of inserting a fake column in the table because of the asymmetrical costs you need to the fake node. It might be possible to re-cost the table in-place to achieve the open destination option, but I'll leave that as an exercise for the implementer to try.

[emaxedon]

I'm still running into issues with the Trip service. Are there any known workarounds to getting the trip service to calculate with roundtrip=false? I'm getting the exact same issue as @moeinpaki.

[mjjbell]

I've taken a stab at implementing @danpat's suggestion in #6050
I think you can get away without the fake node and just set all costs to the start node to 0.
In effect, finding a round-trip that ignores the cost of getting back to the start.

[tammarut]

I've taken a stab at implementing @danpat's suggestion in #6050 I think you can get away without the fake node and just set all costs to the start node to 0. In effect, finding a round-trip that ignores the cost of getting back to the start.

Need this feature to be merged! it's especially useful👏🏻
How is this PR going?