Shortest Path Tomography: A Tool for Optimizing Public Transit Networks, Phase I

Principal Investigator: Dirk Brockmann, Associate Professor, Engineering Sciences and Applied Mathematics

Center Project Number: Y6-01
Award Amount: $69,804

Start Date: February 1, 2012
End Date: November 30, 2012

The goal of the proposed project is the development of a software application for optimizing urban transit and transportation systems. The application will implement a novel network theoretic technology that: 1) interactively reveals structural features in complex urban transit and transportation networks; 2) facilitates the optimization of operation of these systems, and; 3) quantifies the effect of anticipated modifications and unexpected disruption of normal operation modes. The technology will implement algorithms recently developed in the PI’s lab that are based on network shortest path trees and shortest path tomography (SPaTo). The proposed technology seeks to improve the service planning process in transit systems. SPaTo is designed to visualize and analyze large scale network data and can extract essential and salient features in network data. It offers an interface for hands-on service planning with the goal to increase overall ridership. This technology accomplishes two general goals of network theory in applications: 1) it bridges the gap between local and global network perspectives by providing a novel view of entire transit networks from a user specified perspective, and; 2) it is designed to reveal and visualize hidden structures in complex, multi-scale and time-dependent transit networks.  The synergy of node-centric views and extraction of meaningful network substructures offers a novel technique to address some of the key questions that transit agencies are confronted with. The effect of adding/removing service to specific locations or adding and removing routes can be tested on the fly and interactively. The approach is exemplified by a key component of the technology: SPaTo provides an operational approach to plausible geographic or spatial subdivisions and transit induced effective borders that are implicitly generated by a given network, that are typically masked by the networks’ high degree of complexity, and that do not necessarily coincide with subdivisions based on administrative or census related subdivision.  Effective subdivisions can be mode-specific or time-dependent.

The anticipated software application will implement the full SPaTo-technology, starting with a prototype that is operational in the PI’s lab and has been applied to multi-scale, complex networks in various applications. The prototype will be developed to a sophisticated, scalable and platform-independent computational software application tailored for urban transportation and transit systems and in compliance with transit data specifications, e.g. GTFS. A pilot study and application benchmark will be the transportation networks operated by the Chicago Transportation Authority (CTA).

PI: Dirk Brockmann, Associate Professor, Civil and Environmental Engineering

View Project Summary (PDF)