Re: Increase in Travel Time upon adding additional Transit Line

[James DeWeese]

Hey, Brian, 

I ran into exactly the same situation when performing an identical analysis.  In short, it seems like that's to be expected because OTP is hardwired in a way that minimizes generalized trip cost, not strictly travel time.  Several people were kind enough to offer detailed explanations of how OTP works under the hood.  Some other folks offered helpful tweaks to the run-time configurations to try to reduce the frequency of those cases with longer travel times. With that, I got it to the point where I had very few of those seemingly counterintuitive results.  About 2,000 out of 600,000 trips.  For these, I felt comfortable simply taking the lesser of the travel times from the "old" network since logically that trip configuration still existed and was available to a would-be rider. 

I'm pasting below the various email threads so they're all in one place.  The first is from Andrew Byrd, one of the developers, who took the time to break down exactly how OTP was designed to work. See also his note about possible support for a more strictly time-based functionality.  The second set is from Francisco Jose Penarrubia, who gave me some tips on configuring the router-config.json. 

Hope this helps a little. 

Jamie 

Andrew Byrd <and...@fastmail.net>	Mon, Jun 29, 5:53 AM
to me, opentrippl...@googlegroups.com

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 

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

-----------

Francisco José Peñarrubia	Fri, Jun 26, 6:30 PM
to me, OpenTripPlanner

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.

El sáb., 27 jun. 2020 a las 0:11, James DeWeese (<jdew...@gmail.com>) escribió:

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] 

On Fri, Jun 26, 2020 at 5:00 PM Francisco José Peñarrubia <fpen...@gmail.com> wrote:

Hi James.

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

There are some of them that can produce extrange results.

Best regards.

Fran

------ 

On Sun., Jul. 19, 2020, 2:37 p.m. Brian Hill, <brian...@berkeley.edu> wrote:

Hello!

New to the group -- I was looking to measure the decreases in travel time resulting when we added a new transit line to the graph (ran with original GTFS file and an additional file), however we noticed some increases in travel time on some origin destination pairs after adding the new line.  

Is this the expected behavior of OTP?

The travel times mostly improved, it was just a few that took longer upon adding the additional transit option. 

I have provided a link to the scripts that we used, same times for both, happy to provide more information if this is not the expected behavior.

Kind regards,

Brian

https://drive.google.com/drive/folders/12P00NDslnu-wMATt1TINauz97vpCZLBX?usp=sharing

--
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/09c26b76-9b4f-42b2-98a9-8018d07df11cn%40googlegroups.com.