Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints

This paper focuses on how to minimize the total passenger waiting time at stations by computing and adjusting train timetables for a rail corridor with given time-varying origin-to-destination passenger demand matrices. Given predetermined train skip-stop patterns, a unified quadratic integer programming model with linear constraints is developed to jointly synchronize effective passenger loading time windows and train arrival and departure times at each station. A set of quadratic and quasi-quadratic objective functions are proposed to precisely formulate the total waiting time under both minute-dependent demand and hour-dependent demand volumes from different origin–destination pairs. We construct mathematically rigorous and algorithmically tractable nonlinear mixed integer programming models for both real-time scheduling and medium-term planning applications. The proposed models are implemented using general purpose high-level optimization solvers, and the model effectiveness is further examined through numerical experiments of real-world rail train timetabling test cases.     

The variation in the value of travel-time savings and the dilemma of high-speed rail in China

This paper examines the variation in the value of travel-time savings (VTTS), a fundamental element determining the market demand for high-speed rail. Following a review of time allocation theories, a time allocation model for general travel behavior is proposed as a further elaboration of Evans’ (1972) activities analysis. There are relationships among activities that can be expressed using a linear inequality to show the constraints on the arrangement of activities. This model indicates that two or more activities can be simultaneously rearranged to improve time management, which may be a source of variation in VTTS. This time allocation model can explain why large-scale high-speed rail construction in China faces significant market risks and a high likelihood of economic loss. Data from a new ticket sales and booking system for railway passengers indicate that passengers prefer conventional overnight sleeper trains, rather than high-speed trains, for long-distance travel, which supports the analysis of the time allocation model.     

A differential evolution approach for the vehicle routing problem with backhauls and time windows

This paper presents a differential evolution algorithm (DEA) to solve a vehicle routing problem with backhauls and time windows (VRPBTW) and applied for a catering firm. VRPBTW is an extension of the vehicle routing problem, which includes capacity and time window constraints. In this problem, customers are divided into two subsets: linehaul and backhaul. Each vehicle starts from a depot and goods are delivered from the depot to the linehaul customers. Goods are subsequently brought back to the depot from the backhaul customers. The objective is to minimize the total distance that satisfies all of the constraints. The problem is formulated using mixed integer programming and solved using DEA. Proposed algorithm is tested with several benchmark problems to demonstrate effectiveness and efficiency of the algorithm and results show that our proposed algorithm can find superior solutions for most of the problems in comparison with the best known solutions. Hence, DEA was carried out for catering firm to minimize total transportation costs. Copyright © 2013 John Wiley & Sons, Ltd.     

A bi-level model for single-line rail timetable design with consideration of demand and capacity

This paper proposes a bi-level model to solve the timetable design problem for an urban rail line. The upper level model aims at determining the headways between trains to minimize total passenger cost, which includes not only the usual perceived travel time cost, but also penalties during travel. With the headways given by the upper level model, passengers’ arrival times at their origin stops are determined by the lower level model, in which the cost-minimizing behavior of each passenger is taken into account. To make the model more realistic, explicit capacity constraints of individual trains are considered. With these constraints, passengers cannot board a full train, but wait in queues for the next coming train. A two-stage genetic algorithm incorporating the method of successive averages is introduced to solve the bi-level model. Two hypothetical examples and a real world case are employed to evaluate the effectiveness of the proposed bi-level model and algorithm. Results show that the bi-level model performs well in reducing total passenger cost, especially in reducing waiting time cost and penalties. And the section loading-rates of trains in the optimized timetable are more balanced than the even-headway timetable. The sensitivity analyses show that passenger’s desired arrival time interval at destination and crowding penalty factor have a high influence on the optimal solution. And with the dispersing of passengers' desired arrival time intervals or the increase of crowding penalty factor, the section loading-rates of trains become more balanced.     

An investigation of passenger interchange and train standing time at LRT stations: (ii) Estimation of standing time

The standing-time of trains at urban rail stations is pertinent to determining the line capacity and fleet size. The assumption of uniform boarding and alighting leads to under-estimation of the standing time. It is shown that the train standing-time is related to the fraction of boarders and the maximum demand for boarding and alighting at a door. It is further shown that the probability distribution of passengers at a door depends on the platform entrance locations. A methodology that takes into account the above factors is proposed for estimating the train standing-time.     

Equity-oriented skip-stopping schedule optimization in an oversaturated urban rail transit network

In this study, we focus on improving system-wide equity performance in an oversaturated urban rail transit network based on multi-commodity flow formulation. From the system perspective, an urban rail transit network is a distributed system, where a set of resources (i.e., train capacity) is shared by a number of users (i.e., passengers), and equitable individuals and groups should receive equal shares of resources. However, when oversaturation occurs in an urban rail transit network during peak hours, passengers waiting at different stations may receive varying shares of train capacity leading to the inequity problem under train all-stopping pattern. Train skip-stopping pattern is an effective operational approach, which holds back some passengers at stations and re-routes their journeys in the time dimension based on the available capacity of each train. In this study, the inequity problem in an oversaturated urban rail transit network is analyzed using a multi-commodity flow modeling framework. In detail, first, discretized states, corresponding to the number of missed trains for passengers, are constructed in a space-time-state three-dimensional network, so that the system-wide equity performance can be viewed as a distribution of all passengers in different states. Different from existing flow-based optimization models, we formulate individual passenger and train stopping pattern as commodity and network structure in the multi-commodity flow-modeling framework, respectively. Then, we aim to find an optimal commodity flow and well-designed network structure through the proposed multi-commodity flow model and simultaneously achieve the equitable distribution of all passengers and the optimal train skip-stopping pattern. To quickly solve the proposed model and find an optimal train skip-stopping pattern with preferable system-wide equity performance, the proposed linear programming model can be effectively decomposed to a least-cost sub-problem with positive arc costs for each individual passenger and a least-cost sub-problem with negative arc costs for each individual train under a Lagrangian relaxation framework. For application and implementation, the proposed train skip-stopping optimization model is applied to a simple case and a real-world case based on Batong Line in the Beijing Subway Network. The simple case demonstrates that our proposed Lagrangian relaxation framework can obtain the approximate optimal solution with a small-gap lower bound and a lot of computing time saved compared with CPLEX solver. The real-world case based on Batong Line in the Beijing Subway Network compares the equity and efficiency indices under the operational approach of train skip-stopping pattern with those under the train all-stopping pattern to state the advantage of the train skip-stopping operational approach.     

Train design and routing optimization for evaluating criticality of freight railroad infrastructures

Freight transportation by railroads is an integral part of the U.S. economy. Identifying critical rail infrastructures can help stakeholders prioritize protection initiatives or add necessary redundancy to maximize rail network resiliency. The criticality of an infrastructure element, link or yard, is based on the increased cost (delay) incurred when that element is disrupted. An event of disruption can cause heavy congestion so that the capacity at links and yards should be considered when freight is re-routed. This paper proposes an optimization model for making-up and routing of trains in a disruptive situation to minimize the system-wide total cost, including classification time at yards and travel time along links. Train design optimization seeks to determine the optimal number of trains, their routes, and associated blocks, subject to various capacity and operational constraints at rail links and yards. An iterative heuristic algorithm is proposed to attack the computational burden for real-world networks. The solution algorithm considers the impact of volume on travel time in a congested or near-congested network. The proposed heuristics provide quality solutions with high speed, demonstrated by numerical experiments for small instances. A case study is conducted for the network of a major U.S. Class-I railroad based on publicly available data. The paper provides maps showing the criticality of infrastructure in the study area from the viewpoint of strategic planning.     

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.     

Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition

This paper focuses on the simultaneous passenger train routing and timetabling problem on the rail network consisting of both unidirectional and bidirectional tracks using an efficient train-based Lagrangian relaxation decomposition. We first build an integer linear programming model with many 0–1 binary and non-negative integer decision variables, after then reformulate it as a train path-choice model for providing an easier train-based Lagrangian relaxation decomposition mechanism based on the construction of space-time discretized network extending from node-cell-based rail network. Moreover, through reformulating safety usage interval restrictions with a smaller number of constraints in this reformulated model, the train-based decomposition needs fewer Lagrangian multipliers to relax these constraints. On the basis of this decomposition, a solving framework including a heuristic algorithm is proposed to simultaneously optimize both the dual and feasible solutions. A set of numerical experiments demonstrate the proposed Lagrangian relaxation decomposition approach has better performances in terms of minimizing both train travel time and computational times.     

Train scheduling simulation that minimises operational conflicts due to service constraints

This paper presents an attempt made to facilitate re‐scheduling of trains to minimize operational delays and accommodate uniform headways for off peak sub urban services subject to resource constraints such as locomotive availability, poor track conditions and stations without siding facilities. The paper describes the computer simulation model designed to optimize train schedules on single‐track rail lines. Using this simulation program it is possible to plan and optimize timetables for railway networks with train runs within short time periods for both single track and double track conditions. The paper describes the capabilities of presenting the results of the simulation runs. These include the time‐distance graph, the network with train movements, dialog boxes with information about selected trains. The programme is capable of changing the starting point, departure time, train destinations and adding or deleting a stop etc. from the user interface. Four objects of array variables are used in the simulation process to keep train and station data. Two object arrays are used for the train movements in up and down directions. The stations' data are stored in the other two object arrays. One of these arrays of stations contains all the stations of the line while the other one contains only the stations with siding facilities. A case study that covers a 61 km long single‐track line with 14 stations is presented to highlight the model capabilities.     

High-Speed Rail Operations on an Existing Network: An Assessment Model for China

High-speed rail operations have the potential to reduce the long-term decline in rail passenger travel demand for the medium to long distance inter-urban markets. Such decline has been evident through most of the industrialized countries where air and road transport tend to be the dominant modes. In China, the operations of long distance high-speed rail on fully dedicated track is not very easy to implement, due to the high proportion of passengers who travel between high-speed and conventional railways. An alternative approach would be to allow for mixed operations with trains of various speeds on the same track. This article puts forward a simulation model designed to allow an evaluation of the most efficient distance for high-speed rail operations under mixed train speed scenarios. The model takes into account the main operating parameters such as passenger volumes, train speeds, capital and maintenance costs, train operating costs and energy consumption. The distance of high-speed train running on conventional rail that will yield the most economic benefit can be estimated using the model. The article includes the results of using the model for a specific example. It is concluded that large-scale high-speed trains have the potential to be successfully operated on conventional rail networks.     

Train routing and timetabling problem for heterogeneous train traffic with switchable scheduling rules

This paper proposes a mathematical model for the train routing and timetabling problem that allows a train to occasionally switch to the opposite track when it is not occupied, which we define it as switchable scheduling rule. The layouts of stations are taken into account in the proposed mathematical model to avoid head-on and rear-end collisions in stations. In this paper, train timetable could be scheduled by three different scheduling rules, i.e., no switchable scheduling rule (No-SSR) which allows trains switching track neither at stations and segments, incomplete switchable scheduling rule (In-SSR) which allows trains switching track at stations but not at segments, and complete switchable scheduling rule (Co-SSR) which allows trains switching track both at stations and segments. Numerical experiments are carried out on a small-scale railway corridor and a large-scale railway corridor based on Beijing–Shanghai high-speed railway (HSR) corridor respectively. The results of case studies indicate that Co-SSR outperforms the other two scheduling rules. It is also found that the proposed model can improve train operational efficiency.     

高铁枢纽建设与城市功能空间协同发展效率评价

随着我国高铁迅速发展,高铁建设如何与城市功能空间协同发展的问题引起广泛关注。为了评价高铁与城市协同发展的效率,本文从城市协同性、高铁枢纽建设、站城距离等角度,构建高铁枢纽建设与城市功能空间协同发展效率评价指标体系。并引入DEA模型进行分析计算其效率匹配度,为城市既有高铁站与城市协同发展程度提供依据。最后以京沪高铁为案例分析了24个车站与所在城市的协同关系效率值,结果表明,北京南站、上海虹桥站等高铁枢纽发展较好,常州北站、苏州北站、天津南站等较差,尤其是天津南站的通过能力、客流量等产出指标还需要进一步加强。     

A study of train dwelling time at the hong kong mass transit railway system

This paper investigates the relationship between the dwelling time of trains and the crowding situations at Mass Transit Railway (MTR) stations in Hong Kong. Regression models were established for the dwelling delays of trains due to congestion at stations, and a simulation model making use of the Monte-Carlo technique is developed to assess the reliability of the estimated train dwelling time. Therefore, the distribution and the confidence interval of the train dwelling time can be predicted on the basis of observed boarding and alighting distributions.     

Online distributed cooperative model predictive control of energy-saving trajectory planning for multiple high-speed train movements

The cooperative energy-efficient trajectory planning for multiple high-speed train movements is considered in this paper. We model all the high-speed trains as the agents that can communicate with others and propose a local trajectory planning control model using the Model Predictive Control (MPC) theory. After that we design an online distributed cooperative optimization algorithm for multiple train trajectories planning, under which each train agent can regulate the trajectory planning procedure to save energy using redundancy trip time through tuning ACO’s heuristic information parameter. Compared to the existing literature, the vital distinctions of our work lies not only on the online cooperative trajectory planning but also on the distributed mechanism for multiple high-speed trains. Experimental studies are given to illustrate the effectiveness of the proposed methods with the practical operational data of Wuhan-Guangzhou High-speed Railway in China.     

A heuristic for the train pathing and timetabling problem

In a railroad system, train pathing is concerned with the assignment of trains to links and tracks, and train timetabling allocates time slots to trains. These important tasks were traditionally done manually, but there is an increasing move toward automated software based on mathematical models and algorithms. Most published models in the literature either focus on train timetabling only, or are too complicated to solve when facing large instances. In this paper, we present an optimization heuristic that includes both train pathing and train timetabling, and has the ability to solve real-sized instances. This heuristic allows the operation time of trains to depend on the assigned track, and also lets the minimum headway between the trains to depend on the trains’ relative status. It generates an initial solution with a simple rule, and then uses a four-step process to derive the solution iteratively. Each iteration starts by altering the order the trains travel between stations, then it assigns the services to the tracks in the stations with a binary integer program, determines the order they pass through the stations with a linear program, and uses another linear program to produce a timetable. After these four steps, the heuristic accepts or rejects the new solution according to a Threshold Accepting rule. By decomposing the original complex problem into four parts, and by attacking each part with simpler neighborhood-search processes or mathematical programs, the heuristic is able to solve realistic instances. When tested with two real-world examples, one from a 159.3 km, 29-station railroad that offers 44 daily services, and another from a 345 km, eight-station high-speed rail with 128 services, the heuristic obtained timetables that are at least as good as real schedules.     

Standardization of capacity unit for headway-based rail capacity analysis

Determining the required capacity upgrades to accommodate future demand is a critical process in assisting public and private financing of capacity investments. Conventional railway systems usually operate multiple types of trains on the same track. These different types of trains can exert substantially different capacity impact, and can cause serious operational conflicts. In the past, rail line capacity is commonly defined as the maximum number of trains that can be operated on a section of track within a given time period. However, a specific unit (trains/hr or trains/day) does not reflect the heterogeneity of train types. According to the concept of base train equivalents (BTE) and base train unit (BTU), this study developed headway-based models to determine BTE for transforming different train types into a standard unit (i.e., BTU). An approximate method for lines with three and more types of trains was also proposed to compute BTEs for non-base trains. Results from the case studies demonstrate that this method enables the standardization of rail capacity unit, facilitates assessment of the impact from heterogeneous trains, and allows comparison and evaluation of the capacity measurements from different lines and systems.     

An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows

The solution of routing problems with soft time windows has valuable practical applications. Soft time window solutions are needed when: (a) the number of routes needed for hard time windows exceeds the number of available vehicles, (b) a study of cost-service tradeoffs is required, or (c) the dispatcher has qualitative information regarding the relative importance of hard time-window constraints across customers. This paper proposes a new iterative route construction and improvement algorithm to solve vehicle routing problems with soft time windows. Due to its modular and hierarchical design, the solution algorithm is intuitive and able to accommodate general cost and penalty functions. Experimental results indicate that the average run time performance is of order O(n²). The solution quality and computational time of the new algorithm has been compared against existing results on benchmark problems. The presented algorithm has improved thirty benchmark problem solutions for the vehicle routing problems with soft time windows.     

Transportation service procurement problem with transit time

In this work, we investigate transit time in transportation service procurement, which is conducted by shippers using auctions to purchase transportation service from carriers in the planning stage. Besides cost, we find that many shippers are most concerned with transit time in practice; shorter transit time indicates better transportation service. To minimize both the total cost and transit time, the problem faced by shippers is the biobjective transportation service procurement problem with transit time. To solve the problem, we introduce a biobjective integer programming model that can also accommodate some important business constraints. A biobjective branch-and-bound algorithm that finds all extreme supported nondominated solutions is developed. To speed up the algorithm, two fast feasibility checks, a network flow model for particular subproblems, and lower bounds from relaxation are proposed. In addition, a sophisticated heuristic is introduced to meet shipper’s requirements in some situations. Computational experiments on evaluating the performance of the algorithms are conducted on a set of test instances that are generated from practical data.     

基于客户满意度的货运动车组开行方案研究

高铁货运逐渐兴起,本文对货运动车组开行方案优化进行了研究。针对高铁运输安全、快捷、运输成本较低等特性,提出以货运动车组及客货混编动车组为主,客运动车组捎带运输为补充的开行模式,结合运输需求、线路通过能力等限条件,以运输成本最小和货主满意度最大为目标,建立多目标综合优化模型,运用线性加权组合法,以lingo软件为依托进行求解。通过算例给出具体开行方案,并对同一运输区间各种运输方式的单位成本及用时进行对比分析。结果表明,相对于传统运输方式,高铁货运综合运输成本较低,用时更短,能够兼顾运输企业与货主的双重要求;所建模型优化效果明显,可为未来货运动车组的开行提供参考。