OTP often returning identical itineraries

[samvermette]

Very often OTP returns 3 identical itineraries (sometimes each leaving 20min apart from one another) instead of returning other options that leave asap but might take a little longer. For instance:

If I move my start location by a 100m, I'm getting completely different results (but again, all 3 given options are pratically identical, except for the 18 taking away some walk time)

One would expect to find some of the suggested itineraries in the first screenshot in the 2nd one, and vice-versa. What could be problem here?

Possible cause 1

We currently have our maxWalkDistance set to 5km because otherwise OTP would return "Directions not found" if the closest bus stop was further away than the maxWalkDistance. Although I read on #778 that:

Currently, when a search fails, the router will increase the max walk and search again for a route.

This doesn't seem to be the case at all. At nightime, where active bus routes are much more sparse, users used to complain that the trip planner would return "No Directions Found" (because the closest bus stop was further away than the 0.5 miles default max walking distance).

If we revert it back to that default maxWalkDistance, then we get actual alternatives for that same trip I was mentioning earlier:

Notice that all 3 routes are longer than the ones in the first 2 screenshots. But still, one would expect some of these routes to appear as alternatives in both the 1st and 2nd screenshot.

Possible cause 2

We tried setting numItineraries and CLAMP_ITINERARIES to 10 and again that gives us true alternative itineraries:

Why aren't the first 3 itineraries in that list what's returned by OTP when we have numItineraries set to 3?

This is all using the master branch.

[benmoovit]

Hi Sam Take a look at a similar discussion here (https://groups.google.com/d/topic/opentripplanner-dev/GJ7_sAueeMM/discussion), I figured it may interest you although there is no solution there. Regarding your questions, if I understand correctly, in every search for itinerary the otp searches for the fastest path in time, after a path is found the opt ban the trips in that path and run another search. Because the banning is on the trips we could find others path that use the same route but in different time (meaning others trip of the same route). I have try to change it to ban route and retrieve higher variety in the results. Using this strategy is more complicated and there are several questions that need to be answered. for example, if we have more then one route in an itinerary should we ban all of them for the next search or only same of them and if so which routes should be banned. May this (ban routes) should be an option in the search request?

[abyrd]

On 02/18/2013 11:57 PM, Sam Vermette wrote:

Very often OTP returns 3 identical itineraries (sometimes each leaving 20min apart from one another) instead of returning other options that leave asap but might take a little longer.

This should just be a question of search parameters. Typically we weight initial wait time lower than wait time at transfers to return some later trips. Using the prototypeRoutingRequest property in the API-webapp's application-context.xml, set the waitAtBeginningFactor property (which defaults to 0.2) closer to 1.0, and let me know if your results improve.

We currently have our |maxWalkDistance| set to 5km because otherwise OTP would return "Directions not found" if the closest bus stop was further away than the |maxWalkDistance|. Although I read on #778 https://github.com/openplans/OpenTripPlanner/issues/778 that:

Currently, when a search fails, the router will increase the max
walk and search again for a route.

This doesn't seem to be the case at all. At nightime, where active bus routes are much more sparse, users used to complain that the trip planner would return "No Directions Found" (because the closest bus stop was further away than the 0.5 miles default max walking distance).

One big question: which pathservice are you using?

We tried setting |numItineraries| to 10 and again that gives us true alternative itineraries:

Screenshot-2013-02-18-at-17 45 52 https://f.cloud.github.com/assets/265901/169418/8d43b69c-7a1e-11e2-9678-6797e739894c.png

Why aren't the first 3 itineraries in that list what's returned by OTP when we have |numItineraries| set to 3?

The fact that raising the maximum number of transfers changes the result is a bit troubling, because resource limiting (e.g. limiting the number of transfers in the optimal path) is algorithmically incorrect except under certain circumstances. The way we compare paths using different sequences of trips is intended to make the resource limiting valid.

Again here, it would be helpful to know more about your setup (primarily application-context).

[abyrd]

On 02/19/2013 10:17 AM, benmoovit wrote:

Hi Sam Take a look at a similar discussion here (https://groups.google.com/d/topic/opentripplanner-dev/GJ7_sAueeMM/discussion), I figured it may interest you although there is no solution there. Regarding your questions, if I understand correctly, in every search for itinerary the otp searches for the fastest path in time, after a path is found the opt ban the trips in that path and run another search. Because the banning is on the trips we could find others path that use the same route but in different time (meaning others trip of the same route). I have try to change it to ban route and retrieve higher variety in the results. Using this strategy is more complicated and there are several questions that need to be answered. for example, if we have more then one route in an itinerary should we ban all of them for the next search or only same of them and if so which routes should be banned. May this (ban routes) should be an option in the search request?

We originally banned routes in the retrying path service, and decided to ban trips specifically to give more than one itinerary using the same route if these were indeed the best options (according to the routing parameters).

You should be able to tune what kind of results you receive by adjusting the relative weight of initial wait time, transfer wait time, walking time, etc. If it's not possible to skew the results in the direction you want with these parameters, we will need to identify and fix the problem.

The route/trip banning approach is inherently problematic because, as you mention, the only "fair" way to do it is to ban all the trips/routes used in the previous itineraries, but this excludes other itineraries that happen to include one of the trips/routes. Banning them in some arbitrary order will not necessarily give you optimal routes.

The multiShortestPathTree actually checks the list of trips used in each state and does a prefix comparison to decide whether to allow co-dominant states. This means that if, instead of retrying, you just let the search keep running until it hit the destination N times, you'd get a wider variety of routes (org.opentripplanner.routing.core.State.similarRouteSequence(State)). This is how the multiobjective search works.

However, this often causes too much branching to be efficient. It would be interesting to see how well multiobjective search works with the new ThreadedBidirectionalHeuristic I wrote -- I need to try that out.

[gcamp]

Andrew, we use the default application_context.xml, so the pathservice is RetryingPathServiceImpl. We also tried raptor without any visible changes.

It makes perfect sense to ban a trip and not the entire route, but there is definitely other alternatives that are not shown in the result. If the second trip would be faster by taking the 45 again (instead of an other route), we would have no problem with the result.

waitAtBeginningFactor does seems to fix in indeed. Something like 0.9 seems the better. I believe the default should be changed since it doesn't show trips that are interesting. In the end, if the user is not looking at trips that are acceptable to him he will just look farther in the future. 1.0 would be extreme I understand that (leave 20 min early to gain 1 min).

[abyrd]

On 02/19/2013 07:28 PM, Guillaume Campagna wrote:

waitAtBeginningFactor does seems to fix in indeed. Something like 0.9 seems the better. I believe the default should be changed since it doesn't show trips that are interesting. In the end, if the user is not looking at trips that are acceptable to him he will just look farther in the future. 1.0 would be extreme I understand that (leave 20 min early to gain 1 min).

Glad to hear this improved the situation. If you can observe trip results for a while with a couple of different waitAtBeginningFactors and provide some feedback about the variety of itineraries produced, we can change the default to match.

-Andrew

[phuongnk11]

Dear Andrew,

I'm new to OTP, so I'm writing to ask for your help. I tested OTP with basic usage (following the link: http://opentripplanner.readthedocs.io/en/latest/Basic-Usage/), things work well with my own GTFS and OSM.

Now, I also want to do tests on the routing algorithm, I'm trying to find the "application-context.xml" file that you mentioned, but there is a problem:

1) I can't not find any "application-context.xml"if I downloaded OTP project from the following link: https://github.com/opentripplanner/OpenTripPlanner (--> From this link I get the folder named "OpenTripPlannerMaster", and from it, I can create my own stand-alone JAR file that is the one that ends with "-shaded.jar")

2) I found a lot of files "application-context.xml" if I downloaded OTP from this link: https://github.com/dssg/cta-otp (but I can't create stand-alon JAR file from this one).

Can you please help me ? Where I can download the "application-context.xml" file.

And the most important issue: once I get this file, (I may change it as you suggested later on), then where I should put it, so that I can run OTP as what I did with the basic usage instruction?

Thank you very much and I am looking forward to hearing from you soon.

Flix

[abyrd]

Hi @phuongnk11,

The application-context.xml file has not been used for a very long time in OTP. The CSA-OTP repository is a very old copy of OTP.

Please do not use the issue tracking system when seeking personal assistance with setting up or using OTP. opentripplanner-dev and opentripplanner-users Google groups for this purpose. Rather than attempting to reproduce things that have been mentioned in old mailing list posts or issues, let everyone know your end goal, what you are really trying to accomplish. It will then be easier for them to help you find a solution.

Andrew

[rsktash]

Hi @abyrd I understood the problem when banned the whole route in order to ignore duplicate itineraries. But there must be solution to get all possible routes at first query with some changes. Say we could identify itineraries with unique path to ban it for the next request. Thank you

[abyrd]

Hi @rustamsmax. This is an old closed issue. If you have questions or comments about OTP please contact one of the mailing lists. If you have identified a problem with OTP and want to propose a solution, please open a new issue, in which you state the problem and expected or desired behavior.