search

opentripplanner / OpenTripPlanner

An open source multi-modal trip planner
http://www.opentripplanner.org
Other
2.18k stars 1.02k forks source link

ROUTING: weird biking dog-leg, which only appears on Transit & BIke trip #353

Closed novalis closed 13 years ago

novalis commented 13 years ago

Planning a trip with mode:TRANSIT,BIKE vs. mode:BIKE has a strange difference on the final BIKE leg...with a little dog-leg detour (see two attached images to compare).

http://maps5.trimet.org/opentripplanner-webapp/index.html?purl=/osm&fromPlace=45.29980542656,-122.77069645014&toPlace=45.379879699824,-122.2655217278&mode=TRANSIT,BICYCLE&time=5:40%20pm&submit

Here's a couple links to the Graph & graph config:

 http://maps5.trimet.org/otp-bugs/1-2011/graph-builder.xml
 http://maps5.trimet.org/otp-bugs/1-2011/Graph.obj
novalis commented 13 years ago

--andrewbyrd

novalis commented 13 years ago

I see this error is sensitive to the max walk distance search parameter. There is multiplier which grows rapidly once you exceed max walk, which is applied only when transit is among the modes. I would suspect overflow, but weight is a double...

I can reproduce this bug with older revisions around 1212, but checking more recent revisions I'm getting paths with incorrect walk distances. Am looking into the recent revision oddness before specifically addressing the dogleg.

--andrewbyrd

novalis commented 13 years ago

This error is due to interactions between the max walk distance parameter and contraction hierarchies. When transit is among the chosen modes, the weight of street segments is multiplied by increasingly larger factors after the specified walk distance is exceeded. With distanceWalkFactor modified to always return 1, tests give consistently reasonable routing results.

In general, path-dependent edge weights will make shortcut-based techniques and reasoning about routing correctness difficult (this is also an argument in favor of turn-edge type graphs). Maximum walk distance can be handled in routing logic with constant edge weights (per mode). This can be implemented in conjunction with #306 and #359.

This also suggests that all components of weight (e.g. turn costs) should probably be expressed in identical units (meters) unless the routing algorithm considers them separately when selecting a vertex's set of non-dominated states.

This should not cause problems with walk reluctance or speed since they scale all weights by a single factor independent of path. However, as long as such scaling parameters exist, a single shortcut cannot include both a walking and a transit leg.

--andrewbyrd

novalis commented 13 years ago

distanceWalkFactor removed in rev 1218. max walk switched (temporarily) to a hard limit, pending a more elegant fix to be combined with #306 and #359.

--andrewbyrd

novalis commented 13 years ago

{{{

!html

}}} This ticket has been referenced in ticket #371:

''distanceWalkFactor removed in rev 1218 to avoid routing aberrations in #353. Max walk distances are now implemented as a hard limit in AStar. They should b...''

--andrewbyrd