# Real-time redesign of public transport lines under fluctuating traffic conditions

Andrea Araldo, Zihao Guo, Faycal Touzout, Mounim El Yacoubi

► To cite this version:

Andrea Araldo, Zihao Guo, Faycal Touzout, Mounim El Yacoubi. Real-time redesign of public transport lines under fluctuating traffic conditions. 2026. hal-05529041

HAL Id: hal-05529041

https://hal.science/hal-05529041v1

Preprint submitted on 26 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Real-Time Redesign of Public Transport Lines under Fluctuating Traffic Conditions

Andrea Araldo¹

Zihao Guo¹

Fayçal Touzout²

Mounim El-Yacoubi¹

¹SAMOVAR, Télécom SudParis, Institut Polytechnique de Paris, 91120 Palaiseau

²Université Gustave Eiffel

February 26, 2026

## Abstract

Public Transport (PT) lines are traditionally designed to optimize performance under nominal traffic conditions. In practice, however, operating conditions frequently deviate from the nominal ones, leading to substantial performance deterioration. Existing adaptation mechanisms typically rely on corrective and reactive interventions, such as stop-skipping, which prove insufficient under large or recurrent traffic fluctuations. In such contexts, incremental adjustments are inadequate, and a structural redesign of the network becomes necessary. This paper introduces a real-time optimization method for proactively redesigning PT networks to maintain high levels of user- and operator-oriented performance under pronounced traffic fluctuations. We adopt a predict-then-optimize paradigm in which PT lines are reconfigured based on predicted traffic conditions via an algorithm based on the Non-dominated Sorting Genetic Algorithm III (NSGA-III). To ensure operational implementability, we explicitly constrain structural deviations by enforcing high Jaccard similarity between the baseline and redesigned networks, thereby preserving network continuity and limiting operational disruption. To account for the effect of prediction inaccuracies on redesign quality, we construct a statistical model of the errors made by a well-established deep learning-based prediction model (Diffusion Convolutional Recurrent Neural Network) trained on real-world data. Computational results on Mandl's benchmark network, under high traffic fluctuations, show that at least 77.9% of OD pairs experience travel time reductions of at least 20%, alongside operational cost savings of up to 37%, while retaining 79% of the original network structure. Experiments on the large-scale Beijing network further demonstrate average travel time improvements of up to 20.5% and operational cost reductions of 15.6%, while maintaining more than 60% route overlap with the incumbent configuration. These findings demonstrate that proactive, prediction-driven redesign can substantially improve performance, compared to current inflexible PT designs, thereby motivating a transition from current static planning paradigms toward continuous and adaptive PT network design.

## 1 Introduction

Public Transport (PT) networks are typically planned for nominal, scheduled conditions (Ibarra-Rojas et al. 2015), while real-world operations are continuously subject to variability caused
by congestion and other factors (Büchel and Corman 2020a, Danaher et al. 2020), especially in mixed traffic environments. Such routine perturbations occur daily and can propagate across the network, progressively degrading service reliability (Marra and Corman 2020). For example, in Xi'an, 74.34% of bus runs were delayed (Zhang et al. 2022). Beyond operational impacts, insufficiently reliable public transport can also induce behavioral responses, including increased reliance on private vehicles (Rodier et al. 2025).

Existing approaches to cope with recurrent perturbations can be broadly classified as preventive, reactive, or proactive, depending on the decision horizon and intervention level. Preventive strategies enhance robustness ex ante through structural measures, such as dedicated bus lanes that isolate buses from mixed traffic (Russo et al. 2022). However, limited street space and high infrastructure costs often make such measures infeasible in dense urban areas (Li et al. 2009), and preventive capacity tends to be inflexible and underutilized (International Transport Forum (ITF) 2024, 2025).

Reactive strategies attempt, at the operational level, to restore service after perturbations have occurred, for instance via stop-skipping, holding, or detouring (Peled et al. 2021, Tang, Ceder, and Ge 2018, Zheng et al. 2023). These actions deteriorate under high uncertainty, inconvenience passengers (Gkiotsalitis and Cats 2021, §2), and are insufficient to manage cascading perturbations when no alternative network structure is available (Mahdavi and Bhouri 2024).

A key limitation shared by both preventive and reactive strategies is that the PT network structure typically remains fixed, despite persistent changes in operating conditions. Network design decisions are revised infrequently, and traditional models assume deterministic or fixed travel times (Fonseca 2020, Büchel and Corman 2020b), limiting their ability to address recurrent traffic fluctuations. Proactive approaches aim to overcome this limitation by anticipating variability through short-term predictions and redesigning services in advance (Peled et al. 2019).

The **main contribution** of this paper is a new method for the real-time redesign of bus networks under fluctuating traffic conditions. The method follows a “predict-then-optimize” framework and provides good user- and network-centric performance, even when coupled with imperfect traffic predictions. We formulate a multi-objective optimization problem that balances passenger travel time, operating cost, and network stability, and solve it using a customized Nondominated sorting genetic algorithm III (NSGA-III)-based optimization method. Prediction uncertainty is explicitly modeled via fitting the probability distributions of prediction errors of a well-established deep learning model. Our method is extensively evaluated on Mandl's network and a Beijing region network, under different uncertainty levels, and shows substantial improvements in relevant user- and operator-related indicators.

The remainder of the paper is organized as follows. Section 2 reviews related work, Section 3 formulates the problem, Section 4 presents the solution approach, Section 5 describes the evaluation method, Section 6 reports the results, and Section 7 concludes.
# 2 Related Work

Previous work related to ours typically focuses on either *network design* at strategic and tactical levels, where PT lines are planned from scratch, or *reactive operational control*, which manages daily operations without altering the network structure. *Network redesign* occupies an intermediate position by adapting existing networks rather than starting anew. Within this domain, *offline redesign* relies on re-optimization for known future scenarios, whereas emerging *proactive redesign* approaches anticipate short-term uncertainty. However, these proactive methods often overlook the critical trade-off between responsiveness and structural stability, a gap that this paper specifically addresses.

## 2.1 Public Transport Network Design under Nominal Conditions

The PT Network Design Problem (TNDP) consists of designing line routes and their frequencies, balancing user- and operator-centric objectives. These approaches formulate public transport networks *from scratch*, without reference to any pre-existing service configuration, and are intended for long-term strategic or tactical planning. The TNDP is NP-hard (Magnanti and Wong 1984).

User-centric performance has been expressed in numerous ways. In addition to overall travel duration (John, Mumford, and Lewis 2014, Heyken Soares et al. 2019), recent studies also examine network coverage (Cadarso et al. 2017), route efficiency (Suman and Bolia 2019), and demand fulfillment (Barahimi, Eydi, and Aghaie 2021). Operator-centric objectives are focused on limiting operational and capital expenditures (Ahern, Paz, and Corry 2022, Chen et al. 2018, Calabrò et al. 2023), or proxies for them, such as the overall length of line routes. Multi-objective optimization is employed to balance these different objectives. Szeto and Jiang (2014) established a bilevel PT network design framework, wherein the upper-level model aims to minimise passenger transfers, while the lower-level model focuses on PT assignment. Tian, Wang, and Lin (2021) proposed a trilevel optimization, where the upper-level minimizes both passenger and operational costs, the middle level formulates passenger routing strategies, and the lower-level describes the equilibrium state under congested public lines. Based on these approaches, Cervantes-Sanmiguel, Chavez-Hernandez, and Ibarra-Rojas (2023) investigated the trade-off between reducing travel time and decreasing fares.

Note that all these methods design PT network based on *nominal* (e.g., average, peak, etc.) *traffic conditions*. Therefore, as noted by (Tan et al. 2024), the resulting networks may be inefficient faced with real-time variations in traffic patterns, deviating from nominal conditions.

## 2.2 Reactive Operational Control under Disruptions and Uncertainty

In most real-world operations, the structure of the public transport network remains fixed as originally planned. When deviations from nominal conditions occur due to exogenous factors (Nissen et al. 2020, Chen et al. 2009), operators rely on short-term corrective actions to mitigate supply-demand mismatches. Typical examples include stop-skipping (Peled et al. 2021), short-turning, speed changing, holding (Tang, Ceder, and Ge 2018, Manasra and Toledo 2019, Gkiotsalitis 2020, Olvera-Toscano et al. 2023), detouring of interrupted lines (Zheng et al. 2023),
and replacement buses. Each control action has distinct disadvantages. Namely, bus holding increases the inconvenience of on-board passengers at the holding stops, short-turning requires passengers to disembark and wait for a subsequent bus trip, rescheduling affects the timetables and the crew/vehicle schedules; speed control cannot be implemented when the required speeds are beyond the safety limits, and stop-skipping results in refused passenger boardings (Gkiotsalis- tis 2021). While some works integrate real-time data into operational decision-making, such as schedule adjustment for enhanced reliability (?), these frameworks focus on timetable or speed control within a fixed route structure and do not explicitly consider structural reconfiguration of the network topology under time-varying conditions.

More importantly, when actual conditions deviate significantly from the nominal ones, such corrective actions may not be sufficient to restore performance (Guo, Araldo, and Yacoubi 2024), since the overall structure is maintained as planned. Strategies such as stop-skipping and short-turning have also appeared in the context of offline or preplanned redesign, to generate alternative route configurations or long-term service plans under hypothetical disruption scenarios. They are outside the scope of this paper, which instead focuses on real-time line redesign.

## 2.3 Offline and Preplanned Network Redesign under Known Scenarios

Various approaches can be employed in the bus route adjustment problem to generate adaptive bus routes, including rerouting, short-turning, skip-stopping, and branching (Cao and Ceder 2019, Ma, Yang, and Li 2023, Wu et al. 2021). In contrast to the network design approaches described in §2.1, these studies explicitly start from an *existing* public transport network and allow service or structural modifications under a limited set of anticipated scenarios. Previous research on bus route localized adjustments has often aimed at two main objectives: accommodating demand fluctuations and enhancing integration with subway networks.

Guan et al. (2023) introduced a bilevel planning model to optimize customized bus routes offline based on a spatiotemporal state network. While effective for static planning, this method is impractical for real-time dispatching. Concretely, it relies on a computationally expensive nested algorithm and requires a full re-solve for any new event. Zhang et al. (2018) investigated long-distance replacement bus services to improve coordination with urban rail networks. While effective under static demand assumptions, this approach is inherently offline and cannot be applied in real-time operational contexts. When passenger flow control is implemented in a subway system, Zhou et al. (2021) optimized existing bus routes to transport passengers temporarily restricted from entry, in case of disruptions. Wang et al. (2022) proposed a two-stage method to mitigate disruptions to bus routes under planned construction scenarios, relying on predefined work-zone impacts and static travel-time estimates. Wu et al. (2024) proposed a multi-objective ant colony algorithm to adjust existing bus routes and introduced a sequence-level similarity to prevent the redesigned network from being excessively different from the original. However, their approach remains static and cannot capture time-varying adaptations. Zheng et al. (2024) proposed localized adaptive bus routes under anticipated disruptions, while Zhang, Xu, and Wang (2024) addressed large-scale emergency disruptions assuming available spare capacity. These assumptions do not hold under recurrent traffic fluctuations, where no
redundant lines exist and adaptation must occur within the same constrained topology.

## 2.4 Proactive Network Redesign under Predictive Uncertainty and Structural Consistency

Traditional network design handles uncertainty primarily by optimizing for expected scenarios (stochastic optimization) or worst-case bounds (robust optimization) (Bertsimas, Gupta, and Kallus 2018, Wang and Qi 2020). However, these approaches typically determine a single network configuration prior to realization, without any adaptation to the realized road conditions (i.e., without any reconfiguration). Another line of work studies topological metrics to evaluate network resilience (Massobrio and Cats 2024, Pu, Li, and Ma 2022), e.g., they measure vulnerability after a perturbation occurs. These approaches remain purely diagnostic and descriptive, rather than being prescriptive (as the approach we present in this paper), in that they do not provide guidance on the optimization of the network design.

## 2.5 Vehicle Routing Problems and Demand-Responsive Transport (DRT)

In Vehicle Routing Problems (VRPs), vehicle routes are constructed on-demand to serve realized customer requests. These problems are typical in transport systems such as DRT. In these cases, the concept of *solution stability* is often employed to keep revised plans close to a baseline, in order to reduce organization strain (Touzout, Ladier, and Hadj-Hamou 2021). Yet, this stability is typically applied to routing or scheduling assignments, rather than the structure of the PT line network itself. The actual network topology is rarely treated as a flexible structural variable that requires consistency.

This operational flexibility could, in principle, also be used to adjust itineraries in response to changing traffic conditions. However, DRT (and other VRP-based systems) do not exhibit a structured network of lines. As a consequence, they typically fail to achieve sufficient passenger consolidation, which constrains their effective throughput in terms of the number of passengers that can be served (Calabrò et al. 2022). By contrast, we consider a high-capacity mass transit system based on a structured network of fixed lines. Rather than computing routes from scratch, we reconfigure existing lines, and we preserve the high passenger aggregation and capacity levels characteristic of conventional public transport.

## 2.6 Research gaps

Our literature review reveals several gaps in existing approaches to public transport network adaptation (see Table 4 in the Appendix, which summarizes related work). Most existing studies treat PT network design as a deterministic optimization problem, ignoring the inherent uncertainty and variability in urban traffic conditions. As shown in the table, only a few studies consider any form of uncertainty, and none combine real-time network redesign capability with systematic travel time variability modeling. To the best of our knowledge, no studies have proposed a sample-based method for redesigning bus lines in real time to adjust to time-varying road conditions. An exception is Guo, Araldo, and El Yacoubi (2025), where, however, (i) future travel times on road links were assumed to be perfectly known (which is unrealistic),
<figure><img src="image_2.png" /><figcaption>Figure 1: Real-Time Network Rolling Redesign Framework.</figcaption></figure>

so the impact of prediction errors was not considered, while we model the error of a well established prediction model, (ii) only a single simplified objective was adopted, while we solve a multiobjective optimization, and (iii) their approach is tested only on a simple hypothetic scenario, while we consider real-world dataset to fit the prediction error models.

Our work introduces a novel methodology for redesigning routes in response to predicted time-varying road conditions through controlled modifications that balance passenger service quality and operational efficiency.

# 3 Model and Problem Formulation

As illustrated in Fig. 1, our methodology follows a predict-then-optimize framework that explicitly integrates current observations into prediction. The prediction model is first trained offline on historical data to learn travel times on road links. During operation, it receives current observations from the latest time steps and outputs a short-term prediction of link travel times $\hat{t}_{ij}$, which are then supplied to the optimization model for potential network redesign. To ensure timely responsiveness, this procedure is repeated periodically, e.g., on an hourly basis, with further details provided in §3.4.1. The resulting network design is then evaluated against realized travel times $t_{ij}$ to assess the actual performance of our adaptive network under realistic conditions. The notation is summarized in Table 1.

## 3.1 Graph Model of PT Network

We represent the underlying road infrastructure as an undirected substrate network $G^{sub} = (V^{sub}, E^{sub})$, where $V^{sub}$ are candidate bus stops and $E^{sub} = V^{sub} \times V^{sub}$ the potential connections among them. Observe that a single $\ell \in E^{sub}$ may represent a sequence of road links from a stop to another. Let $\mathcal{L}$ denote the set of all PT lines in the network. Each PT line $\ell \in \mathcal{L}$ is defined by a set of undirected substrate edges, representing the physical stop-to-stop connections served by the line. To ensure path continuity and avoid disconnected or cyclic line configurations, the undirected edge set of each line is represented through a directed simple
path graph $G_\ell = (V_\ell, \mathcal{E}_\ell)$ on the undirected substrate $G^{\text{sub}}$, where $V_\ell \subseteq V^{\text{sub}}$ is the set of stops served by line $\ell$, and $\mathcal{E}_\ell \subseteq \mathcal{E}^{\text{sub}}$ denotes the set of connections between consecutive stops along the path representation of line $\ell$. Vehicles operating on line $\ell$ are assumed to traverse this path in both directions; the reverse traversal is implicitly captured through symmetric travel times (Schmid 2014). The complete public transport network is constructed by aggregating all individual lines and is denoted by $G_{\text{PT}} = (V_{\text{PT}}, \mathcal{E}_{\text{PT}}, \mathcal{H})$. In this formulation, $V_{\text{PT}} = \cup_{\ell \in \mathcal{L}} V_\ell$ and $\mathcal{E}_{\text{PT}} = \cup_{\ell \in \mathcal{L}} \mathcal{E}_\ell$, while $\mathcal{H} = \{h_\ell | \ell \in \mathcal{L}\}$ represents the set of line headways, with each $h_\ell$ defined as the time interval between two consecutive vehicles (Vuchic, Clarke, and Molinero 1981). Accordingly, $G_{\text{PT}}$ can be viewed as a line-labeled directed multigraph for modeling purposes, while operationally each line provides bidirectional service along its physical path.

For each PT line $\ell \in \mathcal{L}$, headway $h^\ell$ can be calculated by $h^\ell = \frac{T^\ell}{n^\ell}$, where $T^\ell$ represents the round trip time along the entire line, and $n^\ell$ denotes the number of vehicles operating on that line (Eq. 4.4 of (Vuchic, Clarke, and Molinero 1981)). Let $t^\ell$ denote the one-way travel time from the origin terminal to the destination terminal of line $\ell$, the round-trip cycle time is $T^\ell = 2t^\ell$. Accordingly, the headway of line $\ell$ is given by $h^\ell = \frac{2t^\ell}{n^\ell}$. We use a fixed dwell time $d$, at each stop to account for the time a bus spends at a stop, including the time needed for passengers to board and alight, and the time lost for accelerating and decelerating. While in practice dwell times may depend on passenger volumes, for simplicity and in line with PT network design models (Huynh and Barthelemy 2022, Chen, Li, and Qu 2022), we assume a constant $d$. Assuming random passenger arrivals, the average waiting time for line $\ell$ is given by

$$w^\ell = \frac{h^\ell}{2}, \text{ where } h^\ell \text{ denotes the service headway of line } \ell. \qquad (1)$$

This assumption is standard in public transport modeling (Parbo, Nielsen, and Prato 2018, Zhang, Wang, and Meng 2018). Liu and Miller (2020) confirm that such an assumption is appropriate when the headway is relatively small (see their § 3.3.1), and passengers simply go at the stop as soon as possible, without explicitly synchronizing at specific PT departure times; they also show that such a simple behavior is most time the most convenient for users, even better than a more complicated possible user strategies. For a transfer at stop $i$ from line $\ell$ to line $\ell'$, the expected waiting time is therefore $w^{\ell'} = \frac{h^{\ell'}}{2}$, consistent with the waiting-time formulation in (1).

### 3.1.1 Virtual Node-Based Transfer Model

To model passenger route choice, we construct an auxiliary directed graph $G^{\text{PAX}} = (V^{\text{PAX}}, \mathcal{E}^{\text{PAX}})$. The node set $V^{\text{PAX}}$ comprises physical stop nodes $i \in V^{\text{sub}}$ and line-specific virtual nodes $v_i^\ell$ for each line $\ell$ serving stop $i$. As illustrated in Fig. 2, yellow nodes denote physical stops, while colored nodes represent line-specific virtual nodes; connections between colored nodes indicate potential passenger transfers. The edge set $\mathcal{E}^{\text{PAX}}$ incorporates three distinct directed link types, each associated with a specific temporal cost. (1) **In-vehicle edges:** Connect virtual nodes $v_i^\ell$ and $v_j^\ell$ along the same line $\ell$. Their weights represent in-vehicle travel times. (2) **Transfer edges:** Connect virtual nodes of different lines (e.g., $v_i^\ell$ to $v_i^{\ell'}$) at the same physical node. (3) **Access edges:** Connect physical nodes to virtual nodes (e.g., $i$ to $v_i^\ell$). These represent initial
<figure><img src="image_3.png" /><figcaption>Figure 2: Example of a four-station PT network with asymmetric routes.</figcaption></figure>

boarding waiting times. The weights of (2) and (3) correspond to passenger waiting times, which are defined in (1) in § 3.1. Transfer edges are not created at origin or destination nodes.

## 3.2 Stochastic Modeling of Travel Times

Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space. For the sake of realism, we model the aforementioned bus travel times $t_{ij}$ from stop $i$ to stop $j$, for each edge $(i, j) \in \mathcal{E}^{\text{sub}}$, at a given time of day, as random variables. For simplicity, we omit explicitly specifying the time of day in the notation. Let $t_{ij}^{\omega}, \omega \in \Omega$ denote a realization of this variable. This is the travel time we would measure if we take a snapshot of the network at a certain point in time. Observe that, if we take another snapshot (at the same time of day, but in another day), we would observe another travel time $t_{ij}^{\omega'}$, corresponding to another realization of variable $t_{ij}$. We assume that a prediction model provides predictions $\hat{t}_{ij}$ for each edge. If the prediction model were “perfect”, for every sample $\omega \in \Omega$, the realizations would satisfy $\hat{t}_{ij}^{\omega} = t_{ij}^{\omega'}, \forall \omega \in \Omega, (i, j) \in \mathcal{E}^{\text{sub}}$. This is obviously impossible in reality, as any realistic prediction model is subject to some errors. Let the prediction error (which is another random variable) be:

$$ \epsilon_{ij} \stackrel{\text{def}}{=} \hat{t}_{ij} - t_{ij} \qquad (2) $$

whereas $t_{ij}$ and $\hat{t}_{ij}$ denote the realized and predicted travel times, respectively. Let $e_{ij}^{\ell}$ indicate whether edge $(i, j)$ is used by line $\ell$. The time from one terminal to the other on line $\ell$ is:

$$ t^{\ell} = \underbrace{\sum_{i \in \mathcal{N}} \sum_{j \in \mathcal{N}} t_{ij} e_{ij}^{\ell}}_{\text{in-vehicle travel time}} + d \cdot \underbrace{\left( \sum_{i \in \mathcal{N}} \sum_{j \in \mathcal{N}} e_{ij}^{\ell} - 1 \right)}_{\text{dwell time at stops}} \qquad (3) $$

Here, $d$ denotes a fixed dwell time per stop. Since the actual link travel times $t_{ij}$ for edge $(i, j)$ are inherently uncertain, the true line travel time $t^{\ell}$ cannot be determined a priori. We can only calculate a “predicted” $\hat{t}^{\ell}$, obtained by replacing $t_{ij}$ with $\hat{t}_{ij}$ in (3).

## 3.3 Trip Travel Times

Let $\mathcal{G}^{\text{sub}}$ and $\mathcal{G}_{\text{PT}}$ denote the substrate and public transport (PT) graphs, respectively (§3.1). Each OD pair $k \in \mathcal{K}$ is defined by an origin stop $o_k \in \mathcal{V}^{\text{sub}}$ and a destination stop $d_k \in \mathcal{V}^{\text{sub}}$. We assume origins and destinations are both stops, since we take responsibility of user trips from the moment they enter PT to the moment they exit, as considered in recent graph-based public transport modeling studies (Zhao et al. 2024).
<table><caption>Table 1: Notation for PT Network Re-Design Problem</caption><thead><tr><th>Symbol</th><th>Description</th></tr></thead><tbody><tr><td colspan="2"><strong>Sets:</strong></td></tr><tr><td><i>N</i></td><td>Set of nodes, indexed by <i>i, j</i> ∈ <i>N</i></td></tr><tr><td><i>L</i></td><td>Set of PT lines, indexed by <i>l</i> ∈ <i>L</i></td></tr><tr><td><i>K</i></td><td>Set of origin-destination pairs, indexed by <i>k</i> ∈ <i>K</i></td></tr><tr><td><i>E</i></td><td>Set of feasible edges in the network, indexed by (<i>i, j</i>) ∈ <i>E</i></td></tr><tr><td colspan="2"><strong>Parameters:</strong></td></tr><tr><td><i>q</i><sub><i>k</i></sub> ∈ <i>N</i>, <i>k</i> ∈ <i>K</i></td><td>Demand for OD pair <i>k</i> (passengers) - §3.4.2.</td></tr><tr><td><i>t</i><sub><i>ij</i></sub> ∈ <i>R</i><sub>+</sub>, (<i>i, j</i>) ∈ <i>E</i>; <i>t</i><sup><i>ω</i></sup><sub><i>ij</i></sub>, (<i>i, j</i>) ∈ <i>E</i>, <i>ω</i> ∈ <i>Ω</i></td><td><i>t</i><sub><i>ij</i></sub> is the true travel time on link (<i>i, j</i>); this is a random variables; we denote its realizations as <i>t</i><sup><i>ω</i></sup><sub><i>ij</i></sub> - §3.2.</td></tr><tr><td><i>t</i><sup>0</sup><sub><i>ij</i></sub> ∈ <i>R</i><sub>+</sub>, (<i>i, j</i>) ∈ <i>E</i></td><td>Baseline link time (the ones referred to nominal conditions) - §3.3.</td></tr><tr><td><i>t̂</i><sub><i>ij</i></sub> ∈ <i>R</i><sub>+</sub>, (<i>i, j</i>) ∈ <i>E</i></td><td>Predicted travel time on link (<i>i, j</i>) - §3.4.2.</td></tr><tr><td><i>t</i><sup>0</sup><sub><i>k</i></sub> ∈ <i>R</i><sub>+</sub>, <i>k</i> ∈ <i>K</i></td><td>Baseline trip travel time: travel time for OD pair <i>k</i> in the original network design <i>G</i><sup>org</sup><sub>PT</sub> under nominal (unperturbed) conditions - §3.3.</td></tr><tr><td><i>o</i><sub><i>k</i></sub>, <i>d</i><sub><i>k</i></sub> ∈ <i>N</i>, <i>k</i> ∈ <i>K</i></td><td>Origin and destination node of OD pair <i>k</i> - §3.3.</td></tr><tr><td><i>e</i><sup><i>l, 0</i></sup><sub><i>ij</i></sub> ∈ {0, 1}, <i>i, j</i> ∈ <i>N</i>, <i>l</i> ∈ <i>L</i></td><td>Original network configuration (1 if link (<i>i, j</i>) is used by line <i>l</i>) - §3.4.2</td></tr><tr><td><i>M</i>, <i>d</i> ∈ <i>R</i><sub>+</sub></td><td>Large constant, Fixed dwell time</td></tr><tr><td colspan="2"><strong>Upper-level decision variables (network design):</strong></td></tr><tr><td colspan="2">Binary Variables:</td></tr><tr><td><i>y</i><sup><i>l</i></sup>, <i>l</i> ∈ <i>L</i></td><td>1 if line <i>l</i> is activated (operated)</td></tr><tr><td><i>e</i><sup><i>l</i></sup><sub><i>ij</i></sub>, <i>i, j</i> ∈ <i>N</i>, <i>l</i> ∈ <i>L</i></td><td>1 if edge (<i>i, j</i>) is used by line <i>l</i> in new network</td></tr><tr><td><i>a</i><sup><i>l</i></sup><sub><i>i</i></sub>, <i>b</i><sup><i>l</i></sup><sub><i>i</i></sub>, <i>i</i> ∈ <i>N</i>, <i>l</i> ∈ <i>L</i></td><td>1 if node <i>i</i> is the start/end terminal of line <i>l</i></td></tr><tr><td colspan="2">Discrete or Continuous Variables:</td></tr><tr><td><i>n</i><sup><i>l</i></sup> ∈ <i>N</i>, <i>l</i> ∈ <i>L</i></td><td>Number of vehicles on line <i>l</i> (fleet size)</td></tr><tr><td><i>u</i><sup><i>l</i></sup><sub><i>i</i></sub> ∈ <i>N</i>, <i>i</i> ∈ <i>N</i>, <i>l</i> ∈ <i>L</i></td><td>Auxiliary variable for subtour elimination (MTZ): it denotes the order in which stop <i>i</i> appears in line <i>l</i>.</td></tr><tr><td><i>ŵ</i><sup><i>l</i></sup> ∈ <i>R</i><sub>+</sub>, <i>l</i> ∈ <i>L</i></td><td>Average waiting time for line <i>l</i></td></tr><tr><td><i>t̂</i><sup><i>l</i></sup> ∈ <i>R</i><sub>+</sub>, <i>l</i> ∈ <i>L</i></td><td>Travel time from one terminal to the other on line <i>l</i></td></tr><tr><td colspan="2"><strong>Induced quantities (passenger assignment outputs):</strong></td></tr><tr><td><i>p</i><sup><i>k,l</i></sup><sub><i>ij</i></sub> ∈ {0, 1}</td><td>1 if OD pair <i>k</i> traverses arc (<i>i, j</i>) using line <i>l</i></td></tr><tr><td><i>t̂</i><sub><i>k</i></sub> ∈ <i>R</i><sub>+</sub>, <i>k</i> ∈ <i>K</i></td><td>Travel time of OD pair <i>k</i></td></tr></tbody></table>
**Assumption 1 (Deterministic Shortest-Path Passenger Routing).** Given a fixed PT network design, including line structures ($e_{ij}^\ell, a_i^\ell, b_i^\ell$) and fleet allocations $n^\ell$, passengers are assumed to behave rationally and select routes that minimize their individual travel time on the designed PT network (Goerigk and Schmidt 2017, Schöbel and Urban 2022). Under this behavioral assumption with additive link costs, OD paths are induced by the design and can be computed via shortest-path algorithms.

For any network configuration $\mathcal{G}_{\text{PT}}$ and any realization $\omega \in \Omega$, each link $(i,j)$ can be traversed in time $t_{ij}^\omega$. Based on such values, we compute shortest paths for any OD pair $k \in \mathcal{K}$ and denote the trip travel time as $t_k^\omega$. Note that $t_k^\omega$ includes (i) in-vehicle travel times, (ii) dwell times, (iii) initial waiting times, and (iv) transfer waiting times, according to §3.1.1. Let $t_{ij}$ be the random variable with realizations $t_{ij}^\omega, \omega \in \Omega$. To formalize these paths, we define binary dependent variables $p_{ij}^{k\ell,\omega}$ indicating whether arc $(i,j)$ on line $\ell$ belongs to the shortest path for OD pair $k$ in realization $\omega \in \Omega$. These variables are uniquely determined by the network state and computed algorithmically (§4) rather than being direct decision variables.

Let $\mathcal{G}_{\text{PT}}^{\text{org}}$ denote the original PT network, i.e., "master" schedule of PT over a typical day of operation. Classically, this is the network that will be operated every day. We instead allow adaptation, which means that the PT line network at a certain time is $\mathcal{G}_{\text{PT}}$, which may or may not correspond to the original one (Fig. 1). In our framework, three notions of OD travel time are defined: (i) the actual travel time $t_k$, described in the paragraph above; we consider its realizations when evaluating the performance of our method. (ii) the predicted travel time $\hat{t}_k$, computed as the sum of the predicted link times $\hat{t}_{ij}$ along the shortest paths described in the paragraph above; we use these predicted values as input parameters of optimization (5)-(14); (iii) the baseline travel time $t_k^0$, defined as the OD travel time on the original network design $\mathcal{G}_{\text{PT}}^{\text{org}}$ under baseline link times $t_{ij}^0, \forall (i, j \in \mathcal{E})$.

## 3.4 Problem Statement

This research tackles the optimization of public transport lines in real time to adapt to fluctuating and unknown road conditions. The proposed optimization method has three complementary objectives: (i) minimizing user cost by reducing trip travel time deterioration due to fluctuations of substrate link times, with respect to the nominal ones (resulting in changes of actual travel time $t_k$ experienced on OD pair $k$, relative to the baseline travel time experienced in the original network, which we denote as $t_k^0$), (ii) lowering operator costs represented by total vehicle-hours traveled by the fleet of buses, and (iii) avoiding excessive changes in the PT network compared to the original to improve operational manageability and prevent user disorientation.

Our optimization problem addresses the following three decision problems: (a) how to dynamically modify PT lines (line topology, fleet allocation, headways) to adapt to actual road conditions when they severely deviate from the expected ones? (b) which route should we make available for users to travel among OD pairs? and (c) where to locate the terminals of each line?
### 3.4.1 Timeframe and Stability Considerations

Reconfiguring PT lines may affect users and operators in distinct ways.

For passengers, changes in routes can reduce perceived regularity and predictability. First, we assume that smartphone navigation apps are available to provide passengers with the best itinerary on the current PT network, so that they can navigate the reconfigured network structure. This is in line with real-world observations, where navigation apps are increasingly used (Federal Highway Administration 2016) and more and more passengers rely on them (Duran et al. 2024). Ghahramani and Brakewood (2016, p 147) report that 80% of New York PT passengers use those apps twice or more in one day. Li and Shalaby (2024) show that “people seek out transit information the most during times of uncertainty” to find their best itinerary. In addition to the availability of smartphone apps, behavioral trends of PT users suggest that they could be willing to adapt their trips to reconfigured network structures if this would allow them to arrive at their destination more efficiently. Indeed, empirical evidence suggests that passengers operate a trade-off between efficiency and regularity (Devarasetty, Burris, and Shaw 2012). Specifically, some travelers may prefer an alternative path that ensures on-time arrival over a habitual route that, under adverse traffic conditions on a given day, results in delay. In this sense, deviations from regular routes are not necessarily detrimental if they yield tangible gains in travel time reliability.

For the operator, frequently updated itineraries may increase cognitive load on the drivers. Nonetheless, in practice, several agencies operate services with “route deviation”, in which vehicles may depart from established routes, within a defined area (National Rural Transit Assistance Program (National RTAP) 2024). The definition of such an area is needed for liability reasons, but it lies outside the scope of this work (we thus assume that the operating areas have been defined ex-ante). Moreover, in the future, vehicle automation will further ease PT line reconfiguration by removing the barrier of the additional driver cognitive overload, thanks to the possibility of central vehicle dispatching (Fagnant and Kockelman 2015).

Although PT line reconfiguration is implementable, PT lines are more easily manageable if disruptive reconfigurations are limited. For this reason, we measure structural stability using the Jaccard index (Jaccard 1901), defined for the edge sets of the original and redesigned networks as

$$J(\mathcal{E}_{\text{orig}}, \mathcal{E}_{\text{new}}) = \frac{|\mathcal{E}_{\text{orig}} \cap \mathcal{E}_{\text{new}}|}{|\mathcal{E}_{\text{orig}} \cup \mathcal{E}_{\text{new}}|} \in [0, 1]. \quad (4)$$

It provides a simple, system-wide measure of overlap and has been shown to be particularly effective in sparse networks (Travieso, Benatti, and Costa 2024), which reflect typical PT topologies. Unlike sequence-based metrics such as edit distance (Cheng et al. 2025), which focus on local route alignment and scale poorly in multi-line systems (Jain et al. 2024), the Jaccard index offers a tractable, network-level notion of similarity that directly matches our design objectives. We assume access to a short-term traffic prediction module, as is often the case in urban operations (e.g. Metropolitan Transportation Authority (MTA) (2026), Transport for London (TfL) (2026)), and focus on the subsequent optimization step. As shown in Fig. 1, we consider an hourly monitoring policy: if average relative deviation $(1/|\mathcal{E}^{\text{sub}}|) \sum_{(i,j) \in \mathcal{E}^{\text{sub}}} |\hat{t}_{ij} - t_{ij}^0|/t_{ij}^0$ remain within a tolerance (e.g., 0.1), the network is kept unchanged or reset to the original configuration.
ration to avoid accumulated drift; larger deviations trigger a redesign. This selective updating strategy preserves temporal consistency while facilitating response to fluctuating traffic conditions. Moreover, deciding reconfigurations (when needed) always 1 hour in advance, gives the operator and drivers the needed time to adapt.

The Jaccard distance inherently prevents abrupt structural jumps between consecutive re-designs. Specifically, if redesigned public transport (PT) network $G_{PT}^{(k)}$ at each time interval $k$ remains sufficiently similar to the original configuration $G_{PT}^{(0)}$, the pairwise similarity between successive redesigns $G_{PT}^{(k)}$ and $G_{PT}^{(k+1)}$ is ensured to be bounded from below.

**Proposition 1.** Let $\mathcal{E}^{(k)}$ denote the set of active edges in the redesigned network at step $k$, and analogously $\mathcal{E}^{(0)}$ for the original network and $\mathcal{E}^{(k+1)}$ for the next redesign. Then, for any consecutive redesigns $k$ and $k+1$, it holds that

$$J(\mathcal{E}^{(k)}, \mathcal{E}^{(k+1)}) \geq J(\mathcal{E}^{(k)}, \mathcal{E}^{(0)}) + J(\mathcal{E}^{(k+1)}, \mathcal{E}^{(0)}) - 1.$$

The proof is provided in App. B.

### 3.4.2 Objective Functions

We formulate our public transport network adaptation problem as a three-objective optimization, as expressed in (5). The first objective, $Z_1$, minimizes passenger travel time deterioration, where $q_k$ represents the travel demand flow. The use of $\max(\hat{t}_k - t_k^0, 0)$ guarantees that only travel-time increases relative to the nominal benchmark are penalized, thereby avoiding situations where improvements for certain OD pairs compensate for deterioration in others. The second objective $Z_2$ minimizes operational costs through total vehicle-hours. The third objective $Z_3$ minimizes network structural changes using the Jaccard index (§ 3.4.1), calculated as the ratio between the number of shared edges (i.e., those present both in the original and in the re-designed network) and the total number of edges (i.e., the union of the edges in the two networks).

$$\min_{G_{PT}^{\text{adpt}}} \left( \begin{array}{c} Z_1 \\ Z_2 \\ Z_3 \end{array} \right) = \left( \begin{array}{c} \underbrace{\sum_{k \in \mathcal{K}} q_k \cdot \max(\hat{t}_k - t_k^0, 0)}_{\text{Passenger travel time deterioration}} \\ \underbrace{\sum_{\ell \in \mathcal{L}} n^\ell \cdot 2\hat{t}^\ell}_{\text{Total vehicle-hours (operating cost)}} \\ \underbrace{1 - \frac{\sum_{\ell \in \mathcal{L}} \sum_{(i,j) \in \mathcal{E}} \min(e_{ij}^\ell, e_{ij}^{\ell,0})}{\sum_{\ell \in \mathcal{L}} \sum_{(i,j) \in \mathcal{E}} \max(e_{ij}^\ell, e_{ij}^{\ell,0})}}_{\text{Route dissimilarity}} \end{array} \right) \quad (5)$$

In (5), $e_{ij}^{\ell,0}$ and $e_{ij}^\ell$ denote whether line $\ell$ uses substrate link $(i, j)$ in the original and the redesigned network, respectively. Observe that $e_{ij}^{\ell,0}$ are parameters of our problem, whereas $e_{ij}^\ell$ are decision variables. Observe that when solving our optimization problem, the realized link travel times $t_{ij}$ are not available, we will thus optimize the decision variables based on prediction
$\hat{t}_{ij}$ and then evaluate, ex-post in the results, the objective function evaluated using the realized link travel times $t_{ij}$

### 3.4.3 Constraints

We now report the constraints that, together with the objective (5), formalize the upper-level network design problem. Passenger route variables are treated as induced (follower) variables and are discussed separately.

**Performance-Related Constraints (1) and (3).**

**Line Structure Constraints**

$$ \sum_{i \in \mathcal{N}} a_i^\ell = y^\ell, \quad \sum_{i \in \mathcal{N}} b_i^\ell = y^\ell \qquad \forall \ell \in \mathcal{L} \qquad (6) $$

$$ a_i^\ell + b_i^\ell \le 1 \qquad \forall i \in \mathcal{N}, \forall \ell \in \mathcal{L} \qquad (7) $$

$$ e_{ij}^\ell + e_{ji}^\ell \le y^\ell \qquad \forall \{i, j\} \in \mathcal{E}, \forall \ell \in \mathcal{L} \qquad (8) $$

$$ \sum_{j:\{i,j\} \in \mathcal{E}} e_{ji}^\ell + a_i^\ell = \sum_{j:\{i,j\} \in \mathcal{E}} e_{ij}^\ell + b_i^\ell \qquad \forall i \in \mathcal{N}, \forall \ell \in \mathcal{L} \qquad (9) $$

$$ \sum_{j:\{i,j\} \in \mathcal{E}} e_{ij}^\ell \le 1, \quad \sum_{j:\{i,j\} \in \mathcal{E}} e_{ji}^\ell \le 1 \qquad \forall i \in \mathcal{N}, \forall \ell \in \mathcal{L} \qquad (10) $$

$$ u_i^\ell - u_j^\ell + 1 \le |\mathcal{N}|(1 - e_{ij}^\ell) \qquad \forall \{i, j\} \in \mathcal{E}, \forall \ell \in \mathcal{L} \qquad (11) $$

$$ 1 \le u_i^\ell \le |\mathcal{N}| \qquad \forall i \in \mathcal{N}, \forall \ell \in \mathcal{L} \qquad (12) $$

$$ n^\ell \ge y^\ell, \quad n^\ell \le \bar{n} y^\ell \qquad \forall \ell \in \mathcal{L} \qquad (13) $$

$$ \sum_{\ell \in \mathcal{L}} n^\ell \le V_{\max} \qquad (14) $$

Constraints (6)–(14) establish the topological structure and operational limits of the designed network. Constraints (6)–(7) synchronize line activation with terminal selection, mandating that every active line ($y^\ell = 1$) connects exactly one initial terminal to one final terminal, thereby preventing zero-length loops. Constraint (8) ensures that if a line is not activated ($y^\ell = 0$), there are no links associated to it. Otherwise, it ensures that the line is constructed in one direction (links $(i, j)$ and $(j, i)$ cannot be both selected) and then buses go back and forth along it (as specified in page 7). Route continuity and linearity are enforced by the flow conservation in (9) combined with the degree Constraints in (10); the latter restrict nodes to a maximum of one predecessor and one successor, strictly imposing a non-branching simple path topology. Acyclic integrity is further guaranteed by Constraints (11)–(12), which adapt the Miller-Tucker-Zemlin (MTZ) formulation to eliminate disconnected subtours that might otherwise satisfy flow balance: if link $(i, j)$ is used in line $\ell$, then node $j$ should appear after $i$ along the line (its order of appearance ($u_j$) must be higher than $i$). Finally, resource allocation is governed by Constraints (13)–(14), which assign vehicles only to active lines and enforce the global fleet budget.

**Induced Passenger Paths.** Passenger routes are not decision variables of the network design problem. Given a fixed network design $(e, n)$, passenger paths for each OD pair $k \in \mathcal{K}$
<figure><img src="image_4.png" /><figcaption>Figure 3: Flowchart of the Proposed NSGA-III-based optimization method.</figcaption></figure>

are deterministically induced by solving a shortest-path problem on the auxiliary passenger graph $G^{PAX}$ defined in §3.1.1. Let $\hat{t}_k$ denote the resulting shortest-path travel time under predicted link costs $\hat{t}_{ij}$. For bookkeeping and interpretation, we also define $p_{ij}^{k\ell} \in \{0,1\}$ as an induced indicator equal to one if the shortest path for OD pair $k$ traverses arc $(i,j)$ on line $\ell$, and zero otherwise. Accordingly, $\hat{t}_k$ can be expressed as the sum of the costs of the traversed arcs (including in-vehicle, dwell, access, and transfer components) on $G^{PAX}$. These induced quantities are computed algorithmically and are not part of the optimization decision set.

# 4 Solution Algorithm

The optimization model presented in § 3 is a mixed-integer formulation featuring discrete network design choices and nonlinear objective terms. While the delay penalty in $Z_1$ is piecewise linear, the fractional Jaccard objective $Z_3$ introduces nonconvexity and global variable coupling. Since an exact linearization of this ratio would require auxiliary constraints that severely compromise scalability, we retain the fractional structure. Given the tri-objective nature of the problem and the nonconvex trade-offs, we adopt an NSGA-III framework (Algorithm 1) to approximate the Pareto front. As illustrated in Fig. 3, we adopt a **design-evaluation decomposition** for computational tractability. The evolutionary search operates on network design variables (line topologies $e_{ij}^\ell$ and fleet allocations $n^\ell$). For any fixed design $(\mathbf{e}, \mathbf{n})$, passenger routing is **not** treated as an independent optimization model; instead, it is a deterministic **decode-and-assign mapping** induced by Assumption 1. Specifically, OD travel times and the corresponding assignment outputs are computed by shortest-path calculations on the virtual graph $G'$ (§3.1.1), which provides the objective values ($Z_1, Z_2, Z_3$) used by NSGA-III. Accordingly, the proposed workflow is structured into three coordinated modules: (i) **Solution Encoding and Initialization** (§ 4.1) constructs a population of structurally feasible designs; (ii) the **NSGA-III Evolutionary Loop** (§ 4.2) drives the feasible solution search, employing reference-point-based selection and variation & repair operators to evolve the topology; and
(iii) the **Decode-and-Assign Strategy** (§ 4.3) performs deterministic passenger assignment to compute the objective vector $(Z_1, Z_2, Z_3)$.

<caption>**Algorithm 1 NSGA-III based Adaptive PT Network Optimization**</caption>

**Input:** $\mathcal{G} = (\mathcal{N}, \mathcal{E})$, $\mathcal{K}$, $\mathcal{L}$, $V_{\max}$, $q_k$, $\hat{t}_{ij}$, PopSize, MaxIter, $N_{ref}$, $P_c$, $P_m$, $J_{min}$
**Output:** Approximate Pareto set $\mathcal{P}^*$
1: Initialize a population $\mathcal{P}$ of size PopSize via §4.1 and §4.2.1 (using parameter $J_{min}$)
2: Evaluate $(Z_1, Z_2, Z_3)$ for all $p \in \mathcal{P}$ via decode-and-assign (§4.3)
3: **for** iter = 1 **to** MaxIter **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;Select parents from $\mathcal{P}$ via binary tournament selection
5: &nbsp;&nbsp;&nbsp;&nbsp;Generate offspring $\mathcal{Q}$ by crossover (§4.2.2) with $P_c$ and mutation (§4.2.3) with $P_m$
6: &nbsp;&nbsp;&nbsp;&nbsp;Apply feasibility-oriented repair to offspring when line-level structural infeasibility (e.g., disconnection or discontinuity) is detected (Alg. 2)
7: &nbsp;&nbsp;&nbsp;&nbsp;Evaluate $(Z_1, Z_2, Z_3)$ for all $q \in \mathcal{Q}$ via decode-and-assign (§4.3)
8: &nbsp;&nbsp;&nbsp;&nbsp;R $\leftarrow \mathcal{P} \cup \mathcal{Q}$
9: &nbsp;&nbsp;&nbsp;&nbsp;Perform non-dominated sorting on $\mathcal{R}$
10: Apply NSGA-III selection with $N_{ref}$ reference points to obtain next $\mathcal{P}$ (§4.2.4)
11: **end for**
12: **return** the non-dominated solutions in $\mathcal{P}$ as $\mathcal{P}^*$

## 4.1 Solution Encoding

In Alg. 1, each PT line $\ell$ is represented as an ordered simple path $p_\ell = (i_1, i_2, \dots, i_{n_\ell})$ with $i_j \in \mathcal{N}$ and no repeated nodes, which enforces acyclicity by construction according to constraints (6)–(14). PT lines may either be constructed from scratch or obtained by reconstructing routes from the existing network. Starting from a current node $i$, the algorithm maintains a visited-node set $\mathcal{V}_{\text{visited}}^\ell$ and defines the set of feasible candidates as $\mathcal{N}_{\text{unvisited}}(i) = \{j \in \mathcal{N}(i) : j \notin \mathcal{V}_{\text{visited}}^\ell\}$, which is used whenever a new path segment needs to be generated. For lines constructed from scratch, the path is iteratively extended by selecting the next node $j \in \mathcal{N}_{\text{unvisited}}(i)$ according to the travel-time weighted probability

$$ \mathbb{P}(j | i) = \frac{1/t_{ij}}{\sum_{k \in \mathcal{N}_{\text{unvisited}}(i)} 1/t_{ik}}, \quad (15) $$

which favors temporally efficient connections while preserving stochastic exploration. When a line is derived from the existing network, local modifications are applied by replacing a selected route segment with an alternative feasible path that preserves the original endpoints.

Simultaneously, vehicle allocation is managed by assigning integer variables $n_\ell$ to each line. During initialization (Alg. 1, line 1), each line is pre-allocated one vehicle to guarantee basic service availability. The remaining $V_{\max} - |\mathcal{L}|$ vehicles are then distributed across lines proportionally to their initial one-way travel times $t^\ell$ (computed based on nominal link travel times $t_{ij}$).

## 4.2 Evolutionary Search Procedure

Each individual encodes a complete PT network design, comprising a set of line path representations and the associated vehicle allocations. Starting from an initial population, the algorithm evolves solutions in a generational manner. At each generation, offspring are produced through
selection, variation, and evaluation, followed by the NSGA-III reference-point-based environmental selection, which prioritizes non-dominated solutions while maintaining diversity along the Pareto front. The overall procedure is summarized in Alg. 1.

### 4.2.1 Population Initialization

During population initialization (Alg. 1, line 1), each individual is generated using the line construction rules described in § 4.1. PT lines are either constructed from scratch or obtained by locally perturbing routes reconstructed from the existing network. Given a set of lines, vehicle allocations are initialized by assigning one vehicle to each active line to guarantee basic service availability. The remaining fleet is then distributed across lines according to the chromosome encoding scheme described in § 4.1, ensuring $\sum_{\ell \in \mathcal{L}} n^\ell = V_{\max}$.

To expedite initialization, candidate solutions are screened via a connectivity check on the undirected graph induced by $\mathcal{E}_{PT} = \bigcup_{\ell \in \mathcal{L}} \mathcal{E}_\ell$, i.e., the union of all active line edges in $\mathcal{G}_{PT}$. By employing a Union-Find data structure, we efficiently identify connected components, and verify that, for every OD pair $k \in \mathcal{K}$, the origin $o_k$ and destination $d_k$ belong to the same connected component (which implies that it is possible to go from one to the other). The procedure is repeated until PopSize individuals (i.e., PT network structures) are generated that satisfy: (i) structural validity (lines are simple-paths, with no branches nor cycles), (ii) connectivity-based serviceability, i.e., all OD pairs $k \in \mathcal{K}$ are connected within $\mathcal{G}_{PT}$, and (iii) similarity, i.e., individual $\mathcal{G}_{PT}$ is not extremely different from original PT network $\mathcal{G}_{PT}^{\text{org}}$, i.e., the Jaccard similarity index (4) must be above threshold $J_{\min}$. These criteria enforce a necessary (but not sufficient) condition for OD reachability; full feasibility and network performance are subsequently evaluated using the decode-and-assign objective.

### 4.2.2 Crossover Operation

With probability $P_c$, a crossover operator is applied to two parent solutions, denoted as parents A and B. Each solution consists of a fixed set of PT lines, where each line is treated as a basic inheritance unit characterized jointly by its route topology and vehicle allocation. The crossover exchanges complete lines between parents as the primary recombination mechanism; any subsequent modifications are limited to feasibility restoration.

Line inheritance is governed by a binary selection mask $\xi = (\xi_\ell)_{\ell \in \mathcal{L}}$, where each component is independently drawn as $\xi_\ell \sim \text{Bernoulli}(0.5)$, so that both parents are treated symmetrically and structural diversity is promoted at the line level. Given $\xi$, the offspring design is defined by block-wise inheritance:

$$ (e_{ij}^{\ell})^{\text{off}} = \xi_{\ell}(e_{ij}^{\ell})^{A} + (1 - \xi_{\ell})(e_{ij}^{\ell})^{B}, \quad \forall \ell \in \mathcal{L}, (i, j) \in \mathcal{E}, \quad (16) $$

$$ (n^{\ell})^{\text{off}} = \xi_{\ell}(n^{\ell})^{A} + (1 - \xi_{\ell})(n^{\ell})^{B}, \quad \forall \ell \in \mathcal{L}. \quad (17) $$

Whenever a line topology is inherited from a parent, its vehicle allocation is inherited jointly, thereby preserving the coupling between route geometry and service frequency.

If any inherited line becomes structurally infeasible (e.g., disconnected or discontinuous), a feasibility-oriented restoration operator is applied to recover a valid simple-path representation
(Alg. 2). Finally, fleet constraints ($n^\ell \ge 1$ for all active lines and $\sum_{\ell \in \mathcal{L}} n^\ell = V_{\max}$) are enforced via minimal $\pm 1$ adjustments on a small subset of lines. This correction is a feasibility projection and is not guided by objective improvement.

### 4.2.3 Mutation Operation

With probability $P_m$, a mutation perturbs a single line $\ell$ via local structural modifications, including node insertion, node deletion, or segment reconnection. These operations introduce stochastic variations in line topology while preserving the overall chromosome structure. If the mutation results in a disconnected or discontinuous line, feasibility is restored by reconnecting the affected segments (Alg. 2). This repair step is feasibility-oriented and does not explicitly consider objective values. Finally, global fleet conservation ($\sum_{\ell \in \mathcal{L}} n^\ell = V_{\max}$) is enforced in the same manner as described in § 4.2.2.

### 4.2.4 Environmental Selection

After offspring generation, parent and offspring populations are merged and ranked via non-dominated sorting. Environmental selection follows the standard NSGA-III mechanism, employing a set of reference points $N_{\text{ref}}$ to maintain population diversity (Deb and Jain 2014). The implementation details are provided in App. D.3.

## 4.3 Objective Evaluation via Decode-and-Assign

The evaluation phase (Alg. 1, line 7) maps each chromosome into the objective space through a systematic decode-and-assign procedure. Following Assumption 1, we treat passenger routing as a deterministic response to the network configuration, thereby decoupling routing behavior from the upper-level network design decisions. For each individual, the algorithm first constructs a comprehensive virtual-node graph $\mathcal{G}'$ that integrates in-vehicle travel times and waiting times $w^\ell$, the latter being derived from the allocated vehicle units $n^\ell$ (§ 3.1.1). To evaluate the travel-time deterioration $Z_1$, the algorithm solves a shortest-path problem (Dijkstra) for every OD pair $(o_k, d_k) \in \mathcal{K}$ on $\mathcal{G}'$. The resulting shortest path yields the predicted OD travel time $\hat{t}_k$. Feasibility is enforced by construction: $\mathcal{G}'$ includes only arcs corresponding to active line segments in the decoded network design, and OD paths are initialized through access/egress connections between physical stops and their associated line-specific virtual nodes (§3.1.1). This shortest-path evaluation is performed for each candidate network, consistently reflecting the current decoded topology and headways. Simultaneously, the operational cost $Z_2$ and network dissimilarity $Z_3$ are computed. Specifically, $Z_3$ is quantified using a line-specific Jaccard similarity, where each network element is defined as a triplet $(\min(i, j), \max(i, j), \ell)$. This representation ensures that identical physical links served by different lines are treated as distinct entities, accurately capturing the topological shifts in the service network.
# 5 Evaluation Method

In order to test if our real-time PT re-design method would perform well in a realistic situation with realistic uncertain fluctuations of link times, we need to tackle the following two challenges: (i) link travel times are inherently stochastic, and (ii) re-design decisions are based on travel time predictions, which might deviate from the true ones. To account for (i), we generate stochastic travel times for all links, with different levels of variability (§ 5.1). To account for (ii), we then generate, in § 5.2, prediction errors $\epsilon_{ij}, \forall (i, j) \in \mathcal{E}^{\text{sub}}$, statistically representative of the level of inaccuracy of well established prediction models (we consider Diffusion Convolutional Recurrent Neural Network (DCRNN) - see §5.2).

## 5.1 Model of Travel Time

To account for the variability in travel times, we model them as random variables, according to § 3.2. The shape we choose for this random variable is a log-normal distribution, which effectively captures the skewed nature of travel time data (Guessous et al. 2014) and accounts for extreme delay scenarios that can occur in reality, although not often. On each link $(i, j)$, we generate travel time realization $t_{ij}^{\omega}$ by performing Monte-Carlo sampling from random variable $t_{ij} \sim \text{log-normal}(\mu_{ij}, \sigma_{ij}^2)$ such that the median of $t_{ij}$ corresponds to the nominal time reported in the Mandl's dataset, and the coefficient of variation (cv) matches a predetermined value: we test $cv = 0.05, 0.25, 0.5, 1.0$. To test the performance of our optimization when faced with different levels of hypothetical traffic variability, for each cv, we generate a set of samples $\Omega_{cv}$, where each sample $\omega \in \Omega_{cv}$ corresponds to a collection of travel times $\{t_{ij}^{cv,\omega} \mid (i, j) \in \mathcal{E}^{\text{sub}}\}$ across the network. The details on how we translate means and coefficient of variations into the parameters of log-normal distributions are in App. C.1.

## 5.2 Travel Time Prediction with KDE-Based Error Modelling

Recall that our re-design method is based on predicted travel times (the input parameters of the optimization problem in § 3.4 are predicted link travel times $\hat{t}_{ij}$ rather than the true values $t_{ij}$, which are unknown in practice). We therefore need to evaluate whether the resulting decisions remain satisfactory despite the inevitable prediction errors $\epsilon_{ij} \stackrel{\text{def}}{=} \hat{t}_{ij} - t_{ij}$.

Recall from § 3.2 that prediction errors are modeled as random variables. We generate them through a three-stage procedure:

* In **Stage 1** (see § 5.2.1), we train a prediction model to predict link travel times.

* In **Stage 2** (see § 5.2.1), we use the trained model to predict new travel times and we collect the corresponding error samples.

* In **Stage 3** (see § 5.2.2), we estimate the error probability distribution using the collected error samples via Kernel Density Estimation (KDE).

As for the prediction model in Stage 1, we adopted Diffusion Convolutional Recurrent Neural Network (DCRNN) (Li et al. 2017), since it is a well-established spatiotemporal model that captures both spatial diffusion and temporal dynamics. Recall that our goal is not to achieve
state-of-the-art forecasting accuracy, but to obtain realistic and structurally coherent prediction errors for subsequent stochastic modeling. This is why comparing many different predictive models is out of the scope. Obviously, better predictions will improve the quality of our decisions, without altering either the workflow or the conclusions of our framework. In this sense, the adoption of DCRNN yields a conservative evaluation.

### 5.2.1 Stage 1 and 2: Prediction model and error generation

We train a Diffusion Convolutional Recurrent Neural Network (DCRNN). Due to the absence of historical traffic data for Mandl's Swiss network, the DCRNN is trained on the METR-LA dataset (Li et al. 2017), which contains traffic speed measurements from 207 sensors in Los Angeles County collected at 5-minute intervals over four months. Although METR-LA is a different network from Mandl's, we apply the error patterns derived via DCRNN in the METR-LA to our Mandl's network, as a practical way to reproduce the realistic errors of predictive models. This approximation does not affect the methodological validity of the presented approach, which focuses on optimization under uncertainty rather than on predicting models' accuracy. For the real-world Beijing case study, instead, we utilize the Q-Traffic dataset (Liao et al. 2018), which provides traffic speed and road network data for the 6th Ring Road in Beijing, China.

Post-training, we collect the 1-hour-ahead speed predictions in each link $(i, j) \in \mathcal{E}$ and the corresponding errors $\epsilon_{ij}$. Training details and error collection methodology are provided in App. C.2.

### 5.2.2 Stage 3: KDE modeling of prediction errors

Following the framework of (Peled et al. 2021), we model travel-time prediction errors as stochastic inputs to the network optimization problem. While Peled et al. (2021) relies on pre-specified parametric noise distri butions, we instead adopt a data-driven, non-parametric approach based on Kernel Density Estimation (KDE) to characterize prediction errors. In particular, instead of assuming a Gaussian or Weibull prediction error shape as in Peled et al. (2021), we obtain prediction errors from an actual predicting model and fit their distribution using Kernel Density Estimation (Chen 2017), thereby modeling errors without any distributional assumptions (Akritas and Van Keilegom 2001). App. C.3 details the implementation of fitting methods and confirms the superiority of KDE through evaluations.

### 5.2.3 Simulating predicted travel times

For each simulation realization $\omega \in \Omega$ and link $(i, j) \in \mathcal{E}^{\text{sub}}$, we implement a two-step process: (1) sample actual travel time $t_{ij}^{\omega}$ from the log-normal distribution of $\S 5.1$, and (2) generate prediction error $\epsilon_{ij}^{\omega}$ from the estimated error distribution (20). The resulting predicted travel time is:

$$ \hat{t}_{ij}^{\omega} = \underbrace{t_{ij}^{\omega}}_{\S 5.1} + \underbrace{\epsilon_{ij}^{\omega}}_{\S 5.2} \qquad (18) $$
# 6 Numerical Results

We evaluate the proposed adaptive public transport (PT) redesign framework on both benchmark and real-world networks.

## 6.1 Considered scenarios

Mandl's Swiss network, initially used by Mandl (1980), consisting of 15 nodes, 21 links, and a symmetric demand of 15,570 passenger trips, is employed as a canonical benchmark for comparison with existing PT network design methods (Liang, Xu, and Wang 2025, Ahern, Paz, and Corry 2022). To further assess the method's applicability under realistic operating conditions, we consider a real-world urban public transport network in a region in Beijing, China, recently analyzed by Wu et al. (2024), which comprises 301 bus stops, 3,758 road sections, and 29 bus lines. Its origin-destination demand matrix is constructed from smart card data collected during peak hours by aggregating trips between boarding station *i* and alighting station *j*.

Key parameters are set as follows: a fixed dwell time of *d* = 1 min per stop is assumed following Chen, Li, and Qu (2022). The maximum fleet size ($V_{max}$) is capped at 60 for Mandl's network, which permits relatively short headways (approximately 3–4 minutes in the resulting solutions) and enables the emergence of express-like services. For the Beijing network, $V_{max}$ is set to 1,000 to accommodate a constant 12-minute headway across this large PT system.

## 6.2 Compared PT networks

We wish to show the benefits of adapting PT network design in real-time to varying road conditions via our method, against current network design approaches, which all keep the PT structure unchanged.

For Mandl's Swiss network, the current network design approaches are represented by two networks:

* A network $G_{PT}^{static}$, generated by jointly optimizing passenger travel time ($Z_1$) and operational cost ($Z_2$) via our solution method (§ 3.4) without adaptive mechanisms (therefore the network is static).

* A state-of-the-art network design $G_{PT}^{ver}$, derived from the exact formulation of Vermeir et al. (2021).

To ensure comparability and avoid excessively short routes, for all methods we consider $|\mathcal{L}| = 3$ lines in the Mandl's network, which results in headways of about 3-4 minutes in the obtained solutions.

For the real-world Beijing network, instead, the current design approaches are represented by

* The original bus line network, denoted by $G_{PT}^{orig}$, serving as the current operational standard against which the adaptive redesign is assessed.
Across all experiments, the baseline travel time for an OD pair $k \in K$, denoted by $t_k^0$ (§3.3), is computed as the shortest-path travel time between origin $o_k$ and destination $d_k$ in either network $G_{PT}^{static}$, $G_{PT}^{ver}$, or $G_{PT}^{orig}$, depending on which one will be used as reference for comparison.

All experiments are conducted on an Intel Core i5 (4.6 GHz, 16 GB RAM) with a maximum computational time of 1h per instance, which is compatible with the decision-making timings (see Fig. 1 and §3.4.1). The values of the parameters of the proposed Alg. 1, as well as a thorough performance comparison against other multiobjective optimization methods, is extensively discussed in App. D. (To respect double-blind review requirements, all problem instances will be later made available in GitHub.)

## 6.3 Case Study Analysis

We assess the effectiveness of our method under varying degrees of travel time uncertainty through four coefficient of variation levels:

* Minimal Variation ($cv = 0.05$)

* Low Variation ($cv = 0.25$)

* Moderate Variation ($cv = 0.50$)

* High Variation ($cv = 1.00$).

To ensure statistical reliability, we evaluate the method's robustness across multiple realizations of link travel times and prediction errors, using 5 random seeds (each corresponding to a single $\omega \in \Omega$ - §3.2). Following our predict-then-optimize framework, the optimization phase utilizes predicted travel times $\hat{t}_{ij}$ to design adaptive networks, while the evaluation phase assesses actual performance using realized travel times $t_{ij}^{\omega}, \omega \in \Omega$. This separation enables us to quantify the impact of the prediction error on the quality of network adaptation.

### 6.3.1 Performance Metrics

To evaluate the adaptive network under uncertain travel times, we report three application-specific performance indicators aligned with the objectives in (5):

* **20% Improvement Share (%) (IS$_{20}$):** The percentage of OD pairs that achieve a travel time reduction of at least 20% compared to the original PT network.

* **Operational Cost Reduction (OCR):** percentage reduction in total vehicle-hours operated relative to the original PT network.

* **Route Overlap (RO):** Jaccard-based percentage overlap (4) between the edge sets of the original and adaptive PT networks.

All three metrics depend on realized travel times and are therefore random variables; in the numerical results, we report their empirical means (and 95% confidence intervals) over five independent realizations. Formal definitions are provided in App. E.
<figure><img src="image_5.png" /><figcaption>Figure 4: Inverse Cumulative Distribution of OD Pair Travel Time Improvement (Left) and the percentage of OD pairs with ≥ 20% reduction (Right) under High Variability (CV=1.0). The different curves correspond to 5 different random realizations $\omega \in \Omega$.</figcaption></figure>

### 6.3.2 Performance Comparison under Different Scenarios

To select representative compromise solutions for the Mandl network under fluctuating travel-time, we compute the solutions on the Pareto front via the proposed Alg. 1. Then, we compute the Euclidean distance from each of those solutions to an ideal point, $(\tilde{Z}_1, \tilde{Z}_2, \tilde{Z}_3)$, representing the median observed values in the Pareto front, across the three objectives of (5). The three solutions minimizing this distance are then chosen as the final candidates and are denoted as $S1, S2, S3$.

We use predicted travel times $\hat{t}_{ij}$ in Eq. (18) as input to the optimization problem, and we evaluate the resulting adaptive network against realized link travel times and prediction errors across multiple scenarios. Fig. 4 shows remarkable improvements of OD pair travel times, under high variability ($cv = 1.0$). Even with lower variability, improvements are significant. Table 2 summarizes average performance across five independent realizations. As expected, when variability is $cv = 0$, the central reference point (described in the previous paragraph) corresponds exactly to $G_{PT}^{static}$. As travel-time variability increases, both 20% Improvement Share (IS$_{20}$) and Operational Cost Reduction (OCR) rise systematically, reflecting the increasing value of adaptive redesign under highly fluctuating conditions. At low variability ($cv = 0.05$), a sizable IS$_{20}$ is still observed. This is because extreme link travel times are still possible in reality, even at low $cv$ (the possibility of such extreme values is preserved by our choice of a Log-normal distribution §5.1. For a small-scale scenario like Mandl's network, such extremes inflate original trip times $t_k^0, k \in K$. Accordingly, by exploring alternative trade-offs within the same objective space, the proposed approach can reduce passenger travel time while maintaining or improving operational costs, even in near-deterministic settings. Across all variability levels and redesign schemes, Route Overlap (RO) remains high, indicating that these improvements result from targeted adjustments rather than wholesale restructuring.

### 6.3.3 Trip Travel Time Distribution Analysis

In the following sections, we will show the performance of solution $S1$. To provide a conservative performance evaluation, we considered the “worst” realization, i.e., the seed that yielded the
<table><thead><tr><th rowspan="2">Metric</th><th colspan="3">CV=0.05</th><th colspan="3">CV=0.25</th></tr><tr><th>S1</th><th>S2</th><th>S3</th><th>S1</th><th>S2</th><th>S3</th></tr></thead><tbody><tr><td>20% improvement share (%)</td><td>3.42 ± 2.54</td><td>3.82 ± 2.27</td><td>4.42 ± 4.38</td><td>21.86 ± 10.51</td><td>19.08 ± 11.22</td><td>18.84 ± 11.01</td></tr><tr><td>Op. Cost Red. (%)</td><td>7.31 ± 8.33</td><td>9.99 ± 7.20</td><td>8.31 ± 7.30</td><td>11.41 ± 2.34</td><td>10.56 ± 6.80</td><td>9.33 ± 6.63</td></tr><tr><td>Route Overlap (%)</td><td>88.12 ± 6.77</td><td>82.51 ± 10.11</td><td>83.11 ± 9.70</td><td>86.51 ± 6.51</td><td>88.57 ± 5.40</td><td>90.89 ± 6.53</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">Metric</th><th colspan="3">CV=0.50</th><th colspan="3">CV=1.00</th></tr><tr><th>S1</th><th>S2</th><th>S3</th><th>S1</th><th>S2</th><th>S3</th></tr></thead><tbody><tr><td>20% improvement share (%)</td><td>32.58 ± 18.19</td><td>34.18 ± 15.96</td><td>35.60 ± 11.77</td><td>85.46 ± 9.21</td><td>85.24 ± 8.78</td><td>85.34 ± 9.59</td></tr><tr><td>Op. Cost Red. (%)</td><td>13.95 ± 9.28</td><td>19.44 ± 13.44</td><td>20.62 ± 9.26</td><td>37.34 ± 13.59</td><td>36.24 ± 13.33</td><td>37.68 ± 14.13</td></tr><tr><td>Route Overlap (%)</td><td>91.52 ± 1.67</td><td>86.41 ± 11.38</td><td>83.23 ± 13.43</td><td>84.87 ± 5.05</td><td>85.98 ± 3.25</td><td>84.87 ± 5.05</td></tr></tbody></table>

20% improvement share. (IS$^{20%}$): fraction of Passengers whose travel Time Improvement is at least 20%; Op. Cost Red. (OCR): Operational Cost Reduction. Entries report mean ± 95% confidence interval over 5 realizations.

<figure><img src="image_6.png" /><figcaption>Figure 5: Trip Time Distribution Comparison Under Various Variability Conditions in a randomly chosen realization.</figcaption></figure>

worst results in terms of the metrics of Table 2. Fig. 5 illustrates trip time distributions across varying coefficients of variation (cv). It highlights the benefits of our adaptive public transport planning method, as travel time uncertainty increases from minimal to high levels, against current network design approaches, represented by the original static network $G_{PT}^{static}$ and Vermeir's network $G_{PT}^{ver}$, in accordance to §6.2. At low variability levels (cv=0.05), less than 50% of OD pairs improve their travel time. This occurs because these static networks are already well-optimized for stable conditions, leaving little room for enhancement. Moreover, our optimization operates on predicted travel times that inevitably include errors. This is why, as illustrated in Fig. 1, we would not trigger any reconfiguration, faced with minor fluctuations in link travel times, such as those experienced with cv = 0.05.

However, as variability increases, the benefits of our approach ($G_{PT}^{adpt}$) become pronounced. For instance, under high uncertainty (cv=1.0), our adaptive network $G_{PT}^{adpt}$ improves by at least 30% the travel time of at least 40% of travelers compared to both $G_{PT}^{static}$ and $G_{PT}^{ver}$. This confirms the superiority of our proactive network redesign against current approaches, all keeping the network unchanged, in particular in highly fluctuating conditions.
<table><caption>Table 3: Performance comparison under varying travel-time variability based on Beijing Network.</caption><thead><tr><th>Coeff. of variation (CV)</th><th>Avg. Route Overlap (%)</th><th>Avg. Operational Cost Reduction (%)</th><th>Avg. Travel Time Improvement (%)</th></tr></thead><tbody><tr><td>0.00</td><td>90.12</td><td>6.10</td><td>11.68</td></tr><tr><td>0.05</td><td>87.49</td><td>6.18</td><td>12.55</td></tr><tr><td>0.25</td><td>81.25</td><td>8.05</td><td>14.47</td></tr><tr><td>0.50</td><td>73.60</td><td>11.35</td><td>18.39</td></tr><tr><td>1.00</td><td>65.24</td><td>15.61</td><td>20.50</td></tr></tbody></table>

### 6.3.4 Network Structure Analysis on the Real-World Network

We now move the analysis to the real Beijing network. To identify a representative solution for analysis, among the three solutions obtained as in Section 6.3.2, we only select here $S1$, i.e., the closest to the ideal point.

In addition to the previous metrics, we also compute the following

* **Avg. Travel Time Improvement (Avg.TTI):** percentage reduction in aggregate travel time across all OD pairs $k$ relative to the original network.

$$ \text{Avg.TTI} = \frac{\sum_{k \in \mathcal{K}} (t_k^0 - t_k^*)}{\sum_{k \in \mathcal{K}} t_k^0} \times 100\%, \text{ where } t_k^0, t_k^* \text{ are original and adaptive travel times.} \qquad (19) $$

The results in Table 3 show that the original network exhibits some inefficiencies: indeed, the solution of our optimization yields an 11.68% Avg. travel time improvement, even at $cv = 0$. This inefficiency can be attributed to the constraints of real-world planning, where routes often evolve through incremental expansions rather than system-wide optimization. The benefit of modifying the PT lines to adapt to travel time variability emerges as variability ($cv$) increases: the PT lines optimized by the algorithm become more and more different than the original static ones (lower route overlap), to achieve both travel time improvements and line shortening, which in turn yields lower operational cost.

## 7 Conclusion

This paper introduced a novel framework for real-time PT proactive network redesign that maintains high performance under uncertain traffic conditions. We formulated a multi-objective optimization problem balancing passenger travel time, operational costs, and network stability. Our predict-then-optimize approach relies on an NSGA-III-based optimization framework that proactively redesigns bus lines based on predicted line travel times.

We evaluated our approach against the inevitable prediction errors of well-established traffic-predicting models. To this aim, we fit the prediction error distribution via kernel density estimation. Experiments on Mandl's network and a real-world Beijing network demonstrate effective adaptation across varying levels of travel-time uncertainty. Results indicate that, faced with
non-negligible link travel-time variability, the proposed approach yields substantial OD-level trip travel-time reductions, while achieving operational cost savings and preserving a high degree of structural similarity with the baseline network. These findings highlight the importance of moving beyond static network design toward continuous, adaptive redesign in dynamic operating environments.

## References

Ahern Z, Paz A, Corry P, 2022 *Approximate multi-objective optimization for integrated bus route design and service frequency setting*. *Transportation Research Part B: Methodological* 155:1–25.

Akritas MG, Van Keilegom I, 2001 *Non-parametric estimation of the residual distribution*. *Scandinavian Journal of Statistics* 28(3):549–567.

Barahimi AH, Eydi A, Aghaie A, 2021 *Multi-modal urban transit network design considering reliability: multi-objective bi-level optimization*. *Reliability Engineering & System Safety* 216:107922.

Bertsimas D, Gupta V, Kallus N, 2018 *Data-driven robust optimization*. *Management Science* 64(12):5667–5684.

Büchel B, Corman F, 2020a *Review on statistical modeling of travel time variability for road-based public transport*. *Frontiers in Built Environment* 6:70.

Büchel B, Corman F, 2020b *Review on statistical modeling of travel time variability for road-based public transport*. *Frontiers in Built Environment* 6:70, URL http://dx.doi.org/10.3389/fbuil.2020.00070.

Cadarso L, Codina E, Escudero LF, Marín A, 2017 *Rapid transit network design: considering recovery robustness and risk aversion measures*. *Transportation research procedia* 22:255–264.

Calabrò G, Araldo A, Oh S, Seshadri R, Inturri G, Ben-Akiva M, 2023 *Adaptive transit design: Optimizing fixed and demand responsive multi-modal transportation via continuous approximation*. *Transportation Research Part A: Policy and Practice* 171:103643.

Calabrò G, Le Pira M, Giuffrida N, Inturri G, Ignaccolo M, Correia GHdA, 2022 *Fixed-route vs. demand-responsive transport feeder services: An exploratory study using an agent-based model*. *Journal of Advanced Transportation* 2022(1):8382754.

Cao Z, Ceder AA, 2019 *Autonomous shuttle bus service timetabling and vehicle scheduling using skip-stop tactic*. *Transportation Research Part C: Emerging Technologies* 102:370–395.

Cervantes-Sanmiguel KI, Chavez-Hernandez MV, Ibarra-Rojas OJ, 2023 *Analyzing the trade-off between minimizing travel times and reducing monetary costs for users in the transit network design*. *Transportation Research Part B: Methodological* 173:142–161.

Chen J, Liu Z, Wang S, Chen X, 2018 *Continuum approximation modeling of transit network design considering local route service and short-turn strategy*. *Transportation Research Part E: Logistics and Transportation Review* 119:165–188.

Chen X, Yu L, Zhang Y, Guo J, 2009 *Analyzing urban bus service reliability at the stop, route, and network levels*. *Transportation research part A: policy and practice* 43(8):722–734.

Chen YC, 2017 *A tutorial on kernel density estimation and recent advances*. *Biostatistics & Epidemiology* 1(1):161–187.

Chen Z, Li X, Qu X, 2022 *A continuous model for designing corridor systems with modular autonomous vehicles enabling station-wise docking*. *Transportation Science* 56(1):1–30, URL http://dx.doi.org/10.1287/trsc.2021.1085.
Cheng Q, Yan D, Wu T, Huang Z, Zhang Q, 2025 *Computing approximate graph edit distance via optimal transport*. *Proceedings of the ACM on Management of Data* 3(1):1–26.

Danaher A, Wensley J, Dunham A, Orosz T, Avery R, Cobb K, Watkins K, Queen C, Berrebi S, Connor M, et al., 2020 *Minutes matter: A bus transit service reliability guidebook* .

Deb K, Jain H, 2014 *An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part i: Solving problems with box constraints*. *IEEE Transactions on Evolutionary Computation* 18(4):577–601, URL http://dx.doi.org/10.1109/TEVC.2013.2 281535.

Deb K, Pratap A, Agarwal S, Meyarivan T, 2002 *A fast and elitist multiobjective genetic algorithm: Nsga-ii*. *IEEE transactions on evolutionary computation* 6(2):182–197.

Devarasetty PC, Burris M, Shaw WD, 2012 *The value of travel time and reliability-evidence from a stated preference survey and actual usage*. *Transportation research part A: policy and practice* 46(8):1227–1240.

Durand A, Hamersma M, van Oort N, Hoogendoorn S, 2024 *Digital engagement for travel information among car and public transport users in the Netherlands*. *Transportation Research Interdisciplinary Perspectives* 28:101285.

Fagnant DJ, Kockelman KM, 2015 *Preparing a nation for autonomous vehicles: Opportunities, barriers and policy recommendations*. *Transportation Research Part A: Policy and Practice* 77:167–181, URL http://dx.doi.org/10.1016/j.tra.2015.04.003.

Federal Highway Administration, 2016 *Smartphone applications to influence travel choices: Practices and policies*. Technical Report FHWA-HOP-16-023, U.S. Department of Transportation, Office of Operations, URL https://ops.fhwa.dot.gov/publications/fhwahop16023/index.htm, chapter 1: Introduction and Overview.

Fonseca JFP, 2020 *Timetable Integration in Public Transport Planning*. Ph.D. thesis, Technical University of Denmark (DTU), URL https://orbit.dtu.dk/files/206223149/Thesis_JFPF.pdf.

Ghahramani N, Brakewood C, 2016 *Trends in mobile transit information utilization: An exploratory analysis of transit app in new york city*. *Journal of Public Transportation* 19(3):139–160.

Gkiotsalitis K, 2020 *Public transport optimization*. *City*.

Gkiotsalitis K, 2021 *Stop-skipping in rolling horizons*. *Transportmetrica A: Transport Science* 17(4):492–520.

Gkiotsalitis K, Cats O, 2021 *At-stop control measures in public transport: Literature review and research agenda*. *Transportation Research Part E: Logistics and Transportation Review* 145:102176, URL http://dx.doi.org/10.1016/j.tre.2020.102176.

Goerigk M, Schmidt M, 2017 *Line planning with user-optimal route choice*. *European Journal of Operational Research* 259(2):424–436.

Guan Y, Xiang W, Wang Y, Yan X, Zhao Y, 2023 *Bi-level optimization for customized bus routing serving passengers with multiple-trips based on state-space-time network*. *Physica A: Statistical Mechanics and its Applications* 614:128517.

Guessous Y, Aron M, Bhouri N, Cohen S, 2014 *Estimating travel time distribution under different traffic conditions*. *Transportation Research Procedia* 3:339–348.

Guo Z, Araldo A, El Yacoubi M, 2025 *Data sampling-driven adaptive modification of bus routes under time-varying road conditions*. *The 19th Learning and Intelligent Optimization Conference*.

Guo Z, Araldo A, Yacoubi MAE, 2024 *Restoring accessibility during urban rail disruptions via bus network redesign*. *arXiv preprint arXiv:2411.08782*.
Hansen P, Mladenović N, 2001 *Variable neighborhood search: Principles and applications*. *European journal of operational research* 130(3):449–467.

Heyken Soares P, Mumford CL, Amponsah K, Mao Y, 2019 *An adaptive scaled network for public transport route optimisation*. *Public Transport* 11(2):379–412.

Huynh N, Barthelemy J, 2022 *A comparative study of topological analysis and temporal network analysis of a public transport system*. *International Journal of Transportation Science and Technology* 11(2):392–405, URL http://dx.doi.org/https://doi.org/10.1016/j.ijtst.2021.05.003.

Ibarra-Rojas OJ, Delgado F, Giesen R, Muñoz JC, 2015 *Planning, operation, and control of bus transport systems: A literature review*. *Transportation Research Part B: Methodological* 77:38–75.

International Transport Forum (ITF), 2024 *Transport system resilience: Summary and conclusions*. Technical report, OECD/ITF, URL https://www.oecd.org/content/dam/oecd/en/publications/reports/2024/05/transport-system-resilience_f51c36d9/d90b86ac-en.pdf.

International Transport Forum (ITF), 2025 *Transport network resilience: Policy paper*. Technical report, OECD/ITF, URL https://www.itf-oecd.org/sites/default/files/docs/transport-network-resilience-policy-paper.pdf.

Jaccard P, 1901 *Étude comparative de la distribution florale dans une portion des alpes et des jura*. *Bull Soc Vaudoise Sci Nat* 37:547–579.

Jain E, Roy I, Meher S, Chakrabarti S, De A, 2024 *Graph edit distance with general costs using neural set divergence*. *Advances in Neural Information Processing Systems* 37:73399–73438.

John MP, Mumford CL, Lewis R, 2014 *An improved multi-objective algorithm for the urban transit routing problem*. *European Conference on Evolutionary Computation in Combinatorial Optimization*, 49–60 (Springer).

Levandowsky M, Winter D, 1971 *Distance between sets*. *Nature* 234(5323):34–35.

Li JQ, Song MK, Li M, Zhang WB, Miller M, 2009 *Evaluation of cost-effective planning and design options for bus rapid transit in dedicated bus lanes*.

Li L, Shalaby A, 2024 *Navigating the transit network: Understanding riders' information seeking behavior using trip planning data*. *Transportation Research Part A: Policy and Practice* 185:104096.

Li Y, Yu R, Shahabi C, Liu Y, 2017 *Diffusion convolutional recurrent neural network: Data-driven traffic forecasting*. *arXiv preprint arXiv:1707.01926*.

Liang M, Xu M, Wang S, 2025 *A novel multi-objective evolutionary algorithm for transit network design and frequency-setting problem considering passengers' choice behaviors under station congestion*. *Transportation Research Part B: Methodological* 197:103238.

Liao B, Zhang J, Wu C, McIlwraith D, Chen T, Yang S, Guo Y, Wu F, 2018 *Deep sequence learning with auxiliary information for traffic prediction*. *Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining*, 537–546.

Liu L, Miller HJ, 2020 *Does real-time transit information reduce waiting time? an empirical analysis*. *Transportation Research Part A: Policy and Practice* 141:167–179.

Lu Z, Lv W, Xie Z, Du B, Xiong G, Sun L, Wang H, 2022 *Graph sequence neural network with an attention mechanism for traffic speed prediction*. *ACM Transactions on Intelligent Systems and Technology (TIST)* 13(2):1–24.

Ma H, Yang M, Li X, 2023 *Integrated optimization of customized bus routes and timetables with consideration of holding control*. *Computers & Industrial Engineering* 175:108886.

Magnanti TL, Wong RT, 1984 *Network design and transportation planning: Models and algorithms*. *Transportation science* 18(1):1–55.
Mahdavi S, Bhouri N, 2024 A synthetic indicator for structuring resilient public transport operation. Sustainable and Resilient Infrastructure URL http://dx.doi.org/10.1080/23789689.2024.234.6705.

Manasra H, Toledo T, 2019 Optimization-based operations control for public transportation service with transfers. Transportation Research Part C: Emerging Technologies 105:456-467.

Mandl CE, 1980 Evaluation and optimization of urban public transportation networks. European Journal of Operational Research 5(6):396-404.

Marra AD, Corman F, 2020 From delay to disruption: Impact of service degradation on public transport networks. Transportation Research Record 2674(10):886-897.

Massobrio R, Cats O, 2024 Topological assessment of recoverability in public transport networks. Communications Physics 7:108, URL http://dx.doi.org/10.1038/s42005-024-01596-8.

Metropolitan Transportation Authority (MTA), 2026 Schedules. https://www.mta.info/schedules, official MTA webpage providing scheduled and real-time transit service information.

National Rural Transit Assistance Program (National RTAP), 2024 Route Deviation Service Requirements. National Rural Transit Assistance Program, URL https://irp.cdn-website.com/270961f6/files/uploaded/ADA_Toolkit_2025.pdf, section on route deviation service in the National RTAP ADA Toolkit.

Nissen K, Becker N, Dähne O, Rabe M, Scheffler J, Solle M, Ulbrich U, 2020 How does weather affect the use of public transport in berlin? Environmental Research Letters 15(8):085001.

Olvera-Toscano CM, Ríos-Solís YÁ, Ríos-Mercado RZ, Sánchez Nigenda R, 2023 Holding times to maintain quasi-regular headways and reduce real-time bus bunching. Public Transport 15(3):595-628.

Parbo J, Nielsen OA, Prato CG, 2018 Reducing passengers' travel time by optimising stopping patterns in a large-scale network: A case-study in the copenhagen region. Transportation Research Part A: Policy and Practice 113:197-212.

Peled I, Lee K, Jiang Y, Dauwels J, Pereira FC, 2019 Online predictive optimization framework for stochastic demand-responsive transit services. arXiv URL https://arxiv.org/abs/1902.09745.

Peled I, Lee K, Jiang Y, Dauwels J, Pereira FC, 2021 On the quality requirements of demand prediction for dynamic public transport. Communications in Transportation Research 1:100008.

Pu H, Li Y, Ma C, 2022 Topology analysis of lanzhou public transport network based on double-layer complex network theory. Physica A: Statistical Mechanics and its Applications 592:126694.

Riquelme N, Von Lücken C, Baran B, 2015 Performance metrics in multi-objective optimization. 2015 Latin American computing conference (CLEI), 1-11 (IEEE).

Rodier C, Zhang Y, Harold BS, Drake C, 2025 Evaluation of a large scale universal basic mobility wallet in south los angeles (phase 1).

Russo A, et al., 2022 Dedicated bus lanes, bus speed and traffic congestion in rome. Transportation Research Part A: Policy and Practice 164:1-18, URL http://dx.doi.org/10.1016/j.tra.2022.08.006.

Schmid V, 2014 Hybrid large neighborhood search for the bus rapid transit route design problem. European Journal of Operational Research 238(2):427-437.

Schöbel A, Urban R, 2022 The cheapest ticket problem in public transport. Transportation Science 56(6):1432-1451.

Suman HK, Bolia NB, 2019 Improvement in direct bus services through route planning. Transport Policy 81:263-274.
Szeto WY, Jiang Y, 2014 <u>Transit route and frequency design: Bi-level modeling and hybrid artificial bee colony algorithm approach</u>. Transportation Research Part B: Methodological 67:235-263.

Tan W, Peng X, Huang J, Wang Y, Qiu J, Liu X, 2024 <u>Optimizing transit network departure frequency considering congestion effects</u>. Journal of Advanced Transportation 2024(1):8131887.

Tang C, Ceder A, Ge YE, 2018 <u>Optimal public-transport operational strategies to reduce cost and vehicle's emission</u>. PLoS One 13(8):e0201138.

Tian Q, Wang DZ, Lin YH, 2021 <u>Service operation design in a transit network with congested common lines</u>. Transportation Research Part B: Methodological 144:81-102.

Touzout FA, Ladier AL, Hadj-Hamou K, 2021 <u>Modelling and comparison of stability metrics for a re-optimisation approach of the inventory routing problem under demand uncertainty</u>. EURO Journal on Transportation and Logistics 10:100050, URL http://dx.doi.org/10.1016/j.e jtl.2021.100050.

Transport for London (TfL), 2026 <u>Live bus arrivals</u>. https://tfl.gov.uk/modes/buses/live-bus-a rrivals, official Transport for London webpage providing real-time bus arrival predictions.

Travieso G, Benatti A, Costa LdF, 2024 <u>An analytical approach to the jaccard similarity index</u>. arXiv preprint arXiv:2410.16436.

Vermeir E, Engelen W, Philips J, Vansteenwegen P, 2021 <u>An exact solution approach for the bus line planning problem with integrated passenger routing</u>. Journal of Advanced Transportation 2021(1):6684795.

Vuchic VR, Clarke R, Molinero A, 1981 <u>Timed transfer system planning, design and operation</u>. United States Department of Transportation Urban Mass Transportation Administration.

Wang Y, Chen J, Yu X, An Q, Wu X, 2022 <u>Optimization of bus rerouting to alleviate the impact of rail transit construction</u>. Journal of Advanced Transportation 2022(1):5773362.

Wang Z, Qi M, 2020 <u>Robust service network design under demand uncertainty</u>. Transportation Science 54(3):676-689.

Wu B, Zuo X, Zhou M, Wan X, Zhao X, Yang S, 2024 <u>A multi-objective ant colony system-based approach to transit route network adjustment</u>. IEEE Transactions on Intelligent Transportation Systems 25(7):7878-7892.

Wu J, Kulcsár B, Qu X, et al., 2021 <u>A modular, adaptive, and autonomous transit system (maats): An in-motion transfer strategy and performance evaluation in urban grid transit networks</u>. Transportation Research Part A: Policy and Practice 151:81-98.

Zhang J, Wang DZ, Meng M, 2018 <u>Which service is better on a linear travel corridor: Park & ride or on-demand public bus?</u> Transportation Research Part A: Policy and Practice 118:803-818.

Zhang L, Xu M, Wang S, 2024 <u>Improving robustness of large-scale bus transit networks against cascading failures: A preventive control or an emergency control?</u> Transportation Research Part C: Emerging Technologies 162:104602.

Zhang SJ, Jia SP, Bai Y, Mao BH, Ma CR, Zhang T, 2018 <u>Optimal adjustment schemes on the long through-type bus lines considering the urban rail transit network</u>. Discrete Dynamics in Nature and Society 2018(1):8029137.

Zhang Y, Xu H, Lu QC, Fan X, 2022 <u>Travel time reliability analysis considering bus bunching: A case study in xi'an, china</u>. Sustainability 14(23):15583.

Zhao D, Mihăiță AS, Ou Y, Grzybowska H, Li M, 2024 <u>Origin-destination matrix estimation for public transport: A multi-modal weighted graph approach</u>. Transportation Research Part C: Emerging Technologies 165:104694.
Zheng H, Sun H, Kang L, Dai P, Wu J, 2023 Multi-route coordination for bus systems in response to road disruptions. Transportation Research Part E: Logistics and Transportation Review 179:103258.

Zheng H, Sun H, Wu J, Kang L, 2024 Alternative service network design for bus systems responding to time-varying road disruptions. Transportation Research Part B: Methodological 188:103042.

Zhou W, Hu P, Huang Y, Deng L, 2021 Integrated optimization of bus route adjustment with passenger flow control for urban rail transit. IEEE Access 9:63073–63093.
# A Summary of related work

<table><caption>Table 4 summarizes the related work.</caption><thead><tr><th>Study</th><th>Solution Method</th><th>Online/Proactive Redesign</th><th>Similarity Control</th><th>Decision Focus</th></tr></thead><tbody><tr><td>(Magnanti and Wong 1984)</td><td>Exact methods</td><td>No</td><td>No</td><td>ND</td></tr><tr><td>(John, Mumford, and Lewis 2014)</td><td>Multi-objective GA</td><td>No</td><td>No</td><td>ND</td></tr><tr><td>(Heyken Soares et al. 2019)</td><td>Scaled network GA</td><td>No</td><td>No</td><td>ND</td></tr><tr><td>(Cadarso et al. 2017)</td><td>Branch-and-cut</td><td>No</td><td>No</td><td>ND</td></tr><tr><td>(Ahern, Paz, and Corry 2022)</td><td>Gradient-based</td><td>No</td><td>No</td><td>ND</td></tr><tr><td>(Tan et al. 2024)</td><td>Congestion analysis</td><td>No</td><td>No</td><td>FS</td></tr><tr><td>(Guan et al. 2023)</td><td>Custom bilevel</td><td>No</td><td>No</td><td>OR</td></tr><tr><td>(Zhang et al. 2018)</td><td>Tailored GA</td><td>No</td><td>No</td><td>OR</td></tr><tr><td>(Wang et al. 2022)</td><td>Two-stage heuristic</td><td>No</td><td>No</td><td>DR</td></tr><tr><td>(Wu et al. 2024)</td><td>Ant Colony</td><td>No</td><td>NW</td><td>OR</td></tr><tr><td>(Zheng et al. 2024)</td><td>Heuristic</td><td>No</td><td>No</td><td>DR</td></tr><tr><td>(Cao and Ceder 2019)</td><td>Skip-stop heuristic</td><td>No</td><td>No</td><td>VC</td></tr><tr><td>(Ma, Yang, and Li 2023)</td><td>Integer programming</td><td>No</td><td>No</td><td>OR</td></tr><tr><td>(Tang, Ceder, and Ge 2018)</td><td>Optimal control</td><td>No</td><td>No</td><td>VC</td></tr><tr><td>(Manasra and Toledo 2019)</td><td>Branch-and-bound</td><td>No</td><td>No</td><td>VC</td></tr><tr><td>(Gkiotsalitis 2020)</td><td>Evolutionary</td><td>No</td><td>No</td><td>VC</td></tr><tr><td>(Olvera-Toscano et al. 2023)</td><td>Holding optimization</td><td>No</td><td>No</td><td>VC</td></tr><tr><td>(Zheng et al. 2023)</td><td>Coordination heuristic</td><td>No</td><td>No</td><td>VC</td></tr><tr><td>(Guo, Araldo, and El Yacoubi 2025)</td><td>Exact methods</td><td>Partial</td><td>Penalty</td><td>NR</td></tr><tr><td><strong>Our Approach</strong></td><td><strong>NSGA-III based optimization</strong></td><td><strong>Yes</strong></td><td><strong>Jaccard</strong></td><td><strong>NR</strong></td></tr></tbody></table>

Notes: Online/Proactive Redesign – **No**: no online or proactive redesign; **Partial**: limited redesign capability (e.g., sampling-based or scenario-specific updates); **Yes**: proactive redesign enabled (e.g., predict-then-optimize). Similarity Control – **No**: no explicit similarity mechanism; **NW**: Needleman-Wunsch-based similarity; **Penalty**: penalty-based similarity; **Jaccard**: Jaccard-based similarity. Decision Focus – **ND**: from-scratch network design; **FS**: frequency setting; **OR**: offline or preplanned redesign of an existing network; **DR**: per tu ap ti o n-oriented redesign or response; **VC**: vehicle or operational control; **NR**: network redesign under uncertain travel times.

<caption>Table 4: Comparative analysis of public transport optimization approaches across decision scope, online/proactive redesign capability, and similarity control mechanisms.</caption>

# B Proof and Discussion of Proposition 1

**Proof.** Setting $A = \mathcal{E}^{(k)}$, $B = \mathcal{E}^{(0)}$, and $C = \mathcal{E}^{(k+1)}$. The Jaccard distance between two sets $X$ and $Y$ is

$$d_J(X, Y) = 1 - \frac{|X \cap Y|}{|X \cup Y|} = 1 - J(X, Y).$$

Levandowsky and Winter (Levandowsky and Winter 1971) noted that this dissimilarity measure satisfies the triangle inequality on finite sets, so that $d_J$ may be regarded as a distance function. Hence,

$$d_J(A, C) \le d_J(A, B) + d_J(B, C).$$

Substituting $d_J(X, Y) = 1 - J(X, Y)$ into the above inequality yields

$$1 - J(A, C) \le [1 - J(A, B)] + [1 - J(B, C)],$$

which is equivalent to

$$J(A, C) \ge J(A, B) + J(B, C) - 1.$$

, gives the desired result.

<figure><img src="image_7.png" /></figure>
**Remark.** This implies that if two consecutive designs exhibit a similarity of ≥ 90% relative to the original (consistent with our numerical results), the similarity between these two consecutive designs is guaranteed to be at least 80%.

C Stochastic Modelling of Travel Times and Prediction Errors

C.1 Parameter Derivation for Log-Normal Distribution

**Proposition 2.** Let $t_{ij}$ be a lognormal random variable representing the travel time on link $(i, j) \in \mathcal{E}$ with median $m_{ij}$ and coefficient of variation $cv$. The parameters $(\mu_{ij}, \sigma_{ij})$ of the underlying normal distribution satisfy

$$
\mu_{ij} = \ln(m_{ij}), \quad \sigma_{ij} = \sqrt{\ln(1 + cv^2)}.
$$

**Proof.** For a lognormal random variable $X \sim \text{LogNormal}(\mu, \sigma^2)$, the median is $\text{Med}(X) = \exp(\mu)$, so specifying the median $m$ yields

$$
\mu = \ln(m).
$$

The mean and variance of $X$ are

$$
E[X] = \exp\left(\mu + \frac{1}{2}\sigma^2\right), \quad \text{Var}(X) = \left(\exp(\sigma^2) - 1\right) \exp\left(2\mu + \sigma^2\right).
$$

Hence the coefficient of variation is

$$
cv = \frac{\sqrt{\mathrm{Var}(X)}}{\mathrm{E}[X]} = \frac{\sqrt{(\exp(\sigma^2) - 1) \exp(2\mu + \sigma^2)}}{\exp(\mu + \frac{1}{2}\sigma^2)} = \sqrt{\exp(\sigma^2) - 1}.
$$

Equating this expression with the prescribed value of *cv* gives

$$
cv^2 = \exp(\sigma^2) - 1 \implies \sigma^2 = \ln(1 + cv^2) \implies \sigma = \sqrt{\ln(1 + cv^2)}.
$$

C.2 Traffic Speed Prediction and Error Estimation

To generate realistic stochastic prediction errors, we employ the Diffusion Convolutional Recur-
rent Neural Network (DCRNN) (Li et al. 2017) to model spatiotemporal traffic dependencies.
Two benchmark datasets are utilized: **METR-LA** (4 months of highway data from 207 sensors)
as a proxy for Mandl’s network, and **Q-Traffic** (61 days of Beijing 6th Ring Road segments)
for the real-world case study. We split both datasets, chronologically, as recommended by Li
et al. (2017) and Lu et al. (2022), respectively: we train the prediction model on the first part
endeavoring to predict the next part (test set), and we measure prediction errors on the last part (training set).

The conversion from predicted speed $\hat{v}(t)$ to travel-time error $\epsilon(t)$ accounts for differences in
available network attributes. For **METR-LA**, where segment lengths are not directly provided,
we define directed links between upstream sensors *s* and downstream sensors *r*, determining the
link length *d* via the network distance between them. The link speed is then approximated by averaging the endpoint measurements: $\hat{v}_{(s,r)}(t) = (\hat{v}_s(t) + \hat{v}_r(t))/2$. In contrast, **Q-Traffic** explicitly provides the length *d* for each road segment *i*, and the model output directly represents the segment speed $\hat{v}_i(t)$. In both cases, the travel-time error $\epsilon(t)$ is derived as:

time to traverse a link: $t(t) = \frac{d}{v(t)}$, predicted time: $\hat{t}(t) = \frac{d}{\hat{v}(t)} \implies$ prediction error: $\epsilon(t) = \hat{t}(t) - t(t)$.

We pool all empirical prediction errors on the test sets, across links and time steps, to estimate a representative error distribution via Kernel Density Estimation (KDE) (App. C.3). Finally, independent samples $\epsilon_{ij}^\omega$ are drawn from the estimated distribution KDE for each link $(i, j)$ and scenario $\omega$, and the predicted link travel times $\hat{t}_{i,j}$, used to make decisions via solving (5)-(14), are computed adding $\epsilon_{ij}^\omega$ to the actual travel time $t_{i,j}$, according to (18). We do this in both Mandl and Beijing scenarios. Under this modeling choice, all links share the same error distribution.

### C.3 Error Distribution Fitting for Travel Time Prediction

Let $D_{tt}$ denote the empirical dataset of link-level travel-time prediction errors extracted from App. C.2. Each observation corresponds to the difference between realized and predicted travel times over consecutive sensor pairs. To model the stochastic structure of these errors, we estimate their probability density using Kernel Density Estimation (KDE). Specifically, given $n = |D_{tt}|$ samples, the KDE estimator is defined as

$$ \hat{f}(\epsilon) = \frac{1}{nh} \sum_{a \in D_{tt}} K\left(\frac{\epsilon - a}{h}\right), \qquad (20) $$

where $\epsilon$ denotes the prediction-error random variable, *a* is an observed error sample, $K(u) = \frac{1}{\sqrt{2\pi}}e^{-u^2/2}$ is the Gaussian kernel, and the bandwidth $h = 0.082$ is selected using Scott's rule. To assess the adequacy of KDE, we compare it with three alternative distributional models: Johnson SU, Gaussian Mixture Models (GMM), and the skew-normal family. Goodness-of-fit is evaluated using the Kolmogorov-Smirnov (KS) statistic and discrepancies in the first four moments (mean, standard deviation, skewness, and kurtosis) between empirical and synthetic samples. The results are summarized in Table 5. While GMM achieves the smallest KS statistic,

<table><caption>Table 5: Distribution fitting comparison for travel-time prediction errors.</caption><thead><tr><th>Method</th><th>KS Stat</th><th>Mean Diff</th><th>Std Diff</th><th>Skew Diff</th><th>Kurt Diff</th></tr></thead><tbody><tr><td>KDE</td><td>0.042</td><td><strong>0.0001</strong></td><td>0.007</td><td><strong>0.254</strong></td><td><strong>1.793</strong></td></tr><tr><td>JOHNSON</td><td>0.022</td><td>0.005</td><td>0.051</td><td>1.620</td><td>208.981</td></tr><tr><td>GMM</td><td><strong>0.020</strong></td><td>0.002</td><td><strong>0.001</strong></td><td>2.440</td><td>51.339</td></tr><tr><td>SKEWNORM</td><td>0.211</td><td>0.018</td><td>0.019</td><td>5.452</td><td>87.860</td></tr></tbody></table>

KDE provides the best overall compromise between global fit and moment preservation. In particular, KDE exhibits negligible bias in the mean and standard deviation and substantially smaller discrepancies in skewness and kurtosis, indicating a more faithful representation of both the central mass and tail behavior of the empirical error distribution. Accordingly, we adopt the
KDE-based estimator $\hat{f}$ in (20) to generate prediction-error samples $\epsilon_{ij}^\omega$ used in the numerical experiments.

# D Algorithmic Framework and Evaluation

## D.1 Parameter values for the proposed Algorithm 1

When computing adaptive network $G_{PT}$ using the solution method described in § 4, we set the algorithmic parameters introduced therein as follows. The minimum path-overlap threshold is set to $J_{min} = 0.5$ (§4.2.1), the crossover and mutation probabilities to $P_c = 0.85$ (§4.2.2) and $P_m = 0.35$ (§4.2.3), and the number of reference points to $N_{ref} = 5^3 = 125$ (§4.2.4), respectively.

## D.2 Performance Metrics for Multi-Objective Optimization

We evaluate algorithm performance using three standard metrics for multi-objective optimization: Hypervolume (HV), Inverted Generational Distance (IGD), and Generational Distance (GD). The HV metric quantifies the volume of the objective space dominated by the Pareto solutions:

$$HV(X, P) = \Lambda \left( \bigcup_{x \in X} v(x, P) \right) \qquad (21)$$

where $X$ is the approximation set, $P$ is the reference point, and $v(x, P)$ is the hypervolume dominated by solution $x$ relative to $P$. Higher HV values indicate better coverage of the objective space. To ensure a fair comparison across algorithms, we report the HV metric calculated relative to a unified reference point. This reference point is constructed by collecting all solutions generated by all algorithms for each objective and selecting the worst (largest) value observed for each objective. The IGD metric measures the closeness of the approximation set to the true Pareto front:

$$IGD(X, \mathcal{P}^*) = \frac{\sum_{x^* \in \mathcal{P}^*} d(x^*, X)}{|\mathcal{P}^*|} \qquad (22)$$

where $\mathcal{P}^*$ is a set of reference points on the true Pareto front, $d(x^*, X)$ is the minimum distance from $x^*$ to any point in $X$, and $|\mathcal{P}^*|$ is the cardinality of $\mathcal{P}^*$. Lower IGD values indicate better convergence to the true Pareto front. The GD metric complements IGD by measuring how far the obtained solutions are from the true Pareto front:

$$GD(X, \mathcal{P}^*) = \frac{\sum_{x \in X} d(x, \mathcal{P}^*)}{|X|} \qquad (23)$$

where $d(x, \mathcal{P}^*)$ is the minimum distance from a solution $x$ to the true Pareto front $\mathcal{P}^*$, and $|X|$ is the cardinality of the approximation set. Lower GD values indicate better convergence of the approximation set to the true Pareto front.

## D.3 Implementation Details of the NSGA-III Environmental Selection

The algorithm adopts the reference-point-based environmental selection mechanism of NSGA-III (Deb and Jain 2014) to maintain diversity across the objectives (5). Since all objectives are formulated as minimization problems, normalization is performed on the combined population
$R_t = P_t \cup Q_t$. For each objective $j \in \{1, 2, 3\}$, objective-wise lower and upper bounds are computed as $z_j^{\min} = \min_{x \in R_t} Z_j(x)$ and $z_j^{\max} = \max_{x \in R_t} Z_j(x)$, and each objective is linearly scaled to $[0, 1]$ accordingly.

A set of uniformly distributed reference points on the unit simplex is generated following the simplex-lattice design in Deb and Jain (2014). As in standard multiobjective optimization, we say that solution $x$ dominates $y$ if $x$ is no worse than $y$ in all objectives and strictly better in at least one. We employ non-dominated sorting, which partitions the **combined population** $R_t = P_t \cup Q_t$ (comprising both parent and offspring individuals) into a sequence of Pareto fronts $F = \{F_1, F_2, \dots, F_l\}$. Here, $F_1$ contains the globally non-dominated solutions $F_2$ contains solutions dominated exclusively by members of $F_1$, and $F_l$ represents the **critical front** where the cumulative count of solutions first meets or exceeds the population capacity *PopSize*. Each solution is associated with its nearest reference point by computing perpendicular distances from the solution to the reference lines in the normalized space. The environmental selection process (line 10 of Alg. 1) adds complete Pareto fronts $F_1$ through $F_{l-1}$ sequentially; for the last front $F_l$, slots are filled by prioritizing solutions associated with reference points that have fewer assigned solutions to ensure diversity.

<caption>**Algorithm 2 Feasibility-Oriented Path Completion for Line Repair**</caption>

**Input:** Substrate graph $\mathcal{G} = (\mathcal{N}, \mathcal{E})$, endpoints $(u, v)$, visited node set $\mathcal{V}_{\text{used}}^{\ell}$
**Output:** Connecting path $\mathcal{P}_{u \to v}$ or $\emptyset$
1: $\text{visited} \leftarrow \{u\} \cup \mathcal{V}_{\text{used}}^{\ell}$, $\text{queue} \leftarrow \langle u \rangle$, $\text{parent}(\cdot) \leftarrow \emptyset$
2: **while** $\text{queue}$ is not empty **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow \text{queue.pop_front()}$
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $i = v$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**break**
6: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
7: &nbsp;&nbsp;&nbsp;&nbsp;**for** each neighbor $j$ of $i$ in $\mathcal{G}$ **do**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $j \notin \text{visited}$ **then**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{visited} \leftarrow \text{visited} \cup \{j\}$
10: &nbsp;&nbsp;&nbsp;&nbsp;11: $\text{queue.push_back}(j)$
12: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
13: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
14: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
15: &nbsp;&nbsp;&nbsp;&nbsp;**if** $v \notin \text{visited}$ **then**
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $\emptyset$
17: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
18: $\mathcal{P}_{u \to v} \leftarrow \text{Backtrack from } v \text{ to } u$ using $\text{parent}(\cdot)$
19: **return** $\mathcal{P}_{u \to v}$

## D.4 Performance of NSGA-III for Static Optimal Network Generation

For generating our baseline static optimal network $\mathcal{G}_{\text{PT}}^{\text{static}}$, we employ NSGA-III for multi-objective optimization. Fig. 6 displays the resulting Pareto frontier with non-dominated solutions balancing vehicle operation time against passenger travel time. We identify $\mathcal{G}_{\text{PT}}^{\text{static}}$ as the solution that is closest to the ideal point, defined as the point where all objectives attain their minimum value. Specifically, we select the Pareto-optimal solution that minimizes the normalized Euclidean distance to this ideal point. This choice corresponds to the “knee” re-
<figure><img src="image_8.png" /><figcaption>Figure 6: Pareto Frontier Generated by NSGA-III for Static Optimal Network</figcaption></figure>

region of the Pareto frontier, where any further improvement in one objective would cause a disproportionately large deterioration in the other.

## D.5 Algorithm Performance Evaluation

Algorithmic performance is evaluated via the Hypervolume (HV), the Inverted Generational Distance (IGD), and the Generational Distance (GD), which are standard performance metrics in multi-objective evolutionary optimization as surveyed in (Riquelme, Von Lücken, and Baran 2015). Formal definitions and computational details are provided in App D.2. The Hypervolume (HV) evaluates both convergence and diversity by measuring the dominated volume in the objective space, where higher values indicate better performance (↑). In contrast, GD and IGD are distance-based indicators that assess convergence to a reference Pareto front, with lower values indicating better convergence (↓).

To evaluate the effectiveness of NSGA-III for real-time PT redesign, we compare it with NSGA-II (Deb et al. 2002) and hybrid multi-objective algorithms that combine non-dominated sorting with variable neighborhood descent, based on Mandl's Swiss network. Specifically, we consider two Non-dominated Sorting Variable Neighborhood Descent (NSVND) variants inspired by the integration of NSGA-II with variable neighborhood search strategies (Hansen and Mladenović 2001). The first variant (NSVND-II) follows the NSGA-II framework while replacing crossover and mutation with variable neighborhood descent, whereas the second variant (NSVND-III) further incorporates an adaptive neighborhood selection mechanism to enhance exploration of the Pareto frontier.

Table 6 presents an algorithm performance comparison for adaptive network optimization assuming no travel time deviation from the nominal ones ($cv=0$). Although no adaptive redesign is required when $cv = 0$, this setting provides a noise-free benchmark for comparing optimization algorithms. NSGA-III maintains an optimal balance between solution diversity (high hypervolume) and convergence precision.
<table><thead><tr><th>Performance Metric</th><th>NSGA-II</th><th>NSGA-III</th><th>NSVND-II</th><th>NSVND-III</th></tr></thead><tbody><tr><td>Inverted Generational Distance (IGD, lower is better)</td><td>347.64</td><td><strong>22.63</strong></td><td>38.90</td><td>34.80</td></tr><tr><td>IGD Change<sup>a</sup></td><td>-</td><td><strong>-325.01</strong></td><td>-308.74</td><td>-312.84</td></tr><tr><td>Generational Distance (GD, lower is better)</td><td>75.36</td><td><strong>17.17</strong></td><td>24.40</td><td>22.80</td></tr><tr><td>GD Change<sup>a</sup></td><td>-</td><td><strong>-58.19</strong></td><td>-50.96</td><td>-52.56</td></tr><tr><td>Hypervolume (HV, higher is better)<sup>b</sup></td><td>30.52 × 10<sup>9</sup></td><td>31.49 × 10<sup>9</sup></td><td>31.23 × 10<sup>9</sup></td><td>31.31 × 10<sup>9</sup></td></tr><tr><td>HV Change<sup>a</sup></td><td>-</td><td><strong>0.97 × 10<sup>9</sup></strong></td><td>0.71 × 10<sup>9</sup></td><td>0.79 × 10<sup>9</sup></td></tr></tbody></table>

<caption>Table 6: Multi-objective algorithm comparison under noise-free travel times ($cv = 0$).</caption>

## E Network Performance Metrics

This appendix details the performance indicators used in § 6.3.1. For each realization $\omega \in \Omega$ of stochastic travel times, we define the following performance metrics: **20% Improvement Share (IS$_{20}$)**, **Operational Cost Reduction (OCR)**, and **Route Overlap (RO)**. Since these metrics vary with the realized scenario $\omega$, they are treated as random variables. In our numerical results, we report their empirical averages (and confidence intervals) over five independent realizations.

* **20% Improvement Share (%):** The proportion of OD pairs experiencing a travel time reduction of at least 20% under realization $\omega$.

$$ \text{IS}_{20}(\omega) = \frac{\sum_{k \in \mathcal{K}} \mathbb{I}\left(\frac{t_k^0 - t_k^*(\omega)}{t_k^0} \ge 20\%\right)}{|\mathcal{K}|} \times 100\%, \text{ where } \mathbb{I}(\cdot) \text{ is the indicator function.} $$

Here $t_k^0$ and $t_k^*(\omega)$ denote the original and adaptive travel times for OD pair $k$, respectively. Since both depend on random travel-time realizations, $\text{IS}_{20}$ is a random variable.

* **Operational Cost Reduction (OCR)**

$$ \text{OCR}(\omega) = \frac{\sum_{\ell \in \mathcal{L}} n^{\ell} \cdot t^{\ell} - \sum_{\ell \in \mathcal{L}} n^{\ell,*}(\omega) \cdot t^{\ell,*}(\omega)}{\sum_{\ell \in \mathcal{L}} n^{\ell} \cdot t^{\ell}} \times 100\%. $$

Here $t^{\ell}$ and $t^{\ell,*}(\omega)$ are the realized travel times of route $\ell$ in the original and adaptive networks, respectively, and $n^{\ell}$ and $n^{\ell,*}$ are the corresponding vehicle allocations. Because $t^{\ell}$ and $t^{\ell,*}(\omega)$ vary with the realization, OCR is also a random variable.

* **Route Overlap (RO)** To quantify structural similarity between the original and adaptive networks, we use the Jaccard index:

$$ \text{RO}(\omega) = \frac{|\mathcal{E}_{\text{PT}} \cap \mathcal{E}_{\text{PT}}^*(\omega)|}{|\mathcal{E}_{\text{PT}} \cup \mathcal{E}_{\text{PT}}^*(\omega)|} \times 100\%. $$

Here $\mathcal{E}_{\text{PT}}$ and $\mathcal{E}_{\text{PT}}^*(\omega)$ denote the realized edge sets of the original and adaptive networks, respectively. Since these sets depend on the travel-time realization, RO is likewise a random variable.

<footnote>a Improvement/Change are computed relative to NSGA-II (baseline).</footnote>

<footnote>b HV uses a single fixed reference point shared by all algorithms.</footnote>
The numerical results therefore report the *empirical means* (and 95% confidence intervals) of PTI, OCR, and RO over the five realizations $\omega \in \Omega$, providing a stochastic assessment of adaptive-network performance.