Comprehensive optimization of urban rail transit timetable by minimizing total travel times under time-dependent passenger demand and congested conditions

The comprehensive optimization of the timetables of urban rail transit systems under more realistic conditions is essential for their practical operation. Currently, most time-dependent timetabling models do not adequately consider train capacity and variable operation parameters. To bridge this gap, this study mainly investigates the timetable design problem of the urban rail transit system so as to adapt to time-dependent passenger demand under congested conditions by considering the variable number of trains, train running time, and train dwell time. Two nonlinear non-convex programming models are formulated to design timetables with the objective of minimizing the total passenger travel time (TTT) under the constraints of train operations, and passenger boarding and alighting processes. The difference between the two models is that one is a train-capacity unconstrained model and the other is a train-capacity constrained model. The proposed models are examined through real-world cases solved by the adaptive large neighborhood search algorithm. The results show that the first model can minimize passenger TTT under dynamic passenger demand, whereas the second can comprehensively optimize passenger TTT and meantime keep the train load factor within a reasonable level. Accordingly, it is concluded that the proposed models are more realistic.     

Metaheuristics for High School Timetabling

In this paper we present the results of an investigation of the possibilities offered by three well-known metaheuristic algorithms to solve the timetable problem, a multi-constrained, NP-hard, combinatorial optimization problem with real-world applications. First, we present our model of the problem, including the definition of a hierarchical structure for the objective function, and of the neighborhood search operators which we apply to matrices representing timetables. Then we report about the outcomes of the utilization of the implemented systems to the specific case of the generation of a school timetable. We compare the results obtained by simu lated annealing, tabu search and two versions, with and without local search, of the genetic algorithm. Our results show that GA with local search and tabu search based on temporary problem relaxations both outperform simulated annealing and handmade timetables.     

Modelling and optimization of average travel time for a metro line by simulation and response surface methodology

This research presents a modelling and solution approach based on discrete-event simulation and response surface methodology for dealing with average passenger travel time optimization problem inherent to the metro planning process. The objective is to find the headways optimizing passenger average travel time with a satisfactory rate of carriage fullness. Due to some physical constraints, traffic safety and legal requirements, vehicle speeds cannot be raised any further to decrease travel time. But travel time can be optimized by arranging headways (i.e. the time period between the departure times of two consecutive transportation vehicles) in a timetable. In the presented approach, simulation metamodels that best fit the data collected from the simulated experiments are constructed to describe the relationship between the responses (average travel time and rate of carriage fullness) and input factors (headways). Then, the Derringer–Suich multi-response optimization procedure is used to determine the optimal settings of the input factors that produce the minimum value of the average travel time by providing a proper rate of carriage fullness. This methodology is applied for a real metro line, and good quality solutions are obtained with reduced number of experiments that needed to provide sufficient information for statistically acceptable results.     

公交网络时刻表再协同设计的多目标优化模型

为了改善公交服务质量,公交运营者试图调整现有时刻表的发车时间,使不同线路的车次协同到达换乘站点以方便乘客换乘。针对此场景,研究了公交时刻表重新协同设计问题,提出了求解该问题的多目标模型。模型考虑了对发车间隔灵敏的乘客需求、灵活的车次协同到站方式和发车时间的规则性,分析了该多目标模型的特征和计算复杂性,表明本文研究的问题是NP-hard问题,且它的帕累托最优前沿是非凸的,设计了基于非支配排序的遗传算法求解模型。算例表明,与枚举算法相比,提出的求解算法在较短的时间内可获得高质量的帕累托解。     

Design method using hybrid of line-type and circular-type routes for transit network system optimization

Transit network design is a very important problem. In particular, it has a great influence on passenger satisfaction with the whole transit network system. The present research proposes a simulated annealing (SA) method for optimizing a transit network design. In the algorithm, the strategy to search for neighborhood solutions provides the chance to find the best hybrid of line-type and circular-type routes. The proposed SA method is also compared with other methods. The results show that the proposed SA model is a good alternative for transit network design, particularly as it provides the scope to design hybrids of line-type and circular-type routes.     

Developing railway timetables which guarantee a better service

In order to improve passenger service, a waiting cost function, weighting different types of waiting times and late arrivals, is designed and minimised. The approach is applied to a small part of the Belgian railway network. In the first phase of the approach, ideal buffer times are calculated to safeguard connections when the arriving train is late. These buffer times are based on the delay distributions of the arriving trains and on the weighting of different types of waiting times. In a second phase, standard linear programming is used to construct an improved timetable with well-scheduled connections and, whenever possible, with ideal buffer times. Simulation compares different timetables and optimises the LP timetable. For the case of the Belgian railway network, the final result is a timetable with well-scheduled connections and a waiting cost that is 40% lower than the current timetable. Since only LP modelling is applied, the proposed technique is very promising for developing better timetables—even for very extensive railway networks.     

Estimating bus passenger waiting times from incomplete bus arrivals data

This paper considers the problem of estimating bus passenger waiting times at bus stops using incomplete bus arrivals data. This is of importance to bus operators and regulators as passenger waiting time is a key performance measure. Average waiting times are usually estimated from bus headways, that is, time gaps between buses. It is both time-consuming and expensive to measure bus arrival times manually so methods using automatic vehicle location systems are attractive; however, these systems do not usually provide 100% data coverage and missing data are problematical. The paper contributes to the general theory of estimating headway variance using incomplete data. Various methods for replacing missing buses or discarding spurious bus headways are compared and tested on different data sets.     

Vehicle routing problems with time windows and multiple service workers: a systematic comparison between ACO and GRASP

This paper systematically compares an ant colony optimization (ACO) and a greedy randomized adaptive search procedure (GRASP) metaheuristic. Both are used to solve the vehicle routing problem with time windows and multiple service workers. In order to keep the results comparable, the same route construction heuristic and local search procedures are used. It is shown that ACO clearly outperforms GRASP in the problem under study. Additionally, new globally best results for the used benchmark problems are presented.     

Robust Metaheuristic Algorithm for Redundancy Optimization in Large-Scale Complex Systems

Based upon the general tabu search methodology, this paper develops a robust metaheuristic algorithm for the redundancy optimization in large-scale complex system reliability that performs a rigorous search of the “attractive” feasible space and is capable of escaping from a local solution. An illustrative example is provided and extensive computational results are reported on two test problems from the literature (Aggarwal, 1976; Shi, 1987) and also on randomly generated large-scale instances of complex systems with up to 200 components. The computational results indicate that the proposed metaheuristic algorithm possesses a superior robustness and efficiency for solving the class of hard optimization problems studied in this paper.     

Strategic timetable scheduling for last trains in urban railway transit networks

Well-designed timetables, with appropriate coordination between the last feeder trains and the last connecting trains so that passengers can enjoy “smooth” transfers, are desired by passengers and are a major service goal of metro corporations. This paper addresses the strategically last train scheduling problem in urban railway transit networks. First, two practical optimization models for last trains are proposed to minimize the standard deviation of transfer redundant times and to balance the last train transfers in subway networks. Second, we design a new heuristic algorithm to solve the developed models. Finally, the models and the heuristic are applied to the Beijing subway network. The results show that the last train timetables for the Beijing subway network have been improved by increasing the average travelling speed and the average technical speed by 9.9% and 8.42%, respectively. This means that the last train passengers can save 97.4 min in total in the Beijing subway network when riding last trains.     

The planning of headways in urban public transit

A basic issue in the planning of urban public transport is the determination of headways or inter-dispatch times. During each season, i.e. distinct time-period whose demand characteristics are constant, the following tradeoff must be considered. Dispatching too many vehicles on a route causes high operating costs, while too few vehicles may result in unsatisfactory levels of service. An appropriate policy on headways will help to balance resources between lines (routes) in peak-demand hours and will influence the total number of buses acquired by a transit company. Previous practice in industry usually bases the planning of headways upon satisfying service criteria on a most-congested segment. This approach reduces the problem from that of studying a route to that of a single segment (stop), but thereby fails to account for other important information about the line's characteristics. In this article, we develop two new service criteria which consider the line as a whole: (1) crowding-over-distance takes into account discomfort resulting from a vehicle carrying too many passengers, and the corresponding distance travelled; and (2) probability-of-failure, the frequency with which a waiting passenger fails to board due to lack of space. COD will be analyzed using simulation. POF will be related to a time-dependent Markov chain that is inhomogeneous in terms of distance along the route. Optimal headways are those which dispatch the smallest number of buses while meeting the particular service criterion. Models based on each of the two criteria are illustrated and applied to a number of routes of the Israeli transit company, DAN.The preparation of this paper was partially supported by the Natural Sciences and Engineering Research Council of Canada, Grant No. OGP 05292.     

A simplicial decomposition method for the transit equilibrium assignment problem

A transit equilibrium assignment problem assigns the passenger flows on to a congested transit (public transportation) network with asymmetric cost functions and a fixed origin-destination matrix. This problem which may be formulated in the space of hyperpath flows, is transformed into an equivalent problem in the space of total arc flows and an auxiliary variable. A simplicial decomposition algorithm is developed and its convergence is proved under the usual assumptions on the cost functions. The algorithm requires relatively little memory and its efficiency is demonstrated with computational results.     

Strategic route extension in transit networks

This study proposes a methodology through which transportation analysts and policy makers can use spatial optimization to support strategic planning, with the goal of extending existing service networks. Based on modeling objectives common to many service industries, an approach is developed for integrating geographic information systems (GIS) and spatial optimization modeling in order to extend an existing transit system through prioritizing route and stop additions. Development of a strategic methodology such as this is vital for agencies interested in extending transit networks to accommodate urban growth and development. This is especially true in public transit applications, such as bus route planning, as the future of bus-based public transportation depends on the success of route expansion and modification. The developed approach is applied to the transit system in Columbus, Ohio.     

Transit passenger origin-destination estimation in congested transit networks with elastic line frequencies

This paper deals with the transit passenger origin-destination (O-D) estimation problem by using updated passenger counts in congested transit networks and outdated prior O-D matrix. A bilevel programming approach is extended for the transit passenger O-D updating problem where the upper-level problem seeks to minimize the sum of error measurements in passenger counts and O-D matrices, while the lower level is the stochastic user equilibrium assignment problem for congested transit networks. The transit assignment framework is based on a frequency-adaptive transit network model in this paper, which can help determine transit line frequencies and the network flow pattern simultaneously in congested transit networks. A heuristic solution algorithm is adapted for solving the transit passenger O-D estimation problem. Finally, a numerical example is used to illustrate the applications of the proposed model and solution algorithm. The work described in this paper was mainly supported by two research grants from the Research Grants Council of the Hong Kong Special Administrative Region (Project No. PolyU 5143/03E and PolyU 5040/02E).     

Optimizing the release of passenger flow guidance information in urban rail transit network via agent-based simulation

The passenger flow guidance is an effective demand management strategy to alleviate the excessive congestion in the urban rail transit network. In order to determine the scope and the timing, a simulation-based optimization model is proposed to optimize the release of passenger flow guidance information in the rail transit network in this paper. In the optimization model, we mainly focus on three aspects namely; where, when and what type of the guidance information should be released to the passengers. In the simulation model, the passenger choice behavior is captured by the agent-based simulation method, which responses to the congestion and the guidance information. Based on this, the dynamic passenger flow distribution can be derived. Furthermore, the adoption rate of the displayed guidance information on passenger information system as well as its impact on passenger travel behavior are also considered in the model. A hybrid heuristic solution algorithm, integrated with passenger simulator and genetic algorithm, is developed to solve the proposed simulation-based optimization model. Finally, a case study of Beijing subway is carried out with the large-scale smart card data. The numerical study shows that the passenger flow demand affects the guidance effect significantly and the best guidance effect can be met with sufficiently high passenger flow demand. And the guidance rate is also found to affect the guidance results. The results also show that the proposed model can provide a detailed guidance scheme for every station at selected time intervals. The results show that the dynamic releasing scheme can save up to a total of 46,319 min in passenger travel time during a single guidance period.     

Routing a mix of conventional,plug-in hybrid,and electric vehicles

We introduce an electric vehicle routing problem combining conventional, plug-in hybrid, and electric vehicles. Electric vehicles are constrained in their service range by their battery capacity, and may require time-consuming recharging operations at some specific locations. Plug-in hybrid vehicles have two engines, an internal combustion engine and an electric engine using a built-in rechargeable battery. These vehicles can avoid visits to recharging stations by switching to fossil fuel. However, this flexibility comes at the price of a generally higher consumption rate and utility cost.To solve this complex problem variant, we design a sophisticated metaheuristic which combines a genetic algorithm with local and large neighborhood search. All route evaluations, within the approach, are based on a layered optimization algorithm which combines labeling techniques and greedy evaluation policies to insert recharging stations visits in a fixed trip and select the fuel types. The metaheuristic is finally hybridized with an integer programming solver, over a set partitioning formulation, so as to recombine high-quality routes from the search history into better solutions. Extensive experimental analyses are conducted, highlighting the good performance of the algorithm and the contribution of each of its main components. Finally, we investigate the impact of fuel and energy cost on fleet composition decisions. Our experiments show that a careful use of a mixed fleet can significantly reduce operational costs in a large variety of price scenarios, in comparison with the use of a fleet composed of a single vehicle class.     

Hybrid large neighborhood search for the bus rapid transit route design problem

Due to an increasing demand for public transportation and intra-urban mobility, an efficient organization of public transportation has gained significant importance in the last decades. In this paper we present a model formulation for the bus rapid transit route design problem, given a fixed number of routes to be offered. The problem can be tackled using a decomposition strategy, where route design and the determination of frequencies and passenger flows will be dealt with separately. We propose a hybrid metaheuristic based on a combination of Large Neighborhood Search (LNS) and Linear Programming (LP). The algorithm as such is iterative. Decision upon the design of routes will be handled using LNS. The resulting passenger flows and frequencies will be determined by solving a LP. The solution obtained may then be used to guide the exploration of new route designs in the following iterations within LNS. Several problem specific operators are suggested and have been tested. The proposed algorithm compares extremely favorable and is able to obtain high quality solutions within short computational times.     

Integration of timetable planning and rolling stock in rapid transit networks

The aim of this paper is to propose an integrated planning model to adequate the offered capacity and system frequencies to attend the increased passenger demand and traffic congestion around urban and suburban areas. The railway capacity is studied in line planning, however, these planned frequencies were obtained without accounting for rolling stock flows through the rapid transit network. In order to provide the problem more freedom to decide rolling stock flows and therefore better adjusting these flows to passenger demand, a new integrated model is proposed, where frequencies are readjusted. Then, the railway timetable and rolling stock assignment are also calculated, where shunting operations are taken into account. These operations may sometimes malfunction, causing localized incidents that could propagate throughout the entire network due to cascading effects. This type of operations will be penalized with the goal of selectively avoiding them and ameliorating their high malfunction probabilities. Swapping operations will also be ensured using homogeneous rolling stock material and ensuring parkings in strategic stations. We illustrate our model using computational experiments drawn from RENFE (the main Spanish operator of suburban passenger trains) in Madrid, Spain. The results show that through this integrated approach a greater robustness degree can be obtained.     

Flexible <Emphasis Type="Italic">versus</Emphasis> fixed timetabling: a case study

This case study presents the timetabling problem of the Flight Training Department at Embry-Riddle Aeronautical University. The problem consists of scheduling the flight resources to students to various time blocks. This problem represents a well-studied field in operations research, mainly adopting variations of mathematical programming models. This paper initially presents the efforts towards developing a fixed timetable using optimization models for the case under study. It is, however, demonstrated that implementation of optimum solutions obtained using this approach cannot be sustained, mainly because of the dynamic nature of the governing parameters. A flexible and dynamic timetable utilizing the university computer network, allowing the instructors and students to make their own decentralized flexible timetables, is proposed. A simulation study is initiated to compare the performance measures under both timetables. The analysis shows that implementation of a flexible system generates higher utilization of flight resources as well as improving key performance measures.     

Real-time freight locomotive rescheduling and uncovered train detection during disruption

This paper discusses rescheduling of freight train locomotives when dealing with a disrupted situation in the daily operations in Japan. Within the current framework of dispatching processes, passenger railway operators modify the entire timetables and an adjusted freight train timetable is distributed to a freight train operator. For this timetable, we solve the locomotive rescheduling problem by changing the assignment of the locomotives to all the trains and considering their periodic inspections. We then solve the uncovered train detection problem that selects unassigned trains according to their value if the rescheduling phase fails.