search

Project-OSRM / osrm-backend

Open Source Routing Machine - C++ backend
http://map.project-osrm.org
BSD 2-Clause "Simplified" License
6.41k stars 3.39k forks source link

with waypoints, reduce the number of roads shared by both segments #5074

Open MichalPP opened 6 years ago

MichalPP commented 6 years ago

while routing A -> B -> C sometimes the segments A->B and B->C share a large segment of the trip. this is very undesirable with hiking or tourism routing. an extreme example. It would be nice that the route from start to 1 would go over the blue road. when routing directly start to 1, the route also shows alt routes which would be more fitting for the previous case.

a naive implementation would be to calculate A->B and B->C including all alternatives and then choose route A->B->C of the alternative which share the least of geometry.

please change subject so that it describes the topic in a better way

danpat commented 6 years ago

@MichalPP You might want to investigate using the continue_straight=true API parameter - this will force waypoints in the middle to continue in the direction that the the waypoint was arrived at, preventing this kind of retracing-your-steps behaviour.

MichalPP commented 6 years ago

continue_straight does not help. it only tells to continue straight, so it helps only when the waypoint is on a long edge. It fails in situations when the waypoint is at the end of the dead-end road or on a small side road: router then returns to the road (which shares a lot with the way to the waypoint)

danpat commented 6 years ago

@MichalPP ok - if continue_straight isn't going to work for you, then it'll need some fairly major work in the routing algorithm side.

Fundamentally, OSRM's two main (current) algorithms, CH and MLD, structure the routing graph optimized for finding shortest paths quickly. To do this, they exclude paths like you want here - these paths simply aren't available to the routing algorithm.

I'm going to mark this as a feature request, but I don't see anyone working on it any time soon.

MichalPP commented 6 years ago

@danpat do I understand calculation of route A->B->C as two separate calculations A->B and B->C (by CH or MLD) which are then sewed together? this would fairly easy allowed to solve this feature request. plus it would also allow to publish alternatives for routes with waypoints.