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.

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 ].

The high-speed rail, offering train services with affordable fares and expedient quality, is playing a pivotal role for the intercity commuting in many counties (e.g., China). However, effected by the demand fluctuation, it is commonly observed that the tickets for train services in peak hours are sold out early, while many seats are left empty during off-peak hours. Noticing that time-dependent pricing measure is too aggregated to cater for individualized demand, this study proposes a novel ticketing/exchanging scheme allowing passengers to exchange for a highly-demanded and already-sold ticket with certain endogenously generated compensation. With assumption that this ticketing/exchanging scheme is applied in high-speed rail service operation, this study aims to determine the optimal operation strategies including the fleet size and timetable to optimize certain objectives from both operator’s and passengers’ perspectives. This problem is formulated into a two-stage stochastic programming, and a heuristic solution algorithm is designed to solve it efficiently. Numerical experiments are conducted to validate the model formulation and solution method in the context of real practice in the Beijing-Tianjin Intercity Railway.

Focusing on improving the operation efficiency and riding comfort of metro rail lines in the peak hours, this article investigates the real-time train regulation and passenger load control problem with respect to frequent disturbances. To better illustrate the relationship between the train timetable and the on-board passengers, the variations of the departure time and the passenger load are elaborated in the form of a state-space model. Based on the Lyapunov stability theory, the problem of minimizing an upper bound on the quadratic performance function is transformed to a dynamic optimization problem with a set of linear matrix inequalities (LMIs), and a predictive control strategy is designed to guarantee the actual train schedule and number of in-vehicle passengers track the nominal timetable and the expected passenger load with a given disturbance attenuation level. With the objective to reduce the computational workloads and cut down the utilization of wireless transmitting resources, an event-triggered strategy is developed to implement the proposed stabilizing feedback controller only when the measurement error exceeds certain threshold, which has better adaptability to the application in large-scale metro networks. Some numerical examples based on the Beijing Yizhuang Metrol Line are provided for illustration of the effectiveness of the proposed scheme.

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.

This study aims to investigate a robust network design problem to maximise the expected space-time accessibility, in which the origin-destination demand matrices are time-varying or unsynchronised under stochastic space-time scenarios. By defining the accessibility measure as the expected amount of accessible demand pairs, a linear 0-1 integer programming model is formulated to characterise the network design process. In order to find the near-optimal solutions for the problem of interest, an effective heuristic algorithm is proposed based on the framework of Lagrangian relaxation that decomposes the primal model into a series of tractable subproblems. Finally, the performance of the developed methods is demonstrated through numerical experiments in two networks with different scales. The results highlight the importance of considering robustness in transportation network design problems.

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.

Owing to environmental concerns, the energy-efficient subway train scheduling problem is necessary in subway operation management. This paper designs an approximate dynamic programming (DP) approach for energy-efficient subway train scheduling problem with time-dependent demand. The train traffic model is proposed with the dynamic equations for the evolution of train headway, train passenger loads, and the energy consumption along the subway line. For the dynamic changing of the onboard passengers with time, the total train energy usage is modeled as the sum of energy consumptions from the traction system and auxiliary facilities. A nonlinear DP problem is formulated to generate a near optimal timetable to realize the tradeoff among the utilization of trains, passenger waiting time, service levels, and energy consumption. To overcome the curse of dimensionality in this optimization problem, we construct an approximate DP framework, where the conceptions of states, policies, state transitions, and reward function are introduced. And this algorithm is able to converge to a good solution with a short time compared to the genetic algorithm and differential evolution algorithm. Finally, the numerical experiments are given to demonstrate the effectiveness of the proposed model and algorithm.

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 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.

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.

The majority of existing studies in subway train operations focus on timetable optimization and vehicle tracking methods, which may be infeasible with disturbances in actual operations. To deal with uncertain passenger demands and realize real-time train operations (RTOs) satisfying multiobjectives, including overspeed protection, punctuality, riding comfort, and energy consumption, this paper proposes two RTO algorithms via expert knowledge and an online learning approach. The first RTO algorithm is developed by a knowledge-based system to ensure the multiple objectives with a constant timetable. Then, by considering uncertain passenger demand at each station and random running time errors, we convert the train operation problem into a Markov decision process with nondeterministic state transition probabilities in which the aim is to minimize the reward for both the total time delay and energy consumption in a subway line. After designing policy, reward, and transition probability, we develop an integrated train operation (ITO) algorithm based on Q-learning to realize RTOs with online adjusting the timetable. Finally, we present some numerical examples to test the proposed algorithms with real detected data in the Yizhuang Line of Beijing Subway. The results indicate that, taking the multiple objectives into account, the RTO algorithm outperforms both manual driving and automatic train operations. In addition, the ITO algorithm is capable of dealing with uncertain disturbances, keeping the total time delay within 2 s and reducing the energy consumption.

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.

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.

In this paper, a multi-objective assignment problem is studied, in which two objectives, i.e., the profit and the consumed time, are considered. Due to the uncertainty of the real life, it is assumed that the elements of the profit matrix and the consumed time matrix are fuzzy variables. In order to obtain an assignment plan, a dependent-chance goal programming model is constructed for the problem. Also tabu search algorithm based on fuzzy simulation is designed to solve the problem. Finally, an example is given to show the efficiency of the algorithm

It is well-known that Hölder, Minkowski, Markov, Chebyshev and Jensen's inequalities are important and useful results in probability theory. This paper proposes to extend the usefulness of the above inequalities to the context of uncertainty analysis in intelligent systems. In order to further discuss the mathematical properties of fuzzy random variables, the analogous inequalities for fuzzy random variables are first proved based on the chance measure and expected value operator. After that, monotonicity and continuity of critical values of fuzzy random variables are also investigated. Finally, a convergence theorem of critical values for fuzzy random sequence is obtained.

A warehouse layout problem under fuzzy random environment is considered, in which different types of materials need to be placed in a warehouse so that the total transportation cost is minimized. For convenience of handling, the materials in the same class need to be placed in the adjacent cells. As a result, we construct expected value model for the problem and then design a hybrid intelligent algorithm for this model. Finally, some numerical examples are presented to show the efficiency of the algorithm.