Random Round Tours

[boldtrn]

This PR contains the possibility to create random round tours. When passing tour_length=APPROX_DISTANCE_IN_KM to the request it returns a roundtour of approximately the requested distance. The actual distances can vary a lot, since I only calculate the beeline distance of the waypoints.

The current results are ok, but not good. Especially because the unique_paths PR is not included here (this will probably improve the results.

Currently this feature is not available in the GUI. We just use the first waypoint and create a route.

Something that could be added as well is to calculate a number of tours and select the best one, to remove bad results created by this approach.

[ratrun]

I tried this branch out because it sounds interesting. But it does not work for me. Whenever I add &tour_length=100, no route is found any longer.

This is the trace:

2015-11-29 09:44:16,864 [qtp781309882-27] INFO  com.graphhopper.http.GHBaseServlet - point=48.011975%2C14.331665&point=48.019324%2C14.394493&type=json&key=Cmmtvx01R56rdHcQQo7VjI6rgPgxuFLvqI8cR31u&locale=de-DE&vehicle=bike&weighting=fastest&elevation=true&tour_length=100 127.0.0.1 de_DE Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/46.0.2490.86 Safari/537.36 OPR/33.0.1990.115 [48.011975,14.331665, 48.019324,14.394493], took:0.43054375, , fastest, bike, distance: 0.0, time:0min, points:3, debug - idLookup:9.07056E-4s, algoInit:1.9745E-5s, dijkstrabi-routing:1.9342E-5s, extract time:2.418E-6, algoInit:1.5715E-5s, dijkstrabi-routing:1.2491E-5s, extract time:1.208E-6, algoInit:2.3372E-5s, dijkstrabi-routing:2.0148E-5s, extract time:1.208E-6, simplify (3->3)
2015-11-29 09:44:27,066 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 11.111111111111112
2015-11-29 09:44:27,075 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 3.703703703703704
2015-11-29 09:44:27,085 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 1.234567901234568
2015-11-29 09:44:27,094 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 0.41152263374485604
2015-11-29 09:44:27,105 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 0.13717421124828535
2015-11-29 09:44:27,115 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 0.045724737082761785
2015-11-29 09:44:27,115 [qtp781309882-27] WARN  com.graphhopper.routing.util.TourWayPointGenerator - Could not find a valid point after 50 iterations, for the Point:48.011975,14.331665
2015-11-29 09:44:27,286 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 3.703703703703704
2015-11-29 09:44:27,295 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 1.234567901234568
2015-11-29 09:44:27,305 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 0.41152263374485604
2015-11-29 09:44:27,314 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 0.13717421124828535
2015-11-29 09:44:27,324 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 0.045724737082761785
2015-11-29 09:44:27,332 [qtp781309882-27] INFO  com.graphhopper.routing.util.TourWayPointGenerator - Cannot find anything, reducing the distance to: 0.015241579027587262
2015-11-29 09:44:27,332 [qtp781309882-27] WARN  com.graphhopper.routing.util.TourWayPointGenerator - Could not find a valid point after 50 iterations, for the Point:48.011975,14.331665
2015-11-29 09:44:27,332 [qtp781309882-27] INFO  com.graphhopper.GraphHopper - Calculating a tour instead of regular navigation along these Waypoints: [48.011975,14.331665, 48.011975,14.331665, 48.011975,14.331665, 48.011975,14.331665]
2015-11-29 09:44:27,334 [qtp781309882-27] INFO  com.graphhopper.http.GHBaseServlet - point=48.011975%2C14.331665&point=48.019324%2C14.394493&type=json&key=Cmmtvx01R56rdHcQQo7VjI6rgPgxuFLvqI8cR31u&locale=de-DE&vehicle=bike&weighting=fastest&elevation=true&tour_length=100 127.0.0.1 de_DE Mozilla/5.0 (Windows NT 10.0; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/46.0.2490.86 Safari/537.36 OPR/33.0.1990.115 [48.011975,14.331665, 48.019324,14.394493], took:0.43731946, , fastest, bike, distance: 0.0, time:0min, points:3, debug - idLookup:0.001402693s, algoInit:2.3774E-5s, dijkstrabi-routing:1.9745E-5s, extract time:2.418E-6, algoInit:1.2492E-5s, dijkstrabi-routing:8.865E-6s, extract time:8.06E-7, algoInit:1.5715E-5s, dijkstrabi-routing:1.2089E-5s, extract time:1.209E-6, simplify (3->3)

[boldtrn]

@ratrun haven't tested it for Austria. This might happen sometimes, but shouldn't happen regularly. What area did you use?

[ratrun]

The first log line contains the coordinates and the exact URL. It looks as you can choose any. I tried at least 8 times with differnt start and end point and never got a result.

[boldtrn]

@ratrun thanks for pointing out that there was a mistake. I fixed it and got rid of the ((LocationIndexTree) locationIndex).setMaxRegionSearch(100);

Attached is a screenshot of the generated route (thats actually a good one - took me about 10 repetitions - but you should get a result every time). Currently edges are taken twice, but this should be fixed by #579.

[ratrun]

Thank you. I can confirm that now I always get a result.
I would have a small suggestion for improvement (except for unique paths avoidance): It would be great if one could add another iteration_attempts parameter, which instructs how many routes get calculated and only the result with the lowest overall weighting result should be returned. This iteration_attempts parameter must be limited to a hard-coded value, e.g. 20 such that the computation does not take too long. Most probably @karussell will not want deploy this possibility to the graphhopper main server because of the load. But this would be an interesting feature for private instances.

[karussell]

Thanks for the work. I would like to integrate #420 in the next days first and then adapt this solution to integrate as second alternative to round trip calculation and see which is better in terms of speed and quality or algorithmical approach etc, maybe then combine two approaches or keep them as they are. The unique path calculation should be done in the weighting, where we have to improve the API to allow combination of weightings like suggested by @boldtrn in the other PR.

Furthermore we will definitely deploy this to the API at some point, even if it is load intense, also probably to the GraphHopper Maps demo. That will happen once we have the flexibilty work improved and production ready.

[karussell]

The parts to integrate this into GH are now mostly done: https://github.com/graphhopper/graphhopper/tree/alternate_route2 Would you mind to integrate this?

Currently you need to trigger alternative calculation via &algorithm=alternativeroute&alternative_route.max_num=4 and something similar will be necessary for round trips. Later we can enable this via the UI somehow ...

[karussell]

@boldtrn The alternative routing and 'round trip alt' algorithm are now integrated in the master - enable via algorithm=alternativeroute.

And you can now easily integrate this algorithm (or any improved version you might have) via adding it to RoutingAlgorithmFactorySimple ... and roundtrip is reserved for you. Feel free to throw away my approach which is currently slower and would need a quality boost to come near your results.

[ratrun]

@boldtrn Do you plan to integrate your solution as suggested by Peter? I was thinking about if I should give it a try. But I'm sure it would be much easier for you and if you already started that would make sense at all.

[boldtrn]

@ratrun Yes, this is planned. I might work a bit on this issue today. I hope it's quite straight forward. I wanted to integrate this in the next time.

[ratrun]

Thanks. Great.

[boldtrn]

@ratrun I updated my branch. Let me know what you think.

[karussell]

Thanks @boldtrn that you took the time to reintegrate it!

round_trip.distance

I would use meters as this is the same unit we use for the response

We also need at least one unit and one integration test e.g. in GraphHopperIT for this round trip algo.

GHPoint from, locationIndex

Can we avoid somehow the prepare? The 'lat,lon' stuff is meant for the higher level API and lower level should always use node or edge IDs. Why do you have only 'lat,lon' available when generating the random points? Or could you create the random points at the higher level layer instead? Especially for the unit tests and other integrations it is harder to handle 'lat,lon's instead of IDs.

Can we reduce the complexity a bit? E.g. remove TourStrategyFactory, merge the TourStrategy classes into one and moving TourWayPointGenerator methods into the RoundtripAlgo class? I would avoid introducing an abstraction layer if there is just one implementation or do you have already alternates for them (then it would be okay).

And is the method in CoordinateProjection maybe already covered from a DistanceCalcXY method? If not, I would put the method into an existing Helper class to avoid classes just for one method (?)

[ratrun]

@boldtrn Thank you. This really works very well and the feature is great. I intend to use it for planning of cycle tours in spring. My tests from my location look promising. It chooses very similar cycle routes which I would take.
I have not looked into your implementation yet.
Do you know a possibility to extend the algorithm and also somehow use a second point or alternatively a heading parameter as input in addition? It would be really great if one could influence the direction one intends to go. One explame is that I want to go to direction east. Currently the only possibility is to give it multiple tries and hope that the direction changes to the one you intend.

I'll try to implement a web interface for it based on my master, such that the usage becomes more simple.

@karussell :

round_trip.distance

I would use meters as this is the same unit we use for the response

I believe that kilometers are what users would expect, so this would be more user friendly. But as the end users will not manually mangle URI parameters, I don't care.

[ratrun]

I merged your branch into my master, implemented the WEB UI and pushed the changes.

[boldtrn]

@karussell

I would use meters as this is the same unit we use for the response

Yes sure, we can change this. I started with km since that's usually the unit the user is interested in.

We also need at least one unit and one integration test e.g. in GraphHopperIT for this round trip algo.

Yes, you are right. I will add some tests.

Can we avoid somehow the prepare? The 'lat,lon' stuff is meant for the higher level API and lower level should always use node or edge IDs. Why do you have only 'lat,lon' available when generating the random points? Or could you create the random points at the higher level layer instead? Especially for the unit tests and other integrations it is harder to handle 'lat,lon's instead of IDs.

For the round trip generation I use a technique that is called point projection. I use the starting point and project this point into a certain direction over a certain distance. Then I use the locationIndex to find the closest node. We could do it in the GraphHopper.java class but than we have to pass the generated points to the roundtrip algorithm via RoutingOptions. If we want to generate multiple roundtrips (for alternative paths), we need to generate all these points beforehand. What do you think, should where and how should we generate these points?

Can we reduce the complexity a bit? E.g. remove TourStrategyFactory, merge the TourStrategy classes into one and moving TourWayPointGenerator methods into the RoundtripAlgo class? I would avoid introducing an abstraction layer if there is just one implementation or do you have already alternates for them (then it would be okay).

The current strategy is not the best, but with this layer adding new strategies is really easy and straight forward. I think we will see a lot of interesting strategies in the future. @ratrun just requested adding a second point. This could be easily done by just adding another strategy. In the StrategyFactory on could define what strategy should be picked according to the current situation (e.g. using the two-point strategy only if distance > 50km).

And is the method in CoordinateProjection maybe already covered from a DistanceCalcXY method? If not, I would put the method into an existing Helper class to avoid classes just for one method (?)

I haven't found something like that. Sure, where would you move it?

Do you know a possibility to extend the algorithm and also somehow use a second point or alternatively a heading parameter as input in addition?

@ratrun Yes both should be quite straight forward. Just create a new TourStrategy. Probably you have to extend everything a bit to set an initialBearing. But should be quite easy. Let me know if you need more details. I will add another helper method to the TourStrategy, which should make it easier to generate several points.

I merged your branch into my master, implemented the WEB UI and pushed the changes.

Great news :) Thanks.

[boldtrn]

I just committed the helper function and some tests (not enough).

[karussell]

Yes sure, we can change this. I started with km since that's usually the unit the user is interested in.

Yes, but developers do not care about the unit either as long as it is documented or consistent :) (IMHO)

I haven't found something like that. Sure, where would you move it?

I would put it into DistanceCalcEarth as the earth radius is also there (or could be also related to AngleCalc as it is the 'opposite' of calcOrientation). Furthermore the projectCoordinateRandomBearingAndModifiedDistance is something which should be testable and I would put it as none-static method into the round tour class so unit tests can avoid randomness via creating a fixed seed or a fixed result and method overridign.

Maybe also 'bearing' should be renamed to 'heading' for more consistency to the existent functionality.

The current strategy is not the best, but with this layer adding new strategies is really easy and straight forward. I think we will see a lot of interesting strategies in the future.

Okay, I'm fine with it if there are already two strategies :) but it is overhead if we just plan for them as then it is nearly always the case that refactorings etc are necessary.

For the round trip generation I use a technique that is called point projection. I use the starting point and project this point into a certain direction over a certain distance. Then I use the locationIndex to find the closest node. We could do it in the GraphHopper.java class but than we have to pass the generated points to the roundtrip algorithm via RoutingOptions.

Okay, that sounds doable. Will have to think about it, because an algo setup which requires the location index is too heavyweight and should be 'somehow decoupled' ;). In the worst case instead of passing the locationindex I would provide a lookup hook.

[karussell]

Kind of related a post on HN regarding abstractions vs. unhandleable mess https://news.ycombinator.com/item?id=11093733

[karussell]

When thinking about this more ...

we should move the point creation out of the algorithm and e.g. provide the created points as input for the algorithm or let clients explicitly define points or just one point and a heading etc either with some simple ifs or with the TourStrategy class. Also the randomness should move out of the algorithm if not even to the client itself e.g. providing a random heading direction. What do you think? Should I make a branch to show what I mean (when I find time ;))?

[boldtrn]

@karussell Ok, I am excited. Moving the generated points as input to the algorithm is a good idea (even though the algorithm won't do very much right now if there are no points to generate). For a simple single point strategy generating a random heading by the user seems appropriate. I am not sure about more complex strategies, but I am excited about your branch :).

[ratrun]

@boldtrn

Thank you for the advice. The extension with an initial bearing (=heading) was pretty easy and it works well. As entering of a distance value and bearing value in the GUI as numerical values is not so super intuitive, I'll try to try to implement a two points approach on the WEB UI and calculate the distance parameter and the bearing on the UI.

Here is the basic workflow:
The user will need to enter a first point. Then or before he/she will be able to click on a simple button for round tours. Once pressed, the icon for the second point will change to a center symbol. When the user has entered an initial position of the second point, the JS code will compute the radius distance between the start point and the second point and the direction (=bearing). I intend to use Leaflet distanceTo and http://stackoverflow.com/questions/3932502/calcute-angle-between-two-latitude-longitude-points. The target tour distance gets simply computed with 2_PI_DistanceBetweenTheTwoPoints. At movement of the any of the two points the same thing will happen again. On a click on the center point of the tour, the center point of the tour gets randomly moved to a point on a circle with the start point as center of the circle, and the tour gets recalculated. In case if you have better ideas please let me know.

[boldtrn]

@ratrun

Thanks for explaining. That is actually a nice idea to work with the two points. I don't know if you have made any progress here?

I just recently added the roundtrip feature to a project of mine. There is use https://github.com/aterrien/jQuery-Knob to allow a user to set the bearing. A distance and starting point has to be entered additionally.

[ratrun]

@boldtrn Thanks for the feedback on the GUI idea. I haven't implemented anything as this PR unfortunately is still not accepted and a numerical entry field of the bearing was good enough for me.

[karussell]

Please have a look at this branch: https://github.com/graphhopper/graphhopper/compare/issue_582

What I did:

• merged master
• removed the old round trip algo
• made classes better pluggable and testable -> avoid statics a bit
• avoid randomness via seeds
• avoid a bit casting
• use meters instead km
• improved integration test, added unit test
• renamed a few things

Please question naming and everything. This is for now a rough sketch of what I meant. Still missing is the part where one calculates the initial heading from the second point.

Also I would somehow use the TourPointGenerator which has more control over the whole process instead of the TourStrategy but for now both is still used.

[boldtrn]

@karussell

Thanks. Looks nice. Unfortunately I cannot comment in the code, so I'll just add my comments here.

// TODO use the second point to calculate the initial direction
Actually I am not sure if we should really do it that way. I experimented with a knob and had quite good feedback. See the Roundtour generation at Kurviger.de.

Object algoControl = null;
Would be great if we could create a defined class here. Currently it is only used for the TourPointGenerator right?

long seed = request.getHints().getLong("round_trip.seed", 0L);
Great idea to pass it in the request!

Rates already used Paths worse.
Javadoc needs an update :)

Something I personally would love to improve is the RoundTripPointGenerator. There is to much randomness when generating the points in my opinion. it would be great if there would be a more intelligent solution. When the street network density is low (e.g. in the Alps), there are situations were this approach performs not very well. That might be a different ticket, though.

I am still a fan of the strategy, since this makes the whole approach customizable.

[karussell]

Thanks. Looks nice. Unfortunately I cannot comment in the code, so I'll just add my comments here.

Uhm, ugly. And I cannot push and add to your commits so I've created the branch ... probably I should have opened yet another PR to make it the 'github way'

Actually I am not sure if we should really do it that way. I experimented with a knob and had quite good feedback.

From the API usage I prefer the "point&heading" parameters but the current system prefers "2 points" as with 1 point we get a bit problems with the QueryResult. Still we can workaround this with duplicating the first QueryResult as the second... I'll do that and try to avoid the currently required second point and also we should try to read the (first) heading

See the Roundtour generation at Kurviger.de.

👍 I really like that :)

Would be great if we could create a defined class here. Currently it is only used for the TourPointGenerator right?

Yes. That was necessary to avoid the special cast.

A better approach to put it into the hints but this is only usable for string values :(. And that is by intention as I wanted all 'real objects' being explicit in the AlgorithmOptions or being later created from the strings. Hmmh. Now the Object serve the generic purpose and could be used from any algo. Not sure how to solve this better, a specific class would not make sense too.

Something I personally would love to improve is the RoundTripPointGenerator

You want to improve the implementation details? That should indeed go into another issue :)
For now I would be happy if we can get this merged as a first step :)

[karussell]

Regarding the 'algoControl': what if we calculate the points already and assign the new points and do the regular routing all in the GraphHopper class (point calculation delegated to the point generator). And in the GraphHopper class we would need to intercept the weighting change somehow. Maybe with a custom RoutingAlgorithmFactory?

I mean this part here (except the AvoidPathWeighting) is duplicate to the loop in GraphHopper, and if we can somehow merge this into the normal process we do not need a new roundtrip class, maybe just a factory and the point creation strategy. A further benefit would be that the used algorithm would stay customizable and not fixed to DijkstraBidirectionRef and we could even specify 'pass_through' etc for the round trip segments

[boldtrn]

Uhm, ugly. And I cannot push and add to your commits so I've created the branch ... probably I should have opened yet another PR to make it the 'github way'

Yes, probably you should have created a PR to my PR :D.

Still we can workaround this with duplicating the first QueryResult as the second

Yes, could be a nice workaround.

A better approach to put it into the hints but this is only usable for string values :(. And that is by intention as I wanted all 'real objects' being explicit in the AlgorithmOptions or being later created from the strings.

Could we maybe create an empty Interface called AlgorithmControl (or something like that) to specify what type of object to put in. I am actually not even sure if it's allowed to create empty interfaces, but it would improve the readability for the user.

I mean this part here (except the AvoidPathWeighting) is duplicate to the loop in GraphHopper, and if we can somehow merge this into the normal process we do not need a new roundtrip class, maybe just a factory and the point creation strategy.

Yes you are right. I think I it copied from the GraphHopper class ;). I did not do this for two reasons.
a) We have to add the AvoidPathWeighting to the GraphHopper class, but it would be only used for the roundtrips
b) With random roundtrips you regularly end up with bad routes. Therefore, it is better to calculate several routes and select the best one. We might solve that using the alt paths approach and offer the user for example 3 different routes for one round tour request. But still we need to change the generated points with each iteration, which again changes the core routing functionality of the GraphHopper class.

I would love to implement it in the GraphHopper class, but I thought you would not like it.

[karussell]

I am actually not even sure if it's allowed to create empty interfaces, but it would improve the readability for the user.

Good idea. And yes, that is allowed and called 'marker interface'

I would love to implement it in the GraphHopper class, but I thought you would not like it.

I would not convolute the GraphHopper with round trip specific stuff, that is right. But if we could find a way to abstract this away and bundle it in a round trip algo factory or something that this would be nice. But maybe also part of another PR :)

[karussell]

I've applied the suggestions to the branch. Please have a look.

[boldtrn]

Good idea. And yes, that is allowed and called 'marker interface'

Thanks I didn't know that.

I've applied the suggestions to the branch. Please have a look.

Looks nice, but tests are failing?

I would not convolute the GraphHopper with round trip specific stuff, that is right. But if we could find a way to abstract this away and bundle it in a round trip algo factory or something that this would be nice. But maybe also part of another PR :)

Mhm, if we want to do that, I think we should do it now.
I think there is no way to avoid changes to the GraphHopper class. At least we have to add the AvoidPathWeighting to the path calculation, and update it with the used paths. Another issue is how to calculate multiple paths and how to find the best one.

[karussell]

Looks nice, but tests are failing?

Fixed

Mhm, if we want to do that, I think we should do it now.

Okay, sure. I'll have a look.

[karussell]

The route method has kind of 3 parts: 1. points lookup, 2. route loop and 3. path merger.

Now if I understood this correctly for the round trip we need:

1. create points via some customizable round trip strategy
2. route loop with adjusted weighting and
3. path merger with potentially retry at 1?

[boldtrn]

Now if I understood this correctly for the round trip we need:

Exactly.

[karussell]

I had a bit success in moving 2 and 3 out into another class (probably step 1 is also possible soonish), but then for a new 'round trip implementation' we would need to copy and paste most of this. Hmmh, tricky

[neiljp]

@boldtrn I had a look at your kurvinger.de, since I was interested in the roundtrip work. I'm not fluent in german, but this is for motorbikes? Is the intention to generate round-trips which are of approximately the length (double-headed arrow) in km? I ask since I've used it in some cases and got ones which are eg. 22km instead of "3", though some generated routes were about 3... should it do that? :)
(the use-case I looked at was based on starting at a rail station, since there have been other tools I looked at in the past where people travelled by rail and then did a loop from there - not sure that applies to a motorbike, though ;))

[boldtrn]

@karussell Yes it's really tricky.

@neiljp Yes this is true. The algorithm works best for distances greater than 50km. The usual input is at around 200km. Motorcyclists often ride round tours as day trips. So the intention was to easily generate round trips.

[neiljp]

@boldtrn Ah, shame it doesn't work well for shorter, as it'd be great to have time/distance-guided routes for walking/cycling too :)

[boldtrn]

@neiljp I optimized the algorithms at Kurviger for routes with more than 50km. Maybe you are able to create a nice algorithm for short distances. Feel free to contribute it.

[karussell]

I've created #709 which integrates this PR in a clean fashion (at least it seems so ;)). If someone can have a look at it I would merge or improve it.

@neiljp the current roundtrip algorithm from @boldtrn seems to work for every vehicle rather good.

[neiljp]

@karussell That's great news - I look forward to seeing it in action :)

[karussell]

@karussell That's great news - I look forward to seeing it in action :)

You can easily check the branch #709 out - we would love to get feedback as early as possible :)

Also we do not yet have a UI for this, so it will not be directly available on GraphHopper Maps. Maybe we need something similar like @boldtrn did on kurviger or also @ratrun had something if I remember correctly.