🔬 physics

Modeling Accessibility-Constrained Networks with Time-Weighted Graphs

This paper proposes a pipeline that models university campuses as time-weighted graphs using Strava data and a custom Least Resistance algorithm to identify optimal wheelchair-accessible paths and highlight critical accessibility constraints compared to standard algorithms like Dijkstra's.

Original authors: Marc Walden, Jason Liu, Ryan Liu, Hamza Khan

Published 2026-01-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marc Walden, Jason Liu, Ryan Liu, Hamza Khan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine UCLA's campus as a giant, hilly maze. For most people, it's a fun adventure with shortcuts and steep climbs. But for students in wheelchairs, this maze is full of dead ends, locked doors (stairs), and paths that are so steep they're impossible to climb.

This paper is like a team of detectives trying to map out that maze to find the easiest routes for everyone, especially those who can't use stairs. Here is how they did it, explained simply:

1. The Problem: The "Hilly Maze"

The UCLA campus is built on a very steep hill. To get around, the designers built lots of stairs and steep ramps. While this looks cool for walking, it's a nightmare for wheelchair users. Some important buildings are completely unreachable, and others require taking a huge, winding detour that takes twice as long as a normal walk.

2. The Map-Making: Two Ways to Draw the Lines

The team needed to turn the physical campus into a digital map (a network) where every intersection is a "dot" and every path is a "line." They tried two ways to build this map:

The "Human Walk" Method (Prototype): First, they just walked the paths themselves. Four team members walked every route once normally and once pretending to push a heavy wheelchair. They timed themselves.
- The Catch: Humans get tired, walk at different speeds, and make mistakes. It's like trying to measure a marathon by having one person guess the time. It's okay for a small test, but not for the whole school.
The "Digital Detective" Method (Production): For the real map, they used a smart tool called the Strava API. Think of this as a giant, public GPS logbook where millions of people have recorded their walks, runs, and rides.
- They pulled this data into a computer program that automatically drew lines for every path, even the tiny, unofficial shortcuts people use.
- The "Curved Road" Trick: A simple map might draw a path as a straight line. But in reality, paths curve over hills. To fix this, the team used a "Depth-First Search" (a computer method that explores every nook and cranny) to break every path into tiny, 5-meter segments. This allowed them to see the tiny bumps and curves that a straight line would miss.

3. The Navigation Tools: Finding the Best Route

Once they had the map, they needed a way to calculate the best route. They built two "GPS engines":

Dijkstra's Algorithm (The Classic GPS): This is the standard way computers find the shortest path. It checks every possible route from Point A to Point B and picks the one that takes the least time. It's very thorough but can be slow if the map is huge.
The "Least Resistance" Algorithm (The Energy Flow): This was their own custom invention. Imagine electricity flowing through a wire. The electricity naturally takes the path of least resistance. Their algorithm simulates this: it sends out a "voltage" that slowly gets stronger, exploring paths until it finds a connection between two points.
- Why it's cool: Unlike the classic GPS that checks every spot on the map, this one only looks at the area between the start and finish. It's like sending a scout to find a specific door rather than mapping the whole house. It's much faster for point-to-point trips.

4. The Big Discovery: The "Double Time" Penalty

When they ran the numbers, the results were stark:

The Time Gap: On average, it takes a wheelchair user almost twice as long to get between two points as a non-disabled person.
The "Stairs" Penalty: In some cases, the difference is even worse. For example, going from one building to another might take a wheelchair user 2.7 times longer because they have to take a long, winding ramp, while a walking student just takes a shortcut up a flight of stairs.
The "Dead End" Problem: Some areas, like the Northern Lights Cafe, are so hard to reach that wheelchair users have to take a massive U-turn, go to a different building, take an elevator, and come back. It's like being forced to drive around the entire city just to get to the next block.

5. The "Traffic Lights" of the Campus

The team also looked at which spots on campus are the most important "hubs." They used a measure called Betweenness Centrality, which is like counting how many people have to pass through a specific intersection to get where they are going.

They found three "Super-Hubs":

Wilson Plaza
Pauley Walk
The John Wooden Center

These are the "main arteries" of the campus. If a ramp breaks or a path gets blocked here, it causes a massive traffic jam, especially for wheelchair users who have fewer alternative routes.

6. What They Couldn't Do (Yet)

The team wanted to include exact elevation data (how high the hill is) to make the map perfect. They tried to use online tools to get this data, but the tools weren't accurate enough for their needs. So, while they know where the paths are, they couldn't perfectly calculate how steep every single inch is yet.

The Bottom Line

The team successfully built a digital model of UCLA that shows exactly how hard it is for wheelchair users to get around. They proved that the current layout forces disabled students to take much longer, more exhausting routes. By identifying the "bottlenecks" (the Super-Hubs) and the "dead ends" (areas with no ramps), they hope to give the university a clear blueprint on where to build new ramps or add signs to make the campus fair for everyone.

They also plan to take this "map-making" idea to other universities, because hilly campuses are a problem everywhere, not just at UCLA.

Technical Summary: Modeling Accessibility-Constrained Networks with Time-Weighted Graphs

Problem Statement

The University of California, Los Angeles (UCLA), situated in the hilly Westwood area, presents significant accessibility challenges for physically disabled individuals. The campus design, characterized by numerous stairs and steep slopes to accommodate the terrain, renders many integral halls and centers inaccessible to wheelchair users or forces them to take lengthy detours. With physically disabled students comprising 2.1% of the student body and an increasing number of users relying on wheeled transport (e.g., electric scooters), the need for data-driven accessibility analysis is critical. The core problem addressed is the lack of a systematic network model to quantify travel time disparities between disabled and non-disabled individuals and to identify infrastructure bottlenecks that hinder mobility.

Methodology

Data Collection and Network Construction

The authors developed a two-tiered modeling approach:

Prototype Model: A manual process involving 21 manually selected nodes (key intersections) and 43 potential paths. Accessibility was determined by visual inspection for stairs or slopes exceeding 30 degrees. Traversal times were recorded via physical walking and wheelchair simulation by team members.
Production Model: A scalable, automated pipeline utilizing the Strava Global Heatmap API and OpenStreetMap.
- Graph Generation: GPS data was imported into QGIS (WGS84 projection) to create vector line geometries. Nodes were generated at all line intersections, and vertices were added along paths to track curvature.
- Intermediate Node Integration: To capture elevation changes and curvature that straight-line approximations miss, a Depth-First Search (DFS) algorithm was employed to insert intermediate nodes along paths. A tunable parameter $c$ (set to $\approx 4.5 \times 10^{-5}$ geodesic degrees, or ~5 meters) controlled the spacing of these nodes to balance accuracy and computational cost.
- Edge Weighting: Edges represent pedestrian pathways, and nodes represent intersections. Weights are derived from traversal times, calculated based on distance, speed, and elevation.

Algorithms

Two algorithms were implemented to compute optimal paths:

Dijkstra's Algorithm: A standard implementation using a min-heap to find the shortest path in a weighted graph with non-negative edges. It computes the shortest time between a source and all other nodes, resulting in an $N \times N$ time matrix with a complexity of $O(E \log N)$ .
Least Resistance Algorithm: A custom algorithm inspired by electrical current flow (voltage). It simulates energy flow between a specific start and end pair, incrementally increasing "voltage" to explore paths until a connection is found. Unlike Dijkstra's, it does not compute distances to all nodes, making it computationally cheaper for point-to-point queries.

Accessibility Constraints and Metrics

Accessibility Definition: Paths are deemed inaccessible if they contain stairs or slopes steeper than 8% (1:12 ratio), the legal standard for wheelchair compliance.
Elevation Data: The team attempted to integrate elevation APIs (Open Maps and Open Topo) to refine slope calculations but encountered accuracy discrepancies at their operational scale. Consequently, the final model relies on the structural network and time weights, with elevation integration noted as a future refinement.
Centrality Analysis: The authors utilized Betweenness Centrality (calculated via NetworkX) to identify nodes that appear most frequently on shortest paths. This metric highlights critical bottlenecks and high-traffic hubs essential for network connectivity.

Key Results

Network Scale and Validation

The model successfully scaled from the prototype's 21 nodes to a production network of 1,290 nodes covering the entire UCLA campus. The accuracy of the Dijkstra implementation was verified by cross-referencing 100 random node pairs with the Least Resistance algorithm, yielding matching results.

Travel Time Disparities

Analysis of the time-weighted graph revealed significant inefficiencies for wheelchair users:

Average Time: The average traversal time for disabled individuals is nearly double that of non-disabled individuals.
Specific Case Studies:
- Kerckhoff Hall to Mathematical Sciences Building: Wheelchair users require a factor of 2.7x longer travel time due to winding ramps, whereas non-disabled users can utilize stairs.
- Fowler Museum to Northern Lights Cafe: Users face significant detours and U-turns due to a lack of accessible slopes, often requiring elevator use within buildings or long backtracking routes.

Centrality Findings

Betweenness centrality analysis identified three critical hubs: Wilson Plaza, Pauley Walk, and the John Wooden Center. These locations serve as essential intermediaries between residential areas (The Hill) and the academic core. The distribution of centrality values showed that a small number of nodes hold high centrality (up to ~0.175), while the majority of campus nodes have low centrality, indicating they are peripheral to main travel routes.

Significance and Contributions

The paper claims its primary contribution is a scalable pipeline that models a university campus as an accessibility-constrained network to derive quantitative insights into mobility disparities. By combining Strava data, DFS, and custom pathfinding algorithms, the authors demonstrate:

Quantifiable Inaccessibility: The model provides empirical evidence of the extra time and effort required for disabled individuals, highlighting specific infrastructure gaps (e.g., lack of ramps, reliance on elevators).
Bottleneck Identification: Centrality measures effectively pinpoint nodes where infrastructure improvements (e.g., new ramps, signage) would yield the highest reduction in travel time and disruption risk.
Engineering Framework: The pipeline is designed to support future expansion, specifically the integration of accurate elevation data to strictly enforce ADA slope compliance and the development of algorithms to propose specific engineering solutions.

The authors maintain a modest stance, acknowledging current limitations in elevation data accuracy and the absence of an automated algorithm for proposing new infrastructure designs. They position this work as a foundational step toward creating comprehensive tools for inclusive campus planning, with the potential to be applied to other universities nationwide.