Utility vs Distance threshold for cutoff point when creating bike route choice paths and logsums.

[dhensle]

Background
The bike route choice model relies on SciPy's Dijkstra's algorithm to build paths between OD pairs. This implementation is very fast but has the downside that only a single generalized cost variable can be applied to the links that the paths are built on. The SciPy implementation allows the user to select a limit such that the algorithm will stop if the total generalized cost summed across the links in the path hits that limit. This drastically improves runtimes by limiting the number of OD pairs it builds paths between.

The existing Java implementation has a bespoke Dijkstra's algorithm that uses the generalized costs when building the paths, but keeps track of the distance separately to apply the limit. The limit is currently set to 20 miles for TAZs and 3 miles for MAZs.

It is not feasible to move away from SciPy's Dijkstra implementation for the python development of the bike route choice model and we are therefore stuck with having to supply a generalized cost as the limit. The question comes into how we present that limit to the user -- either as a distance that gets converted to a cost, or as a cost itself.

Case for Distance Limit
Allowing the user to set the cutoff limit in miles is ideal considering it is easy to comprehend and understand. However, in practice, this has proved challenging. In development we have tried to convert the average utility per mile into a distance by the applying variations of the following:
avg_utility_per_mile = ((edge_utility + avg_traversal_utility) / edge_distance)
where the edge_distance is in miles. (The average traversal utility is included under the assumption that each edge has an associated traversal that must be crossed.)

This implementation, while theoretically appropriate, produces paths that are much longer than our expected distance threshold. We suspect a few reasons why this is the case:

• the average traversal utility is over-estimated because turning movements are more onerous and there are more of them whereas the actual paths are more likely to go straight.
• Edge utilities include links that are cost-prohibitive like major arterials that bikers are likely to avoid

These essentially boil down to the assumption that the cost-per-mile across the entire network is not representative of the cost-per-mile along paths that are actually chosen.

Case for Utility Limit
Setting the cost directly in the user settings avoids having to calculate an average utility per mile and the setting gets passed directly to Dijkstra. It also allows for a consistent cutoff in the bike logsum that gets output by the model -- it doesn't necessarily matter how long the bike trip is but instead how onerous the trip is as measured by the logsum.

Downsides to this approach are:

• If utilities / coefficients are modified in the model, a new cost threshold would need to be developed
• Users have a harder time understanding what the cutoff means
• We need to run a couple tests to see find what the initial cutoff should be

Upsides:

• More consistent logsum outputs -- as more bike facilities are built we would allow people to travel even further on more comfortable paths.
• Avoids arbitrary heuristics added to the avg_utility_per_mile calculation to make it work.

My Personal Take
Having a distance threshold would have been ideal, but I don't think its worth figuring it out when we can just use a utility threshold as long as the SANDAG team understands that there is not a hard distance cutoff when generating logsums.

I also don't think it really matters -- the number of bike trips happening out at this 20-ish mile is so small that changing the limit by +/- a mile or so at that limit will make no meaningful difference.

For reference, the below plot is the distribution of bike trips coming out of the ABM3 model with a tail that extends all the way out to 27 miles --the distance threshold in the current Java implementation of 20 miles does not currently translate directly to the outputs right now anyways.

[aber-sandag]

Thanks David, this is a great summary and I think covers most of what we discussed last week. I'm leaning towards using a utility cutoff for the reasons you gave - more reflective of the actual implementation using SciPy and more consistent output. Because the utility threshold is unintuitive for users as compared to a distance threshold, we would want to clearly document how we arrived at that threshold and what steps to take to update that threshold in the future.

I want to graph out the bike logsum values for all bike trips in some existing no-build and build scenarios so we can try to find a threshold where almost no trips are choosing bike mode. How close can we expect the final logsum to be to the original path utilities? Do we need to temporarily add a "logsum without path size" to the bike model output to get closer to the path utility?

[americalexander]

The biggest driver of the conversation to date has been the fact that we're seeing distances that significantly exceed the threshold we specify, both in the Python and Java implementations. David did a great job of summarizing the path ahead of us. Practically, there is no way to implement a true distance cutoff without re-implementing Dijkstra's algorithm, and we don't presently have resources to accomplish that. I support shifting to a cost-based threshold in spite of the user-unfriendliness because it should actually adhere to a firm cutoff. Nonetheless, it's important to keep in mind that, either way, the cutoff is merely a heuristic for improving runtime and, if set properly, should have next to no impact on the actual logsums used in the model.

I agree wholeheartedly with Alexander about wanting a clearly documented derivation of the chosen thresholds. I think it's worth designing a procedure to do so from scratch (either in addition to or in lieu of a procedure for updating existing thresholds). As David mentioned, the cutoff will likely need to change every time the coefficients are altered, and I can envision scenarios (e.g. the e-bike vs. regular bike discussion) in which the existing cutoff values may have little to no relevance. Whether developing from scratch or updating existing values is more efficient will likely vary heavily depending on the changes made, but having a means to do so from scratch should probably come first; we can then build updating procedures on top of that.

[bhargavasana]

Thank you all for your input. We do not update the coefficients very often. I recommend going ahead with a utility threshold.

Next steps

• Develop a procedure to derive the utility-based threshold and document it. Methodology for deriving a utility threshold for Dijkstra's algorithm (scipy) in bike model #332