Optimizing the freight train connection service network of a large-scale rail system

This paper presents a formulation and solution for the train connection services (TCSs) problem in a large-scale rail network in order to determine the optimal freight train services, the frequency of services, and the distribution of classification workload among yards. TCS problem is modeled as a bi-level programming problem. The upper-level is intended to find an optimal train connection service, and the lower-level is used for assigning each shipment to a sequence of train services and determining the frequency of services.Our model solves the TCS problem of the China railway system, which is one of the largest railway systems in the world. The system consists of 5544 stations, and over 520,000 shipments using this system for a year period. A subnetwork is defined with 127 yards having some minimum level of reclassification resources and 14,440 demands obtained by aggregating 520,000 shipments to the subnetwork. We apply a simulated annealing algorithm to the data for optimal computation after pre-processing and get an excellent result. Comparing our optimal solution with the existing plan result, there are improvements of about 20.8% in the total cost.     

Multi-objective optimization of train routing problem combined with train scheduling on a high-speed railway network

Based on train scheduling, this paper puts forward a multi-objective optimization model for train routing on high-speed railway network, which can offer an important reference for train plan to provide a better service. The model does not only consider the average travel time of trains, but also take the energy consumption and the user satisfaction into account. Based on this model, an improved GA is designed to solve the train routing problem. The simulation results demonstrate that the accurate algorithm is suitable for a small-scale network, while the improved genetic algorithm based on train control (GATC) applies to a large-scale network. Finally, a sensitivity analysis of the parameters is performed to obtain the ideal parameters; a perturbation analysis shows that the proposed method can quickly handle the train disturbance.     

Traffic signal timing problems with environmental and equity considerations

Traffic signal timings in a road network can not only affect total user travel time and total amount of traffic emissions in the network but also create an inequity problem in terms of the change in travel costs of users traveling between different locations. This paper proposes a multi‐objective bi‐level programming model for design of sustainable and equitable traffic signal timings for a congested signal‐controlled road network. The upper level of the proposed model is a multi‐objective programming problem with an equity constraint that maximizes the reserve capacity of the network and minimizes the total amount of traffic emissions. The lower level is a deterministic network user equilibrium problem that considers the vehicle delays at signalized intersections of the network. To solve the proposed model, an approach for normalizing incommensurable objective functions is presented, and a heuristic solution algorithm that combines a penalty function approach and a simulated annealing method is developed. Two numerical examples are presented to show the effects of reserve capacity improvement and green time proportion on network flow distribution and transportation system performance and the importance of incorporating environmental and equity objectives in the traffic signal timing problems. Copyright © 2013 John Wiley & Sons, Ltd.     

An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network

In practice, a train-conflict resolution is decentralized around dispatchers each of whom controls a few segments in a global railway network with her rule-of-thumb to operational data. Conceptually, the global sub-optimality or infeasibility of the decentralized system is resolved by a network controller who coordinates the dispatchers and train operators at the lower layers on a real-time basis. However, such notion of a multi-layer system cannot be effectual unless the top layer is able to provide a global solution soon enough for the dynamic lower layers to adapt in a seamless manner. Unfortunately, a train-conflict resolution problem is NP-hard as formally established in this paper and an effective solution method traded off between computation time and solution quality has been lacking in literature. Thus, we propose a column-generation-based algorithm that exploits the separability of the problem. A key ingredient of the algorithm is an efficient heuristic for the pricing subproblem for column generation. Tested on the real data from the Seoul metropolitan railway network, the algorithm provides near-optimal conflict-free timetables in a few seconds for most cases. The performance of the proposed algorithm is compared to the ones of the previous MIP-based heuristic by Törnquist and Persson (2007) and the priority-based heuristic by Sahin (1999).     

Hybrid simulated annealing and genetic algorithm for optimizing arterial signal timings under oversaturated traffic conditions

The implementation of system‐wide signal optimization models requires efficient solution algorithms that can quickly generate optimal or near‐optimal signal timings. This paper presents a hybrid algorithm based on simulated annealing (SA) and a genetic algorithm (GA) for arterial signal timing optimization. A decoding scheme is proposed that exploits our prior expectations about efficient solutions, namely, that the optimal green time distribution should reflect the proportion of the critical lane volumes of each phase. An SA algorithm, a GA algorithm and a hybrid SA‐GA algorithm are developed here using the proposed decoding scheme. These algorithms can be adapted to a wide range of signal optimization models and are especially suitable for those optimizing phase sequences with oversaturated intersections. To comparatively evaluate the performance of the proposed algorithms, we apply them to a signal optimization model for oversaturated arterial intersections based on an enhanced cell transmission model. The numerical results indicate that the SA‐GA algorithm outperforms both SA and GA in terms of solution quality and convergence rate. Copyright © 2014 John Wiley & Sons, Ltd.     

Integrated optimization on train scheduling and preventive maintenance time slots planning

We address the problem of simultaneously scheduling trains and planning preventive maintenance time slots (PMTSs) on a general railway network. Based on network cumulative flow variables, a novel integrated mixed-integer linear programming (MILP) model is proposed to simultaneously optimize train routes, orders and passing times at each station, as well as work-time of preventive maintenance tasks (PMTSs). In order to provide an easy decomposition mechanism, the limited capacity of complex tracks is modelled as side constraints and a PMTS is modelled as a virtual train. A Lagrangian relaxation solution framework is proposed, in which the difficult track capacity constraints are relaxed, to decompose the original complex integrated train scheduling and PMTSs planning problem into a sequence of single train-based sub-problems. For each sub-problem, a standard label correcting algorithm is employed for finding the time-dependent least cost path on a time-space network. The resulting dual solutions can be transformed to feasible solutions through priority rules. Numerical experiments are conducted on a small artificial network and a real-world network adapted from a Chinese railway network, to evaluate the effectiveness and computational efficiency of the integrated optimization model and the proposed Lagrangian relaxation solution framework. The benefits of simultaneously scheduling trains and planning PMTSs are demonstrated, compared with a commonly-used sequential scheduling method.     

Balancing energy consumption and risk of delay in high speed trains: A three-objective real-time eco-driving algorithm with fuzzy parameters

Eco-driving is an energy efficient traffic operation measure that may lead to important energy savings in high speed railway lines. When a delay arises in real time, it is necessary to recalculate an optimal driving that must be energy efficient and computationally efficient.In addition, it is important that the algorithm includes the existing uncertainty associated with the manual execution of the driving parameters and with the possible future traffic disturbances that could lead to new delays.This paper proposes a new algorithm to be executed in real time, which models the uncertainty in manual driving by means of fuzzy numbers. It is a multi-objective optimization algorithm that includes the classical objectives in literature, running time and energy consumption, and as well a newly defined objective, the risk of delay in arrival. The risk of delay in arrival measure is based on the evolution of the time margin of the train up to destination.The proposed approach is a dynamic algorithm designed to improve the computational time. The optimal Pareto front is continuously tracked during the train travel, and a new set of driving commands is selected and presented to the driver when a delay is detected.The algorithm evaluates the 3 objectives of each solution using a detailed simulator of high speed trains to ensure that solutions are realistic, accurate and applicable by the driver. The use of this algorithm provides energy savings and, in addition, it permits railway operators to balance energy consumption and risk of delays in arrival. This way, the energy performance of the system is improved without degrading the quality of the service.     

Ant colony optimization for the real-time train routing selection problem

This paper deals with the real-time problem of scheduling and routing trains in a railway network. In the related literature, this problem is usually solved starting from a subset of routing alternatives and computing the near-optimal solution of the simplified routing problem. We study how to select the best subset of routing alternatives for each train among all possible alternatives. The real-time train routing selection problem is formulated as an integer linear programming formulation and solved via an algorithm inspired by the ant colonies’ behavior. The real-time railway traffic management problem takes as input the best subset of routing alternatives and is solved as a mixed-integer linear program. The proposed methodology is tested on two practical case studies of the French railway infrastructure: the Lille terminal station area and the Rouen line. The computational experiments are based on several practical disturbed scenarios. Our methodology allows the improvement of the state of the art in terms of the minimization of train consecutive delays. The improvement is around 22% for the Rouen instances and around 56% for the Lille instances.     

A bi‐level programming approach — Optimal transit fare under line capacity constraints

The fare of a transit line is one of the important decision variables for transit network design. It has been advocated as an efficient means of coordinating the transit passenger flows and of alleviating congestion in the transit network. This paper shows how transit fare can be optimized so as to balance the passenger flow on the transit network and to reduce the overload delays of passengers at transit stops. A bi‐level programming method is developed to optimize the transit fare under line capacity constraints. The upper‐level problem seeks to minimize the total network travel time, while the lower‐level problem is a stochastic user equilibrium transit assignment model with line capacity constraints. A heuristic solution algorithm based on sensitivity analysis is proposed. Numerical example is used to illustrate the application of the proposed model and solution algorithm.     

Optimizing train operational plan in an urban rail corridor based on the maximum headway function

The train operational plan (TOP) plays a crucial role in the efficient and effective operation of an urban rail system. We optimize the train operational plan in a special network layout, an urban rail corridor with one terminal yard, by decomposing it into two sub-problems, i.e., the train departure profile optimization and the rolling stock circulation optimization. The first sub-problem synthetically optimizes frequency setting, timetabling and the rolling stock circulation at the terminal without a yard. The maximum headway function is generated to ensure the service of the train operational plan without considering travel demand, then we present a model to minimize the number of train trips, and design a heuristic algorithm to maximize the train headway. On the basis of a given timetable, the rolling stock circulation optimization only involves the terminal with a yard. We propose a model to minimize the number of trains and yard–station runs, and an algorithm to find the optimal assignment of train-trip pair connections is designed. The computational complexities of the two algorithms are both linear. Finally, a real case study shows that the train operational plan developed by our approach enables a better match of train headway and travel demand, and reduces the operational cost while satisfying the requirement of the level of service.     

Reasonable scheduling for arrival–departure track operations in railway stations

We analyze the train types handled at a section station and the factors affecting the scheduling of the arrival–departure track operation, using the following conditions as our optimization goals: operating the arrival–departure tracks in accordance with a fixed operation scheme, and reducing the influence which the departing–receiving operations impose on shunting operations. We establish a 0–1 integer programming model for formulating a track operation plan. By applying modern sequencing theory, this is transformed into a fixed sequencing model of special parallel machines. We then design a heuristic algorithm to solve the model. Finally, the example of Yiyang railway station is used to verify the advantages of the model and the algorithm. A better operation plan is obtained using MATLAB 7.0 by applying the model and the algorithm provided in the paper, indicating the superiority of our study’s approach.     

Techniques for inserting additional trains into existing timetables

In this paper techniques for scheduling additional train services (SATS) are considered as is train scheduling involving general time window constraints, fixed operations, maintenance activities and periods of section unavailability. The SATS problem is important because additional services must often be given access to the railway and subsequently integrated into current timetables. The SATS problem therefore considers the competition for railway infrastructure between new services and existing services belonging to the same or different operators. The SATS problem is characterised as a hybrid job shop scheduling problem with time window constraints. To solve this problem constructive algorithm and meta-heuristic scheduling techniques that operate upon a disjunctive graph model of train operations are utilised. From numerical investigations the proposed framework and associated techniques are tested and shown to be effective.     

Energy-efficient operation of rail vehicles

This paper describes an analytical process that computes the optimal operating successions of a rail vehicle to minimize energy consumption. Rising energy prices and environmental concerns have made energy conservation a high priority for transportation operations. The cost of energy consumption makes up a large portion of the Operation and Maintenance (O&M) costs of transit especially rail transit systems. Energy conservation or reduction in energy cost may be one of the effective ways to reduce transit operating cost, therefore improve the efficiency of transit operations.From a theoretical point of view, the problem of energy efficient train control can be formulated as one of the functions of Optimal Control Theory. However, the classic numerical optimization methods such as discrete method of optimum programming are too slow to be used in an on-board computer even with the much improved computation power, today. The contribution of this particular research is the analytical solution that gives the sequence of optimal controls and equations to find the control change points. As a result, a calculation algorithm and a computer program for energy efficient train control has been developed. This program is also capable of developing energy efficient operating schedules by optimizing distributions of running time for an entire route or any part of rail systems.We see the major application of the proposed algorithms in fully or partially automated Train Control Systems. The modern train control systems, often referred as “positive” train control (PTC), have collected a large amount of information to ensure safety of train operations. The same data can be utilized to compute the optimum controls on-board to minimize energy consumption based on the algorithms proposed in this paper. Most of the input data, such as track plan, track profile, traction and braking characteristics, speed limits and required trip time are located in an on-board database and/or they can be transmitted via radio link to be processed by the proposed algorithm and program.     

Optimizing train stopping patterns and schedules for high-speed passenger rail corridors

High-speed railway (HSR) systems have been developing rapidly in China and various other countries throughout the past decade; as a result, the question of how to efficiently operate such large-scale systems is posing a new challenge to the railway industry. A high-quality train timetable should take full advantage of the system’s capacity to meet transportation demands. This paper presents a mathematical model for optimizing a train timetable for an HSR system. We propose an innovative methodology using a column-generation-based heuristic algorithm to simultaneously account for both passenger service demands and train scheduling. First, we transform a mathematical model into a simple linear programming problem using a Lagrangian relaxation method. Second, we search for the optimal solution by updating the restricted master problem (RMP) and the sub-problems in an iterative process using the column-generation-based algorithm. Finally, we consider the Beijing–Shanghai HSR line as a real-world application of the methodology; the results show that the optimization model and algorithm can improve the defined profit function by approximately 30% and increase the line capacity by approximately 27%. This methodology has the potential to improve the service level and capacity of HSR lines with no additional high-cost capital investment (e.g., the addition of new tracks, bridges and tunnels on the mainline and/or at stations).     

An improved car‐following model for railway traffic

In this paper, we propose an improved traffic model for simulating train movement in railway traffic. The proposed model is based on optimal velocity car‐following model. In order to test the proposed model, we use it to simulate the train movement with fixed‐block system. In simulations, we analyze and discuss the space–time diagram of railway traffic flow and the trajectories of train movement. Simulation results demonstrate that the proposed model can be successfully used for simulating the train movement in railway traffic. From the space–time diagram, we find some complex phenomena of train flow, which are observed in real railway traffic, such as train delays. By analyzing the trajectories of train movement, some dynamic characteristics of trains can be reproduced. Copyright © 2011 John Wiley & Sons, Ltd.     

Improving recovery-to-optimality robustness through efficiency-balanced design of timetable structure

To improve the service quality of the railway system (e.g., punctuality and travel times) and to enhance the robust timetabling methods further, this paper proposes an integrated two-stage approach to consider the recovery-to-optimality robustness into the optimized timetable design without predefined structure information (defined as flexible structure) such as initial departure times, overtaking stations, train order and buffer time. The first-stage timetabling model performs an iterative adjustment of all departure and arrival times to generate an optimal timetable with balanced efficiency and recovery-to-optimality robustness. The second-stage dispatching model evaluates the recovery-to-optimality robustness by simulating how each timetable generated from the first-stage could recover under a set of restricted scenarios of disturbances using the proposed dispatching algorithm. The concept of recovery-to-optimality is examined carefully for each timetable by selecting a set of optimally refined dispatching schedules with minimum recovery cost under each scenario of disturbance. The robustness evaluation process enables an updating of the timetable by using the generated dispatching schedules. Case studies were conducted in a railway corridor as a special case of a simple railway network to verify the effectiveness of the proposed approach. The results show that the proposed approach can effectively attain a good trade-off between the timetable efficiency and obtainable robustness for practical applications.     

Flexible feeder transit route design to enhance service accessibility in urban area

To improve the accessibility of transit system in urban areas, this paper presents a flexible feeder transit routing model that can serve irregular‐shaped networks. By integrating the cost efficiency of fixed‐route transit system and the flexibility of demand responsive transit system, the proposed model is capable of letting operating feeder busses temporarily deviate from their current route so as to serve the reported demand locations. With an objective of minimizing total bus travel time, a new operational mode is then proposed to allow busses to serve passengers on both street sides. In addition, when multiple feeder busses are operating in the target service area, the proposed model can provide an optimal plan to locate the nearest one to response to the demands. A three‐stage solution algorithm is also developed to yield meta‐optimal solutions to the problem in a reasonable amount of time by transforming the problem into a traveling salesman problem. Numerical studies have demonstrated the effectiveness of the proposed model as well as the heuristic solution approach. Copyright © 2015 John Wiley & Sons, Ltd.     

Analyzing the theoretical capacity of railway networks with a radial-backbone topology

In this work we propose a mechanism to optimize the capacity of the main corridor within a railway network with a radial-backbone or X-tree structure. The radial-backbone (or X-tree) structure is composed of two types of lines: the primary lines that travel exclusively on the common backbone (main corridor) and radial lines which, starting from the common backbone, branch out to individual locations. We define possible line configurations as binary strings and propose operators on them for their analysis, yielding an effective algorithm for generating an optimal design and train frequencies. We test our algorithm on real data for the high speed line Madrid–Seville. A frequency plan consistent with the optimal capacity is then proposed in order to eliminate the number of transfers between lines as well as to minimize the network fleet size, determining the minimum number of vehicles needed to serve all travel demand at maximum occupancy.     

A semi-analytical approach for solving the bottleneck model with general user heterogeneity

This paper proposes a novel semi-analytical approach for solving the dynamic user equilibrium (DUE) of a bottleneck model with general heterogeneous users. The proposed approach makes use of the analytical solutions from the bottleneck analysis to create an equivalent assignment problem that admits closed-form commute cost functions. The equivalent problem is a static and asymmetric traffic assignment problem, which can be formulated as a variational inequality problem (VIP). This approach provides a new tool to analyze the properties of the bottleneck model with general heterogeneity, and to design efficient solution methods. In particular, the existence and uniqueness of the DUE solution can be established using the P-property of the Jacobian matrix. Our numerical experiments show that a simple decomposition algorithm is able to quickly solve the equivalent VIP to high precision. The proposed VIP formation is also extended to address simultaneous departure time and route choice in a single O–D origin-destination network with multiple parallel routes.     

Multi-level condition-based maintenance planning for railway infrastructures – A scenario-based chance-constrained approach

This paper develops a multi-level decision making approach for the optimal planning of maintenance operations of railway infrastructures, which are composed of multiple components divided into basic units for maintenance. Scenario-based chance-constrained Model Predictive Control (MPC) is used at the high level to determine an optimal long-term component-wise intervention plan for a railway infrastructure, and the Time Instant Optimization (TIO) approach is applied to transform the MPC optimization problem with both continuous and integer decision variables into a nonlinear continuous optimization problem. The middle-level problem determines the allocation of time slots for the maintenance interventions suggested at the high level to optimize the trade-off between traffic disruption and the setup cost of maintenance slots. Based on the high-level intervention plan, the low-level problem determines the optimal clustering of the basic units to be treated by a maintenance agent, subject to the time limit imposed by the maintenance slots. The proposed approach is applied to the optimal treatment of squats, with real data from the Eindhoven-Weert line in the Dutch railway network.