برنامه ریزی دوباره قطار با استفاده از الگوریتم های ژنتیکی و شبکه های عصبی مصنوعی برای راه آهن تک مسیر

Train re-scheduling problems are popular among researchers who have interest in the railway planning and operations fields. Deviations from normal operation may cause inter-train conflicts which have to be detected and timely resolved. Except for very few applications, these tasks are usually performed by train dispatchers. Due to the complexity of re-scheduling problems, dispatchers utilize some simplifying rules to resolve conflicts and implement their decisions accordingly. From the system effectiveness and efficiency point of view, their decisions should be supported with appropriate tools because their immediate decisions may cause considerable train delays in future interferences. Such a decision support tool should be able to predict overall implications of the alternative solutions. Genetic algorithms (GAs) for conflict resolutions were developed and evaluated against the dispatchers’ and the exact solutions. The comparison measures are the computation time and total (weighted) delay due to conflict resolutions. For benchmarking purposes, artificial neural networks (ANNs) were developed to mimic the decision behavior of train dispatchers so as to reproduce their conflict resolutions. The ANN was trained and tested with data extracted from conflict resolutions in actual train operations in Turkish State Railways. The GA developed was able to find the optimal solutions for small sized problems in short times, and to reduce total delay times by around half in comparison to the ANN (i.e., train dispatchers)

Developing better solutions for train (re-)scheduling problems has been drawing the attention of researchers for decades. Railway authorities aim to provide transportation services to their customers in a safe as well as effective and efficient manner. The two main constraints forcing them to regulate their services are the limitation of resources and the competition among service providers. Planning train services in tactical level (or medium term) and operational level (or short term) gain particular importance in this respect. In both planning processes inter-train conflicts are detected and resolved to produce feasible and desirable schedules. When trains interfere with one another during actual operation, some trains are delayed by stopping them at meet points (stations or sidings) to allow some others to pass without interruption. So the conflict resolution process most likely causes delay to some trains. If the total delay time incurred by a train does not exceed its recovery time or a conflict resolution delay at a particular meet point does not exceed the associated buffer time, train services are considered to be on time. However, some trains may move considerably away from their schedules, causing unplanned interferences with some other trains. In such cases train dispatchers take necessary actions to resolve inter-train conflicts. Their primary responsibility is to maintain safety in train movements. They are also responsible to keep trains on schedule by taking some controlling actions. Because conflict resolution delays contribute to trains’ overall lateness, the goodness of dispatchers’ resolutions for conflicts is one of the measures for system’s effectiveness and efficiency. The conflict resolution process, which includes a series of tasks, such as monitoring, data gathering, data processing, forecasting, decision making, and decision implementation, is only one of the responsibilities train dispatchers have to deal with during their service hours. When inter-train conflicts are anticipated to arise, dispatchers have to act effectively to re-schedule train movements by changing the locations and times of their planned meet/pass in order to maintain feasible train movements. A framework for systems approach to train re-scheduling process is depicted in Fig. 1, in which train movements are processed according to a pre-established schedule as input, and each of actual train movements is the output of the system. Trains operate in an environment with physical, managerial, and legal constraints imposing on the system. Train dispatchers continuously monitor the system and take necessary actions in a dynamic environment, in which trains are in movement during the dispatching process. This requires urgent decisions. However, train re-scheduling, like other scheduling problems, falls into a hard-to-solve (or NP-complete) class of problems (Garey and Johnson, 1979). From the system optimization point of view, conflict resolutions within a realistic time frame may have an enormous number of alternatives due to problem complexity. The number of solution alternatives increases exponentially with problem size (e.g., number of trains and meet points). Depending on the problem size, the optimal solution of train re-scheduling problems may be beyond the cognitive capability of train dispatchers. This is also the case for computers running an exact solution model established for a realistic size problem instance. The heuristic techniques that have been developed so far to solve (train) scheduling problems can provide near optimal solutions. In order to judge how good the solutions provided by train dispatchers and the heuristics developed are, one has to evaluate the provided solutions by comparison.Train re-scheduling problems have been undertaken in various modeling and solution frameworks in the literature. Three decades ago, Assad (1980) published a comprehensive survey on railway transportation models including train scheduling models. About two decades later, another survey appeared in the literature (Cordeau et al., 1998), concentrating on optimization models for the commonly studied railway routing and scheduling problems. Fay (2000), presents a fuzzy logic-based algorithm. Decisions given by train dispatchers during a 10-h period are used to develop a rule base. Trains are evaluated in a binary scheme in the algorithm, which aims to reproduce dispatcher decisions. The algorithm developed fails to find the optimal solution. Mazzarello and Ottaviani (2005) developed a traffic management system within the scope of an EU Project. The system is consisted of two parts, the first of which anticipates conflicts in the system and the second specifies the optimum velocities of each train in conflict resolutions. Heuristic algorithms are used for conflict resolutions. Trains that are already delayed and trains having priority are favorable to pass in conflict resolutions. The conflicts are resolved locally to reproduce feasible timetables. The system works separately for each dispatching territory. Rodriguez (2005) had a work-factory approach to the problem and developed a Gantt diagram. The constraints used in the model are associated with resources available, capacity and timing. The model developed was experimented on the Pierrefitte–Gonesse intersection in France. Only 6 trains are operated in this section, three TGVs, two suburban trains and a single freight train. 25,920 alternative solutions were possible. The model developed decreased the average delay to 20 s; previously it had been 1210 s. Şahin et al. (2004) developed three heuristics for train dispatching problem. The study deals only with freight trains. The algorithms cover a time window of 48 h and can obtain results in a short period of 5–10 min. The conflicts are defined in time and space and solved by integer programming. In the first heuristic, feasible solutions are generated by defining a “maximum acceptable delay” for trains. As the number of trains operated increase, feasible solutions may not be generated. The conflicts are determined and solved respectively in the second heuristic. If an infeasible solution is obtained (the maximum acceptable delay is exceeded), the conflicts of the train exceeding the maximum acceptable delay is resolved in favor of this train, thus decreasing the delay. The third heuristic includes a look-ahead variable, namely the potential conflicts of the trains. To reach the optimal solution, a branch-and-bound method is used. Heuristics developed are tested for various test problems as well as a real-life problem. In the real-life problem, the dispatchers’ decisions resulted in the total running time of 14,119 min while total delay was 6311 min. The algorithms developed decreased these values to 8245 and 437 min, respectively. Another review of models and algorithms for railway traffic scheduling and dispatching has been presented in Törnquist (2005). This comprehensive study reviews 48 approaches published between 1973 and 2005, and provides a classification framework with respect to problem type, solution mechanism, and type of evaluation. The approaches include priority-based heuristics and traditional operations research techniques such as optimization, simulation and queuing theory. Zhou and Zhong (2007) studied the train timetabling problem for single-track railways. Their solution method is based on a generalized resource-constraint project scheduling formulation with limited resources representing some operational constraints. A branch-and-bound procedure utilizing some lower and upper bound heuristics to reduce the solution space enables to find the solutions efficiently. Corman et al. (2010) test a decision support system called ROMA (Railway traffic Optimization by Means of Alternative graphs) which is a local optimization re-scheduling tool for train traffic under disturbed situations. The coordination of two complex dispatching areas controlled with the help of local ROMAs showed the effectiveness of the distributed system (versus centralized one) in terms of computation time and delay minimization under various operational scenarios. Acuna-Agost et al. (2011) developed an approach named SAPI (Statistical Analysis of Propagation of Incidents), which provides probability of events related with the progress of train’s journey that are affected by a set of incidents or disruptions. This approach is then used to reduce the size of the search space of the mixed integer program for re-scheduling problems in order to obtain near optimal solutions in reasonable durations. Törnquist Krasemann (2012) developed a greedy algorithm to obtain good-enough schedules quickly in disturbed situations, working as a complement to the previously designed re-scheduling approach based on optimization in Törnquist and Persson (2007). In recent years, some other artificial intelligence techniques have increasingly been used to solve various railway transportation problems. The approaches include the expert systems, genetic algorithms (GAs), artificial neural networks (ANNs), tabu search, simulated annealing, and an effective combination of these constituting hybrid systems. We also developed GA and ANN for train re-scheduling. The former model is used to schedule trains in a single-track railway by minimizing total (weighted) delays in conflict resolutions. The latter ANN mimics the decision behavior of train dispatchers in the conflict resolution process. The trained ANN is used to evaluate the outcomes of the GA developed. The exact solutions were also found for small sized problem instances by optimizing the total re-scheduling delay, which is the objective function in the mixed integer mathematical programming model developed for further comparisons. Additionally, another GA proposed in the literature was implemented and run for the same problem instances to evaluate the performance of the GA developed in this study. In the next two sections, the GA and ANN developed are presented, respectively, with the appropriate literature reviews. Then numerical tests and their results are given. Some comments on the models’ outcomes and potential development areas are provided in the conclusions.

A genetic algorithm (GA) for single-track railway train re-scheduling is developed and tested for 51 hypothetical problem instances. To evaluate the effectiveness of solutions provided by the GA, the results are compared with those obtained by two different supplementary solution methods, namely the artificial neural network (ANN) of train dispatchers and the exact model. The test outcomes show that the GA is superior in terms of computation time and total delay (as a measure of effectiveness) with respect to the exact model, and in terms of total delay with respect to the ANN. The GA is able to find optimal solutions for small-sized problems (up to 6 trains, 2 × 4) in about 81 s. For the rest of the problem instances (up to 17 trains, 8 × 9), the GA is able to reach solutions the same as or better than those of the ANN, the mimic model of train dispatchers. The GA can provide up to twice as better solutions in terms of total delay than those of the ANN. With respect to computation times, the GA can give better solutions in 331 s for the large problem instances tested. The GA is terminated when some stopping criteria is reached even if the convergence continues. The termination occurs when an acceptable limit for generation number, computation time, or goodness of total delay is reached. Although the GA can provide better solutions than the ANN mimicking the dispatchers, this does not mean that the models developed replace train dispatchers. On the contrary, such tools can and should only support decisions of the train dispatchers on duty. On the other hand, we can infer from the comparisons that their decisions are usually “good enough” given the complex nature of the conflict resolution problem. The GA shows us the existence of better conflict resolutions. Therefore, further investigation of train dispatchers’ decision could be made for both examining possible measures they employ but may have overlooked and finding ways to improve their decisions towards optimal decisions. It should be noted that we did not notice any specific circumstances in the train-graphs (actual schedules) that we extracted the data for ANN training and testing. But all these issues deserve further investigations. The performance of the GA developed could be improved in terms of computation time and measure of effectiveness by introducing some instrumental rules to the algorithm. The binary GA modeling approach of train re-scheduling is a simple and efficient method compared to another coding scheme in the literature implemented in this study. Eliminating the unnecessary conflicts (associated with non-interfering trains) in the individual (chromosome) representation may shorten computation time. Starting the GA with a better initial feasible schedule representation instead of a completely random one may also contribute to the increase of convergence speed. Introducing some intelligence to the crossover operator may also improve the performance of the GA.