Skip to content
buma edited this page Oct 22, 2014 · 2 revisions

Information about current linker problems and wanted features in new linker

@abryd: I would like to see a rewrite of the linking code from scratch, taking into account all the outstanding and past linking issues we've addressed. The new linker/splitter should be used both for connecting transit stops during graph building and for connecting temporary endpoint vertices. It should also be usable for Analyst population linking (i.e. create samples rather than temporary edges).

In fact, it is worth considering whether OTP should always use a method like analyst samples rather than wedging temporary edges into the graph with all the concurrency issues that creates. The main repercussion I can see is that the check for whether we have reached the destination (on a critical path, in every iteration of the inner search loop) would become a check for set membership rather than identity equality. That is probably insignificant in practice, and certainly no worse than all the "Extra Edges" checks we did in the past.

This new linker implementation should account for and resolve issues. Linking rules should be configurable. We are using heuristics to guess where to link a stop, and the effectiveness of these rules varies from one country to another.

@buma, yes just removing the car preference is tempting. However, consider the cases which I believe led to the addition of this preference in the first place: imagine a street that is tagged as having a sidewalk. Nearby is a foot path behind a fence. The bus stop is halfway between the two. The bus is very likely to be driving on the road, and the stop is associated with that road, not with the nearby path. The general idea is that in the absence of other information, we might guess that a bus is more likely to be found on a car road than anywhere else.

Of course there are all sorts of questionable assumptions in the stop linking code (as detailed in this ticket) and I think a series of small tweaks will not be satisfying -- it really needs a rewrite.

Short version

Countries differences

UK:

If there is a pier or footpath much closer to a stop than a road, especially the case for trams, ferries and gondola, then the pier or footpath should be routed along rather than trying to snap to the nearest road.

Many parts of the British tram network does operate away from roads once you get outwith the town centre, where you only have a footpath between the tramstop and the nearby housing etc. Many of the tram stops are marked with the rail platform, including the connectivity to the street, e.g. if there are steps, thus allowing you to ensure that you get the correct routing avoiding steps.

USA

  • Aerial tram connected to road instead of platform problem
  • Stops not linking to OSM ways that are highway unclassified This appears to be caused by linking the temporary from-vertex directly to the street intersection rather than splitting the street. Disabling that logic in getClosestVertex resolves the problem.

This is caused by some sort of collusion between the path parser, the edge splitting process, and the two alternate endpoint linking methods, and I'm concerned that pushing the pieces into alignment in one place is just pushing them out of alignment someplace else.

The problem is simple: street edges (usually) come in pairs, one for each direction. When those are split for linking to a transit stop during graph building, you get two splitter vertices (which are actually of type IntersectionVertex), one on the edge for each direction.

When creating a temporary endpoint, before splitting the street temporarily we first check if there are intersections or transit stops nearby that we can connect to directly. If there is one or more IntersectionVertex nearby, we link to the closest one. The problem arises when that closest vertex is a splitter vertex along a road rather than the intersection of two roads: we are linking to one side of the road and not the other.

One solution would be to link to every intersection vertex within a certain radius rather than a single vertex, and keep that radius small.

Netherlands

  • Problem with linking on platform 160349080 Netherlands The reason it's not snapping to the stairs, footway, or cyclepath is more complicated. We recently made a change to try to avoid snapping to paths inside rooftop parks or other areas that are mostly disconnected from the rest of the system. The change was to only snap bus stops to platforms and streets which allow cars. This was at @kpwebb's suggestion.

If you add public_transport=platform to the footway, the bus stop will snap to there.

For the arrival, I agree that we should not snap bus stops to railway=platform. But if I change that, we'll still have Stationsplein (82770403) nearby, and we will snap to that instead. Instead, I think you should make 33814910 and the rest of the bus terminal public_transport=platform and remove access=no.

Problem is platform isn't tagged as highway=something

In the Netherland's there is a very conventional pattern where there are two cycleways along a non-cycleable road, where the busstops are put between the road and the cycleways. You're only allowed to leave the busstop via the cyclepaths. In some cases there is a semi-legal cross necessary to reach the busstop if there is only a cycleway on one side.

Also there is a pattern of non-foot/non-cycle reserved busroutes (such as Zuidtangent) where the only thing reaching the busstops is a cyclepath or footpath.

Slovenia

Bus stops should be linked to:

  • public station platform
  • walking paths next to them
  • or serviceways which are only for psv (Used in stations where buses turn)
  • streets

Train stops should be linked to:

  • railway platform

There is no other Public transit system

Other changes

  • Add GTFS pathways support Currently when starting a journey above a tunnel, the linker sometimes snap the starting position to it.

If only it were so easy. Stations are often in tunnels, and GTFS data doesn't tell us which OSM level the station is at. If we create a preference for snapping to surface streets, in places like http://www.openstreetmap.org/node/40532724#map=19/45.51062/-122.71650 the GTFS stop would be connected to the surface walking paths instead of the underground platforms. One solution here is to make the OSM data more clear by adding a way for the transit platform and connecting it to the proper street/sidewalk. OTP has a strong preference for connecting transit stops to ways tagged as transit platforms.

Problems with linking stops

Stops should snap to piers and footpaths when no road nearby #921

@smsm1:

If there is a pier or footpath much closer to a stop than a road, especially the case for trams, ferries and cable cars, then the pier or footpath should be routed along rather than trying to snap to the nearest road.

by cable car I mean gondola, though cable car is the more common name for it in the UK. I'm thinking that I might change the en_gb translation to that.

Many parts of the British tram network does operate away from roads once you get outwith the town centre, where you only have a footpath between the tramstop and the nearby housing etc. Many of the tram stops are marked with the rail platform, including the connectivity to the street, e.g. if there are steps, thus allowing you to ensure that you get the correct routing avoiding steps.

consider pathway types (including loops) rather than entrances during linking #1006

@abyrd: pathways.txt proposal

"Pathways of type 1 connect stops and the entrances that give them access from/to the streets. A stop referenced by a pathway of type 1 can no longer be accessed directly from the streets (i.e., without using an entrance), unless a circular pathway from the stop to itself is given to reinstate direct access. Pathways of type 2 describe pathways for transfers between stops that are separate from the streets (e.g., a tunnel between two subway platforms). Pathways of type 3 provide information about transfers on the streets, for use by transit trip planners instead of, or in addition to, walking directions from other sources."

We currently just check whether stops are connected to entrances. Instead we should check which pathway types reference them, and whether they have pathways to themselves.

OHSU Aerial tram connected to road rather than nearby platforms #1073

@abyrd: In OSM: ohsu_gondola_osm

In OTP graph (no island removal, station building is an island with =platform tag): ohsu_gondola_station

I checked this one in OSM, the footpath's are not tagged with railway=platform thus not considered as possibility's for stop linking (footway's are banned there afaik). The platform is not connected with a single footway/highway thus as unconnected island.

The way's ending in area's is a common thing you see in OSM, to be considered is if the endpoints of way INSIDE an area should be considered as connection between area and way.

I have also done some experimenting. It links to the street (at ground level) even when I properly tag the elevated platforms, so I think it needs further investigation. There is too high a preference for that nearby street.

Stops (not) linking to OSM ways that are highway unclassified #1394

@fpurcell:

The OSM ways in this area (near the Oregon Zoo) are tagged as unclassified (they were recently changed from ‘residential’ to ‘unclassified’). The OSM way ids are: 5518011 and 31791751 nearest stops 13253 and 10300.

Raptor snapping / walking issues #856

Problem with linking on platform 160349080 Netherlands

@skywave & @novalis

Still there is room for improvement.

http://www.opentripplanner.nl/index.html#/submit&fromPlace=52.515686,5.484340&toPlace=52.346500,4.864564&mode=TRANSIT,WALK&min=QUICK&maxWalkDistance=2000&walkSpeed=0.833&time=17:00&date=11-10-2012&arriveBy=false&itinID=1&wheelchair=false&preferredRoutes=&unpreferredRoutes=

Looking at the first itinerary, i don't see why its snapping so far out from the boarding point of Bus 7. There is a steps & stairs & cyclepath very close by. Also the snapping of the arrival of bus 7 is wrong. It snaps to the platform of the trainstation, which is on a different level & should snap to somewhere on the busstation.

On the boarding point, It can't snap to Zuigerplasdreef because that street doesn't allow pedestrians. It can't snap to the De Veste 11 for the same reason.

Looking at Google streetview, I can't actually see a southbound bus stop there, so I don't know the stop is actually accessed.

The reason it's not snapping to the stairs, footway, or cyclepath is more complicated. We recently made a change to try to avoid snapping to paths inside rooftop parks or other areas that are mostly disconnected from the rest of the system. The change was to only snap bus stops to platforms and streets which allow cars. This was at @kpwebb's suggestion.

If you add public_transport=platform to the footway, the bus stop will snap to there.

For the arrival, I agree that we should not snap bus stops to railway=platform. But if I change that, we'll still have Stationsplein (82770403) nearby, and we will snap to that instead. Instead, I think you should make 33814910 and the rest of the bus terminal public_transport=platform and remove access=no.

Problem is platform isn't tagged as highway=something

Walking to Farther Bus Stops #1302

In the new stable version OTP is providing a route that has the user walk to a bus stop that is farther away than necessary. It seems to occur when snapping to a bus stop catty corner from the ideal departure location. This bug does not happen in the old stable version.

Example 1:

When starting trip from StopID 6809, OTP has you walk two blocks north to StopID 6785 instead of going catty corner across the intersection to StopID 6808. If you start from StopID 6808 you get the expected results. It doesn’t seem like it is related to walkReluctance and waitReluctance. Line 8 picks up at StopID 6808 at 10:35 am. When planning a trip from the catty corner stop at 10:30 am you have enough time to walk north two blocks and can catch that bus. However if you plan the trip at 10:33 am you don’t have enough time to make the walk and miss the first bus.

farther_bus1

farther_bus2

@abyrd: I am able to reproduce this problem, and it does not appear to be transit related. If you place the destination marker 1 block south of the origin marker on the opposite side of NE 15th you still get a detour via 15th and Kickitat, choosing either transit or walk mode.

This appears to be caused by linking the temporary from-vertex directly to the street intersection rather than splitting the street. Disabling that logic in getClosestVertex resolves the problem.

This is caused by some sort of collusion between the path parser, the edge splitting process, and the two alternate endpoint linking methods, and I'm concerned that pushing the pieces into alignment in one place is just pushing them out of alignment someplace else.

The problem is simple: street edges (usually) come in pairs, one for each direction. When those are split for linking to a transit stop during graph building, you get two splitter vertices (which are actually of type IntersectionVertex), one on the edge for each direction.

When creating a temporary endpoint, before splitting the street temporarily we first check if there are intersections or transit stops nearby that we can connect to directly. If there is one or more IntersectionVertex nearby, we link to the closest one. The problem arises when that closest vertex is a splitter vertex along a road rather than the intersection of two roads: we are linking to one side of the road and not the other.

Conditionally linking to vertices rather than always splitting an edge avoids microscopic and 0-length temporary edges. Those would not necessarily be a problem by themselves. However, when an endpoint has exactly the same coordinates as a vertex, none of the vertex's associated edges is more appropriate for splitting than the others.

Given the zero-length problems we've run into in the past with JTS, I'm hesitant to remove the direct linking to vertices and always split one edge (with arbitrary tie-breaking). If we retain direct linking to vertices we must find a way to catch both splitter vertices at the same location, but OTP has nothing in place to identify which edges or vertices are part of the same road.

One solution would be to link to every intersection vertex within a certain radius rather than a single vertex, and keep that radius small.

Another problem: farther_bus4

The main road in the area (SW Pacific Highway) is not even considered a candidate edge because it has no sidewalks, and is not pedestrian accessible according to TraversalRequirements.canBeTraversed. The fact that it is one-way (actually a dual carriageway) does not seem to be significant, though this is implied to be a cause by comments in the code. Stop 12743 has its own paved platform connected to the footpaths in the wildlife refuge, but that platform is not mapped or tagged as such in OSM

So stop 12743 is surrounded by pedestrian walkways, but OTP links it to the tiny service road on the other side of a two-lane divided highway because that road happens to be car-accessible and pedestrian accessible. This happens even when the edge scoring system is disabled because of the canBeTraversed() filtering mentioned above.

There are sidewalks nearby but they are being thrown out, because linker.index.getClosestEdges is called with possibleTransitLinksOnly=true, so StreetVertexIndexService L393 skips any bundle that does not allow cars and is not a platform.

In the Beef Bend case, the stop where we'd expect to alight (4267) is linked to Crown Drive off of 116th Ave. This makes it harder to access than the neighboring stop at Bull Mountain (4271). Again, OTP is preferring to link the stop to anything accessible to both cars and pedestrians, or to anything tagged as a transit platform.

As counterintuitive as it seems, no matter how close the pedestrian path is to stop 4267 OTP will still link to the car-accessible street because of the large constant bonus score given to car roads.

Again, as above the short-term solution is to micro-map a transit platform, but this linking code is so problematic that it should be re-written. I'm not comfortable just tweaking the scoring constants because we'll probably trigger a problem elsewhere for each problem we fix.

Problems with start/stop linking

improve endpoint snapping #1077

Ways that are car-traversable and/or have platform tags get a heavy preference when choosing trip endpoints and linking stops.

Consider the underground platform at the zoo: we want the pointlike GTFS stops to connect to that platform and not to the surface paths. The platform tag helps us know that this is the right thing to do.

But the strong preference for car roads might cause problems in a lot of places. If I try to start searches in pedestrian areas, it jumps to nearby parking aisles etc. There are a lot of tram/train/bus stops in pedestrian-only areas. We should probably refine the snapping preferences system to account for this.

Also look into how station linking is different than endpoint snapping.

I think this same issue affects us and trip planning we were recently trying to do within our Tampa Lowry Park Zoo, which some students recently mapped in OSM: http://opentripplanner.usf.edu/index.html#/submit&fromPlace=28.013302,-82.470063&toPlace=28.014612,-82.470553&mode=WALK&min=QUICK&maxWalkDistance=840&walkSpeed=1.341&time=10:15am&date=5/13/2013&arriveBy=false&itinID=1&wheelchair=false&preferredRoutes=&unpreferredRoutes=

Doesn't seem that you can plan a route internally to the park on pedestrian ways, instead it snaps the start and end point outside the zoo to the local roads.

In the Netherland's there is a very conventional pattern where there are two cycleways along a non-cycleable road, where the busstops are put between the road and the cycleways. You're only allowed to leave the busstop via the cyclepaths. In some cases there is a semi-legal cross necessary to reach the busstop if there is only a cycleway on one side.

Also there is a pattern of non-foot/non-cycle reserved busroutes (such as Zuidtangent) where the only thing reaching the busstops is a cyclepath or footpath.

Found a worse example, note i have even tried to disable the "onlyreturnTransitLinks" thus also returning cycle paths etc. Look at this route, it insists on linking to that residential road "Zuigerplasdreef" which is a foot island. In reality it's pretty much linked to the cycle path, which is the only allowed path by foot. Because it's linked to an island it is not possible to go to nearby locations, such as the builidings above there on the "Houtribweg".

Note; the added busplatform's right now in OSM, were added after the OSMdunp which is used in the current graph on this server.

http://opentripplanner.nl/index.html#/submit&fromPlace=52.089969,5.120513&toPlace=52.548906,5.489757&mode=TRANSIT,WALK&min=QUICK&maxWalkDistance=2000&walkSpeed=0.833&time=14:52&date=25-05-2013&arriveBy=false&itinID=1&wheelchair=false&preferredRoutes=&unpreferredRoutes=&bannedRoutes=&hst=

worst linking

Also check for highway=pedestrian, as there are some train stations which have pedestrian or footways outside but don’t get linked due to being too far from the road network. I haven’t looked into the details, however this seems a plausible explanation.

How to adapt search for start/end vertex of route

I recognized another interesting behavior when setting the start/end point. In case of setting it not close enough to the beginning or end of a way tagged "footway" or "pedestrian", the start/end point is shifted to a different position when calculating the route (see attached screenshot). But when setting the start/end point e.g. on a way tagged "residential", "tertiary", or "primary", it is not shifted anywhere. Why is there a difference?

avoid starting search in unsafe place #560

During a check-in call we discussed the problem of searches starting/ending in areas from which one cannot safely access transit on foot/bike.

There are two cases here:

1.) The user actually really wants to start in a place from which you cannot safely access transit. This causes the search to fail, and an appropriate error message is given. 2.) The closest road to where the user clicked in his/her client app does not allow safely reaching transit, but this road was really arbitrarily chosen because the client map is zoomed out to where individual roads are not easily distinguishable.

The solution may be to start the search in several places at once, eg all roads within a certain specific radius of where the user clicked. However, if all these start points are enqueued with 0 initial weight, paths originating at the start point farthest from where the user clicked are likely to dominate. These alternate starting points should therefore be enqueued with a weight greater than a reasonable estimate of walking cost from the principal search start point.

This method would require the client to provide the server with both a start point and a 'radius of ambiguity'. The client can then account for input methods and the display resolution of the device it is running on.

End of ways inside area's #1067

See this situation inside OSM -> http://www.openstreetmap.org/?lat=52.387318&lon=4.638266&zoom=18&layers=M

There are a bunch of unconnected way's ending in the middle of the square/plaza including the busstation. This is done by a lot of OSM'ers who presume this is OK, but ofcourse is a huge pain in the ass when trying to route.

It could be possible to connect the end points with the square geometries but would it result in unintended behaviour? At this point it often results in detours because it can't walk to the busstation from the trainstation directly.

Car routing doesn't find path if start point is closest to bike path intersection. #1437

I accidentally found a bug with car routing: corner

Map link.

If start is nearest to an intersection where CAR has no permission to drive this intersection will be used as starting point because you can walk on it (and bikeWalkingRequirements is used to test permissions) and path finding will fail, because car permission on path is false. Probably connected with #1130.

The source of a problem is in TraversalConstrucor when initializing bike/walking requirements.

Everything starts in GetClosestVertex where pedestrian/bycicle corner is found. Which is intended but reqs.canBeTraversed returns True so this corner is used. Which it shouldn't because CAR permission is false.

Path can be traversed because reqs has CAR mode which in canBeTraversed returns false as it should but hasBikeWalkingRequirements is true and path can be walked/biked so canBeTraversed returns true and this corner is used.

End point which is also in the middle of no car area is found correctly.

Linker should not snap to streets in tunnels #1434

Currently when starting a journey above a tunnel, the linker sometimes snap the starting position to it.

If only it were so easy. Stations are often in tunnels, and GTFS data doesn't tell us which OSM level the station is at. If we create a preference for snapping to surface streets, in places like http://www.openstreetmap.org/node/40532724#map=19/45.51062/-122.71650 the GTFS stop would be connected to the surface walking paths instead of the underground platforms. One solution here is to make the OSM data more clear by adding a way for the transit platform and connecting it to the proper street/sidewalk. OTP has a strong preference for connecting transit stops to ways tagged as transit platforms.

At least we should decrease the tendency to snap to tunnels with (only) car access. In some places it is impossible to set starting/ending point within a pedestrian plaza, since OTP always snaps to parking access tunnels/garages underneath it, creating long detours to connect to the walkable network. In the above case, probably the best thing to do is to tag it correctly in OSM in order to get the preference as a platform.

OTP Refuses to use walking path

Regardless of where I click on that path, I cannot get OTP to route along it. e.g. even if clicking two points on the path to walk between, it still tries to snap to another road, or fails altogether. In other words, OTP refuses to use this path for point-to-point walks under all circumstances - it’s as if the path didn’t exist.

Bike Rental Issue

Hello,

I've been working on implementing bike rentals for USF in Tampa and have had initial success loading stations and routing using them, but have recently encountered a strange issue that hopefully someone can offer feedback with. I think I saw some other messages that might be related awhile back in one of the groups, too..

Our setup will eventually (as far as I understand) include many available bike racks throughout our main tampa campus (which includes many different walking paths and some streets) - see http://www.openstreetmap.org/way/31675479 and so I think many students will want to be able to see accurate walking directions to a given destination on campus including picking up and dropping off a bike along the way.

I tried one such scenario this week and although it mostly worked, the pickup and dropoff locations were off in the following ways:

Using a "walk|bicycle_rent" route from the Interdisciplinary Science building (ISA) to alumni dr/beard dr, it picks up a bike in front/south of ADM (note: walk ... to #46) yet, the #46 node is displayed correctly on leaflet NORTH of ADM problem image

Last two problems are "fixed" with my Linking patch which adds mode to calculating score functions, and preferes bikable streets when Bicycle mode is used, and walkable streets if transit/walking is used, otherwise is the same as current

The documentation on this wiki is outdated and should not be used

unless you are intentionally working with legacy versions of OpenTripPlanner. Please consult the current documentation at readthedocs

Clone this wiki locally