Fair and Efficient Investment in Public Transportation

Martin Bullinger; Edith Elkind; Kassian Köck

cs.GTFeb 3, 2026

Fair and Efficient Investment in Public Transportation

Authors: Martin Bullinger, Edith Elkind, Kassian Köck

Organizations: School of Engineering Mathematics and Technology, University of Bristol, Bristol, UK · School of Engineering, Northwestern University, Evanston, USA · School of Computation, Information and Technology, Technical University of Munich, Munich, Germany

Abstract

We study a stylized model of infrastructure investment in public transportation. In our model, each agent travels between a pair of terminals in a network captured by a weighted graph, where edge weights represent distances. The central planner can reduce the travel time along a fixed number of edges, with the goal of maximizing the utilitarian or egalitarian welfare. When there is only one agent, we provide a polynomial-time algorithm that combines Dijkstra's algorithm with a dynamic program. We then demonstrate how to use this algorithm as a subroutine to solve the problem for two agents. Generalizing this idea, we present an XP algorithm parameterized by the number of agents $n$ ; however, our problem turns out to be W[1]-hard with respect to $n$ . Nevertheless, we establish a fixed-parameter tractability result for the special case where all agents travel to a common hub. If the number of agents is variable, we obtain NP-completeness and inapproximability results. We discuss implications of our results for a related model of railway network design.

Figures & tables

Figure 1 : Illustration of the transit investment problem. The upper panel shows the original graph, the left panel depicts the shortest paths used under base cost, and the right panel demonstrates how reducing the cost on the dashed edge alters these routes.

Figure 2 : Pattern of

2

- TIP with non-empty intersection of the two shortest paths.

Problem	Results	Reference	Restrictions
1- $\texttt{TIP}^{\hskip 1.0pt\star}$	solvable in $\mathcal{O}\left(\beta m\log m+\beta\ell\right)$	Theorem 4.2
2- $\texttt{TIP}^{\hskip 1.0pt\star}$	solvable in $\mathcal{O}\left(\beta m^{2}\log m+m\beta\ell+m^{2}\beta^{2}\right)$	Theorem 4.4
$k$ - $\texttt{TIP}^{\hskip 1.0pt\star}$	solvable in $\mathcal{O}\left((2k)^{4k^{2}+4}m^{k^{2}}\beta^{3k^{2}}\right)$	Theorem 4.7
$k$ - $\texttt{{TIPH}}^{\hskip 1.0pt\star}$	solvable in $\mathcal{O}(m^{3}\beta+3^{k}m\beta^{2}+2^{k}m^{2}\beta^{2})$	Theorem 4.11
$\alpha$ - TIP ${}^{\hskip 1.0pt\star}$ -Dec	$\mathcal{NP}$ -complete	Theorem 4.13
$\alpha$ - TIP ${}^{\hskip 1.0pt\star}$ -Dec	W[1]-hard param. by number of agents and budget	Theorem 4.9

Table 1 : Summary of results. Here,

\alpha

is the discount factor,

\beta

is the budget, and

m

and

\ell

are the number of vertices and edges of the underlying graph.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3 : Illustration of instances constructed in Proposition 4.1 . The greedy algorithms yield an arbitrarily suboptimal solution.

Figure 4 : Instance for illustrating the execution of the algorithm. We display the shortest paths without (left) and with optimal (right) investment.

Figure 5 : Illustration of the reduction from SetCover to TIP for the instance

\langle\mathcal{U},\mathcal{S},2\rangle

with

\mathcal{U}=\{a,b,c,d\}

and

\mathcal{S}=\{\{a,b\},\{b,c\},\{c,d\}\}

. The left panel shows the constructed TIP instance and the right panel highlights a feasible solution corresponding to the set cover

\mathcal{S}^{\prime}=\{\{a,b\},\{c,d\}\}

. The dashed edges indicate the corresponding discounted edges.

Figure 6 : If the solution in the left panel constitutes a feasible solution, then the solution in the right panel is likewise feasible. All shortest paths passing through

y_{1}

x_{2}

can reach

t

with the same or even lower costs.

Figure 7 : Comparison of RDP and TIP : the top diagram shows the base graph; the left subfigure highlights a solution minimizing utilitarian cost in TIP (dashed edges), while the right subfigure displays the corresponding solution in RDP , where all edge weights are scaled by

\zeta=2

. The budget allows modifying exactly one edge in each case.

Explore similar work

AlphaTransit: Learning to Design City-scale Transit Routes
May 27, 2026Bibek Poudel, Sai Swaminathan, Weizi LiTransport Bringing Network Coding
Department of EECS, University of Tennessee, Knoxville, TN, USA · Department of CSE, University of California, Riverside, CA, USA
Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas
Aug 10, 2026Till FluschnikShortest Paths Road Networks
Humboldt-Universität zu Berlin, Department of Computer Science, Algorithm Engineering Group, Germany
Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learning
Jun 2, 2026Dimitris Michailidis, Sennay Ghebreab, Fernando P. SantosBringing Network Coding Neural Combinatorial Optimization
Socially Intelligent Artificial Systems University of Amsterdam

May 27, 2026, cs.AIJ/K move · Enter open · S save

AlphaTransit: Learning to Design City-scale Transit Routes

Bibek Poudel, Sai Swaminathan, Weizi Li

Department of EECS, University of Tennessee, Knoxville, TN, USA · Department of CSE, University of California, Riverside, CA, USA

Transport Bringing Network Coding Monte Carlo Tree Search

Open paper AskPDF arXiv

Designing a transit network requires many sequential route extension decisions, but their quality is often visible only after the full network is assembled. This delayed-feedback challenge lies at the heart of the Transit Route Network Design Problem (TRNDP), where route interactions can be deceptive: an extension that appears useful locally can create transfer bottlenecks, produce redundant overlap, or reduce overall throughput. To guide route construction under delayed simulator feedback, we introduce AlphaTransit, a search-based planning framework for cityscale bus network design. AlphaTransit couples Monte Carlo Tree Search (MCTS) with a neural policy-value network: the policy proposes route extensions, the value estimates downstream design quality, and search uses these predictions to refine each decision. This provides decision-time lookahead during route construction without running simulator rollouts inside the search tree. We evaluate AlphaTransit on a new Bloomington TRNDP benchmark with realistic road topology and censusderived demand, under mixed and full transit demand settings. In the Bloomington network, AlphaTransit attains the highest service rate in both demand settings, reaching 54.6% and 82.1%, respectively. Relative to reinforcement learning without search, these correspond to 9.9% and 11.4% service rate gains; relative to MCTS without learned guidance, they correspond to 2.5% and 11.2% gains. These results suggest that coupling learned guidance with MCTS is more effective than using either approach alone for transit network design. Our code and data are publicly available in https://github.com/poudel-bibek/AlphaTransit.

Abstract

Explore similar work

AlphaTransit: Learning to Design City-scale Transit Routes

Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas

Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learning