Unexpected increases in transit travel time when including wholly additional services

[James DeWeese]

I've been trying to compare centroid-to-centroid travel times under two different transit scenarios: one with express buses and one without.  Rather unexpectedly, I actually get much longer travel times for some O-D pairs WITH the express routes added. I can't really imagine a scenario where the travel time would ever be longer with completely additional, rather than substituted, service.

What I did: 

Using OTP version:   MavenVersion(1, 5, 0, SNAPSHOT, eeb8d50dcb43ff3fd134e4c181b8d1e7b59cb83f), I built two graphs with identical settings, OSM streets and GTFS feeds, except for the removal of express buses from one set of the feeds.  For the feed adjustments, I merely deleted the routes and related stop_times and fares, so there was no change to anything else. Then I generated a travel-time matrix using identical parameters.  

What I got: As expected, without the express buses there were fewer OD pairs with trips identified because I had a total trip time cut-off.  Weirdly though, there were also quite a few pairs where travel time went up, not down, with the addition of the express buses.   (~14,000 out of 650,000). It's causing me to not trust the estimates because I can't logically make sense of it.  As I said, the express buses aren't substituting anything that could lead to weird results.  They're simply layered on top.

I'm pretty new to OTP and I'm stumped.  The only thought I've got is that some random noise is automatically generated by OTP, perhaps because of the the use of frequency-based trips by some providers.  Is that even possible?  Has anyone experienced this behavior and is there a way to control for it? 

[Stefan Steiniger]

Hi,

I as well receive counter intuitive results sometimes and its difficult to figure out why. Anyway, reasons might be: when you remove the express lines, you may remove also its stops? - so the  network could have a lower coverage. Even just crossing a street may change things. And as you say: availability (schedules and lines frequency) could be an issue. So it may be intetesting to see what happens if you shift start time by + and - 5 or even 10 mins.

My 2 cents,

Stefan

Sent from BlueMail

[James DeWeese]

Thanks, Stefan!  I don't think it's the stops. I actually went back and verified that I didn't remove any stops, just the express services to them. It's hard to imagine how removing the stops would make some centroid-to-centroid trips shorter rather than longer in any event. It's just so strange because the express buses are purely additional.  I don't know how removing the sexpress tops could ever yield a shorter travel time for any trips, let alone thousands of them, if it means that users have to walk further or wait longer for transit.

It's just really strange because the frequency_table is identical in both scenarios. It's not that anything has been changed at all with the removal of the express buses from the stop_times tables.  (The transit provider only uses the frequencies for metro, not bus. The bus still relies on the stop_times table. For the frequencies, I just thought that perhaps OTP handled those in some way that was different than stop_times, automatically introducing some sort of random noise into connections to services that rely on frequency-based rather than absolute time schedules.  It was the only thing I could think of.  But I re-ran both scenarios from scratch, rebuilt the graphs and redid the routing, to check. And the travel times and deviations are identical to the old batch. If it was random noise, I'd expect it to be different random noise. So I think I've ruled that out.

Since then, I followed your suggestion:  

- I actually ran the same routing at 10-minute intervals over half an hour, so I did 0800, 0810, 0820, 0830.  Still the same counterintuitive result where totally additional Express service translates into longer travel times from and to certain points.  I also averaged the travel times for all origins and destinations across these time periods.  Still the same thing.

- Then I downloaded a more recent otp.jar from the Maven repository but got the exact same deviations.

- FInally, I thought maybe there might be something wrong with the weighting of walking versus transit, so I changed the routing defaults to make the walkReluctance factor 1 instead of 2 and fixed the maxWalkDistance.  I thought perhaps in some places the absence of the Express would force a user to walk to a more distant stop that ultimately afforded faster connectivity to the destination.  But to be honest,  I don't know why OTP wouldn't have already selected the more distance stop and related route if the travel-time was shorter to begin with. In that case, the existence or nonexistence of the express bus shouldn't matter; it should be irrelevant since there's a faster route that exists regardless of whether an express bus exists.  In any event, there is zero difference between the travel times with the default run-time settings and the new ones I tried.

I'm at a total loss.  When you say you've had counterintuitive results yourself, did you have something where someone having to cross the street actually led to a shorter travel time?

Anyway, thanks again.  If you have any other thoughts, definitely let me know.  I'm willing to try anything.

Jamie

[Francisco José Peñarrubia]

Hi James.

Could you share with us router-config.json parameters?.

There are some of them that can produce extrange results.

Best regards.

Fran

--
You received this message because you are subscribed to the Google Groups "OpenTripPlanner Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to opentripplanner-...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/opentripplanner-users/CAFj-o5_7RKMo4sF_h2HFhtpaqShdO-BrNWqYu_pVx9N8Jss-cQ%40mail.gmail.com.

[James DeWeese]

Hi, Fran. Sure thing.  I left most of the defaults. The ones I changed as an experiment were:

{

  "routingDefaults": {

    "bikeSpeed": 5,

    "bikeSwitchCost": 0,

    "bikeSwitchTime": 0,

    "clampInitialWait": -1,

    "maxWalkDistance": 2000,

    "waitReluctance": 1,

    "walkReluctance": 1,

    "walkSpeed": 1.34

  },

  "timeouts": [5, 4, 3, 1]

}

This is what the initial read-out of the terminal session calling the script looks like.  It seems like OTP saw the router-config.json was there and read in the settings. But comparing the two runs, the travel-times were identical to the second.

14:46:03.956 INFO (OTPServer.java:39) Wiring up and configuring server.

14:46:03.973 INFO (GraphScanner.java:64) Attempting to automatically register routerIds [montreal]

14:46:03.974 INFO (GraphScanner.java:65) Graph files will be sought in paths relative to .

14:46:03.975 INFO (GraphService.java:176) Registering new router 'montreal'

14:46:03.975 INFO (InputStreamGraphSource.java:181) Loading graph...

14:46:04.176 INFO (Graph.java:746) Graph version: MavenVersion(1, 4, 0, , b272f14007c97d769216e9ebab65baad7410cdf5)

14:46:04.176 INFO (Graph.java:747) OTP version:   MavenVersion(1, 4, 0, , b272f14007c97d769216e9ebab65baad7410cdf5)

14:46:04.176 INFO (Graph.java:764) This graph was built with the currently running version and commit of OTP.

14:46:10.570 INFO (Graph.java:731) Main graph read. |V|=572744 |E|=2279677

14:46:13.250 INFO (GraphIndex.java:127) Indexing graph...

14:46:14.999 INFO (GraphIndex.java:595) Clustering stops by geographic proximity and name...

14:46:16.953 INFO (GraphIndex.java:210) Creating a spatial index for stop clusters.

14:46:16.983 INFO (GraphIndex.java:192) Initializing areas....

14:46:16.983 INFO (GraphIndex.java:199) Done indexing graph.

14:46:17.091 INFO (Router.java:96) Loading default routing parameters from JSON:

14:46:17.100 INFO (ReflectiveInitializer.java:108) Initialized 'bikeSpeed' with value 5.

14:46:17.100 INFO (ReflectiveInitializer.java:108) Initialized 'walkSpeed' with value 1.34.

14:46:17.100 INFO (ReflectiveInitializer.java:108) Initialized 'walkReluctance' with value 1.

14:46:17.100 INFO (ReflectiveInitializer.java:108) Initialized 'clampInitialWait' with value -1.

14:46:17.100 INFO (ReflectiveInitializer.java:108) Initialized 'bikeSwitchCost' with value 0.

14:46:17.100 INFO (ReflectiveInitializer.java:108) Initialized 'bikeSwitchTime' with value 0.

14:46:17.101 INFO (ReflectiveInitializer.java:108) Initialized 'maxWalkDistance' with value 2000.

14:46:17.101 INFO (ReflectiveInitializer.java:108) Initialized 'waitReluctance' with value 1.

14:46:17.101 INFO (Router.java:127) Timeouts for router 'montreal': [5.0, 4.0, 3.0, 1.0]

14:46:17.101 INFO (Router.java:134) Incoming requests will not be logged.

14:46:17.102 INFO (GraphUpdaterConfigurator.java:41) Using configurations: [main] 

[Francisco José Peñarrubia]

Hi James.

These are my values:

    "routingDefaults": {
      "walkSpeed": 1.3,
      "boardSlack": 20,
      "alightSlack":20,  
      "transferSlack": 100,
      "transferPenalty": 120,
      "minTransferTime": 50,
      "maxTransfers": 4,
      "waitReluctance": 0.8,
      "waitAtBeginningFactor": 0.9,
      "softWalkLimiting": false,
      "softPreTransitLimiting": false,  
      "walkReluctance": 1.1,
      "stairsReluctance": 1.2,
      "walkBoardCost": 30,
      "compactLegsByReversedSearch": true,
      "itineraryFiltering": 1.0,
      "bikeSwitchCost": 20,
      "bikeSwitchTime": 20
    },

I noticed that transferPenalty and waitReluctance and waitAtBeginningFactor affect a lot to calculation.

In particular, in source code you can see some comments about waitAtBeginningFactor and waitReluctance to be LESS than 1.0.

Otherwise, the user is supposed to prefer to stay on board instead of wait a bit for a better trip.

Please, try, and tell us if something improves.

Good luck!

Fran.

--

Francisco José Peñarrubia

[James DeWeese]

Thanks, Fran. I'll give it a whirl this evening and let you know tomorrow or the next day how it went.

[James DeWeese]

Hi, Fran.  

Thanks again for your advice and the router-config settings.  With your help, I'm definitely getting results that are trending in a more logical direction.  I'm down to about 2,000 trips that are coming back unexpectedly longer with the addition of express bus services.  That still doesn't make any sense to me, but 2,000 out of 600,000-plus isn't bad, and 2,000 is better than the more than 5,000 before.  I still wish I could fully understand what was going on. 

Do you, or someone else, know how I might be able to generate a travel-time matrix based on the absolute shortest trip in minutes (even if it's unreasonable/not reflective of a traveler's preferences or reality)?  If I just wanted to check the absolute minimum travel time under two different scenarios without regard to any weighting or factoring for routing preferences at all, is there a way to do that with Open Trip Planner?  I figure there must be some way to simply set all of the configurations not to their realistic defaults but to something that has zero impact. But I'm inexperienced enough not to really know.  I've used Network Analyst in the past and never experienced this phenomenon. 

Anyway, thanks again.   It definitely got me moving in a better direction. 

Jamie

[Francisco José Peñarrubia]

Hi James.

About 2.000 trips longer... no idea, but sometimes, GTFS files are not correct (for example, from one stop to the next, the arrival is lower, and many other errors. When building the graph, there are warnings that you can see related to those errors. Recently, I've found a good tool to fix some of these errors automatically, and removing duplicated trips, etc.

Here you are the link:

https://github.com/patrickbr/gtfstidy  

About calculating ODMatrix, I have not used OTP for that, but I guess it should be possible. In docs, there is an example about calculating isochrones, and I suppose before calculating the isochrone, a calculation from one point to many is happening, which is the building block of a ODMatrix. (This is important: to calculate from one point to many. Not from one point to another point).

http://docs.opentripplanner.org/en/latest/Intermediate-Tutorial/ 

Also, there is documentation about using scripting to do this kind of thing:

http://docs.opentripplanner.org/en/latest/Scripting/  

https://github.com/opentripplanner/OpenTripPlanner/blob/master/src/test/resources/scripts/test.py  

I suppose you are using this method to calculate ODMatrix.

Hope it helps.

Good luck!

Fran.

--

Francisco José Peñarrubia

[Andrew Byrd]

Hi Jamie,

As you may have gathered from other responses, OTP is not optimizing travel time, it is optimizing the generalized cost of the trips. So in short, the assumption that OTP is returning fastest paths is incorrect. OTP contains multi-criteria routing code that can be seen as a programming toolkit capable of many different behaviors. It's wired up one way by default for typical passenger-facing trip planning, but can be changed. First I'll provide some ideas on how that might be done, then some less technical context.

In GraphPathFinder around line 88 you will see the dominanceFunction field on the routing options is set to MinimumWeight. This can be set to any other function, with two important alternatives being EarliestArrival and Pareto. Do note though that this has been hard-wired to MinimumWeight since 2015, so it's possible other code (such as the goal direction heuristic) has evolved over time to expect MinimumWeight. Some such potential conflicts could be sidestepped by using the TrivialRemainingWeightHeuristic, which is the right approach anyway if you're building full shortest path trees at each origin. As Fran pointed out, it's highly inefficient to calculate a path for each O-D pair independently. Much of the calculation for all paths from a single origin point is the same - ideally you want to build a single shortest path tree from that origin and read off the paths to every destination from that one tree. Using the approach from OTP's isochrone code or various analysis and scripting components this should be possible, but I haven't used OTP for this purpose for several years so I don't know how much coding it will take. Some of this wiring be facilitated by the OTP scripting extensions which I haven't used myself.

Now for some general context: The primary purpose of OTP is to suggest itineraries to transit riders. From this perspective the "best" itineraries are not always the fastest ones. OTP has accumulated a lot of tweaks and ad-hoc rules over the years based on feedback from people running public OTP servers. A lot of compromises have been made between principled optimization methods and factors that were observed to usually reflect riders' travel preferences.

In addition, while OTP is minimizing generalized cost, by default it is not tracking all the trade-offs that occur between time and generalized cost. Strictly speaking this is not algorithmically correct because transit departures are time-dependent. In a multi-leg trip, OTP may choose a "better" but slower or later-departing first leg which then causes it to arrive at a transfer point slightly too later to catch and otherwise possible second leg. OTP actually contains a lot of code and data structures for multi-criteria routing which would allow a thoroughly correct solution to this problem, but the OTP 1.x router design is a decade old and not efficient enough to do this at large scale. We were very hesitant to switch to this potentially problematic single-criteria routing, but based on feedback from major users of OTP at the time, the results obtained with the algorithmically incorrect approach were good from a rider perspective, and response times were much better.

So OTP contains the components of a more strictly correct router that also optimizes travel time, but these are disconnected by default because the router design is too inefficient to do this at large scale. This is why we've spent five or six years testing and building replacement routers to get where we are now: OTP2 which has a much faster transit router inspired by the R4 and R5 projects, and separate projects targeting network analysis that are highly specialized for one-to-many searches minimizing travel time and measuring travel time variation over multi-hour departure time windows.

A lot of transportation network analysis has been done with OTP. In fact, the reason I began working on trip planners was for accessibility analysis and urban planning research, and that remains my primary focus. But the analysis code in OTP is mostly prototypes or programming components that might require direct manipulation of source code to get the results you expect. I would also caution that even when minimizing travel time, OTP results will not account for variation or service frequency, and may be highly sensitive to the exact departure time chosen, which is generally not what you want for analysis purposes.

For five years or more, at least on the Conveyal side our transit and land use analysis work has entirely shifted to the R5 and Conveyal Analysis projects (https://github.com/conveyal/analysis-backend and https://github.com/conveyal/analysis-ui), with OTP shifting back toward its original role. OTP2 (currently under development) is unlikely to have any specifically analysis-oriented features, and will target trip planning for transit riders. Of course as an open source project you can always rewire it to build something different or new, but out of the box it is not expected to support these applications.

Hope this helps!

Andrew 

[James DeWeese]

Thanks so much, Andrew! This is really helpful.

Next on my list of weekend projects is to play around with the source code for OTP a bit to explore adjusting the DominanceFunction.  It's a pretty steep learning curve. The more technical, almost-programming side of things is fairly new to me. But I've been trying to get my hands dirty and train myself up so that I can work confidently to make my own projects more easily reproducible and also, hopefully, learn enough to start contributing more to the open-source community.  It's pretty unbelievable how much time folks in the transport-data community have dedicated to helping me in everything from R to python to OTP and Conveyal.  (We've actually used the cloud-based Conveyal for research at McGill and Anson has been super gracious in responding to questions).

I was actually using OTP for this project as an opportunity to ease myself into some of the configuration adjustments and scripting since I had access to a pre-compiled jar. (I actually only figured out today how to build a jar with maven). I managed to tweak some existing python script to loop through all of my origins and then evaluate the shortest path tree for all of the destinations at multi-minute increments over the morning rush hour to try and average out the sensitivity to exact departure times.  It might not have been lightning quick by comparison to purpose-designed tools, but all things considered it seemed like magic.  Way better than trying to manually calculate accessibility using Arc Network Analyst. 

After seeing some of the results--which still mostly made sense to me--and corresponding with some of the other folks on here, I could see that there was a lot more than time-minimization going on in the route selection. So, I was basically trying to more or less "trick" OTP into solely minimizing travel time by adjusting the router-config settings to level out the weighting as much as possible so that the generalized cost more or less equaled the travel time. Things like setting the walking reluctance factor to 1.  

I'll start tinkering with the OTP source code soon (and make sure to share with other users if I succeed in doing anything interesting). In the meantime, this actually inspired me to try to download, compile and run a local instance of Conveyal to see if I can figure it out. 

Anyway, thanks for the detailed explanation and for all the work you all have done on Conveyal and OTP. The tools, and the analyses that come out of them, have really made an enormous contribution to shifting the focus in transport and land-use planning toward accessibility.

-Jamie

[Andrew Byrd]

Hi Jamie,

Even if we are not planning to provide specific support for accessibility analysis in OTP2, I can see it would be useful for many people if OTP1 offered some possibility to select minimum-time routing without tinkering with the source code. It seems like the most effective or useful place for this to be available is when building shortest path trees as done with the scripting system in https://github.com/opentripplanner/OpenTripPlanner/blob/master/src/test/resources/scripts/test.py

I took a brief look at the scripting system and don't see a way to change the dominance function. I will make a Github ticket for this and hopefully someone can work out a way to default to minimizing generalized cost in special cases without hard-wiring it as it is now.

Can you clarify how you're getting your responses from OTP? You mention using Python scripts, but are you using the OTP scripting system, or just calling the OTP trip planning API from Python scripts over HTTP, or using some other approach?

Thanks,

Andrew

[Andrew Byrd]

Hi again,

I took another look at this and tracked down some older code that was used for these purposes (origin-destination travel time matrices and accessibility metrics). There is an undocumented API for making one-to-many travel time surfaces, then reading off travel times at any number of destination points. This is a weird stateful API that you'd probably never want to use on a public server - it was really intended for use by one person or a small number of people carrying out analysis work in a local setting.

You could use that API directly, or take a look at its source code in the class SurfaceResource:

https://github.com/opentripplanner/OpenTripPlanner/blob/dev-1.x/src/main/java/org/opentripplanner/api/resource/SurfaceResource.java

The methods in that class demonstrate how (in Java code) to make a shortest path tree from one origin, minimizing travel time, then read off travel times to N destinations. I can't guarantee it all still works after 5 years of various modifications, but it should be pretty close to the right approach.

I made an issue suggesting that it should be possible to create one-to-many results minimizing travel time in OTP1 (without tinkering with source code), to make sure people can still use it this way in the future, even if it's technically unsupported/unmaintained:

https://github.com/opentripplanner/OpenTripPlanner/issues/3131

Anyone who is using OTP1 in this way, please add comments on that issue explaining how you use it or difficulties you've encountered.

Thanks,

Andrew

--
You received this message because you are subscribed to the Google Groups "OpenTripPlanner Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to opentripplanner-...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/opentripplanner-users/DBB84C86-6A6F-4946-81D1-8421509E12FE%40fastmail.net.

[James DeWeese]

Thanks, Andrew! 

For this research, I'm using the OTP scripting system.  I call the script from the command line/Terminal. And the script itself is a combination of the example code you linked to https://github.com/opentripplanner/OpenTripPlanner/blob/master/src/test/resources/scripts/test.py and the code that Rafa Pereira mentioned on the list serve and has shared via a github:

* https://github.com/rafapereirabr/otp-travel-time-matrix 

* https://github.com/rafapereirabr/otp-travel-time-matrix/blob/master/python_script_loop_points_parallel.py

But I've also used two api-wrapper R packages (otpr and opentripplanner) to make calls to the OTP api for other things.

Is that what you mean?