Bilevel Optimization and Heuristic Algorithms for Integrating Latent Demand into the Design of Large-Scale Transit Systems

This paper introduces a bilevel optimization model (TN-DA) for designing large-scale transit networks that integrates latent demand through rider adoption behavior, and proposes five efficient heuristic algorithms that outperform exact methods in computational speed while maintaining high solution quality and key adoption properties in real-world case studies.

The Gist

Imagine you are the mayor of a bustling city, and you want to build a new, fancy public transportation system. You have a map, a budget, and a dream. But there's a catch: you don't know exactly who will actually use it.

This is the core problem the paper tackles. If you design a bus line based only on people who already take the bus, you might miss out on the thousands of people driving cars who would take the bus if it were convenient enough. But if you guess wrong and build a massive, expensive network that nobody wants, you've wasted money.

The authors call this challenge "Latent Demand." It's like a hidden treasure chest of potential riders waiting to be discovered.

Here is a simple breakdown of how the paper solves this puzzle, using some everyday analogies.

1. The Game of "You Build, They Choose" (Bilevel Optimization)

The paper describes a two-player game between the Transit Agency (the builder) and the Riders (the customers).

• Player 1 (The Builder): Wants to build a network that is cheap to run but covers as many people as possible.
• Player 2 (The Riders): Look at the new network and decide, "Is this better than my current car? If yes, I'll switch. If no, I'll stay in my car."

The tricky part is that the Builder doesn't know what the Riders will choose until the network is built. But the Riders' choices depend entirely on what the Builder builds. It's a chicken-and-egg problem.

The authors created a mathematical framework called TN-DA (Transit Network Design with Adoptions) to solve this. Think of it as a simultaneous negotiation where the builder tries to design a system that naturally attracts the hidden riders.

2. The Problem: It's Too Complicated to Solve Perfectly

If you try to calculate the perfect network where every single person's choice is predicted exactly, it's like trying to solve a Rubik's Cube while it's spinning on a treadmill. For a small city, you might do it. But for a huge city like Atlanta with millions of trips? It takes supercomputers days or weeks to find the answer, and sometimes they still can't find it.

The paper asks: "Can we find a really good answer quickly, even if it's not mathematically perfect?"

3. The Solution: Five "Smart Guessing" Algorithms

Instead of trying to solve the whole giant puzzle at once, the authors propose five heuristic algorithms. In plain English, these are "smart shortcuts" or "iterative guess-and-check" methods.

They break the problem down into two simpler steps that repeat over and over:

1. Build a Draft: Design a network assuming only a few people will use it.
2. Test the Crowd: Ask the "hidden riders," "Would you use this?"
3. Adjust: If they say "Yes," add them to the list and build a slightly better network. If they say "No," maybe tweak the route or ignore them for now.

The five algorithms are like five different chefs trying to bake the perfect cake:

• The Greedy Adders (Trip-based): These chefs start with the basic ingredients (current riders) and slowly add more potential customers one by one, checking if the cake still tastes good. They are careful not to add too many people at once.
• The Greedy Removers: These chefs start with everyone and slowly remove the people who definitely won't use the service, refining the list until it's just the right crowd.
• The Path Builders (Arc-based): Instead of focusing on people, these chefs focus on the roads. They start with a skeleton of roads and keep adding new street segments (like adding a new bridge or bus lane) that make the most difference, checking if the new roads attract more riders.

4. The "Secret Sauce": Two Golden Rules

The paper introduces two "Golden Rules" to judge if a design is good, even if we don't know the perfect answer:

1. The "No False Rejection" Rule: If a person would use the new bus line, the design must include them. If you build a network that ignores people who actually want to ride, you've failed.
2. The "No False Adoption" Rule: If you build a network for a specific group of people, those people must actually want to use it. If you build a fancy bus line for a neighborhood that hates it, you've wasted money.

The algorithms are designed to get as close to these rules as possible without needing a supercomputer.

5. The Real-World Test: Atlanta and Ann Arbor

The authors didn't just do math on paper; they tested this on real data from two cities:

• Ann Arbor/Ypsilanti (Medium City): A test run to see if the "smart guesses" could find the same answer as the "perfect calculation." Result: They did! And they did it in minutes instead of hours.
• Atlanta (Huge City): A massive test with thousands of stops and tens of thousands of trips. The "perfect calculation" method crashed or took days. The "smart guess" algorithms found a solution that was 99% as good, but in less than an hour.

They tested two types of systems:

• ODMTS: On-demand shuttles that feed into big bus/train lines (like a taxi that drops you at the train station).
• SCTS: Scooter-connected transit (using e-scooters to get to the bus stop).

The Bottom Line

This paper is a guide for city planners who are tired of waiting weeks for a computer to tell them how to build a bus system.

It says: "Don't wait for perfection. Use these smart, iterative shortcuts to build a system that is 95-99% perfect, but do it in the time it takes to drink a coffee."

By treating the design process as a game of "build, test, and adjust," and by focusing on the hidden riders (latent demand), cities can create transit systems that people actually want to use, saving money and reducing traffic congestion.

Technical Summary

Here is a detailed technical summary of the paper "Bilevel Optimization and Heuristic Algorithms for Integrating Latent Demand into the Design of Large-Scale Transit Systems."

1. Problem Definition

The paper addresses the Transit Network Design with Adoptions (TN-DA) problem. Traditional transit network design often assumes fixed demand, ignoring "latent demand"—potential riders who currently do not use public transit but might adopt it if the service quality improves. Omitting these riders during the design phase can lead to suboptimal networks that fail to attract new users or incur unnecessary costs.

The core challenge is modeling the strategic interaction between two entities with potentially conflicting objectives:

• The Transit Agency (Leader): Aims to design a network (selecting arcs/routes) that minimizes operational costs and investment while maximizing ridership.
• Latent Riders (Followers): Evaluate the proposed network based on travel time, cost, and convenience. They decide whether to adopt the new system or stick to their current mode of transport (e.g., private cars).

This interaction is formulated as a bilevel optimization problem:

• Upper Level (Leader): Optimizes the network design $z$ to minimize total system cost (investment + net cost of serving core and adopted latent riders).
• Lower Level (Follower): Determines the optimal path $\pi_r$ for each rider and their adoption decision $\delta_r$ (1 if adopted, 0 if rejected) based on a choice function $C_r$.

The choice function $C_r$ is treated as a black-box, allowing for complex modeling (e.g., machine learning or simple time-based thresholds) without requiring the optimization model to be differentiable or linear.

2. Methodology

A. The TN-DA Framework

The authors propose a generalized bilevel model where:

• Core Trips ($T_{core}$): Existing riders who are guaranteed to use the system.
• Latent Trips ($T_{latent}$): Potential riders whose adoption depends on the network design.
• Objective: Minimize $Invest(z) + \sum_{r \in T_{core}} pr \cdot \zeta_r + \sum_{r \in T_{latent}} pr \cdot \delta_r \cdot \zeta_r$, where $\zeta_r$ is the net cost (cost minus revenue) of serving trip $r$.
• Constraints: The network design must satisfy feasibility, and rider adoption is determined by $C_r(\pi_r)$.

B. Structural Properties

The paper identifies two critical properties for an optimal solution $z^*$:

1. Correct Rejection: Any latent trip not included in the design set should reject the network (i.e., they are correctly identified as non-users).
2. Correct Adoption: Any latent trip included in the design set should adopt the network.

To measure deviations from these properties, the authors introduce two metrics:

• False Rejection Rate (%Rfalse): Percentage of latent trips excluded from design that would actually adopt the system.
• False Adoption Rate (%Afalse): Percentage of latent trips included in design that would actually reject the system.

C. Heuristic Algorithms

Due to the NP-hard nature of the bilevel problem, especially for large-scale instances, the authors propose five iterative heuristic algorithms. These algorithms decompose the problem into a Transit Network Design with Fixed Demand (TN-DFD) subproblem (solving for a fixed set of trips) and an evaluation step (updating the trip set based on rider choices).

The algorithms are categorized into two types:

1. Trip-Based Iterative Algorithms:
These algorithms iteratively adjust the set of trips $\hat{T}$ considered in the TN-DFD problem.

• $\rho$-GRAD (Greedy Adoption): Starts with core trips and greedily adds latent trips that adopt the current design. It guarantees Correct Rejection ($\%R_{false} = 0$).
• $\eta$-GRRE (Greedy Rejection): Starts with a large set and greedily removes trips that reject the design. It aims for rapid approximation but does not guarantee specific adoption properties.
• $\rho$-GAGR: A hybrid approach using $\eta$-GRRE as a subroutine within $\rho$-GRAD to explore more design variations.

2. Arc-Based Iterative Algorithms:
These algorithms start with a fixed network (or empty) and incrementally add sub-networks (arcs) to improve the objective.

• arc-S1 (Arc-based Greedy): Solves TN-DFD, identifies candidate sub-networks (e.g., directed cycles), and greedily adds the one that improves the objective most. It guarantees Correct Rejection if using the "Full Adoption Expansion Rule."
• arc-S2 (Extended Arc-based): A two-phase version of arc-S1. Phase 1 expands the trip set slowly to ensure convergence; Phase 2 expands faster to refine the solution. It offers a balance between solution quality and computational time.

3. Key Contributions

1. Generalized TN-DA Framework: A flexible bilevel model that integrates latent demand and rider choice behavior (as a black-box) into transit network design, applicable to various transit modes.
2. Theoretical Properties & Metrics: Identification of "Correct Rejection" and "Correct Adoption" properties, along with the introduction of %Rfalse and %Afalse metrics to evaluate heuristic performance when optimal solutions are unavailable.
3. Five Novel Heuristic Algorithms: A suite of algorithms designed to solve large-scale instances efficiently, categorized by trip-based and arc-based strategies, with theoretical guarantees on specific adoption properties.
4. Extensive Real-World Validation: Application of the framework to two distinct, large-scale case studies using real data.

4. Results and Case Studies

The authors validated the approach on two transit systems:

Case Study 1: On-Demand Multimodal Transit Systems (ODMTS)

• Context: Integrating on-demand shuttles with fixed rail/bus networks (e.g., Atlanta, GA; Ypsilanti, MI).
• Findings:
  • Medium Instance (Ypsilanti): Heuristics found optimal or near-optimal solutions (0% gap) in minutes, whereas exact methods took hours.
  • Large/Extra-Large Instances (Atlanta): Exact algorithms and MIP-based approaches (P-Path) struggled with memory and time (taking days or failing to solve). The heuristics (specifically arc-S2 and $\rho$-GRAD) found high-quality solutions (within 0.2% - 5% of the best known bound) in under 1 hour.
  • Adoption Properties: Algorithms like arc-S1 (rule c) and $\rho$-GRAD successfully achieved 0% False Rejection Rate, ensuring no potential adopters were ignored.

Case Study 2: Scooters-Connected Transit Systems (SCTS)

• Context: Designing high-frequency bus networks connected to e-scooter services (Atlanta, GA).
• Findings:
  • The arc-based algorithms (arc-S1 and arc-S2) achieved 0% False Rejection and 0% False Adoption rates, matching the performance of the modified exact solver (P-Path) but in a fraction of the time (0.55 hours vs. 4.58 hours).
  • Trip-based algorithms were faster but resulted in higher objective values and non-zero False Rejection rates.

5. Significance

• Scalability: The proposed heuristics make it feasible to design transit networks for major metropolitan areas (millions of trips) where exact bilevel optimization is computationally intractable.
• Practical Decision Support: By providing metrics like %Rfalse and %Afalse, the paper gives transit agencies tools to balance the risk of over-designing (serving non-adopters) vs. under-designing (missing potential riders).
• Flexibility: The "black-box" choice function allows agencies to plug in sophisticated behavioral models (e.g., from machine learning) without reformulating the entire optimization problem.
• Policy Impact: The study demonstrates that integrating latent demand explicitly leads to networks that are more cost-effective and better utilized, preventing the common pitfall of designing systems that fail to attract new riders.

In conclusion, the paper successfully bridges the gap between theoretical bilevel optimization and practical large-scale transit planning, offering a robust toolkit for designing future-proof, rider-centric transit networks.