Number of transfers / duration of an itinerary in OTP.

[Koen Nijbroek]

Hi,

Are there strict boundaries on the number of transfers / duration of an itinerary in OTP? If yes, could anyone point me out in the right direction of where to edit the source code to 'loosen it up'. I am running into limitations and this is the ónly issue that I still need to overcome.

[Koen Nijbroek]

Anyone? :(. 

[Robert Sharp]

Hi Koen,

I've only used OTP for a few days, but I think the answer is "yes".

For example, in "PlannerResource" (/routers/{routerId}/plan), I see multiple options for transfer penalties, and a "maxTransfers" option. Presumably there is some default value there; are you setting a maxTransfers value with your requests?

Moreover, in the description of the "maxTransfers" option, it says the following: "This is limited on the server side by the MAX_TRANSFERS value in org.opentripplanner.api.ws.Planner." That seems like a pretty clear indication that there is a strict limit that you might have to go in and change when you configure your server.

But, it's hard to know without more information. Which REST resources are you using?

-Rob

[Gard Mellemstrand]

I think these hardcoded values overwrite the values set in the config file.

https://github.com/opentripplanner/OpenTripPlanner/blob/master/src/main/java/org/opentripplanner/routing/impl/GraphPathFinder.java#L133

https://github.com/opentripplanner/OpenTripPlanner/blob/master/src/main/java/org/opentripplanner/routing/impl/GraphPathFinder.java#L333

[Seth Budick]

I've also tried setting the value of maxTransfers=2 both in the api call, and in the router-config.json file, but OTP seems to ignore that in generating itineraries.

I'm not a programmer, so from the below, it looks like I need to change that value in the OTP source code.  

Would someone be so kind as to point me towards how to make that change and compile a modified version?

[Andrew Byrd]

Hello,

The API parameter has no effect. It is a vestige that has been left in place in case someone is experimenting with older methods that are still hanging around in the code base, which might read this parameter.

However, it would be questionable to do so. The reason the parameter is disabled is that it is algorithmically invalid to apply a cutoff value to a variable that is not one of the optimization objectives. This is referred to as a "resource limiting problem” in the operations research literature. OTP contains (or at least did in the past) code that allows finding Pareto-optimal paths, which enables capping transfers, but it turned out to be excessively slow on larger networks.

At first it seems intuitive to just discard paths at the point where they exceed a certain number of transfers, and this approach has cropped up from time to time in open source transit routing software. But limiting resources in searches that are not specifically designed to support such limiting will occasionally yield cryptic, inexplicable results that are difficult to debug. It just doesn’t work as expected, and the reasons are well documented.

Instead, to provide reasonable performance we optimize a single generalized cost variable, which is a composite of many different factors (one of which is the number of transfers). The appropriate way to get less transfers in this setting is to increase the cost of each transfer, not cap the number of transfers. This applies across the board in the current incarnation of OTP: you can’t actually cap the number of anything, but you can adjust the per unit cost of many things.

Other alternative algorithms like RAPTOR naturally find the set of Pareto-optimal paths on two variables, travel time and number of transfers. That’s one reason we’ve put a lot of effort into implementing RAPTOR, and are debating integrating our RAPTOR implementation into OTP.

Regards,

Andrew

--
You received this message because you are subscribed to the Google Groups "OpenTripPlanner Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to opentripplanner-...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Andrew Byrd]

> On Mar 22, 2018, at 23:28, Gard Mellemstrand <gar...@gmail.com> wrote:
>
> I think these hardcoded values overwrite the values set in the config file.
>
> https://github.com/opentripplanner/OpenTripPlanner/blob/master/src/main/java/org/opentripplanner/routing/impl/GraphPathFinder.java#L133
>
> https://github.com/opentripplanner/OpenTripPlanner/blob/master/src/main/java/org/opentripplanner/routing/impl/GraphPathFinder.java#L333

At these cited lines the maximum number of transfers set to 4, but I was under the impression it was again overwritten with Integer.MAX_VALUE within the routing algorithm to entirely disable the limit, at the point where it is determined that we are optimizing only generalized cost.

However I can’t find the line where that happens. If we are running a generalized cost optimization with a hard limit on the number of transfers, that could certainly explain some of the odd incorrect routes that have been reported in issues.

-Andrew

[Andrew Byrd]

Upon further inspection and tracing the execution of OTP, I see that maxTransfers is indeed set to 4 while the search is happening, and the lines where this value is checked against the number of transfers in potential solutions are in fact executed. Based on a few long distance searches, in practice paths with over 4 transfers are not encountered during a search in Portland. However in larger national graphs such larger values will be encountered, and pruning them will lead to bizarre and invalid results.

We need to entirely remove the restriction on the number of transfers (set it to MAX_VALUE) and instead influence the number of transfers using the per-transfer cost parameter. The documentation also needs to be updated to reflect this. See comment added to: https://github.com/opentripplanner/OpenTripPlanner/issues/2522

-Andrew

[Andrew Byrd]

Hi Koen,

On Mar 29, 2018, at 00:53, Koen Nijbroek <koenni...@gmail.com> wrote:

Thanks Andrew for the clear explanation. Could you help me out where in the code I would be able to reduce the costs for transfers? And is distance also one of the factors related to the general cost variable?

It’s not exactly the cost of transfers that is controlled, but the cost of boarding a vehicle. The cost is applied to the first boarding as well as transfers. This is controlled via the HTTP API parameters walkBoardCost and bikeBoardCost, which correspond to the Java fields of the same name in the RoutingRequest class. You shouldn’t need to modify any source code to change these parameters.

When you say "is distance also one of the factors” I am not sure what you mean by “distance”. When the road network is being traversed by walking or biking, the length of a road segment contributes heavily to the generalized cost of traversing it. 

-Andrew

[Andrew Byrd]

Hi Seth,

> On Mar 29, 2018, at 02:47, Seth Budick <sbu...@gmail.com> wrote:
> I've found walkBoardCost to be a very valuable parameter in limiting the number of transfers to a "reasonable" number. Can you provide any details on that parameter such as the units (seconds?) or experience that you or others have had with choosing a reasonable "real life" value? From my experiments, it looks like the default is set somewhere around 600.

This is indeed the right parameter for influencing the number of transfers in the results. What you’re controlling is how bad a transfer is from the rider’s perspective, seen as a tradeoff against additional in-vehicle time. That is, how much travel time you need to save before a rider will consider an additional transfer.

One major term of generalized cost that does not have a weighting factor in OTP is in-vehicle travel time. This means that the units for any cost term are essentially seconds of in-vehicle time. The walkBoardCost is how many seconds of ride time you need to save in order to prefer boarding an additional vehicle.

Note that constant cost terms (“costs”) should always be >= 0 and multiplicative cost factors (“weights”) should always be >= 1 for the algorithm to work properly. This is because we use a heuristic for the remaining cost to reach the destination that is based on seconds of in-vehicle time and walk time. This heuristic is assumed to be a hard lower bound on remaining cost, so when conducting the search we can’t scale costs smaller, only larger.

Regards,
Andrew

[Seth Budick]

Thanks again Andrew.  

Could you just clarify then the difference between walkBoardCoast and transferPenalty?  My understanding of transferPenalty (based on the reference here http://dev.opentripplanner.org/apidoc/0.20.0/resource_PlannerResource.html), is that that parameter captures something very similar to how you described walkBoardCost.  What would be best practice for allocating transfer costs between those two parameters?

[Andrew Byrd]

I should have also mentioned transferPenalty. The units are the same, and the difference is simple: walkBoardCost applies every time you board a vehicle including the first, while transferPenalty applies only on the second and later boardings (it applies only to transfers rather than every boarding).

The reason I didn’t mention TransferPenalty is that unlike walkBoardCost it defaults to zero, and is mainly used to implement a legacy feature (OptimizeType.TRANSFERS). It appears to me that the transfer penalty may also be algorithmically invalid for the same reason as transfer limiting - it effectively changes the cost of boarding based on details of previous steps in the path (whether or not the passenger has boarded earlier in the path). To make it technically correct we’d need to move the penalty to the transfer edges rather than the board edges. 

So for that reason I’d advise you to use solely the boardCost parameters and not the transferPenalty until someone can verify that the transferPenalty implementation is truly reliable.

By the way, based on the URLs you referenced, you are looking at a rather old pre-1.0 version of the OTP API docs from Jun 10, 2016. The root URL for the API docs is http://dev.opentripplanner.org/apidoc/ where you’ll see a 1.0.0 directory for more recent docs.

-Andrew