Optimization Of Rolling Stock Scheduling In Long Urban Rail Transit Lines With Multiple Depots And Multiple Line Services

As one of the main public transportation modes in medium-sized and large-sized cities,urban rail transit is recently undergoing a rapid development in many countries(e.g.,China),owing to its many advantages including large capacity,all-weather fast service,safety,reliability,and environmental-friendliness.With the expansion of the cities in China,the operating length of urban rail transit lines may have been increasing,and more urban rail transit lines with multiple depots and multiple intermediate turnback stations have been operated by adopting multiple(full-length and short-turning)line services and rolling stock compositions(distinguished by carriage number)as well as different(express and local)stopping patterns,with the purpose of meeting the time-dependent varying passenger demand among different segments of these urban rail transit lines.The above-mentioned more flexible operation organization methods are likely to improve the service level of urban rail transit lines,however,they also increase the corresponding difficulty of the planning process and daily operation management of urban rail transit companies/operators.Rolling stock scheduling is an important tactical problem in the hierarchical planning process for urban rail transit system.First,the results of the rolling stock scheduling,denoted as the rolling stock schedule and include the rolling stock rotation plan and the daily rolling stock depot deadhead schedule,verify the practical feasibility of the predetermined passenger train timetable;only when a feasible rolling stock schedule is established,the predetermined passenger train timetable is feasible and can be put into motion.Second,rolling stock schedule is the basis for subsequent crew scheduling and real-time traffic management.A good rolling stock schedule in urban rail transit lines can also reduce the operation cost of rolling stocks and increase the usage efficiency of crews,by reducing the non-productive deadhead distance and non-productive working time.Nevertheless,in spite of the above-mentioned practical relevancies of rolling stock scheduling,it is still addressed manually by the urban rail transit operators,with the help of computer-aided decision support tools,which mainly provide convenient user interface and visualization supports but with insufficient optimization ability.Good rolling stock schedules with theoretically guaranteed quality cannot always be efficiently computed,owing to lack of lower bounding capacity to assess the quality of these schedules comprehensively.In this context,it is necessary to conduct continuous researches on the optimization methods for rolling stock scheduling in urban rail transit lines with the full consideration of the practice,by developing efficient and practically feasible optimization models and the corresponding exact and heuristic algorithms,and thus improving the automation level of the urban rail transit operators in preparing high-quality rolling stock schedules.This paper first conducts a thorough literature review on the rolling stock scheduling problems in urban rail transit system and analyzes the shortcomings of these previous related works.Considering the practical conditions and operating characteristics of the urban rail transit lines in China,this paper then studies the rolling stock scheduling problem in a complicated and long urban rail train line(with multiple depots and turnback stations,multiple line services,and multiple rolling stock compositions)under the Chinese case,with the purpose of increasing the efficiency and quality of the rolling stock scheduling,saving the operating cost,and relieving the workload of urban rail transit operators caused by making rolling stock schedules manually.Specifically,this paper investigates the problem of the rolling stock rotation planning and that of the daily rolling stock depot deadhead scheduling,as well as the integrated version of the above two problems(i.e.,the rolling stock scheduling).By using the advanced operations research methods,the above studied problems are formulated as integer linear programming models,which are further solved efficiently by the proposed exact and heuristic algorithms.The works and contributions of this paper are summarized as follows.(1)Taking into consideration of the hierarchical planning process for urban rail transit in China,this paper first performs qualitative analysis on the connotations,characteristics,and preparation elements of the rolling stock scheduling in urban rail transit lines with multiple depots and intermediate turnback stations,multiple line services,and multiple rolling stock compositions.Then,this paper briefly describes several modelling methods,which are widely used by previous researchers,for the rolling stock scheduling problem,including the network flow,set partitioning,time discretized time-space network,and big-M constraints formulation.The analysis on the advantages and shortcomings of the above modelling methods lays the theoretical modelling foundation for designing the corresponding integer linear models of the studied problems in subsequent chapters and sections.(2)Because rolling stock depot deadhead exiting scheduling before the operation start time is the key decision of daily rolling stock depot deadhead scheduling in urban rail transit line,this paper investigates the former problem via optimizing both the corresponding rolling stock deadhead routes and deadhead timetables.Given the train sequences composed of passenger train trips within an operation day,the rolling stock deadhead routing aims at selecting the rolling stock deadhead routes between the depots and the origin station main track of each considered train sequence.The task of the rolling stock deadhead timetabling is to determine the arrival and departure times of rolling stocks along these selected routes.By minimizing the weighted sum of the total deadhead distance and total deadhead running times of rolling stocks during the depot deadhead exiting operation,this paper formulates the studied problem as a mixed integer linear programming model,under the restriction of the depot parking capacity and different types of arrival,departure,and departure-arrival headways at depots and stations for safety purpose.Besides,because the resulting model usually has multiple optimal solutions,an auxiliary model is developed to secondly optimize the obtained rolling stock depot deadhead exiting schedule,such that unnecessary stops of rolling stocks at visited intermediate stations are avoided as much as possible and thus increasing the practical attractiveness of the obtained schedule.Finally,a large-scale real-world instance,which is constructed by means of the real-world data from the Chongqing Rail Transit Line3,is utilized to demonstrate the feasibility and effectiveness of the proposed approach.The above proposed method is the basis of the subsequent decomposition algorithm based on time periods,which is a heuristic to solve the daily rolling stock depot deadhead scheduling.(3)Considering the interactions between rolling stock depot deadhead exiting and entering operations in an operation day,this paper investigates the daily rolling stock depot deadhead scheduling by considering the above two operations simultaneously.By means of a discretized time-space network representation,we formulate the studied problem as a generalized set partitioning type binary linear model,to minimize the weighted sum of total deadhead distance and total deadhead running time during the depot deadhead exiting and entering operations.Owing to large numbers of constraints and variables in the model,a row and column generation-based algorithm RCGA is developed to solve practical-size problems efficiently.A row generation and a column generation are executed iteratively to reduce the numbers of considered constraints and variables,respectively.The pricing subproblem(to identify new variables)in column generation is decomposed into multiple simplified problems(each of which is proved to be equivalent to a shortest path problem)and can be solved in parallel.Because the solution framework of the proposed RCGA is flexible,different truncated versions of this algorithm are constructed,by considering only the κ(κ ≥ 2)shortest candidate routes of each train sequence,and thus computing good quality solutions more efficiently.Furthermore,two decomposition heuristics,which decompose the studied problem by(routing and timetabling)subproblems and by shorter time periods,respectively,are designed by means of the solution framework of the proposed RCGA.Computational experiments on a set of hypothetical instances from a hypothetical urban rail transit line and a set of realistic/real-world instances from the Chongqing Rail Transit Line 3 demonstrate that the proposed approach can compute both tight lower bounds and(near-)optimal solutions(with a relative optimality gap less than 1%)for all the tested instances within a maximum computation time of approximately3 hours for the studied tactical problem.The computed best-known solution for the real-world instance is also better than the empirical solution designed by operators mainly based on experience,in terms of both solution quality and computation time.(4)Computing the rolling stock rotation plan and daily rolling stock depot deadhead schedule sequentially may fall into local optimum or even lead to infeasibility.In this context,this paper investigates the joint optimization of the rolling stock rotation planning and daily rolling stock depot deadhead scheduling.The studied problem is formulated as a large-scale generalized set partitioning type binary linear programming model,to minimize the total deadhead distance and total deadhead running times of rolling stocks,as well as the total penalty caused by cancelling train trips.An improved method of constructing underlying discretized time-space network and that of modelling the departure-arrival headway constraint are proposed in this model to reduce the number of constraints.Because the proposed model contains a well-controlled number of constraints(owing to the proposed improved modelling method of departure-arrival headway constraints)but exponential number of variables,an improved column generation-based algorithm,which embeds both standard and truncated column generations,is designed to compute tight lower bounds and high-quality solutions for practical-size studied problem efficiently.An acceleration mechanism is also developed to increase the convergence speed of the standard and truncated column generations.Besides,in order to further improve the solution efficiency of large-scale studied problem,a heuristic two-stage decomposition algorithm,which computes the rolling stock rotation plan and daily rolling stock depot deadhead schedule sequentially,is also designed.In this twostage decomposition algorithm,the rolling stock rotation plan is computed by using an iterative search idea,i.e.,solving the passenger train trip connection plan and the rolling stock routing plan iteratively;efficient pre-processing strategy and valid inequalities are also developed to eliminate infeasible solutions to the greatest degree and thus increasing the solution efficiency of the proposed iterative search algorithm.Furthermore,by means of combinatorial Benders’ cuts for mixed integer linear programming,this paper also develops more efficient feedback mechanism based on the characteristics of the proposed model,so as to decrease the iteration number of computing the rolling stock rotation plan and the corresponding computation time.Finally,the effectiveness and efficiency of the proposed approaches are verified by a set of hypothetical instances(from a hypothetical urban rail transit line)and a set of realistic/realworld instances(from the Chongqing Rail Transit Line 3),by comparing the proposed approaches with two benchmark algorithms and the empirical method used in practice.