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

# Smart Transportation Without Neurons - Fair Metro Network Expansion with Tabular Reinforcement Learning
Source: [https://arxiv.org/html/2606.04167](https://arxiv.org/html/2606.04167)
Dimitris Michailidis, Sennay Ghebreab, Fernando P\. Santos Socially Intelligent Artificial Systems University of Amsterdam \{d\.michailidis, s\.ghebreab, f\.p\.santos\}@uva\.nl

###### Abstract

We tackle the Metro Network Expansion Problem \(MNEP\), a subset of the Transport Network Design Problem \(TNDP\), which focuses on expanding metro systems to satisfy travel demand\. Traditional methods rely on exact and heuristic approaches that require expert\-defined constraints to reduce the search space\. Recently, deep reinforcement learning \(Deep RL\) has emerged due to its effectiveness in complex sequential decision\-making processes — it remains, however, computationally expensive, environmentally costly and requires additional engineering to interpret\. We show that MNEP problems are small enough to not require Deep RL methods\. Reformulating the MNEP as a Non\-Markovian Rewards Decision Process \(NMRDP\), we use tabular RL to achieve similar performance with significantly fewer training episodes, additionally offering greater interpretability\. Additionally, we incorporate social equity criteria into the reward functions, focusing on efficiency and fairness, highlighting the versatility of our method\. Evaluated in real\-world settings — Xi’an and Amsterdam — our method reduces total episodes by a factor of 18 and total carbon emissions by a factor of 12 on average, while remaining competitive with Deep RL\. This approach offers a replicable, modular, interpretable, and resource\-efficient solution with potential applications to other combinatorial optimization problems\.

*K*eywordsOptimization and Control⋅\\cdotReinforcement Learning⋅\\cdotPublic Transportation⋅\\cdotMetro Networks

## 1Introduction

Public transport is fundamental to modern, fast\-paced lifestyles, as it enables citizens to participate in employment, education, healthcare, and social activities\[[30](https://arxiv.org/html/2606.04167#bib.bib19)\]\. However, planning public transport networks is especially challenging due to physical, social, economic and legal constraints that complicate the creation of new transport routes, or the expansion of existing ones\. Sustainability and equity have become critical considerations in network design, requiring systems to be both accessible by serving diverse populations regardless of location, socioeconomic status, or age, and efficient\. Inefficient systems, such as underutilized buses, can result in higher per\-passenger emissions than private vehicles\[[29](https://arxiv.org/html/2606.04167#bib.bib50)\], while low ridership may degrade service quality over time\[[33](https://arxiv.org/html/2606.04167#bib.bib56)\]\. These trade\-offs introduce complexity into transport planning, making data\-driven and adaptive solutions imperative\.

The Transport Network Design Problem \(TNDP\) is an NP\-hard combinatorial optimization problem focused on designing public transport systems to maximize travel demand satisfaction\[[16](https://arxiv.org/html/2606.04167#bib.bib1)\]\. For metro systems, this challenge is addressed through the Metro Network Expansion Problem \(MNEP\), which specifically targets the expansion of existing metro lines in urban environments\[[53](https://arxiv.org/html/2606.04167#bib.bib2),[51](https://arxiv.org/html/2606.04167#bib.bib67),[46](https://arxiv.org/html/2606.04167#bib.bib60)\]\. Metro networks play a critical role in modern cities due to their speed, reliability, and high passenger capacity, outperforming traditional public transport modes\[[51](https://arxiv.org/html/2606.04167#bib.bib67)\]\. Metro lines generally cover long distances, cross multiple urban zones, and are typically designed as relatively straight routes without excessive meandering\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\]\. As a distinct sub\-problem within TNDP, MNEP introduces additional constraints specific to metro network design\.

Traditionally, TNDP problems have been approached with integer optimization and heuristic algorithms\[[28](https://arxiv.org/html/2606.04167#bib.bib22),[37](https://arxiv.org/html/2606.04167#bib.bib6)\], which require extensive expert\-defined constraints to reduce the search space for tractability\. Recently, the Metro Network Expansion Problem \(MNEP\) has been framed as a sequential decision\-making problem, leveraging Reinforcement Learning \(RL\) to derive optimal solutions\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\]\. RL is well\-suited for sequential decision\-making with multiple objectives, such as efficiency and fairness, and has been successfully applied to combinatorial optimization problems\[[11](https://arxiv.org/html/2606.04167#bib.bib29),[42](https://arxiv.org/html/2606.04167#bib.bib10),[23](https://arxiv.org/html/2606.04167#bib.bib65)\]\. Unlike traditional methods, RL can explore the search space flexibly by optimizing a reward function, avoiding the need for exponentially increasing constraints\.

Given the large state\-action spaces in many problems, the complexity of Reinforcement Learning \(RL\) may seem justified\. Recently, Deep Reinforcement Learning \(Deep RL\) has shown promise in scaling combinatorial optimization, learning policy representations that autonomously identify key features and achieving state\-of\-the\-art results in real\-world problems\[[31](https://arxiv.org/html/2606.04167#bib.bib26),[36](https://arxiv.org/html/2606.04167#bib.bib46),[54](https://arxiv.org/html/2606.04167#bib.bib47)\]\.

While advances in computing power and algorithmic research suggest that RL could transform problems like MNEP, we argue that Deep RL is not always the ideal solution\. Its substantial training time and environmental costs are becoming increasingly significant with the widespread deployment of AI systems\[[3](https://arxiv.org/html/2606.04167#bib.bib71),[45](https://arxiv.org/html/2606.04167#bib.bib69),[38](https://arxiv.org/html/2606.04167#bib.bib70),[25](https://arxiv.org/html/2606.04167#bib.bib72)\]\. Although MNEPs involve complex solution spaces, they are fundamentally static optimization problems with limited input features\. Their scalability is inherently constrained—metro lines are typically spaced 1–3 kilometers apart\[[19](https://arxiv.org/html/2606.04167#bib.bib76)\]and are restricted in placement, shape, and other design factors\. Complex neural network structures, which excel at capturing complex patterns in high\-dimensional feature spaces, may not therefore be necessary for effective policy training\. This is supported by findings in other machine learning domains\[[8](https://arxiv.org/html/2606.04167#bib.bib68)\]\.

In this paper, we argue that traditional RL methods can effectively tackle complex problems like MNEP when properly framed\. We demonstrate that a tabular approach achieves competitive performance against deep\-learning methods while significantly reducing training time in two real\-world environments \(Xi’an and Amsterdam\)\. Additionally, our new formulation, in combination with tabular RL, offers greater interpretability than black\-box deep\-learning models\.

To further showcase the potential of tabular RL, we explore social equity in MNEP by incorporating diverse reward functions based on various notions of social good\. We extend the state\-of\-the\-art RL formulation of MNEP to integrate fairness criteria\. Our key contributions are the following: we reformulate the Transport Network Design and Metro Network Expansion problems as Non\-Markovian Reward Decision Processes, significantly reducing the state\-action space\. We bridge machine learning and transport planning research by extending the RL framework to integrate considerations of social good, with both efficiency and fairness\-based objectives\. We propose a Monte Carlo Tabular Reinforcement Learning algorithm for MNEP, designed to require fewer training episodes than deep learning models\. We validate our method in two real\-world settings—Xi’an, China, and Amsterdam, Netherlands—demonstrating comparable performance to state\-of\-the\-art Deep RL methods, with an 18\-fold reduction in training episodes and a 12\-fold reduction in CO2emissions\. We provide all code, datasets, and hyperparameter settings to replicate our results and enable application to other combinatorial optimization problems111Github: https://github\.com/dimichai/tabular\-tndp\. The remainder of the paper is structured as follows: First, we position our work in the context of previous research \([Section˜2](https://arxiv.org/html/2606.04167#S2)\) and re\-formulate the MNEP \([Section˜3](https://arxiv.org/html/2606.04167#S3)\)\. We continue by describing the tabular model and the proposed social\-welfare reward functions \([Section˜4](https://arxiv.org/html/2606.04167#S4)\) and the real\-world environments used in our experiments \([Section˜5](https://arxiv.org/html/2606.04167#S5)\)\. Finally, we present and discuss our results \([Section˜6](https://arxiv.org/html/2606.04167#S6)\)\.

## 2Related Work

We outline previous work on the TNDP, reinforcement learning for combinatorial optimization, and the analysis of fairness in transportation\.

### 2\.1Transport Network Design Problem

Traditionally, the Transport Network Design Problem \(TNDP\) has been approached through a combination of integer optimization techniques and heuristic methods, including the use of pre\-defined or dynamically discovered corridors\[[28](https://arxiv.org/html/2606.04167#bib.bib22),[57](https://arxiv.org/html/2606.04167#bib.bib63),[21](https://arxiv.org/html/2606.04167#bib.bib3)\], simulated annealing\[[15](https://arxiv.org/html/2606.04167#bib.bib4),[1](https://arxiv.org/html/2606.04167#bib.bib23)\], bee colony optimization\[[56](https://arxiv.org/html/2606.04167#bib.bib61),[47](https://arxiv.org/html/2606.04167#bib.bib5)\], and genetic algorithms\[[37](https://arxiv.org/html/2606.04167#bib.bib6),[34](https://arxiv.org/html/2606.04167#bib.bib64)\]\.

While these approaches have produced promising results in early studies, they have notable limitations\. To make the problem tractable, they restrict the search space by either enforcing a long list of environment\-specific constraints or by setting a predefined set of corridors\. This restriction provides obstacles in application in large, real\-world urban environments with diverse characteristics\. More critically, narrowing the search space in this manner can exclude high\-quality solutions that lie outside of these constraints\.

### 2\.2Reinforcement Learning for Transport Network Design

Reinforcement Learning \(RL\) has proven effective for optimal long\-term sequential decisions\. Through straightforward reward mechanisms, an agent learns to understand its impact on the environment via trial\-and\-error, making RL well\-suited for tackling real\-world NP\-hard combinatorial optimization tasks by leveraging demonstration and experience, without the need for expert prior knowledge\[[31](https://arxiv.org/html/2606.04167#bib.bib26),[52](https://arxiv.org/html/2606.04167#bib.bib48),[6](https://arxiv.org/html/2606.04167#bib.bib51),[23](https://arxiv.org/html/2606.04167#bib.bib65),[10](https://arxiv.org/html/2606.04167#bib.bib73)\]\. Although combinatorial optimization problems can also be approached with Supervised Learning \(SL\), recent studies have shown that RL can generalize more effectively than SL in common problems such as the Travelling Salesman Problem\[[5](https://arxiv.org/html/2606.04167#bib.bib7),[13](https://arxiv.org/html/2606.04167#bib.bib27)\]and Vehicle Routing\[[35](https://arxiv.org/html/2606.04167#bib.bib12),[24](https://arxiv.org/html/2606.04167#bib.bib18)\]\.

Despite the growing utility of RL in combinatorial optimization, its application to transport network design has only recently gained attention\.\[[11](https://arxiv.org/html/2606.04167#bib.bib29)\]employed a policy gradient method to design bus lines, exploring the Pareto front between customer satisfaction and operational costs\. Similarly,\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\]used a pointer\-based model to address the Transit Network Design Problem \(TNDP\), demonstrating superior performance in demand satisfaction\. More recently,\[[2](https://arxiv.org/html/2606.04167#bib.bib74)\]integrated Graph Neural Networks with a Monte Carlo Tree Search \(MCTS\) algorithm, leveraging network connectivity to enhance feature learning\.\[[9](https://arxiv.org/html/2606.04167#bib.bib75)\]also applied MCTS for graph expansion in existing metro networks, albeit without directly addressing the MNEP\. Furthermore, Multi\-objective Reinforcement Learning has been used in TNDP to balance efficiency with accessibility\[[58](https://arxiv.org/html/2606.04167#bib.bib62),[32](https://arxiv.org/html/2606.04167#bib.bib66)\]\.

Most work on the Transit Network Design Problem \(TNDP\) and the closely related Metro Network Expansion Problem \(MNEP\) has focused on complex deep reinforcement learning \(Deep RL\) models\. This paper, however, challenges the necessity of such black\-box models for problems where interpretability is crucial for decision\-makers\. We reformulate the problem to significantly reduce the action space without restricting the solution space, enabling a simpler, Monte Carlo\-based tabular reinforcement learning approach\. Our method is then benchmarked against the state\-of\-the\-art Deep RL approach for MNEP\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\]\.

### 2\.3Social Equity in Transport Network Design

Adopting notions of social equity in transport network design is challenging to optimize due to its multi\-dimensional nature\[[4](https://arxiv.org/html/2606.04167#bib.bib9)\]and the inherent moral judgments involved\[[50](https://arxiv.org/html/2606.04167#bib.bib40)\]\. Drawing on prior research in urban transport, we identify three key decisions necessary to incorporate fairness: utility measure, dimension, and fairness theory\.

Utility measure:This is commonly achieved by establishing accessibility metrics, such as the number of reachable opportunities\[[39](https://arxiv.org/html/2606.04167#bib.bib31),[49](https://arxiv.org/html/2606.04167#bib.bib32),[22](https://arxiv.org/html/2606.04167#bib.bib36)\], the affordability of accessing them\[[17](https://arxiv.org/html/2606.04167#bib.bib38)\], or a combination of both\[[14](https://arxiv.org/html/2606.04167#bib.bib39)\]\.

Dimension:Fairness can be assessed along spatial dimensions, where disparities are evaluated across different geographic or administrative units\[[39](https://arxiv.org/html/2606.04167#bib.bib31),[12](https://arxiv.org/html/2606.04167#bib.bib35)\], or through group\-based measures, where groups are defined by socio\-economic characteristics \(e\.g\., income, race\)\[[49](https://arxiv.org/html/2606.04167#bib.bib32),[40](https://arxiv.org/html/2606.04167#bib.bib33),[7](https://arxiv.org/html/2606.04167#bib.bib34)\]\.

Fairness theory:Multiple theories of fairness and equity inform transport network design\[[4](https://arxiv.org/html/2606.04167#bib.bib9)\]\. Most approaches fall under horizontal fairness—aiming for equal utility across all units or groups—or vertical fairness, which prioritizes groups or areas in greater need\[[50](https://arxiv.org/html/2606.04167#bib.bib40)\]\.

Despite these theoretical analyses, comprehensive application of fairness frameworks within machine learning for TNDP remains limited\. Nonetheless, prior work has made initial attempts to integrate equity considerations\. For example,\[[41](https://arxiv.org/html/2606.04167#bib.bib41)\]explore the efficiency\-equity trade\-off in graph augmentation using RL, applying their approach to Chicago’s transport network\[[41](https://arxiv.org/html/2606.04167#bib.bib41)\]\.\[[48](https://arxiv.org/html/2606.04167#bib.bib30)\]compare bus line designs for advantaged and disadvantaged groups, though not using RL\[[48](https://arxiv.org/html/2606.04167#bib.bib30)\]\.\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\]account for equity by designing a weighted reward that balances travel demand with an area’s development index, though this measure is implemented within the reward function and analyzed only minimally for its impact\. The same approach is used by\[[58](https://arxiv.org/html/2606.04167#bib.bib62)\], who add one more component to the reward function\.

Our paper presents the first attempt to bridge the gap between transport fairness research and RL\-based transport network design in a comprehensive framework\. We design fairness\-based rewards based on\[[4](https://arxiv.org/html/2606.04167#bib.bib9)\]definition, which targets an equitable distribution of benefits introduced by new transport lines\. This framework is adaptable to various utility measures; in this study, we focus on Origin\-Destination flows due to their relevance for mobility demand, rather than accessibility\. Our analysis is done on a socio\-economic group dimension, and we provide diverse reward functions that cover different fairness notions\.

![Refer to caption](https://arxiv.org/html/2606.04167v1/img/xian_ams_env.png)

Figure 1:Two real\-world case studies where the Metro Network Expansion Problem \(MNEP\) can be applied\. The left side features Amsterdam, Netherlands, with each grid cell representing aggregate origin\-destination demand \(visualized using a blue colormap in panel A\), along with the city’s existing metro lines and housing price quintiles \(panel B\)\. On the right, similar data is displayed for Xi’an, China\.

## 3The Metro Network Expansion Problem

The Metro Network Expansion Problem \(MNEP\) is a subproblem of the Transport Network Design Problem \(TNDP\)\. Within the TNDP framework, the main objective is to expand the transport network by constructing a new line that maximizes the captured travel demand left unmet by the existing network\.

In traditional formulations of TNDP and MNEP, the city is modeled as a two\-dimensional grid environment withnnrows andmmcolumns,Hn×mH^\{n\\times m\}\. The aim is to identify a set of adjacent cellsZ=\{z1,z2,…,zT∣zi∈H,∀i=1,2,…,T\}Z=\\\{z\_\{1\},z\_\{2\},\\ldots,z\_\{T\}\\mid z\_\{i\}\\in H,\\,\\forall i=1,2,\\ldots,T\\\}, which sequentially connect to form a new metro line, in order to maximize the total captured demand\. This demand is represented by an Origin\-Destination \(OD\) matrix,O​D\|H\|×\|H\|OD^\{\|H\|\\times\|H\|\}\[[20](https://arxiv.org/html/2606.04167#bib.bib17),[16](https://arxiv.org/html/2606.04167#bib.bib1)\]\. Here,O​D​\[i,j\]OD\[i,j\]denotes the travel demand from grid celliito grid celljj\. In the MNEP, the OD matrix is assumed to be symmetric and deterministic, remaining constant throughout the optimization process\.

The size of setZZis limited by a construction budgetBB, and a maximum number of stationsTT\. We define a functionU​\(Z\)U\(Z\)that calculates the total added benefit of the generated lineZZ\. In the traditional MNEP,U​\(Z\)U\(Z\)is defined as the total sum of satisfied demand\. The optimization problem is then defined as follows\. Find the set of connected cellsZZ, such that:

max\\displaystyle\\maxU​\(Z\)=∑i∑jO​D​\[zi,zj\],i≠j\\displaystyle U\(Z\)=\\sum\\limits\_\{i\}\\sum\\limits\_\{j\}OD\[z\_\{i\},z\_\{j\}\],i\\neq j\(1\)s\.t\.c​o​s​t​\(Z\)≤B\\displaystyle cost\(Z\)\\leq B\|Z\|≤T\\displaystyle\|Z\|\\leq T
Here, the constraintsBBandTTare strict, meaning that the new metro line must not exceed the specified budget or the total number of allowable stations\.

The structural configuration of the metro line depends on the type of transport, which can be directed, as in bus or tram networks, or undirected, as is typical in metro systems\. The focus of our paper is the design of metro networks, hence we tackle the Metro Network Expansion Problem \(MNEP\)\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\]\.

### 3\.1Social Equity in the Metro Network Expansion Problem

The traditional MNEP primarily seeks to maximize total demand coverage, often overlooking the equitable distribution of benefits across various communities within the city\. Prior work on reinforcement learning \(RL\) in this context also tends to prioritize efficiency and adopt a predominantlyutilitarianapproach\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\]\. Here, we demonstrate that RL can effectively optimize for a wider array of objectives that encompass essential principles of social equity, as defined in transport planning literature\. In addition toutilitarianism\([Equation˜1](https://arxiv.org/html/2606.04167#S3.E1)\), we emphasize two additional equity principles:equal sharing of benefitsandRawlsian justiceas articulated by Rawls’ theory of justice\[[4](https://arxiv.org/html/2606.04167#bib.bib9)\]\. Our focus centers on ensuring fairness in the allocation of satisfied Origin\-Destination demand facilitated by the new line, paying particular attention to its distribution across different socioeconomic groups\.

We first define a set of groupsGG, based on socioeconomic indicators such as income, development index, and education\. Each cellh∈Hn×mh\\in H^\{n\\times m\}in the environment is associated with a groupg∈Gg\\in G\. We adjust the objective function for each fairness notion accordingly, defining a utility functionU​\(Z,g\)U\(Z,g\)for each groupg∈Gg\\in G, which returns the satisfied OD demand of lineZZfor groupgg\.

Equal Sharing:This egalitarian objective aims to equalize the added benefits of the transport line among groups in a city, commonly referred to as horizontal equity\. In theory, equal sharing is achieved by minimizing the absolute differences between group utilities:

min​∑i∑j\|U​\(Z,gi\)−U​\(Z,gj\)\|,gi,gj∈G,i≠j\\min\\sum\_\{i\}\\sum\_\{j\}\\lvert U\(Z,g\_\{i\}\)\-U\(Z,g\_\{j\}\)\\rvert,g\_\{i\},g\_\{j\}\\in G,i\\neq j\(2\)To implement fairness objectives in practice, we need to also incorporate total reward as, theoretically,[Equation˜2](https://arxiv.org/html/2606.04167#S3.E2)could be minimized when all group utilities are0\. To address this, we encapsulate the equal\-sharing notion using the Generalized Gini Index \(GGI\)\[[44](https://arxiv.org/html/2606.04167#bib.bib11)\]\.

U​\(Z\)=G​G​I​\(Z,W\)=∑i\|G\|Wi​U​\(Z,σ​\(G\)​i\),U\(Z\)=GGI\(Z,W\)=\\sum\_\{i\}^\{\|G\|\}W\_\{i\}U\(Z,\\sigma\(G\)i\),\(3\)whereσ\\sigmais a permutation that sorts the groups inGGin descending order based on their utility prior to line creation, andWiW\_\{i\}are strictly decreasing weights \(i\.e\.,W1\>W2\>⋯\>W​\|G\|W\_\{1\}\>W\_\{2\}\>\\dots\>W\{\|G\|\}\) normalized to sum to11\.

Rawls’ Theory of Justice:This approach aims to maximize benefits for the most disadvantaged group\.

max⁡\(U​\(Z,gm​i​n\)\),\\displaystyle\\max\(U\(Z,g\_\{min\}\)\),\(4\)wheregm​i​ng\_\{min\}represents the most disadvantaged group withinGG\. In this paper, we define groups based on a house\-price index as a proxy for area development, withgm​i​ng\_\{min\}as the group with the lowest house price index\. Lower house price indexes are used as a proxy to identify the poorer areas of a city\.

To apply this notion, we set the reward function asU​\(Z\)=U​\(Z,gm​i​n\)U\(Z\)=U\(Z,g\_\{min\}\)\. In Figure[1](https://arxiv.org/html/2606.04167#S2.F1), we illustrate the real\-world cities of Amsterdam and Xi’an where we apply our method\. We detail the environments in[Section˜5](https://arxiv.org/html/2606.04167#S5)\.

![Refer to caption](https://arxiv.org/html/2606.04167v1/x1.png)

Figure 2:In the Metro Network Expansion Problem \(MNEP\), a reinforcement learning \(RL\) agent sequentially adds transport segments to the network\. Each action represents the addition of a segment at a specific location, with rewards based on the demand met by that segment\. The objective is to maximize the cumulative reward from all added segments\.

## 4Methods

We define the Metro Network Expansion Problem \(MNEP\) as a Non\-Markovian Reward Decision Process \(NMRDP\) \([Section˜4\.1](https://arxiv.org/html/2606.04167#S4.SS1)\) and describe the Tabular RL algorithm we use to solve it \([Section˜4\.2](https://arxiv.org/html/2606.04167#S4.SS2)\)\.

### 4\.1Metro Network Expansion Non\-Markovian Reward Decision Process

Recent approaches to the MNEP apply reinforcement learning \(RL\) by encoding each city grid cell as a potential action for the agent, resulting in an action space that scales linearly with the grid size \(\|A\|=\|H\|\|A\|=\|H\|\)\[[53](https://arxiv.org/html/2606.04167#bib.bib2),[46](https://arxiv.org/html/2606.04167#bib.bib60)\], with a time complexity ofO​\(n×m\)O\(n\\times m\)\. While physical constraints mask certain actions to limit selectable cells at each timestep, this masking occurs only after the forward pass, immediately before the softmax layer\[[53](https://arxiv.org/html/2606.04167#bib.bib2),[46](https://arxiv.org/html/2606.04167#bib.bib60)\]\. As a result, the policy network must still process all potential cells in every state\.

We argue that this complexity is unnecessary\. Instead, we propose a two\-stage approach: first, the agent selects astarting cell—the initial location for placing the first station on a metro line\. The agent then navigates the grid by choosing among eight possible movement directions \(north, south, east, west, and the four diagonal directions\)\. Each movement forms a segment of the metro line, with the newly entered cell designated as the next station location\.

With our approach, the initial cell selection and the subsequent episode steps are decoupled, substantially reducing the action space to88, regardless of the grid size, reducing the time complexity at each step \(except for the first\) toO​\(1\)O\(1\)\. Additionally, we simplify the state representation to be the agent’s current location, which can be efficiently encoded in a table with rows corresponding to the number of cells in the grid\. However, this new formulation violates the Markov property, since the agent’s current location alone does not encapsulate the previously placed stations\. Future rewards depend on the sequence of past actions\[[18](https://arxiv.org/html/2606.04167#bib.bib77)\]\. Consequently, the decision process deviates from the Markov assumption that all necessary information is contained in the present state\. Nonetheless, as in prior work addressing combinatorial optimization problems like the Travelling Salesman Problem\[[5](https://arxiv.org/html/2606.04167#bib.bib7),[24](https://arxiv.org/html/2606.04167#bib.bib18)\], this departure from a strict Markovian framework is intentional and acceptable for our purposes\. Our goal is to efficiently tackle the static MNEP by generating high\-quality solutions rather than to satisfy all theoretical properties of sequential decision making\. And as we show in this paper, this relaxation does not lead to lower performance\.

The Metro Network Expansion Problem \(MNEP\) can be formulated as a Non\-Markovian Reward Decision Process \(NMRDP\), an extension of the Markov Decision Process\[[18](https://arxiv.org/html/2606.04167#bib.bib77)\],ℳ=⟨𝒮,𝒜,𝒫,ℛ,γ,μ⟩\\mathcal\{M\}=\\langle\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{P\},\\mathcal\{R\},\\gamma,\\mu\\rangleas follows:

𝒮\\mathcal\{S\}is the state space, where each statest=\(xt,yt\)∈𝒮s\_\{t\}=\(x\_\{t\},y\_\{t\}\)\\in\\mathcal\{S\}represents the agent’s current location in the two\-dimensional city grid\.

𝒜=\{N,S,E,W,N​E,N​W,S​E,S​W\}\\mathcal\{A\}=\\\{N,S,E,W,NE,NW,SE,SW\\\}is the action space, corresponding to the eight movement directions: North, South, East, West, and the four diagonals\. The action taken at timettis denoted asat∈𝒜a\_\{t\}\\in\\mathcal\{A\}\.

ℛ:𝒮×𝒜×𝒮×ℋ→ℝ\\mathcal\{R\}:\\mathcal\{S\}\\times\\mathcal\{A\}\\times\\mathcal\{S\}\\times\\mathcal\{H\}\\to\\mathbb\{R\}is the reward function, which encodes the demand satisfied by constructing a metro line segment fromsts\_\{t\}tost\+1s\_\{t\+1\}\. Since the reward depends on the history of visited statesℋ=\{s0,s1,…,st\}\\mathcal\{H\}=\\\{s\_\{0\},s\_\{1\},\.\.\.,s\_\{t\}\\\}, it is non\-Markovian and cannot be fully determined by the current state\-action pair alone\. The reward received at timettisrt=ℛ​\(st,at,st\+1,ℋ\)r\_\{t\}=\\mathcal\{R\}\(s\_\{t\},a\_\{t\},s\_\{t\+1\},\\mathcal\{H\}\)\.

μ:𝒮→\[0,1\]\\mu:\\mathcal\{S\}\\to\[0,1\]is the probability distribution over the starting states0s\_\{0\}, which can be predefined, learned, or randomly sampled\.

Given the discrete and episodic nature of the problem, we set the discount factorγ=1\\gamma=1, and the transition function𝒫\\mathcal\{P\}is deterministic\. Figure[2](https://arxiv.org/html/2606.04167#S3.F2)illustrates this formulation\.

The action space in any state is further constrained by feasibility rulesF​\(Zt\)F\(Z\_\{t\}\), which enforce: no re\-visiting of previously occupied cells, no movement beyond grid boundaries and no reversing direction or forming cycles\. These constraints refine the set of allowable actions to adhere to the constraints of a metro line\. More details on feasibility rules are provided on the Appendix, the accompanying code, and prior work\[[53](https://arxiv.org/html/2606.04167#bib.bib2),[58](https://arxiv.org/html/2606.04167#bib.bib62)\]\.

The reward functionℛ:𝒮×𝒜×𝒮×ℋ→ℝ\\mathcal\{R\}:\\mathcal\{S\}\\times\\mathcal\{A\}\\times\\mathcal\{S\}\\times\\mathcal\{H\}\\to\\mathbb\{R\}expresses the demand covered by the new metro segment, calculated in two steps\. First, the direct demand between the new station and all previously existing stations on the line is computed \(we useZtZ\_\{t\}to express the historyℋ\\mathcal\{H\}— the previously placed stations\)\. Additionally, if connections between the new metro line and existing lines are identified, the reward is increased by the additional transfer demand between each station of the existing line and each station of the extended line\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\]\. The total reward is the sum of these two components\.

Rt=U​\(Zt\)⏟direct demand\+∑l∈L𝟙c​o​n​n​e​c​t​\(Zt,l\)⋅U​\(l×Zt\)⏟transfer demand,R\_\{t\}=\\underbrace\{U\(Z\_\{t\}\)\}\_\{\\text\{direct demand\}\}\+\\underbrace\{\\sum\_\{l\\in L\}\\mathbbm\{1\}\_\{connect\}\(Z\_\{t\},l\)\\cdot U\(l\\times Z\_\{t\}\)\}\_\{\\text\{transfer demand\}\},\(5\)
whereZt=z1,…,ztZ\_\{t\}=\{z\_\{1\},\.\.\.,z\_\{t\}\}is the set of all stations in the current line up to timett,LLis the set of all existing metro lines,SlS\_\{l\}is the set of stations in existing linell,𝟙c​o​n​n​e​c​t​\(zt,l\)\\mathbbm\{1\}\_\{connect\}\(z\_\{t\},l\)is an indicator function that equals 1 if stationztz\_\{t\}connects with linell\(shares a cell\), and0otherwise\.

### 4\.2Tabular Reinforcement Learning for MNEP

We propose a Tabular RL algorithm for metro network expansion, in which a single reinforcement learning \(RL\) agent operates in two stages\. We apply a Monte Carlo\-based method to iteratively update the V and Q\-tables through repeated environment interactions\.

Selecting the Initial CellAn episode begins with the agent selecting the initial stateS0S\_\{0\}\(starting point for the metro line\) using anϵ\\epsilon\-greedy approach\. When exploring, it picks a random cell; when exploiting, it picks the cell maximizing the expected return\. The value of each cell as a starting position is given byVstart​\(S0\)∈ℝ\|H\|V\_\{\\text\{start\}\}\(S\_\{0\}\)\\in\\mathbb\{R\}^\{\|H\|\}, which estimates the expected return for beginning an episode atS0S\_\{0\}\.

Action Selection and TransitionThe agent selects actions usingϵ\\epsilon\-greedy approach\. After choosing an actionAtA\_\{t\}, the agent observes a rewardRtR\_\{t\}and deterministically transitions to a new stateS′S^\{\\prime\}\. This transition\(St,At,Rt\)\(S\_\{t\},A\_\{t\},R\_\{t\}\)is stored in an episodic list, tracking the agent’s path, which is later used to perform Monte Carlo updates\. Episodes end when one of three terminal conditions is met: \(a\) no available directions remain, \(b\) the budget is exhausted, or \(c\) the maximum number of allowed stations is reached\.

Monte\-Carlo Returns and Policy UpdateAt the end of each episode, the agent updates theVVandQQ\-values using Monte Carlo estimation\. First, the total discounted return, denoted byJJ\(we useJJhere to avoid confusion with the group setGG, departing slightly from standard RL notation\), is calculated\. Using this returnJJ, the agent then updates the value functions accordingly\.

Q​\(St,At\)←Q​\(St,At\)\+α​\[J−Q​\(St,At\)\]Vstart​\(S0\)←Vstart​\(S0\)\+α​\[J−Vstart​\(S0\)\]\\begin\{split\}Q\(S\_\{t\},A\_\{t\}\)\\leftarrow Q\(S\_\{t\},A\_\{t\}\)\+\\alpha\[J\-Q\(S\_\{t\},A\_\{t\}\)\]\\\\ V\_\{\\text\{start\}\}\(S\_\{0\}\)\\leftarrow V\_\{\\text\{start\}\}\(S\_\{0\}\)\+\\alpha\[J\-V\_\{\\text\{start\}\}\(S\_\{0\}\)\]\\end\{split\}\(6\)
In[Algorithm˜1](https://arxiv.org/html/2606.04167#alg1)we show the pseudocode of the proposed method\.

Algorithm 1Tabular Metro Network Expansion with Monte\-Carlo Updates1:Parameters:

BB,

TT,

α\\alpha,

γ\\gamma⊳\\trianglerightBudget, total stations, RL parameters

2:Initialize

Q​\(s,a\)Q\(s,a\),

VstartV\_\{\\text\{start\}\}for all

ss, actions

aa, empty

E​p​i​s​o​d​eEpisode,

T​o​t​a​l​C​o​s​t←0TotalCost\\leftarrow 0, and

A​c​t​i​o​n​M​a​s​kActionMaskof ones\.

3:foreach episodedo

4:Select

S0S\_\{0\}via

ϵ\\epsilon\-greedy from

VstartV\_\{\\text\{start\}\}; add

S0S\_\{0\}to

ZZ
5:foreach step

ttdo

6:Choose

AtA\_\{t\}with

ϵ\\epsilon\-greedy, considering

A​c​t​i​o​n​M​a​s​kActionMask
7:Execute

AA, receive reward

RR, observe next state

S′S^\{\\prime\}
8:Append

\(S,A,R\)\(S,A,R\)to

E​p​i​s​o​d​eEpisode, add

ztz\_\{t\}to

ZZ, update

T​o​t​a​l​C​o​s​tTotalCost,

A​c​t​i​o​n​M​a​s​kActionMask,

S←S′S\\leftarrow S^\{\\prime\}
9:if

S​U​M​\(A​c​t​i​o​n​M​a​s​k\)=0SUM\(ActionMask\)=0OR

T​o​t​a​l​C​o​s​t≥BTotalCost\\geq BOR

t≥Tt\\geq Tthenbreak

10:endif

11:endfor

12:Initialize

J←0J\\leftarrow 0
13:foreach step

\(St,At,Rt\)\(S\_\{t\},A\_\{t\},R\_\{t\}\)in

E​p​i​s​o​d​eEpisodefrom last to firstdo

14:

J←γ​J\+RtJ\\leftarrow\\gamma J\+R\_\{t\}
15:if

\(St,At\)\(S\_\{t\},A\_\{t\}\)is first in

E​p​i​s​o​d​eEpisodethen

16:

Q​\(St,At\)←Q​\(St,At\)\+α​\(J−Q​\(St,At\)\)Q\(S\_\{t\},A\_\{t\}\)\\leftarrow Q\(S\_\{t\},A\_\{t\}\)\+\\alpha\(J\-Q\(S\_\{t\},A\_\{t\}\)\)
17:endif

18:endfor

19:Update

Vs​t​a​r​t​\(S0\)←α​\(J−Vs​t​a​r​t​\(S0\)\)V\_\{start\}\(S\_\{0\}\)\\leftarrow\\alpha\(J\-V\_\{start\}\(S\_\{0\}\)\)
20:Reset

T​o​t​a​l​C​o​s​tTotalCost,

E​p​i​s​o​d​eEpisode,

ZZ, and

A​c​t​i​o​n​M​a​s​kActionMask
21:endfor

## 5Experiments

We ran and evaluated the model in two real\-world case study cities: Xi’an and Amsterdam\. To facilitate introducing directional constraints and to provide higher granularity, both cities are split into grids of equally\-sized cells, rather than relying on census tracts \(this assumption can be relaxed\)\.

#### Xi’an environment preparation

\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\]created and publicly released the Xi’an environment222https://github\.com/weiyu123112/City\-Metro\-Network\-Expansion\-with\-RL\. The city is organized into aH29×29H^\{29\\times 29\}grid, comprising1​k​m21km^\{2\}cells\. An origin\-destination \(OD\) demand matrix was generated from GPS data collected over one month from 25 million mobile phones\. Each cell is linked to an average house price index — we categorize them to five quintiles to create groups\. We selected the average house price as a proxy for neighborhood development, as it is widely available across various cities and raises no privacy concerns\. While our group definitions rely on this metric, they could also incorporate other attributes, such as those based on protected categories\. The environment already includes two existing metro lines, and our experiments focus on expanding the network by designing a third line\. This setting provides a wealth of mobility demand data, contrasting with the case study in Amsterdam discussed below\.

#### Amsterdam environment preparation

The Amsterdam environment is organized into aH35×47H^\{35\\times 47\}grid of0\.5​k​m20\.5km^\{2\}cells\. This cell size was chosen to maintain similar problem complexity in all cities, taking into account the smaller size of Amsterdam\. Since GPS data are unavailable, we estimate the origin\-destination \(OD\) demand using the recently published universal law of human mobility, which indicates that the total mobility flow between two areasiiandjjis determined by their distance and visitation frequency\[[43](https://arxiv.org/html/2606.04167#bib.bib24)\]\. We provide details on the estimation on the Appendix\. As in the Xi’an environment, each cell is associated with an average house price sourced from the publicly available statistical bureau of the Netherlands333https://www\.cbs\.nl/nl\-nl/maatwerk/2019/31/kerncijfers\-wijken\-en\-buurten\-2019\. The groups are defined as five quintiles based on this price\.

### 5\.1Evaluation

We evaluate our proposed TabularMNEP algorithm against the state\-of\-the\-art Deep Reinforcement Learning \(DeepRL\) method for Transport Network Design\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\], as well as a Genetic Algorithm \(GA\)\[[37](https://arxiv.org/html/2606.04167#bib.bib6)\]and a Greedy Search Algorithm \(GS\)\[[56](https://arxiv.org/html/2606.04167#bib.bib61)\]\.

The methods are tested on four distinct reward functions: a utilitarian reward, maximizing total captured travel demand \(Max Efficiency\); two equal\-sharing rewards using the Generalized Gini Index with weights of1/2i1/2^\{i\}\(GGI\(2\)\) and1/4i1/4^\{i\}\(GGI\(4\)\); and a Rawlsian reward that maximizes demand from the lowest house price quintile\. We conducted a Bayesian hyperparameter search across 100 runs, selecting the top five configurations, running each five times, and choosing the one with the best average performance\. More details on the Appendix\. DeepRL was trained over 3,500 epochs \(128 episodes per epoch, totaling 448,000 episodes\), while TabularRL required only 25,000 episodes—a reduction of 18\-fold in total training episodes\.

To estimate emissions \(kg CO2equivalent\), we consider GPU electricity consumption \(kWh\), total training hours, and the carbon emissions per kWh based on the 2024 monthly average for The Netherlands, using the formula:CO=2\{\}\_\{2\}=Watt∗\*TrainingHours∗\*CarbonFactor\[[26](https://arxiv.org/html/2606.04167#bib.bib78)\]\.

Model training used two types of in\-house GPUs, the RTX 6000 Ada Generation \(300300Watt\) and GTX 1080Ti \(250250Watt\), depending on availability\. Although our tabular method does not require a GPU, we report emissions based on GPU usage since a GPU\-equipped node was reserved for model runs\.

![Refer to caption](https://arxiv.org/html/2606.04167v1/img/learning_curves.png)

Figure 3:We demonstrate that the proposed TabularMNEP model achieves similar performance while requiring 18 times fewer episodes \(x\-axis is in log\-scale\)\.Table 1:Results on Xi’an and Amsterdam for 10 seeds\.Table 2:Estimated average emissions in kg CO2equivalent for each model’s training\.

## 6Results

We ran both algorithms using1010random seeds and provide code to replicate our results444Github: https://github\.com/dimichai/tabular\-tndp\. This section presents three key analyses: \(1\) a comparison of our proposed Tabular\-TNDP method against recent approaches including Deep\-RL, a Genetic Algorithm, and a Greedy Algorithm \([Section˜6\.1](https://arxiv.org/html/2606.04167#S6.SS1)\); \(2\) a demonstration of TabularMNEP’s versatility across multiple social\-good rewards \([Section˜6\.2](https://arxiv.org/html/2606.04167#S6.SS2)\); and \(3\) a justification for choosing TabularMNEP in scenarios where interpretability is crucial \([Section˜6\.3](https://arxiv.org/html/2606.04167#S6.SS3)\)\.

### 6\.1TabularMNEP performs on par with DeepRL methods

Our proposed TabularMNEP method significantly outperforms both the Greedy Search\[[27](https://arxiv.org/html/2606.04167#bib.bib79)\]and the Genetic Algorithm\[[37](https://arxiv.org/html/2606.04167#bib.bib6)\]baselines for most rewards\. TabularMNEP achieves comparable performance to DeepRL across both the Xi’an and Amsterdam environments, considering both traditional and social good objectives defined in[Section˜3](https://arxiv.org/html/2606.04167#S3)\. Detailed averages and confidence intervals for all methods are presented in[Table˜1](https://arxiv.org/html/2606.04167#S5.T1)\.

Notably, TabularMNEP achieves results within the confidence interval of DeepRL with substantially greater training efficiency, requiring only25​k25kepisodes compared to DeepRL’s450​k450kepisodes \(35003500epochs ×128128episodes\)\. This18×18\\timesreduction in training episodes is visualized in[Figure˜3](https://arxiv.org/html/2606.04167#S5.F3)using a logarithmic x\-axis\.

In[Table˜2](https://arxiv.org/html/2606.04167#S5.T2), we report the average CO2equivalent emissions from running our models across the four proposed reward functions\. We observe that TabularMNEP requires, on average,12×12\\timesfewer emissions to achieve performance comparable to the Deep RL baseline\.

![Refer to caption](https://arxiv.org/html/2606.04167v1/img/genlines_xian.png)\(a\)Generated Lines and Distribution of Benefits \(Xi’an\)
![Refer to caption](https://arxiv.org/html/2606.04167v1/img/genlines_ams.png)\(b\)Generated Lines and Distribution of Benefits \(Amsterdam\)

Figure 4:We present the results of applying various reward functions to design transport lines in Xi’an \(a\) and Amsterdam \(b\)\. The left column displays the generated lines for each city, while the right column shows the distribution of satisfied demand across the five groups for the selected models\.
### 6\.2TabularMNEP effectively optimizes diverse rewards

As with Deep RL methods, TabularMNEP is capable of optimizing diverse rewards\.[Figure˜4](https://arxiv.org/html/2606.04167#S6.F4)shows the generated metro lines and the reward distribution among groups for both environments\. The Max Efficiency reward function achieves the highest overall satisfied origin\-destination flows, but we can observe that the rewards are distributed unequally among the five groups\. In both Xi’an and Amsterdam, the highest quintiles exhibit greater satisfaction than the lowest quintiles, with inequality more pronounced in Amsterdam\. This is due to the spatial distribution: in Xi’an, groups are more uniformly distributed, and segregation is lower, while in Amsterdam, the city center is dominated by higher\-priced areas\.

In contrast, the equality\-based reward functions result in a more balanced distribution\. Both GGI withw=2w=2andw=4w=4effectively equalize the rewards across groups\. Whenw=4w=4, the rewards are distributed more equally, at the cost of overall efficiency\. The Rawls reward prioritizes the lowest quintile in both environments, maximizing its satisfied demand\. As intended, it directs the agent to optimize exclusively for the lowest quintile\.

An additional insight from the Rawls reward function is its ability to reveal how isolated the lowest\-utility group is\. In Xi’an, maximizing for the lowest quintile creates “trickle\-up” effects, benefiting other groups as well\. However, in Amsterdam, where the lowest quintile is more segregated in the southeast, the generated line primarily benefits this group alone\. This is further demonstrated in the spatial distribution of the lines, as shown in[Figure˜4](https://arxiv.org/html/2606.04167#S6.F4)\.

### 6\.3Reduced state\-space and TabularMNEP leads to more interpretable policies

Our new formulation, that reduces the state\-space to be the grid, offers a key advantage in solving the Metro Network Expansion Problem \(MNEP\): inherent interpretability of the policies\. As illustrated in[Figure˜5](https://arxiv.org/html/2606.04167#S6.F5), we can visualize three critical aspects: \(a\) the optimal policy generating the metro line, \(b\) the average reward distribution across initial grid locations, and \(c\) the final Q\-values with their corresponding best actions, which provide a direct interpretation for the best metro segment direction from each possible departing state\. While similar visualizations could be produced for the previously proposed deep RL methods, there is a fundamental difference in how these values are stored and accessed\. In Deep RL, policies are embedded within high\-dimensional, latent representations, making it difficult to extract direct mappings from states to actions without additional processing, such as feature visualization or network probing\. In contrast, our method explicitly stores values for each state\-action pair, allowing for transparent inspection and direct modification, even during training\. This interpretability provides decision\-makers with insights beyond the model’s output, enabling them to understand the relationship between actions and rewards, identify over\-and under\-explored areas in the city, and allowing generating alternative routes to those produced by black\-box models\.

Transparency in this domain is particularly valuable as real\-world metro planning often requires multiple alternative policies rather than a single solution\. Additionally, tabular MNEP allows for incorporating spatial constraints after training, once the model has thoroughly explored the solution space\. This post\-training constraint application enables the model’s ability to discover diverse solutions, while still capable of accommodating practical limitations\.

![Refer to caption](https://arxiv.org/html/2606.04167v1/img/qtables.png)

Figure 5:TabularRL provides better interpretability compared to DeepRL\. In Panel \(a\), the metro line of a trained model optimized for maximum efficiency is illustrated\. Panel \(b\) shows the average achievable reward from various starting points within the city, while Panel \(c\) displays the learned Q\-values for each cell when the agent selects the action associated with the highest Q\-value\. Higher Q\-values indicate more favorable locations for placing a metro station\.

## 7Conclusion

We demonstrate that simple, tabular\-based reinforcement learning methods can effectively tackle complex combinatorial optimization problems with diverse objectives, such as the Transport Network Design and Metro Network Expansion problems\. Our approach reformulates the problem to reduce the action space and employs distinct value tables for different action types\.

We show that well\-engineered problem reformulation, combined with established methods, can yield competitive results while requiring significantly less computational power\. Our method runs efficiently on standard personal computers without a GPU and achieves performance comparable to state\-of\-the\-art deep reinforcement learning techniques, despite using far fewer resources and requiring substantially less training time\. Moreover, our approach enhances interpretability and flexibility in policy selection\.

Our findings highlight that effective computational policy\-making in real\-world applications is achievable without relying on complex, black\-box models\. We hope this work encourages a re\-evaluation of simpler models for other optimization challenges as well, such as link rewiring, which offers a similar setup\[[55](https://arxiv.org/html/2606.04167#bib.bib81)\]\. However, we acknowledge that tabular methods require encoding every possible state in the state space, which can pose scalability limitations\. While our approach performs well in the Metro Network Expansion problem by constraining the state space, it may not generalize to problems with inherently large\-scale state representations\.

We would like to note that Reinforcement Learning in urban planning can enhance decision efficiency, but without careful consideration of the reward function, it can reinforce existing biases, favoring developed areas and deepening mobility inequities\. Automated decision\-making also risks reducing transparency and public engagement\. Thus, the proposed models require human oversight, fairness considerations, and policy constraints for ethical deployment\.

## Acknowledgments

This project was funded by the Innovation Center for Artificial Intelligence \(ICAI\) and the City of Amsterdam\.

## References

- \[1\]\(2022\-01\)Approximate multi\-objective optimization for integrated bus route design and service frequency setting\.Transportation Research Part B: Methodological155,pp\. 1–25\(en\)\.External Links:ISSN 0191\-2615,[Link](https://www.sciencedirect.com/science/article/pii/S0191261521001910),[Document](https://dx.doi.org/10.1016/j.trb.2021.10.007)Cited by:[§2\.1](https://arxiv.org/html/2606.04167#S2.SS1.p1.1)\.
- \[2\]K\. Alkilane and D\. Lee\(2024\)MetroZero: deep reinforcement learning and monte carlo tree search for optimized metro network expansion\.Cited by:[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p2.1)\.
- \[3\]L\. F\. W\. Anthony, B\. Kanding, and R\. Selvan\(2020\)Carbontracker: tracking and predicting the carbon footprint of training deep learning models\.External Links:2007\.03051,[Link](https://arxiv.org/abs/2007.03051)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p5.1)\.
- \[4\]H\. Behbahani, S\. Nazari, M\. Jafari Kang, and T\. Litman\(2019\-07\)A conceptual framework to formulate transportation network design problem considering social equity criteria\.Transportation Research Part A: Policy and Practice125,pp\. 171–183\(en\)\.External Links:ISSN 0965\-8564,[Link](https://www.sciencedirect.com/science/article/pii/S0965856417308030),[Document](https://dx.doi.org/10.1016/j.tra.2018.04.005)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p1.1),[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p4.1),[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p6.1),[§3\.1](https://arxiv.org/html/2606.04167#S3.SS1.p1.1)\.
- \[5\]I\. Bello, H\. Pham, Q\. V\. Le, M\. Norouzi, and S\. Bengio\(2017\-01\)Neural Combinatorial Optimization with Reinforcement Learning\.arXiv:1611\.09940 \[cs, stat\]\.Note:arXiv: 1611\.09940External Links:[Link](http://arxiv.org/abs/1611.09940)Cited by:[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p1.1),[§4\.1](https://arxiv.org/html/2606.04167#S4.SS1.p3.2)\.
- \[6\]Y\. Bengio, A\. Lodi, and A\. Prouvost\(2021\-04\)Machine learning for combinatorial optimization: A methodological tour d’horizon\.European Journal of Operational Research290\(2\),pp\. 405–421\(en\)\.External Links:ISSN 03772217,[Link](https://linkinghub.elsevier.com/retrieve/pii/S0377221720306895),[Document](https://dx.doi.org/10.1016/j.ejor.2020.07.063)Cited by:[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p1.1)\.
- \[7\]W\. Cheng, J\. Wu, W\. Moen, and L\. Hong\(2021\-04\)Assessing the spatial accessibility and spatial equity of public libraries’ physical locations\.Library & Information Science Research43\(2\),pp\. 101089\(en\)\.External Links:ISSN 0740\-8188,[Link](https://www.sciencedirect.com/science/article/pii/S0740818821000190),[Document](https://dx.doi.org/10.1016/j.lisr.2021.101089)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p3.1)\.
- \[8\]G\. Cuccu, J\. Togelius, and P\. Cudre\-Mauroux\(2019\)Playing atari with six neurons\.External Links:1806\.01363,[Link](https://arxiv.org/abs/1806.01363)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p5.1)\.
- \[9\]V\. Darvariu, S\. Hailes, and M\. Musolesi\(2023\)Planning spatial networks with monte carlo tree search\.479\(2269\),pp\. 20220383\.Cited by:[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p2.1)\.
- \[10\]V\. Darvariu, S\. Hailes, and M\. Musolesi\(2024\)Graph reinforcement learning for combinatorial optimization: a survey and unifying perspective\.Cited by:[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p1.1)\.
- \[11\]A\. Darwish, M\. Khalil, and K\. Badawi\(2020\-09\)Optimising Public Bus Transit Networks Using Deep Reinforcement Learning\.In2020 IEEE 23rd International Conference on Intelligent Transportation Systems \(ITSC\),Rhodes, Greece,pp\. 1–7\.External Links:ISBN 978\-1\-72814\-149\-7,[Link](https://ieeexplore.ieee.org/document/9294710/),[Document](https://dx.doi.org/10.1109/ITSC45102.2020.9294710)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p3.1),[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p2.1)\.
- \[12\]E\. C\. Delmelle and I\. Casas\(2012\-03\)Evaluating the spatial equity of bus rapid transit\-based accessibility patterns in a developing country: The case of Cali, Colombia\.Transport Policy20,pp\. 36–46\(en\)\.External Links:ISSN 0967\-070X,[Link](https://www.sciencedirect.com/science/article/pii/S0967070X11001338),[Document](https://dx.doi.org/10.1016/j.tranpol.2011.12.001)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p3.1)\.
- \[13\]M\. Deudon, P\. Cournut, A\. Lacoste, Y\. Adulyasak, and L\. Rousseau\(2018\)Learning Heuristics for the TSP by Policy Gradient\.InIntegration of Constraint Programming, Artificial Intelligence, and Operations Research,W\. van Hoeve \(Ed\.\),Lecture Notes in Computer Science,Cham,pp\. 170–181\(en\)\.External Links:ISBN 978\-3\-319\-93031\-2,[Document](https://dx.doi.org/10.1007/978-3-319-93031-2%5F12)Cited by:[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p1.1)\.
- \[14\]A\. El\-Geneidy, D\. Levinson, E\. Diab, G\. Boisjoly, D\. Verbich, and C\. Loong\(2016\-09\)The cost of equity: Assessing transit accessibility and social disparity using total travel cost\.Transportation Research Part A: Policy and Practice91,pp\. 302–316\(en\)\.External Links:ISSN 0965\-8564,[Link](https://www.sciencedirect.com/science/article/pii/S0965856416305924),[Document](https://dx.doi.org/10.1016/j.tra.2016.07.003)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p2.1)\.
- \[15\]W\. Fan and R\. B\. Machemehl\(2006\-02\)Using a Simulated Annealing Algorithm to Solve the Transit Route Network Design Problem\.Journal of Transportation Engineering132\(2\),pp\. 122–132\(EN\)\.Note:Publisher: American Society of Civil EngineersExternal Links:ISSN 0733\-947X,[Link](https://ascelibrary.org/doi/abs/10.1061/%28ASCE%290733-947X%282006%29132%3A2%28122%29),[Document](https://dx.doi.org/10.1061/%28ASCE%290733-947X%282006%29132%3A2%28122%29)Cited by:[§2\.1](https://arxiv.org/html/2606.04167#S2.SS1.p1.1)\.
- \[16\]R\. Z\. Farahani, E\. Miandoabchi, W\. Y\. Szeto, and H\. Rashidi\(2013\-09\)A review of urban transportation network design problems\.European Journal of Operational Research229\(2\),pp\. 281–302\(en\)\.External Links:ISSN 0377\-2217,[Link](https://www.sciencedirect.com/science/article/pii/S0377221713000106),[Document](https://dx.doi.org/10.1016/j.ejor.2013.01.001)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p2.1),[§3](https://arxiv.org/html/2606.04167#S3.p2.8)\.
- \[17\]S\. Farber, K\. Bartholomew, X\. Li, A\. Páez, and K\. M\. Nurul Habib\(2014\-09\)Assessing social equity in distance based transit fares using a model of travel behavior\.Transportation Research Part A: Policy and Practice67,pp\. 291–303\(en\)\.External Links:ISSN 0965\-8564,[Link](https://www.sciencedirect.com/science/article/pii/S0965856414001785),[Document](https://dx.doi.org/10.1016/j.tra.2014.07.013)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p2.1)\.
- \[18\]M\. Gaon and R\. Brafman\(2020\-04\)Reinforcement Learning with Non\-Markovian Rewards\.34\(04\),pp\. 3980–3987\.External Links:[Link](https://ojs.aaai.org/index.php/AAAI/article/view/5814),[Document](https://dx.doi.org/10.1609/aaai.v34i04.5814)Cited by:[§4\.1](https://arxiv.org/html/2606.04167#S4.SS1.p3.2),[§4\.1](https://arxiv.org/html/2606.04167#S4.SS1.p4.1)\.
- \[19\]V\. T\. T\. Giang, T\. D\. Vinh, N\. T\. Huyen, D\. T\. Nga, N\. M\. Hung,et al\.\(2023\)Connectivity of metro station location with urban space–a study of hanoi metro line n° 2\.3\.InE3S Web of Conferences,Vol\.403,pp\. 07008\.Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p5.1)\.
- \[20\]V\. Guihaire and J\. Hao\(2008\)Transit network design and scheduling: a global review\.Transportation Research Part A: Policy and Practice42\(10\),pp\. 1251–1273\.Cited by:[§3](https://arxiv.org/html/2606.04167#S3.p2.8)\.
- \[21\]G\. Gutiérrez\-Jarpa, G\. Laporte, and V\. Marianov\(2018\-01\)Corridor\-based metro network design with travel flow capture\.Computers & Operations Research89,pp\. 58–67\(en\)\.External Links:ISSN 0305\-0548,[Link](https://www.sciencedirect.com/science/article/pii/S0305054817302137),[Document](https://dx.doi.org/10.1016/j.cor.2017.08.007)Cited by:[§2\.1](https://arxiv.org/html/2606.04167#S2.SS1.p1.1)\.
- \[22\]D\. Hernandez\(2018\)Uneven mobilities, uneven opportunities: Social distribution of public transport accessibility to jobs and education in Montevideo\.Journal of Transport Geography67,pp\. 119–125\(en\)\.External Links:ISSN 0966\-6923,[Link](https://www.sciencedirect.com/science/article/pii/S0966692316303556),[Document](https://dx.doi.org/10.1016/j.jtrangeo.2017.08.017)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p2.1)\.
- \[23\]S\. Jullien, M\. Ariannezhad, P\. Groth, and M\. de Rijke\(2022\)A simulation environment and reinforcement learning method for waste reduction\.Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p3.1),[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p1.1)\.
- \[24\]W\. Kool, H\. van Hoof, and M\. Welling\(2018\)Attention, learn to solve routing problems\!\.InInternational Conference on Learning Representations,Cited by:[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p1.1),[§4\.1](https://arxiv.org/html/2606.04167#S4.SS1.p3.2)\.
- \[25\]S\. Krishnan, M\. Lam, S\. Chitlangia, Z\. Wan, G\. Barth\-Maron, A\. Faust, and V\. J\. Reddi\(2022\)QuaRL: quantization for fast and environmentally sustainable reinforcement learning\.External Links:1910\.01055,[Link](https://arxiv.org/abs/1910.01055)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p5.1)\.
- \[26\]A\. Lacoste, A\. Luccioni, V\. Schmidt, and T\. Dandres\(2019\)Quantifying the carbon emissions of machine learning\.External Links:1910\.09700,[Link](https://arxiv.org/abs/1910.09700)Cited by:[§5\.1](https://arxiv.org/html/2606.04167#S5.SS1.p3.4)\.
- \[27\]G\. Laporte, J\. A\. Mesa, F\. A\. Ortega, and I\. Sevillano\(2005\-04\)Maximizing Trip Coverage in the Location of a Single Rapid Transit Alignment\.136\(1\),pp\. 49–63\.External Links:ISSN 1572\-9338,[Link](https://doi.org/10.1007/s10479-005-2038-0),[Document](https://dx.doi.org/10.1007/s10479-005-2038-0)Cited by:[Table 1](https://arxiv.org/html/2606.04167#S5.T1.8.8.8.9),[§6\.1](https://arxiv.org/html/2606.04167#S6.SS1.p1.1)\.
- \[28\]G\. Laporte and M\. M\. B\. Pascoal\(2015\-10\)Path based algorithms for metro network design\.Computers & Operations Research62,pp\. 78–94\(en\)\.External Links:ISSN 0305\-0548,[Link](https://www.sciencedirect.com/science/article/pii/S0305054815000878),[Document](https://dx.doi.org/10.1016/j.cor.2015.04.007)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p3.1),[§2\.1](https://arxiv.org/html/2606.04167#S2.SS1.p1.1)\.
- \[29\]M\. Lowe, B\. Aytekin, and G\. Gereffi\(2009\-10\)Public Transit Buses: A Green Choice Gets Greener\.Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p1.1)\.
- \[30\]K\. Martens\(2016\-07\)Transport Justice: Designing fair transportation systems\.Routledge\(en\)\.Note:Google\-Books\-ID: m0yTDAAAQBAJExternal Links:ISBN 978\-1\-317\-59958\-6Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p1.1)\.
- \[31\]N\. Mazyavkina, S\. Sviridov, S\. Ivanov, and E\. Burnaev\(2021\-10\)Reinforcement learning for combinatorial optimization: A survey\.Computers & Operations Research134,pp\. 105400\(en\)\.External Links:ISSN 0305\-0548,[Link](https://www.sciencedirect.com/science/article/pii/S0305054821001660),[Document](https://dx.doi.org/10.1016/j.cor.2021.105400)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p4.1),[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p1.1)\.
- \[32\]D\. Michailidis, W\. Röpke, S\. Ghebreab, D\. M\. Roijers, and F\. P\. Santos\(2023\)Fairness in Transport Network Design \- A Multi\-Objective Reinforcement Learning Approach\.\(en\)\.Cited by:[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p2.1)\.
- \[33\]H\. Mohring\(1972\)Optimization and scale economies in urban bus transportation\.The American Economic Review62\(4\),pp\. 591–604\.Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p1.1)\.
- \[34\]M\. A\. Nayeem, M\. M\. Islam, and X\. Yao\(2018\)Solving transit network design problem using many\-objective evolutionary approach\.20\(10\),pp\. 3952–3963\.Cited by:[§2\.1](https://arxiv.org/html/2606.04167#S2.SS1.p1.1)\.
- \[35\]M\. Nazari, A\. Oroojlooy, L\. Snyder, and M\. Takac\(2018\)Reinforcement learning for solving the vehicle routing problem\.InAdvances in Neural Information Processing Systems,S\. Bengio, H\. Wallach, H\. Larochelle, K\. Grauman, N\. Cesa\-Bianchi, and R\. Garnett \(Eds\.\),Vol\.31,pp\.\.External Links:[Link](https://proceedings.neurips.cc/paper/2018/file/9fb4651c05b2ed70fba5afe0b039a550-Paper.pdf)Cited by:[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p1.1)\.
- \[36\]G\. Neustroev, S\. P\. E\. Andringa, R\. A\. Verzijlbergh, and M\. M\. De Weerdt\(2022\-05\)Deep Reinforcement Learning for Active Wake Control\.InProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems,AAMAS ’22,Richland, SC,pp\. 944–953\.External Links:ISBN 978\-1\-4503\-9213\-6Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p4.1)\.
- \[37\]M\. Owais and M\. K\. Osman\(2018\-12\)Complete hierarchical multi\-objective genetic algorithm for transit network design problem\.Expert Systems with Applications114,pp\. 143–154\(en\)\.External Links:ISSN 0957\-4174,[Link](https://www.sciencedirect.com/science/article/pii/S0957417418304573),[Document](https://dx.doi.org/10.1016/j.eswa.2018.07.033)Cited by:[Appendix C](https://arxiv.org/html/2606.04167#A3.p2.1),[§1](https://arxiv.org/html/2606.04167#S1.p3.1),[§2\.1](https://arxiv.org/html/2606.04167#S2.SS1.p1.1),[§5\.1](https://arxiv.org/html/2606.04167#S5.SS1.p1.1),[Table 1](https://arxiv.org/html/2606.04167#S5.T1.16.16.16.9),[§6\.1](https://arxiv.org/html/2606.04167#S6.SS1.p1.1)\.
- \[38\]D\. Patterson, J\. Gonzalez, Q\. Le, C\. Liang, L\. Munguia, D\. Rothchild, D\. So, M\. Texier, and J\. Dean\(2021\)Carbon emissions and large neural network training\.External Links:2104\.10350,[Link](https://arxiv.org/abs/2104.10350)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p5.1)\.
- \[39\]R\. H\. M\. Pereira, D\. Banister, T\. Schwanen, and N\. Wessel\(2019\)Distributional effects of transport policies on inequalities in access to opportunities in Rio de Janeiro\.Journal of Transport and Land Use12\(1\),pp\. 741–764\.Note:Publisher: Journal of Transport and Land UseExternal Links:ISSN 1938\-7849,[Link](https://www.jstor.org/stable/26911287)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p2.1),[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p3.1)\.
- \[40\]V\. D\. Pyrialakou, K\. Gkritza, and J\. D\. Fricker\(2016\-02\)Accessibility, mobility, and realized travel behavior: Assessing transport disadvantage from a policy perspective\.Journal of Transport Geography51,pp\. 252–269\(en\)\.External Links:ISSN 0966\-6923,[Link](https://www.sciencedirect.com/science/article/pii/S0966692316000144),[Document](https://dx.doi.org/10.1016/j.jtrangeo.2016.02.001)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p3.1)\.
- \[41\]G\. S\. Ramachandran, I\. Brugere, L\. R\. Varshney, and C\. Xiong\(2021\-04\)GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning\.arXiv:2012\.03900 \[cs\]\.Note:arXiv: 2012\.03900External Links:[Link](http://arxiv.org/abs/2012.03900)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p5.1)\.
- \[42\]N\. Raman, S\. Shah, and J\. Dickerson\(2021\-10\)Data\-Driven Methods for Balancing Fairness and Efficiency in Ride\-Pooling\.arXiv:2110\.03524 \[cs\]\.Note:arXiv: 2110\.03524External Links:[Link](http://arxiv.org/abs/2110.03524)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p3.1)\.
- \[43\]M\. Schläpfer, L\. Dong, K\. O’Keeffe, P\. Santi, M\. Szell, H\. Salat, S\. Anklesaria, M\. Vazifeh, C\. Ratti, and G\. B\. West\(2021\-05\)The universal visitation law of human mobility\.Nature593\(7860\),pp\. 522–527\(en\)\.Note:Number: 7860 Publisher: Nature Publishing GroupExternal Links:ISSN 1476\-4687,[Link](https://www.nature.com/articles/s41586-021-03480-9),[Document](https://dx.doi.org/10.1038/s41586-021-03480-9)Cited by:[Appendix B](https://arxiv.org/html/2606.04167#A2.p1.2),[§5](https://arxiv.org/html/2606.04167#S5.SS0.SSSx2.p1.4)\.
- \[44\]U\. Siddique, P\. Weng, and M\. Zimmer\(2020\-08\)Learning Fair Policies in Multiobjective \(Deep\) Reinforcement Learning with Average and Discounted Rewards\.arXiv:2008\.07773 \[cs\]\.Note:arXiv: 2008\.07773External Links:[Link](http://arxiv.org/abs/2008.07773)Cited by:[§3\.1](https://arxiv.org/html/2606.04167#S3.SS1.p3.1)\.
- \[45\]E\. Strubell, A\. Ganesh, and A\. McCallum\(2020\-Apr\.\)Energy and policy considerations for modern deep learning research\.34\(09\),pp\. 13693–13696\.External Links:[Link](https://ojs.aaai.org/index.php/AAAI/article/view/7123),[Document](https://dx.doi.org/10.1609/aaai.v34i09.7123)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p5.1)\.
- \[46\]H\. Su, Y\. Zheng, J\. Ding, D\. Jin, and Y\. Li\(2024\)MetroGNN: metro network expansion with reinforcement learning\.InCompanion Proceedings of the ACM on Web Conference 2024,pp\. 650–653\.Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p2.1),[§4\.1](https://arxiv.org/html/2606.04167#S4.SS1.p1.2)\.
- \[47\]W\. Y\. Szeto and Y\. Jiang\(2014\)Transit route and frequency design: Bi\-level modeling and hybrid artificial bee colony algorithm approach\.Transportation Research Part B: Methodological67,pp\. 235–263\(en\)\.External Links:ISSN 0191\-2615,[Link](https://www.sciencedirect.com/science/article/pii/S0191261514000812),[Document](https://dx.doi.org/10.1016/j.trb.2014.05.008)Cited by:[§2\.1](https://arxiv.org/html/2606.04167#S2.SS1.p1.1)\.
- \[48\]D\. Tedjopurnomo, Z\. Bao, F\. Choudhury, H\. Luo, and A\. K\. Qin\(2022\-06\)Equitable Public Bus Network Optimization for Social Good: A Case Study of Singapore\.In2022 ACM Conference on Fairness, Accountability, and Transparency,Seoul Republic of Korea,pp\. 278–288\(en\)\.External Links:ISBN 978\-1\-4503\-9352\-2,[Link](https://dl.acm.org/doi/10.1145/3531146.3533092),[Document](https://dx.doi.org/10.1145/3531146.3533092)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p5.1)\.
- \[49\]A\. S\. van der Veen, J\. A\. Annema, K\. Martens, B\. van Arem, and G\. H\. d\. A\. Correia\(2020\)Operationalizing an indicator of sufficient accessibility – a case study for the city of Rotterdam\.Case Studies on Transport Policy8\(4\),pp\. 1360–1370\(en\)\.External Links:ISSN 2213\-624X,[Link](http://www.sciencedirect.com/science/article/pii/S2213624X20301024),[Document](https://dx.doi.org/10.1016/j.cstp.2020.09.007)Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p2.1),[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p3.1)\.
- \[50\]B\. van Wee\(2011\)Discussing Equity and Social Exclusion in Accessibility Evaluations\.pp\. 18\(en\)\.Cited by:[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p1.1),[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p4.1)\.
- \[51\]L\. Wang, J\. G\. Jin, G\. Sibul, and Y\. Wei\(2023\-03\)Designing Metro Network Expansion: Deterministic and Robust Optimization Models\.23\(1\),pp\. 317–347\.External Links:ISSN 1572\-9427,[Link](https://doi.org/10.1007/s11067-022-09584-7),[Document](https://dx.doi.org/10.1007/s11067-022-09584-7)Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p2.1)\.
- \[52\]Q\. Wang and C\. Tang\(2021\-12\)Deep reinforcement learning for transportation network combinatorial optimization: A survey\.Knowledge\-Based Systems233,pp\. 107526\(en\)\.External Links:ISSN 0950\-7051,[Link](https://www.sciencedirect.com/science/article/pii/S0950705121007887),[Document](https://dx.doi.org/10.1016/j.knosys.2021.107526)Cited by:[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p1.1)\.
- \[53\]Y\. Wei, M\. Mao, X\. Zhao, J\. Zou, and P\. An\(2020\-08\)City Metro Network Expansion with Reinforcement Learning\.InProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,Virtual Event CA USA,pp\. 2646–2656\(en\)\.External Links:ISBN 978\-1\-4503\-7998\-4,[Link](https://dl.acm.org/doi/10.1145/3394486.3403315),[Document](https://dx.doi.org/10.1145/3394486.3403315)Cited by:[Appendix A](https://arxiv.org/html/2606.04167#A1.p1.1),[Appendix C](https://arxiv.org/html/2606.04167#A3.p2.1),[Appendix C](https://arxiv.org/html/2606.04167#A3.p3.1),[§1](https://arxiv.org/html/2606.04167#S1.p2.1),[§1](https://arxiv.org/html/2606.04167#S1.p3.1),[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p3.1),[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p5.1),[§3\.1](https://arxiv.org/html/2606.04167#S3.SS1.p1.1),[§3](https://arxiv.org/html/2606.04167#S3.p5.1),[§4\.1](https://arxiv.org/html/2606.04167#S4.SS1.p1.2),[§4\.1](https://arxiv.org/html/2606.04167#S4.SS1.p10.1),[§4\.1](https://arxiv.org/html/2606.04167#S4.SS1.p11.3),[§5](https://arxiv.org/html/2606.04167#S5.SS0.SSSx1.p1.2),[§5\.1](https://arxiv.org/html/2606.04167#S5.SS1.p1.1),[Table 1](https://arxiv.org/html/2606.04167#S5.T1.24.24.24.9)\.
- \[54\]Z\. Xu, X\. Cheng, and Y\. He\(2022\-05\)Performance of Deep Reinforcement Learning for High Frequency Market Making on Actual Tick Data\.InProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems,AAMAS ’22,Richland, SC,pp\. 1765–1767\.External Links:ISBN 978\-1\-4503\-9213\-6Cited by:[§1](https://arxiv.org/html/2606.04167#S1.p4.1)\.
- \[55\]S\. Yang, M\. KAILI, B\. Wang, T\. Yu, and H\. Zha\(2023\)Learning to boost resilience of complex networks via neural edge rewiring\.Cited by:[§7](https://arxiv.org/html/2606.04167#S7.p3.1)\.
- \[56\]Z\. Yang, B\. Yu, and C\. Cheng\(2007\)A parallel ant colony algorithm for bus network optimization\.Computer\-Aided Civil and Infrastructure Engineering22\(1\),pp\. 44–55\.Cited by:[§2\.1](https://arxiv.org/html/2606.04167#S2.SS1.p1.1),[§5\.1](https://arxiv.org/html/2606.04167#S5.SS1.p1.1)\.
- \[57\]A\. Zarrinmehr, M\. Saffarzadeh, S\. Seyedabrishami, and Y\. M\. Nie\(2016\)A path\-based greedy algorithm for multi\-objective transit routes design with elastic demand\.8,pp\. 261–293\.Cited by:[§2\.1](https://arxiv.org/html/2606.04167#S2.SS1.p1.1)\.
- \[58\]L\. Zhang, L\. H\. U, S\. Ni, D\. Chen, Z\. Li, W\. Wang, and W\. Xian\(2024\)City metro network expansion based on multi\-objective reinforcement learning\.Transportation Research Part C: Emerging TechnologiesPublic TransportIEEE Transactions on Intelligent Transportation SystemsarXiv preprint arXiv:2205\.15455Adaptive and Learning Agents WorkshopNetworks and Spatial EconomicsProceedings of the AAAI Conference on Artificial IntelligencearXiv preprint arXiv:2404\.06492IEEE Transactions on Intelligent Transportation SystemsProceedings of the Royal Society AProceedings of the AAAI Conference on Artificial IntelligenceAnnals of Operations ResearchTransactions on Machine Learning Research169,pp\. 104880\.External Links:ISSN 0968\-090X,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.trc.2024.104880),[Link](https://www.sciencedirect.com/science/article/pii/S0968090X24004017)Cited by:[Appendix A](https://arxiv.org/html/2606.04167#A1.p1.1),[§2\.2](https://arxiv.org/html/2606.04167#S2.SS2.p2.1),[§2\.3](https://arxiv.org/html/2606.04167#S2.SS3.p5.1),[§4\.1](https://arxiv.org/html/2606.04167#S4.SS1.p10.1)\.

## Appendix

## Appendix AFeasibility Rules

The feasibility rules applied in this paper closely resemble those in previous studies\[[53](https://arxiv.org/html/2606.04167#bib.bib2),[58](https://arxiv.org/html/2606.04167#bib.bib62)\]\. The agent’s actions are constrained using anActionMask, which is updated at each timestep based on the agent’s current location and prior positions\. This approach ensures that the agent moves forward, avoids cyclical paths, and does not revisit locations where a station has already been placed\.

Our method optimizes this process by maintaining a constant action mask length of 8, representing all possible directions \(including diagonals\), rather than the entire grid size\. The agent’s movement direction is established by its initial longitudinal and latitudinal steps\. For example, if the agent begins by moving north, southward actions will be masked out to enforce forward progression\. If the agent subsequently moves east, only actions corresponding to the north, east, and northeast directions remain available, with all other actions masked\. Figure[6](https://arxiv.org/html/2606.04167#A1.F6)illustrates how these feasibility rules are applied through the action mask during an episode\.

![Refer to caption](https://arxiv.org/html/2606.04167v1/img/feasibility_rules.jpeg)

Figure 6:A snapshot of an episode, where the action mask created by feasibility rules constraints the next available actions to the agent\.
## Appendix BAmsterdam environment preparation

GPS data is unavailable for Amsterdam, so we estimate the origin\-destination \(OD\) demand using the recently published universal law of human mobility, which indicates that the total mobility flow between two areasiiandjjis determined by their distance and visitation frequency\[[43](https://arxiv.org/html/2606.04167#bib.bib24)\]\. The calculation is as follows:

O​Di​j=μj​𝖪𝗂/di​j2​ln⁡\(fm​a​x/fm​i​n\)OD\_\{ij\}=\\mu\_\{j\}\\mathsf\{K\_\{i\}\}/d^\{2\}\_\{ij\}\\ln\(f\_\{max\}/f\_\{min\}\)\(7\)Here,𝖪𝗂\\mathsf\{K\_\{i\}\}is the total area of the origin locationii,di​j2d^\{2\}\_\{ij\}is the \(Manhattan\) distance betweeniiandjj, andμj\\mu\_\{j\}represents the magnitude of flows, computed as:

μj≈ρp​o​p​\(j\)​r​a​dj2​fm​a​x\\mu\_\{j\}\\approx\\rho\_\{pop\}\(j\)rad^\{2\}\_\{j\}f\_\{max\}\(8\)Wherer​a​dj2rad^\{2\}\_\{j\}is the radius of area j\. We estimate the flows over a week by settingfm​i​n,fm​a​xf\_\{min\},f\_\{max\}to1/71/7and77respectively\. The grid cells are of equal size,KiK\_\{i\}and can be omitted from the calculation\.

## Appendix CHyperparameter Tuning and Selection

Greedy Search \(GS\)— Greedy search is a simple greedy algorithm that begins by adding the segment with the largest OD flow, and then greedily expanding the network from this segment, while following the feasibility rules\.

Genetic Algorithm \(GA\)— We conducted experiments using two sets of hyperparameters: one based on\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\], which included a population size of 500, and crossover and mutation probabilities of 0\.9, and another set based on\[[37](https://arxiv.org/html/2606.04167#bib.bib6)\], which used a population size of 500, a crossover probability of 0\.6, and a mutation probability of 0\.05\. We chose the second set of hyperparameters, as they are directly taken from the original source and are more commonly used in Genetic Algorithms\. To ensure a fair comparison with the Tabular RL method, we trained the Genetic Algorithm for a total of 25,000 episodes, which consisted of 50 iterations, each with 500 generated solutions\.

Deep Reinforcement Learning \(DeepRL\)— We conducted experiments using the hyperparameters reported by\[[53](https://arxiv.org/html/2606.04167#bib.bib2)\], which, at the time of writing the paper, were considered state\-of\-the\-art methodology\. The hyperparameters are as follows:

- •Hidden size: 128
- •Static size: 2
- •Dynamic size: 1
- •Number of layers: 1
- •Dropout: 0\.1
- •Max epochs: 3500
- •Training size: 128
- •Actor learning rate: 0\.001
- •Critic learning rate: 0\.001

Tabular RL \(TabularMNEP\)— To select the hyperparameter values for TabularMNEP, we performed multiple sweeps of parameters and methods, using a bayesian optimization approach, via the Weights & Biases library555https://wandb\.ai/site/\. In[Table˜3](https://arxiv.org/html/2606.04167#A3.T3)we show the ranges we used for each hypeparameter\. Additionally to the Monte\-Carlo update method we used in our final experiments, we also tried Temporal\-Difference and Upper Confidence Bound methods\. In the code we provide the commands to replicate our results\.

ForXi’an, the final experiments were conducted with 47 stations\. The Max\. Efficiency setting used a single group, while the Rawls, GGI4, and GGI2 settings used five groups \(for calculating fairness\)\. All experiments ran for 25000 training episodes with an epsilon decay over 16000 steps, a warmup of 3000 steps, and a single test episode\. The initial and final epsilon values were set to 1 and 0\.01, respectively, with a learning rate \(α\\alpha\) of 0\.1 and a discount factor \(γ\\gamma\) of 1\. Exploration followed an epsilon\-greedy strategy, and updates were done via Monte Carlo methods\.

ForAmsterdam, the final experiments were conducted with 21 stations\. The Max\. Efficiency experiments used a single group, with 14000 epsilon decay steps, 0 warmup steps, and learning rate \(α\\alpha\) set to 0\.1\. The Rawls, GGI4, and GGI2 experiments used five groups, with epsilon decay set to 14,000 steps and no warmup steps\. All experiments ran for 25,000 training episodes, with an initial epsilon of 1, a final epsilon of 0\.01, a discount factor \(γ\\gamma\) of 1\. The exploration followed an epsilon\-greedy strategy, and updates were also performed using Monte Carlo methods\.

Table 3:Parameter values tried during hyperparameter search\.