Questions on graph building, routing algorithms and more

[Victor G]

Hello,

I am new to OTP and I have several questions on how it works at many levels.

My current knowledge is based on the wiki (which I know is outdated) and the fairly recent posts on this group (since 2017). It is highly possible that some of my assumptions are wrong, or no more correct for the current version of OTP, please let me know if that’s the case.

I have quite a few questions so I will try to structure them clearly.

1) Graph building

1.1 Is this page (https://github.com/opentripplanner/OpenTripPlanner/wiki/GraphStructure) still up to date? (If not the following question may not be relevant.)

1.2 From the above page, “the weight of TransitBoardAlight, PatternDwell, and PatternHop edges depends on the time at which they are traversed”. I understand how it is true for the board edges, but I fail to see how it is true for the others.

1.3 I have a hard time figuring out how the time dependance of the graph is actually represented. At first I thought that all the departure times for a given trip where linked to the corresponding board edge for that trip (resulting in a static time-dependant graph). From (https://groups.google.com/forum/#!topic/opentripplanner-users/OFhov2RQKao) I understood that only departure times in a given time window are considered when running a search. So this would aim towards a "dynamic" time-dependant graph. Is that correct?

1.4 How is bike sharing implemented ? My intuitive solution would have been to preprocess the N*(N-1) shortest path between all bike stations pairs, and add these new edges to the graph. However, it wouldn’t support user preferences considered in the “Bike triangle”. So without creating new edges departing from and arriving at bike stations, how does OTP routing ensure that a shared bike is left at a stop before arriving at destination ?

1.5 When connecting the transit graph with the OSM graph, does the linker consider the whole OSM graph or only the edges where walking is authorised ?

2) Routing

2.1 I’ve seen here (https://groups.google.com/forum/#!topic/opentripplanner-users/L8XnN6iyZBE ) and here (https://groups.google.com/forum/#!topic/opentripplanner-users/FK3MKI0PU9Y) that OTP routing doesn’t support hard limits on variables (such as max transits) because it’s based solely on the optimisation of the “generalised cost” variable. Yet I see that it is possible to choose a max walk distance in the trip options. How can this be performed ?

2.2 From (https://opentripplanner.readthedocs.io/en/latest/Bibliography/), I see that routing (for mode combinations using transit) uses the Tung-Chew heuristic. I have two questions about this. First, this is referenced in the bibliography as a technique for multi-objective Pareto optimality. Does it still bring benefit in the current one-variable optimisation ? Second, I’m not sure to understand the part “(i.e. a graph grown backward from the destination providing a lower bound on aggregate weight) for queue ordering”.  If the graph is grown from the destination, how can we calculate dynamically the weight of the PatternBoard edges, which to my understanding were calculated from knowing the time at which they are traversed and finding the next departure time.

2.3 Is that correct that contraction hierarchies is no longer used?

2.4 From (https://groups.google.com/forum/#!topic/opentripplanner-users/anzHLDnlJx4), there was 2 strategies to compute multiple itineraries, and “trip banning” was the one used at this time. Is it still the case ? 

2.5 Some modes of transport brings constraints : e.g. using a bike can only be allowed at the beginning of the trip, be as soon as there is a switch to another mean of transport, you can’t go back to the bike. The same goes for the car. How is the routing performed in order to respect these constraints ?

3) Miscellaneous

3.1 I didn’t come across information about support for car sharing. Are there plans to support it ?

3.2 What does the “Weight” cursor represent in the web client (between “preferred routes” and “banned routes”) ?

3.3 What is the difference between “bicycle and transit” and “bike and ride” options ?

Thank you in advance for any response,

Kind regards,

Victor G

[Victor G]

I have come up with hypothesis for some of my questions, but I would like to know if they are correct.

1.4 How is bike sharing implemented ? My intuitive solution would have been to preprocess the N*(N-1) shortest path between all bike stations pairs, and add these new edges to the graph. However, it wouldn’t support user preferences considered in the “Bike triangle”. So without creating new edges departing from and arriving at bike stations, how does OTP routing ensure that a shared bike is left at a stop before arriving at destination ?

The layer representing the bike network would only be connected to the walk network at the bike stations, this would allow to run a classical Dijkstra/A* to find the best path.

 

2.1 I’ve seen here (https://groups.google.com/forum/#!topic/opentripplanner-users/L8XnN6iyZBE ) and here (https://groups.google.com/forum/#!topic/opentripplanner-users/FK3MKI0PU9Y) that OTP routing doesn’t support hard limits on variables (such as max transits) because it’s based solely on the optimisation of the “generalised cost” variable. Yet I see that it is possible to choose a max walk distance in the trip options. How can this be performed ?

Maybe it is not taken into account during the search, but it is only applied as a filter on the results.

 

2.5 Some modes of transport brings constraints : e.g. using a bike can only be allowed at the beginning of the trip, be as soon as there is a switch to another mean of transport, you can’t go back to the bike. The same goes for the car. How is the routing performed in order to respect these constraints ?

 

The bike network and car network would only be connected to the walk network with unidirectional "alight edges" :

- for BikeAndRide/ParkAndRide : alight edges only at bike/car parkings

- for KissAndRide : alight edges everywhere

When the search starts, the departure node would depend on the mode (you would start from a node in the car network if you chose KissAndRide), and then the search would run as a classical Dijkstra/A*. 

I would appreciate any answer or correction to my hypothesis.

Regards,

Victor G

[andrew byrd]

Hello,

I'm answering a lot of these off the top of my head so some small inaccuracies may be present in the responses below - please confirm any details by examining the source code before making any critical design decisions based on these statements.

On 26 Nov 2018, at 1:09 PM, Victor G <victor1...@gmail.com> wrote:

1) Graph building

1.1 Is this page (https://github.com/opentripplanner/OpenTripPlanner/wiki/GraphStructure) still up to date? (If not the following question may not be relevant.)

The image is still more or less correct. There are still separate vertices for transit stops, offboard arrival, offboard departure, onboard (pattern) arrival, and onboard (pattern) departure. This is the TransitVertex class hierarchy.

There are still distinct types of edges connecting these vertices: PreBoardEdge, PreAlightEdge, TransitBoardAlight, PatternHop and PatternDwell edges. The last three are subclasses of TablePatternEdge - they all reference what we call a "trip pattern", a table of trips all stopping at the same transit stops in the same sequence (class TripPattern).

1.2 From the above page, “the weight of TransitBoardAlight, PatternDwell, and PatternHop edges depends on the time at which they are traversed”. I understand how it is true for the board edges, but I fail to see how it is true for the others.

The weight of boarding a pattern varies depending on when you arrive - if you arrive at the stop one minute before a vehicle arrives, the edge costs one minute. If you arrive ten minutes before the next vehicle, the edge costs 10 minutes.

The costs of the other edges are variable because those edges represent every trip in their pattern - all trips that visit those same stops in the same sequence. Different trips throughout the day may proceed at different speeds or wait (dwell) for different amounts of time at stops. 

This works because of an assumption that vehicles on the same route do not overtake one another, or alternatively that if they do overtake one another, no passenger is going to avoid boarding a bus because the schedule says the next bus on the same route is faster.

1.3 I have a hard time figuring out how the time dependance of the graph is actually represented. At first I thought that all the departure times for a given trip where linked to the corresponding board edge for that trip (resulting in a static time-dependant graph).

All the departure times for a given trip _pattern_ are linked to these edges, because the edges represent being on a pattern rather than a specific trip. Note that every OnboardVertex references a TripPattern, so every onboard edge transitively references a TripPattern. TripPatterns contain a reference to a Timetable and a list of all associated Trips. The timetable may be rewritten and replaced by realtime update messages.

I am not sure what you mean by "all the departure times for a given trip" and a "static time dependent graph", we'd have to go into more detail to determine if this is similar to the system OTP uses.

From (https://groups.google.com/forum/#!topic/opentripplanner-users/OFhov2RQKao) I understood that only departure times in a given time window are considered when running a search. So this would aim towards a "dynamic" time-dependant graph. Is that correct?

Again I don't know what you mean by "dynamic" versus "static" time dependent graph. Based on the linked message, by "time window" you may be referring to windows at timescales of several days rather than several hours. GTFS contains potentially recurring schedules with trips that may repeat on many days. Those "service days" need to be materialized and searched one by one for departures. By default OTP only searches one day into the future. This is one sense in which it is "dynamic", in that trips are re-instantiated on different days during the search.

1.4 How is bike sharing implemented ? My intuitive solution would have been to preprocess the N*(N-1) shortest path between all bike stations pairs, and add these new edges to the graph. However, it wouldn’t support user preferences considered in the “Bike triangle”. So without creating new edges departing from and arriving at bike stations, how does OTP routing ensure that a shared bike is left at a stop before arriving at destination ?

We generally avoid solutions of N^2 complexity when possible. A notable exception is pre-computed transfers, the number of which do not explode too badly because we impose a distance limit. And pre-computed transfers were a later addition to OTP which used to find all transfers on the fly.

This is how bike sharing works. The routing graph is effectively split into multiple layers by considering search states where a bicycle has been rented to be incomparable to search states where a bike has not yet been rented or has been dropped off. See the method: org.opentripplanner.routing.spt.DominanceFunction#betterOrEqualAndComparable

1.5 When connecting the transit graph with the OSM graph, does the linker consider the whole OSM graph or only the edges where walking is authorised ?

Vertices of the classes TransitStop, BikeRentalStationVertex, and BikeParkVertex are all linked to the street network only to roads that can be walked on, at org.opentripplanner.graph_builder.linking.SimpleStreetSplitter#link(org.opentripplanner.routing.graph.Vertex).

2) Routing

2.1 I’ve seen here (https://groups.google.com/forum/#!topic/opentripplanner-users/L8XnN6iyZBE ) and here (https://groups.google.com/forum/#!topic/opentripplanner-users/FK3MKI0PU9Y) that OTP routing doesn’t support hard limits on variables (such as max transits) because it’s based solely on the optimisation of the “generalised cost” variable. Yet I see that it is possible to choose a max walk distance in the trip options. How can this be performed ?

The max walk parameter limits the distance around the origin and destination point where transit can be boarded. It works by ignoring the existence of the rest of the network. Cutting out a subset of the graph this way is algorithmically valid; limiting the total distance walked is not (unless you find all Pareto-optimal paths with walk distance as one of the variables).

2.2 From (https://opentripplanner.readthedocs.io/en/latest/Bibliography/), I see that routing (for mode combinations using transit) uses the Tung-Chew heuristic.

This is still correct - by default we currently use the InterleavedBidirectionalHeuristic which is essentially the Tung-Chew heuristic.

I have two questions about this. First, this is referenced in the bibliography as a technique for multi-objective Pareto optimality. Does it still bring benefit in the current one-variable optimisation ?

Yes, this method has been measured to significantly speed up searches on large networks like the whole Netherlands or New York City regions. The heuristic allows the search algorithm to explore "promising" paths first (cf any general explanation of the A* search process). It's just all the more important when doing multi-objective searches because there is so much more branching, so you want to defer exploring as many paths as possible.

Second, I’m not sure to understand the part “(i.e. a graph grown backward from the destination providing a lower bound on aggregate weight) for queue ordering”.  If the graph is grown from the destination, how can we calculate dynamically the weight of the PatternBoard edges, which to my understanding were calculated from knowing the time at which they are traversed and finding the next departure time.

An A* heuristic does not need to know the exact weight to the destination, it just needs to give a lower bound on that weight. The tighter the lower bound, the more it speeds up the search by selecting the best edges to explore. Negative edge weights are not allowed, so zero is a valid lower bound on any edge or path weight. When we grow the tree backward, we only calculate the weight for very easy edges that don't cause much branching or complicated timetable searches. Anything complicated we can replace with zero. This causes the backward tree to grow much faster than the forward tree, and by the time the forward tree branches too much it is receiving lots of lower bound information from the backward tree. Note that because we are always exploring states of monotonically increasing weight in any Dijkstra-type search, we also have a lower bound for any node that has not yet been explored by the backward search: we can report the highest weight yet seen in the search.

2.3 Is that correct that contraction hierarchies is no longer used?

We no longer use contraction hierarchies. They are well suited for point-to-point queries where weights are all known ahead of time, and where there is a strong hierarchical nature to the paths. Because OTP focuses on multi-modal routing, our target use case for street searches is finding routes to every transit station within a certain radius of the start or end point, which is not the target use case of contraction hierarchies. In addition these paths are found within a relatively short walking or biking radius, a scale at which the network may not exhibit much hierarchical structure. Finally, we have a lot of runtime, request-scoped parameters that let people customize their routes (like the bike triangle). Contraction hierarchies depend on a large amount of pre-calculation assuming fixed edge costs. 

It is probably possible to speed up the street searches using some of the advanced contraction-hierarchy type algorithms that have been published over the years. Variants even exist to accommodate variable edge costs. But my sense is that the speedup would not be worth the complexity and maintenance cost for our use case.

2.4 From (https://groups.google.com/forum/#!topic/opentripplanner-users/anzHLDnlJx4), there was 2 strategies to compute multiple itineraries, and “trip banning” was the one used at this time. Is it still the case ? 

Yes, we still use a form of trip banning. The search is repeated leaving out trips that were used in already-found solutions. This is faster than it used to be because the reverse search results from the bidirectional heuristic are reused when finding subsequent paths. The alternative is to use multi-criteria methods, which is viable but proved to be slower - we just aren't using multi-criteria search by default now.

2.5 Some modes of transport brings constraints : e.g. using a bike can only be allowed at the beginning of the trip, be as soon as there is a switch to another mean of transport, you can’t go back to the bike. The same goes for the car. How is the routing performed in order to respect these constraints ?

This is the same mechanism used for bicycle drop-off. The method org.opentripplanner.routing.spt.DominanceFunction#betterOrEqualAndComparable considers some states completely incomparable to one another, which in essence replicates the routing graph into multiple layers, one for each state of being on a bike, off a bike, in a car, etc.

3) Miscellaneous

3.1 I didn’t come across information about support for car sharing. Are there plans to support it ?

If by car sharing you mean something like bike share / rental systems but with cars (you borrow the car and drop it off, possibly at predetermined locations) then yes, there are people interested in implementing this. It's basically the same thing as bicycle routing but with a different mode, so the idea would be to generalize bike share to other modes. However there is no concrete plan as to when this would be implemented or by whom. But there is a lot of activity currently around integrating OTP with ride share services and other modes.

3.2 What does the “Weight” cursor represent in the web client (between “preferred routes” and “banned routes”) ?

I don't know the answer to this one. I use that web UI only for testing, and in production deployments we usually use completely separate UIs.

3.3 What is the difference between “bicycle and transit” and “bike and ride” options ?

I'm also not sure about this one, are these options that appear in the UI? Some systems allow you to take a bicycle on a train or on a bus rack, so there is a distinction between parking your bike before riding transit vs. trying to take your bike on transit. 

Regards,

Andrew

[andrew byrd]

A few follow-up responses to your other email:

On 6 Dec 2018, at 8:40 PM, Victor G <victor1...@gmail.com> wrote:

The layer representing the bike network would only be connected to the walk network at the bike stations, this would allow to run a classical Dijkstra/A* to find the best path.

There is no separate bike network, bike routing occurs on the same street graph but there are mode / permissions flags on the edges to say which vehicles can use them. 

The bike network and car network would only be connected to the walk network with unidirectional "alight edges" :

- for BikeAndRide/ParkAndRide : alight edges only at bike/car parkings

There are bike rental transition edges, which are loop edges that set a flag on the search state saying that you're on a bike. This information is then used to fork the graph on the fly as described in my other email.

-Andrew

[Victor G]

Thank you very much for these answers, it helped me a lot.

Regards,

Victor G

[Victor G]

Hello,

Sorry to bother you again, but I would like to know if I’m understanding the graph structure correctly.

Here are some related previous messages :

"This is how bike sharing works. The routing graph is effectively split into multiple layers by considering search states where a bicycle has been rented to be incomparable to search states where a bike has not yet been rented or has been dropped off. See the method: org.opentripplanner.routing.spt.DominanceFunction#betterOrEqualAndComparable"

"When we grow the tree backward, we only calculate the weight for very easy edges that don't cause much branching or complicated timetable searches."

"by the time the forward tree branches too much it is receiving lots of lower bound information from the backward tree"

"This is the same mechanism used for bicycle drop-off. The method org.opentripplanner.routing.spt.DominanceFunction#betterOrEqualAndComparable considers some states completely incomparable to one another, which in essence replicates the routing graph into multiple layers, one for each state of being on a bike, off a bike, in a car, etc."

"There is no separate bike network, bike routing occurs on the same street graph but there are mode / permissions flags on the edges to say which vehicles can use them. "

"There are bike rental transition edges, which are loop edges that set a flag on the search state saying that you're on a bike. This information is then used to fork the graph on the fly as described in my other email.”

From that I understand that during routing, a layered graph is constructed by branching/forking the initial graph at nodes where a switch of mode of transport can occur.
I have attached 2 pages explaining what I mean by layered graph structure. (This is part of my project report on multi-modal routing).
Can you please tell me if it it similar to the working of OTP, or if I am off-track ?

Also, while experimenting with the OTP web client, I came across cases where solutions proposed bike segments after walk segments (as shown on the linked image). I guess it is normal if the bike network is not a separate network. In this case it is not really a problem, because the user can walk alongside the bike, but does OTP have a way to prevent using bike after transit ? Or does it consider that bike are allowed in public transportation ?

Regards,
Victor Goossens