We thought it would be useful to let people know sooner rather than later about three resources that we’ve been developing as a part of this project in order to promote a broader and more in-sync understanding of dynamic transit passenger assignment:

• A glossary of terms for describing Dynamic Transit Passenger Assignment,
• Lecture notes and teaching materials, and
• Interactive tutorials using open-source software.

While not perfect nor entirely complete, we hope that they are useful to a few different audiences:

• Consultants or agencies who may be interested in dipping their toe in and seeing what is there,
• Researchers who need to coalesce around terminology, and
• Academics who may be interested in providing an introduction to the topic.

DTPA Glossary

The DTPA Glossary was developed at the suggestion of Natalia Ruiz Juri at the University of Texas at Austin Network Modeling Center. When she participated in a review of our project in 2017 she noted how much the DTA Primer had done to promote a more broad understanding of DTA. While dynamic transit passenger assignment is not nearly as far along as DTA was at the creation of the Primer, she suggested a glossary of terms as a first step towards developing a shared understanding.

Glossary Website: https://fast-trips.github.io/dtpa-glossary/

Source: MTC, PSRC, & SFCTA

It was developed collaboratively first from within the project team, then more broadly via solicitations on the TMIP listserv and ResearchGate. We welcome feedback, suggestions, corrections, contributions, and debate on the glossary and hope that it can be a common resource for the community. It is anticipated that it can grow from a glossary to a more comprehensive resource similar to the DTA Primer.

Networks Page

Source: MTC, PSRC, & SFCTA

Lecture Notes

We have a class-worth of lecture notes developed by Alireza Khani, the original FAST-TrIPs developer and an Assistant Professor at the University of Minnesota. We are in the process of developing datasets within the Fast-Trips open source dynamic transit passenger assignment model code base so that the problems and assignments can be run and analyzed in real-time. We are also going to translate the notes from PDF to a Jupyter notebook where the problems can be run from within the notes.

Tutorials

We unveiled a series of five initial tutorials at the TRB Planning Applications Conference in Raleigh, NC and hope to expand them over time. The tutorials use the open-source Fast-Trips software which can be used on any Windows, Mac or Linux computer.

We hope that these materials will be useful to the community and look forward to working with anybody who wants to help expand and improve upon them.

As we have posted about before, Dynamic Transit Passenger Assignment (DTPA) has no shortage of challenges to explore. Within this project, the Team decided to move forward with the models and frameworks that we had (despite their issues), while pursuing a separate Research Track that identified high-priority research needs in order to make DTPA useful in practice. The Project Team convened a Research Expert Panel, which undertook completed the following three steps:

1. Developed a shared understanding of issues affecting DTPA in practice (TRB Paper)
2. Conducted a literature review of relevant research in order to understand what problems had already been solved and what was outstanding
3. Identified high-priority research needs

The panel arrived at the following research needs that were also supported by the practitioners:

• Efficient and Effective Path Search Algorithms for Transit
• Service Unreliability in Schedule-Based Dynamic Transit Trip Assignment
• Empirically Valid and Computationally Efficient Transit Passenger Route Choice Model

We hope that defining and highlighting these research needs will promote an effective cycle from Practitionerville back to Academia in order to better evaluate current issues affecting transit planning.

We are looking for additional input as well as support for these high-priority research needs. We’d love your help!

• Submit your feedback on these research needs and how to fund them using the disqus comments below
• Comment on and suggest edits to the research needs statements themselves.

Many team members will be in Raleigh, NC this week as part of the TRB Planning Applications Conference and there will be several activities related to Fast-Trips to put on your calendar.

Fast-Trips Tutorial

Sunday May 14th; 3:00PM
Come learn some Fast-Trips basics. Please follow directions to download and software in advance at the GitHub Tutorial Site

Visualization Workshop

Sunday May 14th; 3:00PM
See how we are using various tools to explore the Fast-Trips calibration.
Presentation

Using Surveys for Dynamic Transit Calibration

Tuesday May 16th; 3:30PM
Learn about how we are using surveys [ and what we wish we had access to ] in our Fast-Trips calibration process. Presentation

This past Summer, the Tri-Agency Team has shifted gears away from estimating a route choice model with observed data towards and “assert and calibrate” approach. This shift was motivated by our desire to have a model ready for application at the end of this project and informed by both a more detailed review of the observed data as well as our investigation into methodological challenges of dynamic passenger route choice estimation. We are not leaving these challenges behind, but rather forking the project into two prongs so as to not put solving them on the critical path to having a model that is ready to use.

Several team members will be at the Transportation Research Board Annual Meeting presenting work completed as a part of this project. We hope to see you there!

Passenger Route Choice Challenges

Lisa Zorn will be presenting her paper titled Dynamic Passenger Assignment Challenges and she and Elizabeth will be manning the companion poster and would love to chat with people about any insights they might have towards solutions.

• Presentation Tuesday January 10th, 2017 from 1:30 to 3:15 Convention Center 156
• Poster Wednesday January 11th, 2017 from 10:15 - 12:00 in Convention Center Hall E

Making Open Data Useful

Elizabeth Sall will be manning a poster on an important, but “meta”, topic on open data standards management. Her paper is titled Making Open Transportation Data Useful and Accessible: Recommendations for Good Practices in Open Data Standards Management.

• Poster Monday January 9th, 2017 from 1:30 to 3:15 in Convention Center Hall E

We look forward to discussing these topics and more with many of you there.

What is a hyperpath, anyway?

Over the past few months, our team has spent a lot of time exploring the methods in the existing Fast-Trips software.  The more we run the software with various examples, the more questions we had about how exactly the algorithm works as written in code (which is slightly different from published papers), so we thought we would document what the algorithm actually does in this blog post.

Let’s start with the literature.

Nguyen, S., S. Pallottino, and M. Gendreau, 1998

For any given destination, a strategy specifies a set of attractive lines for every stop and an alighting stop for every line that may be boarded when traveling toward that destination, and a hyperpathis the unique acyclic support graph of a strategy.” ( )

Khani, A., M. Hickman, and H. Noh, 2015

A hyperpath, as defined by Nguyen and Pallottino 1988, is an acyclic subnetwork with at least one link connecting the origin to the destination, and where at each node, there are probabilities for choosing the alternative links.”

I still find this a bit confusing, so let’s start with a visualization (based on Figure 5 from Khani et al 2015):

Are you enjoying running Fast-Trips on the small test network but ready for a “big time” network? Today is your lucky day.

The general approach to creating networks is to take the travel demand model networks that each agency already produces and add information to them to create a schedule-based network as required by our GTFS-PLUS network specification [ and discussed in this blog post ].

We have transit demand – a version of it, anyway. I started with a script that Lisa Zorn developed back in 2012 when she and Alireza Khani worked on the paper Integration of the FAST-TrIPs Person-Based Dynamic Transit Assignment Model, the SF-CHAMP Regional Activity-Based Travel Demand Model, and San Francisco’s Citywide Dynamic Traffic Assignment Model. The script currently does two things: reformats the data, and assigns disaggregated preferred departure and arrival times. In the future, it may combine data from other sources and perform minimal variable synthesis.

Good news – we just put up some instructions and sample data for you run Fast-Trips at home!

The basic requirements are:

• Anaconda ( or equivalent ) installation of Python
• Microsoft Visual C++ Compiler for Python 2.7 (e.g. for Windows )
• TransitFeed for reading GTFS data

We have included a small, five-zone test network [ located in the subdirectory \Examples\test_network ] to facilitate tinkering with and testing various features before instituting a full-scale run.

Small Test Network

Source: MTC, PSRC, & SFCTA

Nothing is perfect, but we would love to know what you think! Please submit issues to our GitHub Issue Tracker. The more people who try it out now, the better and more usable it will be later.

Over the past few months, we have made substantial progress on our standards, the network preparation, and the Fast-Trips software itself. Paperwork has delayed some of our progress in the Travel Behavior task, but that is now behind us and we can push on. Here is a brief summary of a few of the things we have been working on.

Evolution of Standards

We have iterated some on our standards, and updated all of our tools to use them.

Network Standard

• Biggest pain is still the fares, which have changed slightly as we have worked through the various fare types in each region and realized that there were too many exceptions to our simplifications.
• The biggest changes to the standard are to decrease ambiguity.

Demand Standard

• Has remained more constant.

Network Creation

We have substantively completed the code to do the network creation process for Fast-Trips on the fly from within SoundCast and SF-CHAMP.

We have a number of data standards that we are creating as a part of this project (see my previous post about the development of a few). As we progress in the project, we realize that the standards will evolve and need to be updated. As good little developers, we knew that we needed to start version controlling the data standard as well as the software that uses it. You can see the finished result of a version-controlled standard on GithHub, but if you are interested in the journey to get there, read-on!

Starting

We started with using different saved copies of the memo that described the standard:

Network Standard v0.1.pdf
Network Standard v0.2.pdf
Network Standard v0.3.pdf

While sufficient, there are a number of obvious drawbacks with this approach. Most notably, is that in order to see the differences between versions you have to compare each entire PDF document. Even if we were to include a changelog, it would require somebody to cycle through multiple documents if they wanted to understand differences between multiple versions.

What are others doing?

I did some online research to find out how other data standards are controlled and found a variety of examples, which are described below.

Google and GTFS

Google does keep a record of the changes they have made to the GTFS specification but does not assign each change a unique version number or track it in any other way than a change-log. While the specification is very openly “not set in stone”, one of the guiding principles for changes is that they should be backward compatible.

The following is a brief update on the overall status of the Fast-Trips implementation project.

The Tri-Agency group implementing Fast-Trips has been making significant technical progress on: software development, data standards, network development, demand evaluation, and evaluating route choice methodology. In administrative news, Mark Simonson has joined the Management Team from PSRC and Jeff Hood has joined from our consultant bench in order to take a lead on the route choice estimation task.

In software development, we have completed a refactoring of Fast-Trips to Python and fixed many bugs along the way. In order to have a tolerable run time (<6 hours), we:

• vectorized some of the operations so they could be completed in Pandas data frames;
• instituted multi-processing for the path-building; and
• used a C++ extension for loops that could not be vectorized.

Representing a 40X speedup in itself, the C++ extension is as generalized as possible in order to keep all the day-to-day and month-to-month control within the much more usable and legible Python. The next step is to do feature development on modal biases and selections and then to optimize for skimming procedures.

In data standards, we have developed both a transit network data standard that is an extension of GTFS (the most complex part being fare representation) and a demand data standard](/library/T3-TransitDemandData-WorkingCopy-July2015.pdf) that will work equally well for auxiliary and activity-based demand.
The networks team has moved on to develop Python code to create the networks from both EMME/SoundCast and SF-CHAMP/Network Wrangler using agreed upon methodology for translating headways to schedules, while the demand team is finalizing methodology to adjust our demand that we will use for route choice estimation based on the GPS data from the California Household Travel Survey, On-Board Surveys, and Automated Passenger Counter data.

Not far behind, the route choice team completed a draft literature review and is evaluating various possible methodologies while they await some contracting hurdles to pass and data availability milestones to be reached by other parts of the team.

The goal is to have all task teams converge at a mid-October time point and be able to begin route choice model estimation.

In my previous post, I unveiled the size of our “performance problem” for Fast-Trips and discussed various ways that we had and were planning on attacking it. I had already made some speed ups by using the multi-processing for pathfinding (while making sure the random number seeds that were used were unaffected), but the big question mark was if a c++ extension would make a big-enough dent into our run time to be tolerable enough to run in at least a “development mode”.

I spent the past two weeks creating, testing, and documenting the c++ extension and am happy to say that when combined with the multi-processing across 64 cores (reasonable for our case), the projected runtime will be four hours (as opposed to four weeks/months). The c extension alone represented a 40x processing speedup.

Phew!

Next up:

• explore allowing non-additive costs in path search
• improve usability and parameterizing the c-extension
• input/output reading and writing for new Fast-Trips data standards
• allow modal biases / selectivity

There were two main sets of interim deliverables that we assigned to ourselves to complete fairly early on:

1. detailed methodology development and planning (after we had read all the literature, etc. ) and
2. data standards that would enable us to use the same tools and talk the same lingo.

This update discusses data standards (and our lack thereof). Our task was to find a common way for Fast-Trips to be able to interact with our three model systems: SF-CHAMP (SFCTA), SoundCast (PSRC) and Travel Model One (MTC).

Standards everywhere you look

First, let’s talk about the standards that we already have, use, or will use as a part of this project at PSRC, MTC and SFCTA:

• OMX for skim matrices and aggregate demand files (i.e. visitor travel)
• Cube Networks:
  • .NET highway, bike, and pedestrian network files
  • .lin and .link transit network and service files
  • .access, .zac, .xfer, and .pnr SF-CHAMP network wrangler files
• EMME data bank
• APC data dumps
• GTFS schedule based transit service
• HDF5 disaggregate demand files

Clearly that is a lot to consider and we were hesitant to add even more standards to the mix.
We could have opted to code a lot of flexibility into Fast-Trips itself and have it accept a wide variety of inputs, or we could standardize the input that it was expecting and use outside forces to commandeer the variety of data we needed into that standard. We chose the latter approach, not just because of the sheer variety of formats, but also the variety in how those formats are used at each agency. For example, while MTC and SFCTA both use Cube, the data that they include within their Cube networks varies, and some common data elements use different units as well.

Where a Fast-Trips data standard fits in

Our chosen approach for dealing with the varying input data is shown in the figure below.
The blue items on the left represent the unique standards and uses for each individual agency along with the variety of data that might be available in each region. The green boxes in the middle represent the “glue code” that Tasks 2 and 3 (Networks and Demand) are responsible for developing alongside Task 8 (Implementation). The scripts that glue the individual model data to the Fast-Trips standard will make use of a shared library that has a standard set of writing methods and checks. The grey box, represents the network and demand standard that Fast-Trips will be reading in. The read methods for Fast-Trips will be developed as a part of Task 6 (Software Development). The next step was to agree upon the format that the scripts would write and that Fast-Trips would read so that they would be aligned with each other.

Input Data Flow

Source: MTC, PSRC, & SFCTA

The Good!

Translating Fast-Trips from C++ to Python turned out to be a fairly straight forward task. I completed the straight translation within a few weeks, fixed a few bugs in the C++ version, and verified that the Python results were producing the same output as the fixed C++ version.

Voila, a working version of Fast-Trips in Python!

The Bad…

We had always expected Python to not be as fast as C++, but did not anticipate just how many orders of magnitude slower it would be. I have been using a test batch of 121,000 riders in the San Francisco Muni network to test Fast-Trips, which I used to calculate the run times in the image below.

Comparison of Python and C++ Run Times

Source: MTC, PSRC, & SFCTA

Out of the box, Python was over 20 times slower. However, in order to satisfy our target performance of six hours (for the entire Bay Area…which has several million transit trips per day) we would need to get to a point where Fast-Trips was running much faster than the C++ version.

scary numbers:

• Performance Target for Bay Area: 6 hours
• Initial Python Fast-Trips Performance (estimated): 1,666 hours
• Needed speedup: 300X

Undaunted, we plowed ahead with the search for 300X worth of performance improvements.

When our agencies (MTC, SFCTA, and PSRC) were in the early stages of discussing a potential collaboration between us, there were three primary themes that we were all in agreement on:

1. using this money for its intended purpose: implementing a planning-ready dynamic network model within a public agency, that is useful and capable of answering important and relevant questions;
2. making the implementation sustainable from a staffing and operations point of view, so that the investment isn’t lost a few years later; and
3. sharing the knowledge of what we learn about the viability and issues surrounding implementation of dynamic network models with agencies which weren’t lucky enough to win this grant (or weren’t ready to apply) and with academics and funders.

This post discusses our third pillar: communications.

Target Groups

We want to reach out to, learn from, and also disseminate information to three groups: academics, technical practitioners, and planners/managers. I should emphasize that we seek to both gain information from these sources as well as disseminate it to them.

A question we understandably get a lot is what is so different about Fast-Trips compared to what you do now? The generic answer [ for most model development projects] is that it helps us answer important questions relevant to planners and decision-makers that we can’t answer now. Realizing that the lack of specificity in this response leaves a little to be desired, we thought we would dedicate a post to diving a little deeper:

• what are the specific features that differentiate it from the conventional process?
• what questions will in answer?

Promising Characteristics of Fast-Trips

1 - Heterogeneity of riders.

What does that really mean?

Fast-Trips uses simulation, which enables it to consider the spectrum of unique combinations of why riders might choose one route over another. It has the ability to know that some riders might prefer shorter walking distances and seats while others will prefer the fastest possible route.

Fast-Trips doesn't assume that everybody is average.

Source: MTC, PSRC, & SFCTA

Furthermore, rather than grouping every individual into a category (“market segment”) that chooses based on the average desire of the people in that category (i.e. all the speed-demons will pick the 38L despite there not being any seats), Fast-Trips has the ability to understand that “speedy” is relative - and that some speed-demons are more speed-driven than others (i.e. some might be okay with a trip that is a minute slower, but where you can get a seat to read your book.

When the Federal Highway Administration released this grant opportunity, they limited the scope of work in the proposal to less than one page. With such a big undertaking, we knew that our first order of business after getting the contracting in place would be to update the workplan with enough detail so that everybody was on the same page, but enough freedom to allow for innovation along the way.

While you can read the whole workplan, I thought it would be interesting to highlight a few interesting (from our perspective) components.

Tasks led by agency staff

Agency staff are task-leaders and managers. Not only are those who are closest to the problem most likely closest to the solution, but agency staff are more likely to develop solutions that work best in the public agency environment and workflow. We are lucky to have a strong cadre of innovative and motivated staff working on this project, but just in case they need help being pointed in the right direction, they can ask for the help of the technical lead or others on the team.

Defined group decision-making process

Since we are a large group coming from different backgrounds and implementation environments, we thought it was important at the outset to define how we would make decisions as a team. The process we agreed on was as follows:

• Identify important decisions at the get-go and tag them (i.e. transit network data standard)
• Task-leader is responsible for educating and consulting with the technical team on relevant background research, the pros and cons of potential options, and a proposed direction.
• Once any concerns from the technical team are ironed out, send a revised proposal to the management team for approval

Federal Highways requested that we measure our performance on this project, including both monitoring our progress along the way (Are we on track?) and identifying the results of our efforts (How did it work out?). This post summarizes the performance measures that we selected.

Considerations

We wanted metrics that would tie to both outputs (did we do X?) and outcomes (did our work make a difference in Y?) for three categories:

• Tool implementation and deployment
• Capacity building and partnerships
• Technology transfer / research dissemination

We wanted to use metrics that lend themselves to a definitive and objective answer (i.e. yes, no, 1, 9, 33, etc)

We wanted to be able to conduct the evaluation without a significant amount of effort (since this request was added after we had done our budget)

Never underestimate the benefit of compromising in the name of collaboration. This is a favorite saying of mine. The benefits of collaborating across agencies are so tempting: learning from your peers, building a more sustainable product, sharing risk. But the downsides are very real: you must compromise – on big, important decisions. This is difficult for program managers, like myself, who are used to steering projects – not co-steering projects.

In this post I talk a bit about what we’ve learned to date on the Fast-Trips project. I hope my words help at least one peer agency out there in a similar position.

Why did we decide to collaborate?

A pre-condition for successful collaboration is proper motivation. Our key reasons are as follows:

1. Each agency brings a unique and useful perspective, specifically:
   • SFCTA brings experience with dynamic network models generally and Fast-Trips specifically. They also operate in a jurisdiction with very real transit crowding problems.
   • MTC is a large, sophisticated MPO, with top-notch in-house contracting, legal, and travel modeling staff. Further, we want to better leverage travel model research done by SFCTA for the benefit of our region.
   • PSRC brings software expertise, a talented, diverse staff, and, of course, a non-Bay-Area-perspective.
   • University of Texas Network Modeling Center brings a key collaborator from the original Fast-Trips development work and a deep reserve of transportation research skills.
2. Shared risk: I often say that MPO modelers should not do anything they cannot convince two of their peers to go along with. Convincing others should prevent unwise investment decisions.
3. Shared contingency: things come up at public agencies, diverting resources from planned activities. We hope at least two of us will be fully engaged with the project at any given time.
4. More eyeballs: generally speaking, the more eyeballs you put on something, the more likely you are to find errors and improve ideas.
5. Peer-to-peer learning: we work in a small community and need to take every opportunity we can to learn from each other. Working directly with each other is more rewarding than listening to each other talk at conferences.