Experimentation on bike rental support for OTP

[Laurent GRÉGOIRE]

Hi,

I was experimenting a bit on the implementation of bike rental mode for OTP and I would like to share an early state proposal (patch and a teaser screenshot attached). This is a work in progress and this patch is not meant for being included (yet). I'd like to get an early feedback on the current state of development, in particular on some choices made.

The approach taken is to reuse multi-state per vertex capabilities for non-transit mode (no duplication of the street graph needed). IMHO this is more flexible in the long term if a more complex states matrix is needed (I'm thinking of park-and-ride here).

I made several tests on simple scenarios: bike renting only, bike-renting + transit, arrive-by, bike-rental+walk portions (stairs), bike rental + triangle routing, and everything seems to work fine.

A summary of the changes:

== Graph building ==

- Addition of one vertex (BikeRentalStationVertex) and three edges:

  a) StreetBikeRentalLink which link the station to the street network (equivalent to StreetTransitLink)

  b) RentABikeOnEdge - From a bike station to itself, process the "bike renting" state change

  c) RentABikeOffEdge - Dropping off a rented bike.

I break here the assumption that an edge link two different vertexes: the bike rental vertex is unique per rental station. However this has an impact on backward assertion test in StateEditor which has to be disabled when both vertex are equals (to confirm -- does this assertion is really mandatory?) I also made another version with two different vertex type per rental station, but this double the number of links to the street network, and does not bring anything.

- Parsing of bike rental node from OSM (OpenStreetMapGraphBuilderImpl). This is done in two phases:

  a) one early phase parsing the node itself and creating a BikeRentalStationVertex with the two bike rental edges

  b) one later phase linking the bike rental nodes to the street network, creating StreetBikeRentalLink edges. Here I'm reusing internally the NetworkLinkerLibrary with some modifications (to confirm?)

== Routing ==

- Addition of a new boolean state "bike renting" in State.StateData.

- I break here the assumption that *the non-transit traverse mode is fixed* : this is the biggest change so far, and imply that the current traverse mode depends on the current state. This impacts:

  a) TraverseModeSet.getNonTransitMode() is removed

  b) It is replaced by State.getNonTransitMode(TraverseOptions) (to confirm?)

  c) TraverseOptions speed/board cost depends also on state, with new getters for the current speed/board cost, added getters for lower/higher bound values, and define speed for each non-transit modes (walk, bike, car).

  e) canTraverse() functions of several edges/vertex are split in two:

      - one case covering actual traversal check for a given state, where we know actual "real" traverse mode, in the case of actual traverse() call from the router;

      - one case covering potential traversal check for a given TraverseOptions, where we know only "potential" traverse mode, in the case of route linking.

  f) To summarize: if modes defines WALK and BIKE, we allow renting. The current real traverse mode depends on "bikeRenting" state (true: mode=BIKE, false: mode=WALK). Actual modes are not changed (WALK=walk only, BIKE=own bike).

- State.dominates() take into account bike rental mode. Two different bike-renting states never dominates each other to allow for proper handling of multiple states per vertex.

- The end of search condition in the A* algorithm is now based on reached vertex AND state. I created a state.isFinal() method which return true if the state is end-of-search: for bike rental the implementation is simply that the state is not in "bike rental" mode. (to confirm?) Also the AbstractShortestPathTree grab only "final" states from the end vertex, not all of them.

- I force the use of MultiShortestPathTree in case of transit OR bike rental mode, to allow for multiple state per vertex (renting, non renting).

- Boarding a bus depends on actual mode (bike rented or owned, no bike). This covers with only a minor modification the following scenarios:

  a) bike is allowed in transit: walk > rent bike > bike > transit > bike > dropoff bike > walk

  b) bike is not allowed in transit: walk > rent bike > bike > dropoff bike > walk > transit > walk > rent bike > bike > dropoff bike > walk

== Contraction hierarchy ==

- Changes are about the broken assumption of a fixed non transit state. Since we now allow dynamic non-transit traverse mode (walk/bike) this may break the CH optimizer (especially the check for similarity between modes). I'd like to get feedback on this as I have no hand-on experience on how CH works.

== Client (no major modifications) ==

- Bike renting narrative is only a mixed mode of walk/bike. It could be added a specific instruction for "renting a bike"/"dropping off a bike"; but since both walk and biking instructions heads to a "Bike rental station XYZ", the instructions maybe clear enough like that.

- Added "bike renting" mode and "transit + bike renting" by setting traverse modes to "WALK,BIKE" or "TRANSIT,WALK,BIKE" in the mode dropdown.

== Unit testing ==

- All unit tests (to my knowledge) have been updated and run ok. I did not tested however the unit tests requiring external data (city graphs and/or GTFS).

- Proper unit testing have to be added covering bike rental.

Future changes that could/have to be made:

- Backport the changes made to A* to other search algorithms (which ones?)

- Test/validate on other RemainingWeightHeuristics (I only tested on the default one so far) -- especially evaluating the impact of dynamic street speed and boarding cost

- Make the NetworkLinkerLibrary more generic by providing a factory to create street link edges.

- For now on I'm only covering the simple case that the user does not have a rented bike when starting, and must drop it off before arriving. Covering the more complex cases (starting with an already-rented bike, arriving w/o dropping off the bike, and both) can be easily covered by appropriate changes to starting state and isFinal() end condition. The complexity is more on the user interface.

- Proper naming for bike rental stations: optionaly use the network name if it exists, i18n

- Currently, a user can dropoff a bike in any station, regardless of where it has been picked-up. This works for single networks, but where several incompatible bike networks overlap, this is not true anymore. I don't think this is an issue for now (I do not know any city with this strange scenario). We could however cover this simply by saving a rented bike network ID in the state and checking for appropriate condition on dropoff (this would increase the number of states per vertex: you can potentially have as many states per vertex as number of overlapping bike networks + 1)

I'd love to hear some feedback on this development before going further; if the current patch is heading in the correct direction and any other comments.

--Laurent

[Josh Doe]

On Tue, Apr 10, 2012 at 6:01 AM, Laurent GRÉGOIRE
<laurent....@gmail.com> wrote:
>
> I was experimenting a bit on the implementation of bike rental mode for OTP
> and I would like to share an early state proposal

I can't comment on the implementation since I'm not familiar with the
inner workings of OTP, but I'd like to say very cool and thanks for
working on this! It has reignited my interest in getting an OTP
instance setup for the Washington D.C. region.

-Josh

[Andrew Byrd]

Hi Laurent,

On 04/10/2012 12:01 PM, Laurent GRÉGOIRE wrote:
> The approach taken is to reuse multi-state per vertex capabilities for
> non-transit mode (no duplication of the street graph needed). IMHO this
> is more flexible in the long term if a more complex states matrix is
> needed (I'm thinking of park-and-ride here).

Thanks for your work on this, and your detailed explanation. We were
just discussing bike rental capabilities recently, and you have
implemented exactly the approach we planned to use (mode-switching loop
edges).

> I break here the assumption that an edge link two different vertexes:
> the bike rental vertex is unique per rental station. However this has an
> impact on backward assertion test in StateEditor which has to be
> disabled when both vertex are equals (to confirm -- does this assertion
> is really mandatory?)

I wouldn't say it's mandatory. I believe it was just added when
debugging a specific problem, and left in as a general graph coherency
safeguard. Of course it would also be possible to make the bike
rental/drop off edges parallel to the street/bike-station link edges
(i.e. have a rental edge connect the station to the street). It would
also be possible to eliminate the link edges or distinct edge types
entirely by making the behavior of the rental/dropoff loop edge
mode-sensitive.

> - Addition of a new boolean state "bike renting" in State.StateData.
> - I break here the assumption that *the non-transit traverse mode is
> fixed* : this is the biggest change so far, and imply that the current
> traverse mode depends on the current state.

Yes, we were going to need to change this. I was expecting to add a
back-mode field to State to express which mode was used to traverse the
back-edge, instead of the wrapped edgeNarratives we now use. In fact I
think the main reason EdgeNarratives still exist distinctly from edges
is to indicate mode. What does everyone think of this approach?
Traversal mode seems like state to me.

> - State.dominates() take into account bike rental mode. Two different
> bike-renting states never dominates each other to allow for proper
> handling of multiple states per vertex.

Right, I think we want states of different modes to be incomparable
(i.e. neither dominates the other).

> I'd love to hear some feedback on this development before going further;
> if the current patch is heading in the correct direction and any other
> comments.

It sounds like you have adequately considered all the implications of
bike rental, and would be happy to further discuss specific
implementation decisions. The main challenge at this point is more
organizational: I am in the midst of a major overhaul of TraverseOptions
and the stack of Service interfaces we go through to get a path. (see
branch sptservice, more on that in a later email.) We should definitely
coordinate over the next couple of weeks so we don't end up with two
interesting branches that are near impossible to merge.

-Andrew

[Oscar Formaggi]

+1

[Laurent GRÉGOIRE]

Hi Andrew,

Thanks for your feedback.

The approach taken is to reuse multi-state per vertex capabilities for
non-transit mode (no duplication of the street graph needed). IMHO this
is more flexible in the long term if a more complex states matrix is
needed (I'm thinking of park-and-ride here).

Thanks for your work on this, and your detailed explanation. We were just discussing bike rental capabilities recently, and you have implemented exactly the approach we planned to use (mode-switching loop edges).

Glad to hear this. In fact I was not aware of all the discussions so far except the one we had a while ago about integrating work done by Francisco on Valencia bike rental, using the (different) "duplicated street network" approach. I will continue on this line then.

 

I break here the assumption that an edge link two different vertexes:
the bike rental vertex is unique per rental station. However this has an
impact on backward assertion test in StateEditor which has to be
disabled when both vertex are equals (to confirm -- does this assertion
is really mandatory?)

I wouldn't say it's mandatory. I believe it was just added when debugging a specific problem, and left in as a general graph coherency safeguard. Of course it would also be possible to make the bike rental/drop off edges parallel to the street/bike-station link edges (i.e. have a rental edge connect the station to the street). It would also be possible to eliminate the link edges or distinct edge types entirely by making the behavior of the rental/dropoff loop edge mode-sensitive.

Having the loop-edge at the rental station itself and keeping street-to-station link separate may be more natural, in the sense that it model the way a user would pick up a bike: move to the station, pick up the bike, move out the station. Real-world OSM shows that bike rental station can be several meters (sometimes 20-50 meters) from the street network. Having separate edges for linking and renting may also ease and clarify the narrative details (?). Anyway, I disabled the assertion only in the case of from-to vertex being equals, so the assert is still there in most of the cases. I'll keep it that way then for now, it can be easily refactored later if needed.

 

I'd love to hear some feedback on this development before going further;
if the current patch is heading in the correct direction and any other
comments.

It sounds like you have adequately considered all the implications of bike rental, and would be happy to further discuss specific implementation decisions. The main challenge at this point is more organizational: I am in the midst of a major overhaul of TraverseOptions and the stack of Service interfaces we go through to get a path. (see branch sptservice, more on that in a later email.) We should definitely coordinate over the next couple of weeks so we don't end up with two interesting branches that are near impossible to merge.

FYI I'm currently working on a fork, where I will commit my bike-rental changes. I will try to see what imply merging bike rental with the sptservice branch. It would be nice effectively to synchronize each other, if possible, as bike-rental need some modification in TraverseOptions. Anyway, if I plan to make other structural changes (I do not think many more are needed for now), I will let you know beforehand, cc-ing opentripplanner-dev list.

--Laurent

[Francisco José Peñarrubia]

Hi Laurent.

Congratulations Laurent, good job!.

One more question, please. Did you made some tests about performance?.
I mean, using the solution in a place bigger than Nantes?. It could be interesting a comparison between 2 trips (walk+transit+walk, without bike sharing and with bike sharing).

And congratulations also for your icons, they look pretty well! :-)

Best regards.

Fran.

-- 
Fran Peñarrubia
Scolab
www.scolab.es

Asociación gvSIG
www.gvsig.com

[Laurent GRÉGOIRE]

Hi Francisco,

A made a quick performance test in a bigger city (Paris), for a trip going through the whole inner city (around 12km in length in a very dense area street-wise), with dummy transit data of only 2 lines (east-west and south-north... unfortunately I do not have transit data in GTFS format for Paris). Below are the results (in ms per request, on an average PC):

Bike 245

Rented bike 542

Walk only 47

Transit only 290

Transit + rented bike 1010

The covered area contains more than 800 bike rental stations.

Transit + rented bike is not very conclusive, as in my test the departure and end point are quite far from transit stations (several kilometers). In another test, with departure and arrival near transit station (~500 meter), which looks a more real-life scenario, the average time is around 300ms, more than 3 times lower (but this make sense). As I have a very simple transit network on my test, the transit results are to be taken with a pinch of salt anyway.

I did not made any test using CH so far, I plan to test it soon.

HTH,

--Laurent

2012/4/11 Francisco José Peñarrubia <fpen...@gmail.com>

[Wojciech Kulesza]

Hi Laurent!
Great job. Thanx to patches like this, OTP can really become an unique tool that really does the best possible job to convince people to leave their car behind and use alternative modes of transit including bike.
If you could tell me the required tags to be added to osm (bike rental stations etc), we can test it on our environment in Poznan (where around 10 bike rental stations are just being installed - no bikes are allowed on PT though). There's over 100 routes and a population of roughly 1M citizens so a good playground.

Regards,
Wojciech @goEuropa

[Laurent GRÉGOIRE]

Hi Wojciech,

The OSM element is a standard OSM node tagged for bike rental (amenity=bicycle_rental). I also use the tag "name" for display. The tag "capacity" is parsed by not used (for now). For official specs see here:

http://wiki.openstreetmap.org/wiki/Tag:amenity%3Dbicycle_rental

HTH,

--Laurent

2012/4/11 Wojciech Kulesza <wojciech...@goeuropa.eu>

[David Turner]

I've merged Laurent's changes, and I've also added some additional
features to handle bike sharing systems with near-realtime (update
frequency defaults to 5 minutes) availability information.

To give it a try, edit your application-context.xml thus:
<bean id="periodicGraphUpdater"
class="org.opentripplanner.api.servlet.PeriodicGraphUpdater">
<property name="updaters">
<list>
<bean
class="org.opentripplanner.updater.bike_rental.BikeRentalUpdater">
<property name="bikeRentalDataSource">
<bean
class="org.opentripplanner.updater.bike_rental.KeolisRennesBikeRentalDataSource">
<property name="url"

value="http://data.keolis-rennes.com/xml/?version=2.0&amp;key=CFQKOUGDWGDO8NY&amp;cmd=getbikestations&amp;network=levelostar&amp;station=all" />
</bean>
</property>
</bean>
</list>
</property>
</bean>

If you already have a periodic updater for GTFS-realtime, you can just
add the bike rental updater to that.

We support two bike rental APIs at present:
KeolisRennesBikeRentalDataSource, and BixiBikeRentalSource (used in DC,
for instance).

If your city's bike rental API is anything like Bixi or Keolis, it's
trivial to add support for it.

If your city's bike rental API is like Velib (with a separate query
needed for availability data, for no good reason), I would recommend
simply not providing any availability data and assuming that all stops
are available for pickup/dropoff.

Realtime availability is only used for trips planned for times near now
anyway; for future trips, we assume that everything is available.

[Laurent GRÉGOIRE]

Hi David,

Thanks for the merge.

Realtime availability is only used for trips planned for times near now
anyway; for future trips, we assume that everything is available.

This present a temporal discontinuity, conceptually it's maybe not what you would do in real-life: a user can decide to wait at a station if he knows that a new bike has some chance to arrive in the next few minutes.

Another solution would be to use the time/cost of renting to model this: if there is no bike at a station, the cost to rent would be the average (worst?) time to wait for a new bike to arrive. I understand that this average time may be hard to determine, but we can always overestimate it to be on the safe side. This approach takes into account the exact time in the future at which the trip is made: if the computed average time to wait for a bike is 30mn and you plan a trip to depart in 25mn, then the cost to rent at this station would be 5mn+bike rental time. And to my humble point of view this fits well into the concept of planning: in the event a station is empty and there is another bike rental station with bikes nearby, the planner would propose you to go there instead; if no other station is nearby the planner would then propose you to wait there if it estimates the average waiting time is less than walking further.

We could also use a exponential average to model decreasing cost in the future: in that case the average waiting time is considered as some sort of "half-life to see a bike appearing" and the cost would drop exponentially from now. This may be a bit overkill though.

Computing average waiting time for waiting a bike may be a bit complex as this imply probability and real-time data depending on many factor; but we may use real-life data if this exists somewhere. Maybe somebody knows if some existing data is available? A quick back-of-the-envelope-calculation: if we know the average number of dropoff per day, we can determine the average waiting time to be (number of dropoff / 1 day / 2) in case of an exponential distribution memoryless, if nobody else is waiting. That probably imply that the bigger the station is, the shortest the average waiting time is; so the size of the station may be used for a crude approximation. Real-time data history could be also used (history of availability during the day depending on time), but this would be more complex and may be a bit brittle.

The drawback with this approach is that we can potentially direct a user to a known empty station and frustrate him if by no luck no bike arrives soon :)

--Laurent

[David Turner]

On Wed, 2012-04-25 at 10:50 +0200, Laurent GRÉGOIRE wrote:
> Hi David,

> The drawback with this approach is that we can potentially direct a
> user to a known empty station and frustrate him if by no luck no bike
> arrives soon :)

Yes, this is what I'm worried about. Of course, we might do that
anyway, since someone could come along and snag the last bike.

I'm also not 100% sure about planning based on estimates of
availability. I worry about stranding someone far away from
civilization with no bike available. This is especially true if there
is a sudden surge in demand because of (for instance) a transit strike.
There, our normal predictors would be too optimistic.

If we could tell people where all the nearby bike share stations are, we
could plan the sort of hyperpath that you suggest, which tells people to
go to one of a set of nearby bike share stations. I worry that this
would end up multiplying the number of states too much, as states with
bikes rented from different stations would have to be different (at
least within some epsilon).

We could also simply edit the narrative to display bike share stations
near the ones we propose on the map. We could also display capacity
that way. Frank, if I do the backend work to do this, would you be
willing to do the front-end work? Do you think
nearby-bikeshare-stations should be included in the plan, or should be a
separate API call?

[Laurent GRÉGOIRE]

Yes, this is what I'm worried about.  Of course, we might do that

anyway, since someone could come along and snag the last bike.

 

With the "average waiting time" approach, we could model this by a non-zero waiting time when the number of available bikes is low regarding the station size.

I'm also not 100% sure about planning based on estimates of
availability.  I worry about stranding someone far away from
civilization with no bike available.  This is especially true if there
is a sudden surge in demand because of (for instance) a transit strike.
There, our normal predictors would be too optimistic.

Especially that on the client the default departure is "now", and lots of people (including me) do not update this time, even for a departure in the far future, knowing implicitly (but wrongly in that case) that departure time has no influence on a bike ride.

 

If we could tell people where all the nearby bike share stations are, we
could plan the sort of hyperpath that you suggest, which tells people to
go to one of a set of nearby bike share stations.  I worry that this
would end up multiplying the number of states too much, as states with
bikes rented from different stations would have to be different (at
least within some epsilon).

Or we could take the approach used currently with transit: propose a set of (3 or more) paths with "bike rental station" banning: ie computing three time a path, the first one with all stations, the second one w/o the set of used stations of the first, etc... The user would then pick the best one based on bike availability, as displayed in the client interface. And if we choose a small enough waiting time for a station with no bike available, this station could then be still proposed as a second of third choice. But that may be a bit complex to implement in case of "bike rental + transit" modes.

--Laurent

[Tim Moreland]

Or we could take the approach used currently with transit: propose a set of (3 or more) paths with "bike rental station" banning: ie computing three time a path, the first one with all stations, the second one w/o the set of used stations of the first, etc... The user would then pick the best one based on bike availability, as displayed in the client interface. And if we choose a small enough waiting time for a station with no bike available, this station could then be still proposed as a second of third choice. But that may be a bit complex to implement in case of "bike rental + transit" modes.

1+ I like this idea of letting the user choose their own level of risk (ie going to a station that is full or near full). One concern I have is with adding an additional step to the trip making process and that it will confuse and clutter up the process of making a trip. Perhaps there would be a check box when planning trips using bike rental that defaults to "choose bike rental station for me" checked so that users don't have to do the extra step unless they want to (un-checking the box and specifying their desired station).

Here in Chattanooga we will have data on average station occupancy that could be summarized by weekday, weekend, day of the week and time of day (hour). I'm working to open up this data and perhaps it could be used to better estimate the likelihood of a station staying full or empty based day of the week and time of day. We are using the Bixi system here. David is there code on the github site for incorporating this near realtime data into OTP from a Bixi system?

--
Tim Moreland
www.aplannersguide.com

[Francisco José Peñarrubia]

Hi Tim.

You may find interesting this web:

http://biciv.com/

I don't know if it is SL, but you can ask its creator:
https://twitter.com/#!/lexbar

or at least, it will be useful to take ideas. It works also in mobile phones, so, it's really useful.

Hope it helps.

Fran.

[David Turner]

On Thu, 2012-04-26 at 09:20 -0400, Tim Moreland wrote:

>
> Here in Chattanooga we will have data on average station occupancy
> that could be summarized by weekday, weekend, day of the week and time
> of day (hour). I'm working to open up this data and perhaps it could
> be used to better estimate the likelihood of a station staying full or
> empty based day of the week and time of day.

That seems useful. Let us know when it's available!

> We are using the Bixi system here. David is there code on the github
> site for incorporating this near realtime data into OTP from a Bixi
> system?

Yep -- Bixi is one of the two supported systems.