مدیریت زمان واقعی یک پایانه قطار شهری

This paper addresses a scheduling problem arising in the real time management of a metro rail terminus. It mainly consists in routing incoming trains through the station and scheduling their departures with the objective of optimizing punctuality and regularity of train service. The purpose of this work is to develop an automated train traffic control system, able to directly implement most traffic control actions, without the authorization of the local area manager. The scheduling problem is modeled as a bicriteria job shop scheduling problem with additional constraints. The two objective functions, in lexicographical order, are the minimization of tardiness/earliness and the headway optimization. The problem is solved in two steps. At first a heuristic builds a feasible solution by considering the first objective function. Then the regularity is optimized without deteriorating the first objective function. Computational results show that the system is able to manage the terminus very efficiently.

Railway traffic optimization is experiencing an increasing interest both among researchers and practitioners. Solving problems of practical interest in this field requires using detailed models, able to represent real and different railway traffic situations, and developing efficient algorithms to be used as decision support system in traffic control operation. Railway scheduling problems have been studied by using different techniques, including linear programming, integer or non-linear programming, graph theory and dynamic programming. Among the published results, we cite the papers by Carey, 1994, Carey and Lockwood, 1995, Higgins et al., 1997, Cai et al., 1998, Adenso-Díaz et al., 1999, Şahin, 1999 and Dorfman and Medanic, 2004 and the survey paper of Cordeau et al. (1998). Most of published results focus on scheduling trains at off-line planning level and deal with simplified models, in which stations have often unlimited capacity. As observed by Carey and Carville (2003), busy stations may be the most complex part of the network to schedule. This is the case in particular when dealing with metropolitan rail networks, in which scheduling decisions along the lines are typically simple, whereas traffic control at terminal stations is made more difficult because of the smaller area available and heavy traffic conditions. This paper deals with the real time management of a metro rail terminus. The management and control of rail operations is usually based on off-line generated timetables for every train, and consists in operating in real time with strict adherence to these timetables. For a metro rail terminus, it mainly consists in routing incoming trains through the station and scheduling their departures according to the off-line timetable. However, when incoming trains are heavily delayed it is necessary to reschedule their departure times in order to provide service continuity and punctuality as much as possible. To a large extent, this task is carried out by human operators all over the world. A local area manager is in charge of setting routes and scheduling train departures with the objective of pursuing punctuality and regularity of the train service as much as possible. Computer support, when available, consists in most cases of a control panel describing the current situation of the network. On the other hand, there are several attempts to develop computerized decision support systems allowing a more efficient and easier management process. There is a limited amount of published works on routing and scheduling trains at busy stations. Carey (1994) proposes a mixed integer programming (MIP) formulation for the problem, Carey and Carville (2003) provide heuristic algorithms that sequentially considers one train at a time and defines for it an arrival time, a departure time and a platform. If there is a conflict in the schedule, arrival or departure times for some train are increased until there is no longer a conflict. Carey and Crawford (2007) extend the single-station scheduling algorithms to find and resolve conflicts on lines between stations, and carry out an extensive computational study for a corridor with several stations. Zwaneveld et al. (2001) consider the routing of trains through railway stations, given the detailed layout of the stations and a tentative timetable. They formulate the problem as a node-packing problem, and develop a branch and cut algorithm to determine a feasible path for as many trains as possible. Two additional objectives are considered in lexicographical order, namely the minimization of the number of shunting movements, and the maximization of train preferences for certain platforms or routes. Kroon et al. (1997) study the computational complexity of several variants of this routing problem. In this paper we report on the implementation of scheduling algorithms for a real time Train Management System (TMS), able to route and schedule train movements through a metro line terminus. We report in particular on the results of a research project on the management of rail traffic at an underground metro rail terminus, in Italy. The scheduling algorithm developed within the project produces a plan of movements for all trains circulating in the terminus, with the objective of optimizing punctuality and regularity of the train service. According to railway practitioners preferences, punctuality is considered more important than regularity. In fact, respecting the off-line timetable would imply automatically respecting the regularity of train service, while the converse is not true. For this reason, in this paper the two objective functions are considered in lexicographical order.

This paper addresses the real time scheduling of train service in a Metro rail terminus. Since the problem is bi-objective in nature, the train schedules are generated in two steps. The first step addresses the problem of routing and sequencing trains through the station with the objective of optimizing the punctuality, which it is solved with a fast heuristic. The second step addresses the problem of scheduling train departures with the objective of optimizing the regularity of train service, under the constraint that the first objective function does not deteriorate. This second problem is solved at optimality. The computational results, carried out on the basis of a real case, are quite promising. Unfortunately, a comparison with the performance of human local area managers was not possible, due to the real time nature of the problem. However, our results show that the scheduling algorithm is able to generate solutions that are feasible in practice. On the performance side, we observe that the optimization of punctuality is not always sufficient in order to guarantee a satisfactory level of train service. On the other hand, after optimizing the regularity, the solutions obtained are of good quality. This demonstrates the ability of the two optimization algorithms to automate train traffic control operations. Future research should address the development of exact algorithms for the routing/sequencing phase and the comparison of optimal solutions with the solutions produced by our algorithm, in order to certify the quality of the solutions obtained. A further interesting research direction would be to study the problem as a bicriteria problem, i.e. considering the two objective functions simultaneously. Clearly, the automated system has to generate a single plan of operations. However, the availability of several Pareto optimal solutions would make possible a better comparison than the lexicographical order between the two objective functions, and consequently would make possible to generate a better compromise solution.