Zhuojun Jiang, Lei Dong, Lun Wu, and Yu Liu

The complexity of navigation in cities has increased with the expansion of urban areas, creating challenging transportation problems that drive many studies on the navigability of networks. However, due to the lack of individual mobility data, large-scale empirical analysis of the wayfinder's real-world navigation is rare. Here, using 225 million subway trips from three major cities in China, we quantify navigation difficulty from an information perspective. Our results reveal that 1) people conserve a small number of repeatedly used routes, and 2) the navigation information in the sub-networks formed by those routes is much smaller than the theoretical value in the global network, suggesting that the decision cost for actual trips is significantly smaller than the theoretical upper limit found in previous studies. By modeling routing behaviors in growing networks, we show that while the global network can become difficult to navigate, navigability can be improved in sub-networks. We further present a universal linear relationship between the empirical and theoretical search information, which allows the two metrics to predict each other. Our findings demonstrate how large-scale observations can quantify real-world navigation behaviors and aid in evaluating transportation planning.

Cite: Zhuojun Jiang, Lei Dong, Lun Wu, Yu Liu, Quantifying navigation complexity in transportation networks, PNAS Nexus, 1(3), 2022, pgac126.

Data to replicate the results of the paper.

Smart card records in Beijing, Shanghai and Shenzhen. The datasets provide OD at the station level grouped by travel time (see data prepoccessing for details):

• bj_2019.csv: Beijing subway in May 2019.
• sh_2015.csv: Shanghai subway in April 2015.
• sz_2017.csv: Shenzhen subway in October 2017.

Attributes of subway lines and stations in Beijing/Shanghai/Shenzhen (by 2020):

• lines_[bj/sh/sz].csv: list of subway lines.
• stations_[bj/sh/sz].csv: list of subway stations.
• Eudist_[bj/sh/sz].csv: Euclidean distance between each station pair.

Subway/information networks of three cities from 2000 to 2020:

• PrimalGraph_[bj/sh/sz]_[yyyy].gml: the subway network of Beijing/Shanghai/Shenzhen in the year of 'yyyy'.
  • Node: each node represents a station.
  • Edge: each edge represents the subway line connecting adjacent stations.

• DualGraph_[bj/sh/sz]_[yyyy].gml: the information network of Beijing/Shanghai/Shenzhen in the year of 'yyyy'.
  • Node: each node represents a subway line.
  • Edge: each edge represents the transfer station connecting the two intersecting lines.

Usage (Python 3.7)

Import the networkx module with

>>> import networkx as nx

Import the subway network with

>>> H = nx.read_gml('PrimalGraph_bj_2019.gml')

272 subway trips with known routes and duration through questionnaires in the three studied cities.

The official published ridership of the Beijing subway for May 2019. The numbers are obtained from Beijing Subway Company’s official Weibo.

Data used to generate the figures in the paper, which is the output of the code for the paper (see gen_figures for details).

• matrix_matched_path_[bj/sh/sz]_[yyyy].pkl: the results of matched paths from Route matching. The file contains:
  • A matrix of dataframes where the dataframe of matched paths from station i to station j is stored at (i,j).

• ESI/res_stationlevel_card_[bj/sh/sz]_[yyyy].pkl: the results of the station-level empirical search information calculated based on the matched paths from Calculate the empirical search information (ESI). The file contains:
  • A dataframe of empirical search information values for all matched path in the information network
  • A dataframe of the empirical search information between station pairs

dataframe of empirical search information for matched paths

dataframe of empirical search information for station pairs

• ESI/res_linelevel_card_[bj/sh/sz]_[yyyy].pkl: the results of the line-level empirical search information calculated based on the matched paths from Calculate the empirical search information (ESI). The file contains:

  • Matrices of line-level empirical search information between line pairs with all/1/2/3 transfers on the travel paths.

• ESI/ksp_[k]_[bj/sh/sz]_[yyyy].pkl: the results of the empirical search information calculated based on the k shortest paths from Calculate the empirical search information (ESI). The file contains:

  • A matrix of station-level empirical search information values.
  • A matrix of number of subway lines taken between station pairs.
  • A matrix of travel time between station pairs.
  • A matrix of travel distance between station pairs.
  • Matrices of line-level empirical search information between line pairs with all/1/2/3 transfers.

• TSI/[bj/sh/sz]_[yyyy].pkl: the results of the theoretical search information calculated from Calculate the theoretical search information (TSI). The file contains:

  • A matrix of station-level theoretical search information values.
  • A matrix of number of subway lines on the fastest simplest path between station pairs.
  • A matrix of travel time of the fastest simplest path between station pairs.
  • A matrix of travel distance of the fastest simplest path between station pairs.
  • Matrices of line-level theoretical search information between line pairs with all/1/2/3 transfers on the fastest simplest paths.

Usage (Python 3.7)

Import the I/O functions with

>>> from iofiles import *

Import the data for figures with

>>> data = load_variable('data/output/ESI/res_stationlevel_card_bj_2019.pkl')
>>> data[0] # view the dataframe

• data_prepoccessing.sql is used to pre-process smart card data.

• route_matching.py is used to match paths from the OD records.

• ESI_from_matching.py is used to calculate the empirical search information from the matched paths.

• ESI_from_ksp.py is used to calculate the empirical search information from the k shortest paths.

• TSI.py reproduces the amount of theoretical global search information according to Gallotti et al, 2016.

• funcs.py includes the basic functions for the calculations in networks.

• iofiles.py includes the I/O functions for saving and loading files.

• gen_figures.ipynb reproduces figures in the paper.

To generate the route matching results using the provided scripts, run in the terminal:

$ python route_matching.py 

The output will be in output/.

To generate the ESI results based on the matched path from the OD records, run in the terminal:

$ python ESI_from_matching.py

The output will be in output/ESI.

When no smart card data (matched paths) are available from 2000 to 2020, the ESI of the subway networks is calculated using the k shortest paths for each year (Beijing: k=13, Shanghai: k=12, Shenzhen k=6, see paper for detail). To generate the ESI results based on the k shortest paths, run in the terminal:

$ python ESI_from_ksp.py

Reproduce the amount of theoretical global search information according to Gallotti et al, 2016.

To generate the TSI results using the provided scripts, run in the terminal:

$ python TSI.py

The output will be in output/TSI.

Contact: [email protected]