Unexpected disruptions in urban rail transit systems cause the infeasibility of the initial train schedule and delays or cancelations of a lot of trains. Even though some recent studies begun to address the rolling stock and timetable optimization problem (RSTO), there is still a large gap between theoretical models and practical applications due to the real-time requirements of train rescheduling decisions. In this work, we first model RSTO using a path-based formulation, in which each path refers to a spatial-temporal trajectory of a rescheduled train in the considered network. The optimal set of paths can minimize the expected cost of train cancelation and train delay time. Our formulation also considers a series of operational constraints, such as train headway constraints, short-turning constraints and rolling stock constraints. We develop an efficient branch-and-price framework that decomposes the problem into a restricted master problem and a set of pricing subproblems, where we iteratively generate promising paths with negative reduce costs. We show that each subproblem is a resource-constrained shortest path problem and can be solved efficiently by an improved label setting algorithm by proving its optimality conditions. We compare the tightness of our new path-based formulation with state-of-art formulations and test our branch-and-price approach on real-world instances from Beijing rail transit. The results show that our approach can generate near-optimal solutions in less than three minutes with small duality gap, which evidently outperforms existing formulations and fulfills the requirement of rail managers in practical applications. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72288101 and 72322022]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0391 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0391 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Short-term origin-destination (OD) demand prediction is critical in managing the multimodal transportation system. The joint short-term OD demand prediction for multimodal systems faces three challenges: (1) data availability: real-time OD demand is not available for prediction; (2) sparsity and high-dimensionality of OD demand: the OD demand is spatiotemporal sparse and usually high dimension; (3) impact of different transportation modes: the future OD demand for one mode is affected by others, and extensive studies primarily focus on a single transportation mode, overlooking the influence between different modes. To tackle these challenges, we propose a multitask learning and Partial-Differential-based model to predict the short-term Multimodal Transport Systems OD demand (PD-MTSOD), which includes (1) an OD demand learner to estimate real-time OD demand, (2) data aggregation with hypergraph attention to capture spatiotemporal features, and (3) OD demand decomposition into self-generated increment, other-modes-generated increment, and real-time OD demand, and use partial-differential-based methods to model intermodal correlations. Extensive tests on Beijing and New York city's multimodal systems show that PD-MTSOD surpasses baseline models. In addition, we prove the benefits of joint considering multiple transportation and explore the correlations of different transportation modes. This paper offers a reliable method for understanding multimodal transportation systems.

Due to the rapid development of urban rail transit and the expansion of new lines, accurately predicting the passenger flow of newly expanding subway lines has become increasingly important. The lack of historical data and long forecasting times have led to insufficient accuracy in previous studies when directly predicting inflow at new line stations. To address these challenges, this study proposes a method to decompose inflow features into trend features and scale features, and introduces a model named Semi-Conv-Transformer, based on semi-supervised learning and deep learning neural networks, for prediction of newly expanding subway lines. This innovative approach divides the inflow prediction of newly expanding subway lines into three parts: 1) enhancing the dataset using semi-supervised learning for data augmentation, 2) predicting trend features and scale features with Conv-Transformer deep learning model, and 3) combining the trend features and scale features of station passenger flow to obtain the required inflow data. The proposed method was tested on a new subway line operated in Nanning, China. In this experiment, the model achieved better experimental performance than previous methods and achieved higher accuracy.

Express pickup and delivery systems play crucial roles in contemporary urban areas. Couriers within these systems retrieve packages from designated Areas of Interest (AOI) that the express company assigns to them during specific time intervals. The express company traditionally employs historical pickup request data for executing AOI assignments (or pickup request assignments) for couriers, and these assignments are conventionally static and do not evolve over time However, future pickup requests display significant temporal variations. Employing historical data for future assignments is, therefore, somewhat impractical. Furthermore, even if we were to predict future pickup requests beforehand and subsequently employ these predictions for assignments, this two-stage approach proves to be both impractical and trivial, potentially harboring drawbacks. For example, the better prediction results may not necessarily guarantee better clustering outcomes. To address these challenges, we introduce an intelligent end-to-end predict-then-optimize clustering method that simultaneously forecasts future pickup requests for AOIs and dynamically allocates AOIs to couriers through clustering. Initially, we propose a deep learning-based prediction model for predicting order quantities within AOIs. Subsequently, we present a differential constrainedK-means clustering method for AOI clustering based on the prediction results. Finally, we introduce a one-stage end-to-end predict-then-optimize clustering approach for the rational, dynamic, and intelligent allocation of AOIs to couriers. Our results demonstrate that this one-stage predict-then-optimize method significantly enhances optimization outcomes, namely the quality of clustering results. This study offers valuable insights that are relevant to predict-then-optimize-related tasks, particularly when addressing stochastic assignment problems within all types of express systems.

Accurate passenger flow prediction of urban rail transit systems (URT) is essential for improving the performance of intelligent transportation systems, especially during the epidemic. How to dynamically model the complex spatiotemporal dependencies of passenger flow is the main issue in achieving accurate passenger flow prediction during the epidemic. To solve this issue, this paper proposes a brand-new transformer-based architecture called COVID-19 Spatial-Temporal Transformer Network (COV-STFormer) under the encoder-decoder framework specifically for COVID-19. Concretely, a modified self-attention mechanism named Causal-Convolution ProbSparse Self-Attention (CPSA) is developed to model the complex temporal dependencies of passenger flow. A novel Adaptive Multi-Graph Convolution Network (AMGCN) is introduced to capture the complex and dynamic spatial dependencies by leveraging multiple graphs in a self-adaptive manner. Additionally, the Multi-source Data Fusion block fuses the passenger flow data, COVID-19 confirmed case data, and the relevant social media data to study the impact of COVID-19 to passenger flow. Experiments on real-world passenger flow datasets demonstrate the superiority of COV-STFormer over the other thirteen state-of-the-art methods. Several ablation studies are carried out to verify the effectiveness and reliability of our model structure. Results can provide critical insights for the operation of URT systems.

To date immunity to disruptions of multi-scale urban road networks (URNs) has not been effectively quantified. This study uses robustness as a meaningful - if partial - representation of immunity. We propose a novel Relative Area Index (RAI) based on traffic assignment theory to quantitatively measure the robustness of URNs under global capacity degradation due to three different types of disruptions, which takes into account many realistic characteristics. We also compare the RAI with weighted betweenness centrality, a traditional topological metric of robustness. We employ six realistic URNs as case studies for this comparison. Our analysis shows that RAI is a more effective measure of the robustness of URNs when multi-scale URNs suffer from global disruptions. This improved effectiveness is achieved because of RAI’s ability to capture the effects of realistic network characteristics such as network topology, flow patterns, link capacity, and travel demand. Also, the results highlight the importance of central management when URNs suffer from disruptions. Our novel method may provide a benchmark tool for comparing robustness of multi-scale URNs, which facilitates the understanding and improvement of network robustness for the planning and management of URNs.

Railway traffic management focuses on regulating train movements and delivering improved service quality to passengers; however, such efforts are subject to many uncertainties in terms of disruptions and passenger demand on a rail transit line. In contrast to most existing studies, which focus on the rescheduling of passenger timetables in a deterministic framework, this study proposes a two-stage stochastic optimization model for allocating backup rolling stocks (BRS) to storage lines to reschedule the timetable and serve passengers delayed by disruptions. The first stage is an assignment problem to determine the optimal plan for the allocation of BRS to storage lines to achieve a good trade-off between the investment cost for the BRS and the expected travel time of delayed passengers across different stochastic scenarios. The second stage is explicitly formulated as a network flow model to optimize the timetable of the delayed trains on the tracks and the BRS from the storage lines such that the passenger travel time is minimized under each stochastic scenario. To improve the efficiency of convergence, we develop an improved L-shaped method with several accelerating techniques. Among these, we show that the classical integer L-shaped cut can be tightened given the property of the second-stage problem, which can also be generalized to other two-stage integer stochastic programs. Real-world case studies based on historical data from the Beijing metro verify the effectiveness of the proposed approach in reducing the travel time for passengers. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This research was supported by the National Natural Science Foundation of China [Grants 71621001, 71825004, and 71901016]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information [ https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1233 ] or is available from the IJOC GitHub software repository ( https://github.com/INFORMSJoC ) at [ http://dx.doi.org/10.5281/zenodo.6892548 ].

Accurate predictions of bus service time are a prerequisite to improve the efficiency of bus transit. Field observations identified the degree of passenger crowding on the bus as one of the primary causes for the unpredictability of passengers’ average boarding time (ABT). Consequently, the internal areas of buses were divided for the first time to assess the impact of the passenger density distribution (PDD) on the ABT, using field data. An effective BPR function was proposed that accurately predicts the passengers’ ABT. Then, to show the influence of passenger movement preference and density distribution on ABT, a new floor field model was developed. Calibration and validation results indicate that the model can reproduce the dynamic moving process of passengers’ distribution on the bus and clarify the influence of PDD on ABT. Finally, three bus design strategies are proposed to enhance boarding efficiency, and the simulation results show that the optimal strategy improves passenger ABT and improve the operational performance of bus transit. These findings provide theoretical support for bus design as well as for bus operation.

Urban rail transit (URT) system plays a dominating role in many megacities like Beijing and Hong Kong. Due to its important role and complex nature, it is always in great need for public agencies to better understand the performance of the URT system. This paper focuses on an essential and hard problem to estimate the network-wide link travel time and station waiting time using the automatic fare collection (AFC) data in the URT system, which is beneficial to better understanding the system-wide real-time operation state. The emerging data-driven techniques, such as the computational graph (CG) method in the machine learning field, provide a new solution for solving this problem. In this study, we first formulate a data-driven estimation optimization framework to estimate the link travel time and station waiting time. Then, we cast the estimation optimization model into a CG-based framework to solve the optimization problem and obtain the estimation results. The methodology is verified on a synthetic URT network and applied to a real-world URT network using the synthetic and real-world AFC data, respectively. Results show the robustness and effectiveness of the CG-based framework. To the best of our knowledge, this is the first time that the CG is applied to the URT. This study can provide critical insights to better understand the operational state of URT.

Parking is one of the major problems in many cities. Due to the influence of various factors, the number of available parking spaces and travel time is highly dynamic and random. To find the reliable parking lot and the reliable path for travelers, this article proposes two parking guidance models and algorithms considering the earliest arrival time and the latest departure time. First, an extended shifted lognormal distribution (a 3-parameter lognormal distribution) is introduced to describe travel time. Then, a parking guidance model considering the earliest arrival time and a solution algorithm based on travel time bounds are established to find the reliable parking lot, the earliest arrival time, and the corresponding reliable path. Next, a parking guidance model considering the latest departure time and a solution algorithm based on travel time bounds are developed to find the reliable parking lot, the latest departure time, and the corresponding reliable path. Finally, two case studies with a real-world road network are used to verify the effectiveness and superiority of the proposed models and algorithms.

In metro systems, a tactical train schedule with the rolling stock circulation plan aims to determine the movements of all physical trains. To utilize the regenerative energy as much as possible, this paper proposes an integrated model to simultaneously generate the optimal train schedule and rolling stock circulation plan, in which the brake-traction overlapping time at stations is maximized. In particular, our model rigorously considers the train turn-around constraints, train circulation constraints, and dynamic passenger demands to tackle the train loading capacity constraints. To eliminate the effect of non-linear constraints, we reformulate the original model into its equivalent linear model that can be efficiently solved by linear programming solvers. Finally, the numerical experiments based on Beijing Yizhuang Metro Line are implemented to demonstrate the effectiveness of our proposed model.

This paper systematically investigates the efficient real-time control design for automatic train regulation (ATR) of metro loop lines subjected to frequent minor disruptions. To describe the dynamic evolution of the trains periodically operating on the loop line, a train traffic model related to the departure time is proposed based on a state-space equation, where the number of the station increases from circle to circle. Under the frequent minor disruptions, a dynamic optimal control model is developed to determine the ATR strategy to improve the punctuality and the regularity of the metro operation with the safety and control constraints. To solve the formulated optimal control model with the updated information, a real-time control algorithm based on a model predictive control approach is designed, which splits the original optimization problem into a set of convex quadratic programming problems, which can be numerically calculated efficiently and satisfy the real-time control requirement. Numerical examples are given to illustrate the effectiveness of the proposed method.

In urban rail transit systems, energy conservation is a challenging problem due to the rising environmental and social issues. The existing literature on this topic usually ignores time-variant characteristics of passenger demand at each station. Based on the real-world time-dependent smart-card automated fare collection data, this paper develops a bi-objective timetable optimization model to minimize the total passenger waiting time and the pure energy consumption. In the model formulation, the total passenger waiting time is subjected to the train capacity in the oversaturated condition, and the pure energy consumption is represented by the difference between the traction energy consumption and the regenerative energy within a given period. Numerical examples based on the real-world data from Beijing Yizhuang metro line are conducted. The results indicate that the developed model can improve passenger service and reduce energy consumption efficiently in comparisons with the timetable used currently.

In subway systems, electrical trains can generate considerable regenerative braking energy while braking, and such energy can be fed back to the contact line for further reuse by other accelerating trains, or dissipated by heating resistors. In order to reduce the total energy consumption during the operations of trains, a critical problem involves how to enhance the utilization of regenerative braking energy and correspondingly reduce the dissipated energy. With this consideration, this paper particularly investigates a train timetable problem in a subway system, which is equipped with a series of energy storage devices at stations. A nonlinear integer programming model is formulated to maximize the utilization of regenerative braking energy. An effective algorithm is designed to obtain the optimal train timetables. Finally, some experiments are implemented to illustrate the proposed approaches and demonstrate the feasibility and effectiveness of energy storage devices.

Advanced information is increasingly being used as an external intervention tool to positively influence system performance. In many traffic assignment problems, the proportion of travellers that reroute is assumed to be constant (static rerouting behavior), whereas the number of travellers that modify their routes will change dynamically with the cost difference (dynamic rerouting behavior). In this paper, dynamic rerouting behavior is considered in day-to-day traffic assignment models to capture travellers' reactions to advanced information. The properties of a dynamic rerouting weight function are studied using survey data. Our goal is to better understand the dynamic evolution of network flow. In the model, the rerouting weight varies dynamically with the cost difference between travellers' estimated and expected costs. The linear stability of the equilibrium is analyzed. Both theoretical analyses and numerical simulations indicated that dynamic rerouting behavior increases the stability domain and decreases the parameter sensitivity. Additionally, the dynamic evolution of the cost and flow near the stability boundary is studied. The results show that the dynamic rerouting behavior helps to improve the convergence speed and dampen the oscillations in the evolution process. This paper explains the influence of dynamic rerouting choice behavior on the evolution patterns of transportation networks and provides guidance for network design and management.

This paper formulates a two-objective model to optimize the timetables of urban rail transit systems based on energy-saving strategies and service quality levels. With time-dependent passenger demands, the calculation process of passenger travel time simulates boarding and alighting activities with some constraints to guarantee traffic capacity and meet passenger requirements, particularly in the oversaturated conditions. Traction and auxiliary energy consumption are considered in the operational energy consumption calculation. The regenerative energy, which is generated from braking trains and simultaneously used by traction trains, is also taken into account in the calculation with transmission loss. Through adjusting the headway, this model makes a tradeoff between passenger travel time and operational energy consumption with guaranteed traffic capability. Furthermore, a genetic algorithm with the binary encoding method is designed to obtain high-quality timetables. Based on the operational data of the Beijing Yizhuang subway line, we implement some numerical experiments to demonstrate the effectiveness of the proposed approaches.

In this paper, the optimal guaranteed cost cruise control for high-speed train movement with uncertain parameters and control constraints is investigated. Sufficient condition for the existence of guaranteed cost cruise control law is given in terms of linear matrix inequalities, under which each car of the high-speed train tracks the desired speed, the relative spring displacement is stable at the equilibrium state, and meanwhile an upper bound of the train performance is guaranteed. Moreover, a convex optimization problem is formulated to determine the optimal guaranteed cost control law that minimizes an upper bound on the train performance (energy consumption and tracking error). Numerical examples are given to illustrate the effectiveness of the proposed methods.

Train scheduling aims to seek a set of space-time paths for multiple trains on a railway line such that resources can be utilized efficiently with respect to prespecified criteria. By representing the train trajectory through a time-space path in its space-time network, this paper proposes an integer programming model for train scheduling on a single-track railway line, in which velocity choice is particularly considered to further decrease the expected energy consumption and interactions between different trains, and the link energy consumption is derived by the Davis formula with respect to different train speeds. The proposed model is implemented in the GAMS optimization software to solve an approximate optimal solution. Numerical examples show that the optimal timetable with optimized velocities can further decrease the energy consumption and coupling effects in comparison to the fixed velocity based schedule.

This paper proposes a new definition of uncertain time-varying network to capture the uncertain and dynamic characteristics of the network with discrete uncertain link travel times. To find the a priori non-dominated paths in this type of network, three comparison criteria based on the uncertain measure, namely, deterministic dominance rule, first-order uncertain dominance rule and uncertain expected value dominance rule, are proposed to generate non-dominated paths in a single time interval and a time period, as more than one path may exist between an origin and destination for a given departure time. The proposed comparison methods are then applied to solving a simple uncertain time-varying network. The computational results verify the efficiency of three dominance rules for finding non-dominated paths.

Energy efficiency is paid more and more attention in railway systems for reducing the cost of operation companies and emissions to the environment. In subway systems, the optimizations on timetable and driving strategy are two important and closely dependent parts of energy-efficient operations. The former regulates the fleet size and the trip time at interstations, and the latter determines the control sequences of traction and braking force during the trip. Most conventional research optimized the timetable and the driving strategy separately such that global optimality cannot be achieved. In this paper, we analyze the hierarchy of energy-efficient train operation and then propose an integrated algorithm to generate the globally optimal operation schedule, which can get better energy-saving performance. Within the criteria of meeting the passenger demand, the integrated energy-efficient algorithm can simultaneously obtain the optimal timetable and driving strategy for trains, which realizes the combination of the high-level transportation management and the low-level train operation control. The simulation results based on the Beijing Yizhuang Subway Line illustrate that the integrated algorithm can achieve a 24.0% energy reduction for one day, on average. In addition, the computation time is within 2 s, which is short enough to be applied for real-time control system.

Given rising energy prices and environmental concerns, train energy-efficient operation techniques are paid more attention as one of the effective methods to reduce operation costs and energy consumption. Generally speaking, the energy-efficient operation technique includes two levels, which optimize the timetable and the speed profiles among successive stations, respectively. To achieve better performance, this paper proposes to optimize the integrated timetable, which includes both the timetable and the speed profiles. First, we provide an analytical formulation to calculate the optimal speed profile with fixed trip time for each section. Second, we design a numerical algorithm to distribute the total trip time among different sections and prove the optimality of the distribution algorithm. Furthermore, we extend the algorithm to generate the integrated timetable. Finally, we present some numerical examples based on the operation data from the Beijing Yizhuang subway line. The simulation results show that energy reduction for the entire route is 14.5%. The computation time for finding the optimal solution is 0.15 s, which implies that the algorithm is fast enough to be used in the automatic train operation (ATO) system for real-time control.

In subway systems, the energy put into accelerating trains can be reconverted into electric energy by using the motors as generators during the braking phase. In general, except for a small part that is used for onboard purposes, most of the recovery energy is transmitted backward along the conversion chain and fed back into the overhead contact line. To improve the utilization of recovery energy, this paper proposes a cooperative scheduling approach to optimize the timetable so that the recovery energy that is generated by the braking train can directly be used by the accelerating train. The recovery that is generated by the braking train is less than the required energy for the accelerating train; therefore, only the synchronization between successive trains is considered. First, we propose the cooperative scheduling rules and define the overlapping time between the accelerating and braking trains for a peak-hours scenario and an off-peak-hours scenario, respectively. Second, we formulate an integer programming model to maximize the overlapping time with the headway time and dwell time control. Furthermore, we design a genetic algorithm with binary encoding to solve the optimal timetable. Last, we present six numerical examples based on the operation data from the Beijing Yizhuang subway line in China. The results illustrate that the proposed model can significantly improve the overlapping time by 22.06% at peak hours and 15.19% at off-peak hours.

Effective control strategies are required to disperse incident-based traffic jams in urban networks when dispersal cannot be achieved simply by removing the obstruction. This paper develops a selection of such control strategies and demonstrates their effectiveness in dispersing incident-based traffic jams in two-way rectangular grid networks. Using the spatial topology of traffic jam propagation, we apply the concept of vehicle movement ban, which is frequently adopted in real urban networks as a temporary traffic management measure. Four control strategies were developed, which are referred to as single-line control, multiline control, area control, and diamond control. We also explore a combination of these control strategies and evaluate the impact of these control strategies on the changes in traffic jam size and congestion delay. Finally, we simulate the processes of traffic jam formation and dissipation using the cell transmission model and demonstrate the performance of the proposed strategies. Simulation results show that the proposed strategies can indeed disperse incident-based traffic jams efficiently.

The aim of the train timetable problem is to determine arrival and departure times at each station so that no collisions will happen between different trains and the resources can be utilized effectively. Due to uncertainty of real systems, train timetables have to be made under an uncertain environment under most circumstances. This paper mainly investigates a passenger train timetable problem with fuzzy passenger demand on a single-line railway in which two objectives, i.e., fuzzy total passengers' time and total delay time, are considered. As a result, an expected value goal-programming model is constructed for the problem. A branch-and-bound algorithm based on the fuzzy simulation is designed in order to obtain an optimal solution. Finally, some numerical experiments are given to show applications of the model and the algorithm.

We continue the work of a paper by Zhang to introduce the concepts of a third kind of variations for non-additive set functions, the inclusion variations, and discuss some properties of the variations. In particular, we investigate the inclusion variations of signed fuzzy measures, which are closely linked to the uniqueness of Jordan decomposition of non-additive set functions.