search

kuanb / peartree

peartree: A library for converting transit data into a directed graph for sketch network analysis.
MIT License
201 stars 25 forks source link

[feature] Implement custom routing method that allows for transfer and walk limits #124

Open kuanb opened 5 years ago

kuanb commented 5 years ago

As pointed out by @rxl204, it would be handy to limit the number of transfers that can be made when identifying possible routes (e.g. no more than 2 transfers).

Similarly, whatever feature that addresses that might also institute a walking limit (if walk segments are included). That is, just like one can limit the transfer count, one could limit the number of meters an agent can walk (e.g. no more than 1 miles) when determining paths.

HTenkanen commented 5 years ago

@kuanb Hi Kuan!

First of all, I'd like to say and thank for your brilliant work! I really like your approach for creating networkx graph to conduct public transport routing and accessibility analyses. I've been using previously OpenTripPlanner etc quite a bit for similar things, but I prefer doing programming with Python so I'm glad that I found your library. 🙂

I have now played around with peartree a little bit, and I have some issues of getting the routing to produce correct results when combining the road network graph with the transit graph. I guess this might also somehow relate to #123. The following images demonstrate the issue:

image

image

So as you can see, there is a huge difference in the results when calculating shortest path between the exact same nodes. The outcome from using PT-only graph produces valid results that are more or less in line with Google Maps for example, but when using the public transport + walk network, I get more than 20 minutes longer travel time estimate. As you can see from the left image, it seems that the routing algorithm is switching between walking (blue parts) and public transport (red line) and jumping off and on again in different parts of the trip.

I was wondering what could be the reason for this behavior, am I building the graph somehow incorrectly, or is this a problem in peartree? Could you help me out?

You can check the full workflow, get the data and see how I produced the graphs and the figures from this code.

Cheers, Henrikki

HTenkanen commented 5 years ago

Here is another comparison using ego-graph from the same location with PT-only (left) and PT+walk: image. The PT graph on the left reaches much more nodes

kuanb commented 5 years ago

Thanks @HTenkanen!

I'll take a look into this and get back to you. My immediate reaction is that what (I think) is happening is that there is a boarding penalty from the walk network.

So when on the walk network, a penalty (1/2 of headway for a route) is imposed. So, for example, in your first example, when it is just transit, we just look at the time it takes to get from one stop on the network to another point on the network.

But, when the walk network is added, we might start from the walk network in which case the headway is factored in. Let's say that the bus comes 1x per hour, that would mean a 30 minute boarding penalty (which can be controlled in peartree, the default being described here: https://github.com/kuanb/peartree/blob/master/peartree/paths.py#L25-L66).

It might help to show some examples of how these results could be used where the first wait time is pruned to assume the rider planned their trip so as to not wait a full half of the headway each time.

The purpose of that is when modeling accessibility, rather than performing a single journey route, averages are to be taken to see overall trends. Please let me know if this makes sense or doesn't make sense!

HTenkanen commented 5 years ago

@kuanb Yep that might be the reason. I kind of like the approach how urbanaccess has solved this. I.e. they add the headways into the links that connects the stops into the walking network. At least that approach produced quite rational results even when doing shortest path calculations. Of course averaging headways, does not produce most accurate results (in a similar manner as OTP does), but I think they produce overall quite good results.

FYI, I wrote a simple conversion tool that converts urbanaccess Network into NetworkX MultiDiGraph which you can find from: https://github.com/HTenkanen/ua2nx

With that I am able to get quite good results combining walking network and pt network.

d3netxer commented 3 years ago

I don't understand, how does routing take into account the boarding penalties? The boarding penalties are represented at the stop nodes correct? Any code would be appreciated.