⚡ electrical engineering

Where Should Robotaxis Operate? Strategic Network Design for Autonomous Mobility-on-Demand

This paper introduces the Autonomous Mobility-on-Demand Network Design Problem (AMoD-NDP) and a scalable column-generation algorithm to jointly optimize the selection of instrumented road subnetworks and fleet routing, demonstrating through Manhattan data how the framework balances infrastructure investment, fleet efficiency, and safety constraints for strategic AMoD planning.

Original authors: Xinling Li, Gioele Zardini

Published 2026-02-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Xinling Li, Gioele Zardini

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 a city as a giant, chaotic kitchen. Right now, everyone is cooking their own meals (driving their own cars), or hiring a chef who drives around looking for orders (Uber/Lyft). This causes traffic jams, wasted time, and pollution.

Now, imagine a future where a single, super-smart robot chef runs the entire kitchen. This is Autonomous Mobility-on-Demand (AMoD). Instead of human drivers, a central computer controls a fleet of self-driving cars.

But here's the catch: These robot cars aren't magic. They can't just drive anywhere, anytime. They need "smart roads" equipped with special sensors and digital signals to operate safely. Building these smart roads costs money, and the fleet of robots takes up time and energy.

The Big Question:
If you were the boss of this robot taxi company, how would you decide:

Which streets should get the expensive "smart" upgrades?
How many robots should you buy?
Which routes should the robots take to make the most money while keeping passengers happy and safe?

This paper, titled "Where Should Robotaxis Operate?", is a guidebook for answering those questions.

The Problem: The "Fixed Menu" Trap

Most previous research assumed the road network was fixed, like a restaurant with a menu that can't be changed. They just figured out how to move cars around on existing streets.

But in the real world, you can't upgrade every single street in New York City to be "robot-ready" overnight. It's too expensive. You have to pick the best streets to upgrade. If you pick the wrong ones, your robots get stuck in traffic or can't reach customers. If you pick too many, you run out of money.

The Solution: The "Smart Blueprint"

The authors created a new mathematical tool (a "blueprint") to solve this puzzle. Think of it like a GPS for city planners.

Here is how their tool works, using simple analogies:

1. The "Path-Based" Approach (The Recipe Book)

Instead of just looking at individual streets (links), the tool looks at entire routes (paths) from a passenger's home to their destination.

Why? Because safety rules often apply to the whole trip. For example, "No left turns allowed" or "The trip can't take longer than 20 minutes."
The Analogy: Imagine you are planning a road trip. You don't just care about the gas cost of one mile; you care about the whole journey. This tool plans the entire journey at once, ensuring it meets all safety and time rules.

2. The "Column Generation" (The Smart Waiter)

There are millions of possible routes in a city. A computer can't check every single one; it would take forever.

The Analogy: Imagine a waiter who doesn't have the whole menu memorized. Instead, they have a "Master List" of the most popular dishes. When a customer orders, the waiter checks the list. If the customer wants something new, the waiter goes to the kitchen (the "Pricing Problem") to see if a better dish can be made. If yes, they add it to the menu. If no, they stick with what they have.
In the paper: The computer starts with a few good routes. It keeps asking, "Is there a better route we missed?" If it finds one that saves money or time, it adds it. It stops when no better routes exist. This makes the math fast enough to solve for a whole city like Manhattan.

3. The "Safety Net" (Robustness)

What if it rains and traffic slows down? What if more people want rides than expected?

The Analogy: A good captain doesn't just plan for sunny weather; they plan for storms. The authors added a "Robust" mode to their tool. It assumes things might go wrong (like travel times getting longer) and designs a network that still works even in bad conditions. It's like building a bridge that can handle heavier trucks than expected, just in case.

What They Found (The Case Study)

They tested this tool on Manhattan, New York City, using real taxi data. Here are the cool things they discovered:

Less is More: You don't need to upgrade every street. The tool found that upgrading just a few key "corridors" (main arteries) was enough to serve almost everyone efficiently. It's like upgrading the main highways instead of every single driveway.
Stability: Even though traffic patterns change every day, the "best" set of streets to upgrade stayed almost the same. This means city planners can make a long-term plan and not have to panic every morning.
The Balancing Act: There is a sweet spot between Fleet Size (how many robots) and Infrastructure (how many smart streets).
- If you have too few robots, upgrading more streets doesn't help (you have no cars to drive them).
- If you have too few smart streets, adding more robots doesn't help (they get stuck in traffic).
- You need to invest in both to get the best results.
Safety vs. Profit: They tested a rule: "No left turns." Left turns are dangerous for robots.
- Result: If you ban left turns completely, the robots have to take long, winding detours. This costs more time and money, and they serve fewer people.
- Lesson: There is a trade-off. You can make the system safer by banning risky moves, but you have to accept that it will be slightly less efficient. The tool helps leaders decide exactly where that line should be drawn.

Why This Matters

This paper isn't just about math; it's about policy and planning.

For Robot Taxi Companies: It tells them exactly where to invest their money to make a profit.
For City Mayors: It helps them decide which streets to upgrade with sensors and how to regulate the number of robot cars to prevent traffic jams.

In short, this paper provides the strategic map for the future of city transportation, ensuring that when robot taxis arrive, they don't just wander aimlessly, but operate on a smart, safe, and efficient network designed specifically for them.

1. Problem Definition: The AMoD-NDP

The paper addresses a critical gap in Autonomous Mobility-on-Demand (AMoD) research: while most studies focus on fleet control (matching, rebalancing) on a fixed road network, they ignore the strategic decision of which parts of the road network to instrument for autonomous operation.

The authors formalize this as the Autonomous Mobility-on-Demand Network Design Problem (AMoD-NDP).

Objective: A centralized operator seeks to maximize system functionality (specifically, expected profit) by jointly selecting:
1. An operation subnetwork (a subset of road edges to be instrumented for AVs).
2. Fleet capacity (constrained by a fleet-time budget).
3. Passenger routing on the selected subnetwork.
Constraints:
- Infrastructure Budget: Cost to instrument edges (e.g., sensors, digital infrastructure).
- Fleet-Time Budget: Total vehicle-hours available (proxy for fleet size).
- Route-Level Quality of Service (QoS) & Risk: Constraints on specific path attributes, such as maximum travel time or limits on risky maneuvers (e.g., left turns).
- Flow Conservation: Ensuring demand is served without violating edge capacities.

Unlike traditional road network design (which assumes user equilibrium and decentralized routing) or transit design (fixed lines/schedules), the AMoD-NDP is a single-level, centralized optimization problem where the operator controls both the network topology and the routing of all vehicles and passengers.

2. Methodology

The authors propose a scalable solution framework combining a path-based Mixed-Integer Linear Programming (MILP) formulation with a Column Generation (CG) algorithm.

A. Mathematical Formulation

Path-Based Approach: To handle route-level constraints (like travel time bounds or left-turn limits), the authors move away from link-based formulations to a path-based formulation. Flows are defined over Origin-Destination (OD) paths rather than individual edges.
Challenge: The number of feasible paths is exponential, making direct enumeration impossible for city-scale networks.
Decomposition: The problem is decomposed into:
1. Master Problem (Restricted): A Linear Program (LP) optimizing over a small, restricted set of paths.
2. Pricing Problem: Identifies new paths with positive reduced costs to add to the Master Problem.

B. The Column Generation Algorithm

The core innovation is an exact algorithm for the pricing problem, which is formulated as an Elementary Shortest Path Problem with Resource Constraints (ESPRC).

Pricing Objective: Find a path $p$ that maximizes reduced cost: $rc(p) = \text{Profit}(p) - \text{DualPenalties}(\text{Time}, \text{Capacity})$ .
Algorithm Details:
- Preprocessing: Uses Dijkstra's algorithm (forward and backward) to prune nodes that cannot satisfy the travel time budget ( $T(p) \leq M_{od}$ ), significantly reducing the search space.
- Label-Correcting Search: An exact label-setting algorithm is used on the pruned graph. It maintains labels $(v, \text{cost}, \text{time}, \text{visited\_nodes})$ and uses a dominance rule to prune suboptimal paths.
- Elementarity: Ensures paths do not contain cycles (elementary paths), which is realistic for road networks.
Integer Solution: Once the CG converges to the optimal LP relaxation, the algorithm solves a restricted MILP on the generated path set to recover an integer solution (binary instrumentation decisions).
Optimality Gap: The method provides an explicit certificate of the optimality gap: $\epsilon \leq (J^*_{LP} - J^*_{IP}) / J^*_{LP}$ .

C. Robust Extension

The framework is extended to handle box uncertainty in travel times and demand:

Travel Time Uncertainty: Modeled by inflating edge travel times ( $\bar{T}(e) + \rho_e$ ) in the pricing and master problems.
Demand Uncertainty: Modeled by tightening the demand bounds ( $\bar{\alpha}_{od} - \rho_{od}$ ).
Result: The robust counterpart preserves the exact same decomposition structure, requiring only parameter updates, not algorithmic changes.

3. Key Contributions

Problem Formalization: First formal definition of the AMoD-NDP, jointly optimizing network instrumentation and fleet routing under QoS and risk constraints.
Scalable Algorithm: Development of a path-based CG algorithm tailored for city-scale networks. It solves the pricing problem exactly via a tailored label-correcting algorithm with preprocessing, avoiding the need for heuristics.
Optimality Guarantees: The method provides the exact optimal value for the LP relaxation and an explicit upper bound on the optimality gap for the integer solution.
Robustness: Demonstration that the framework naturally extends to robust optimization under uncertainty without structural changes.
Real-World Validation: Application to Manhattan, NYC, using real taxi data and OpenStreetMap networks.

4. Results (Case Study: Manhattan, NYC)

Using data from May 2024 (approx. 200k trips/day) and a network of ~4,300 nodes:

Computational Efficiency: The algorithm solved 31 daily instances (each with a 16,000 vehicle-hour fleet budget and $600k infrastructure budget) to a relative optimality gap of $<10^{-6}$ within 25 minutes.
Subnetwork Structure:
- The optimal operation subnetwork is sparse, focusing on major corridors rather than the entire grid.
- Temporal Stability: Over 90% of the edges selected in the optimal subnetwork were consistent across all 31 days, suggesting that medium-term infrastructure planning is robust to daily demand fluctuations.
Trade-off Analysis:
- Fleet vs. Infrastructure: Profitability is jointly constrained. In "Fleet-limited" regimes, more infrastructure yields no gain; in "Budget-limited" regimes, more vehicles cannot be deployed due to lack of instrumented roads.
- Capacity Saturation: When both budgets are high, performance is limited by physical road capacity.
Risk Constraints (Left Turns):
- Imposing a limit on left turns (a proxy for operational risk) significantly reduces served demand and profit when the budget is tight.
- As the "left-turn budget" increases, performance stabilizes, allowing operators to tune safety vs. profitability.

5. Significance and Impact

Strategic Planning Tool: The framework provides a decision-support tool for both AMoD operators (to determine fleet size and profitable routes) and municipalities (to evaluate infrastructure investment and regulatory policies).
Policy Implications: The results suggest that restricting AVs to a sparse, well-instrumented subnetwork can achieve near-optimal performance, reducing the need for city-wide infrastructure overhaul.
Safety Integration: The ability to incorporate path-level risk constraints (like left turns) directly into the design phase allows for the proactive management of operational safety risks.
Scalability: By proving that city-scale problems can be solved to near-optimality with explicit gap certificates, the paper moves AMoD research from theoretical simulations to practical, deployable strategic planning.

In summary, this paper bridges the gap between high-level infrastructure planning and operational fleet control, offering a mathematically rigorous and computationally efficient method to design the future of autonomous urban mobility.