A Rescheduling Approach for Freight Railway considering Equity and Efficiency by an Integrated Genetic Algorithm

Zhuotong Bai; Hui Wang; Lin Yang; Jiajie Li; Huapu Lu

doi:10.1155/2023/8989644

A Rescheduling Approach for Freight Railway considering Equity and Efficiency by an Integrated Genetic Algorithm

Bai, Zhuotong;Wang, Hui;Yang, Lin;Li, Jiajie;Lu, Huapu 2023-05-25 00:00:00 Hindawi Journal of Advanced Transportation Volume 2023, Article ID 8989644, 22 pages https://doi.org/10.1155/2023/8989644 Research Article A Rescheduling Approach for Freight Railway considering Equity and Efficiency by an Integrated Genetic Algorithm 1 2 3 4 1 Zhuotong Bai , Hui Wang , Lin Yang , Jiajie Li , and Huapu Lu Institute of Civil Engineering, Tsinghua University, Beijing 100084, China Department of Geography, Te University of Hong Kong, Pokfulam, Hong Kong SAR, China School of Management and Economics, Beijing Institute of Technology, Beijing 100081, China Key Laboratory of Advanced Public Transportation Science, China Academy of Transportation Sciences, Beijing 100029, China Correspondence should be addressed to Huapu Lu; luhp@mail.tsinghua.edu.cn Received 21 January 2023; Revised 6 April 2023; Accepted 10 May 2023; Published 25 May 2023 Academic Editor: Ren-Yong Guo Copyright © 2023 Zhuotong Bai et al. Tis is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Since unexpected event occurrences are inevitable, an efcient and efective rescheduling approach is critical in freight railway day-to-day operations. Represented by the minimal-delay objectives, the most commonly used efciency-oriented approach ignores the role of train priority and poses equity problems in rescheduling. For equity, diferent train priority also refects the preference in deciding train orders; i.e., the high-priority train is likely to be favorable. However, a confict may be laid between reducing delays and emphasizing train priority. Hence, it is critical to decide the criteria in train order for freight railway, especially with heterogeneous priority in a competitive resource. To make a tradeof between equity and efciency, this paper makes train priority evolutionary and proposed the dynamic train priority considering delay time and static priority. We formulate an optimization model based on the rescheduling strategies such as retime, reorder, and retrack in a complex railway network containing single-track, double-track, and quadruple-track sections. An integrated two-dimension genetic algorithm (ITGA) approach is developed to reobtain an optimized timetable of sufcient quality while meeting the time requirements for real-time rescheduling. In the experiment, the efectiveness of the ITGA approach was employed in a simple case and a real-world case in the Netherlands freight railway. Te result shows that there is a synergy between delay time and train priority, where the threshold to upgrade the evolutionary train priority plays an important role. Te proposed approach is compared with the benchmark solution frst-in-frst-out (FIFO) approach in a real-world case to verify the performance and efciency. Our work extends the rescheduling approach considering both equity and efciency and provides auxiliary operation support for the dispatcher’s operation rescheduling. reliability and carrier satisfaction in the freight railway 1. Introduction system. Freight railway holds an increasing market share in trans- Nevertheless, due to accidents such as rolling stock portation systems for high-efciency, large-volume, and eco- breakdown, driver behaviors, traveler behaviors, and even friendliness. In 2021, the Chinese freight railway volume the timetables’ quality together with extreme weather [3], the increased by 5.9% and completed a total of 4.774 billion tons. railway system sufers perturbations during real-time trafc Te timetable, which is defned as a set of arrival and de- management [4]. Tese unexpected events cause railway parture times of each train from each of its stopping stations infrastructure resources to be unavailable, resulting in trains [1], plays a vital role in guaranteeing freight railway ef- interfering with one another. To be specifc, it may cause ciency in day-to-day operations. Te design of a train train confict, which is two or more trains requesting to use timetable is a complex process subject to the capacity, safety, the same section simultaneously in operation. Detecting and resource constraints [2]. Performing in accordance with train conficts and resolving them to produce feasible and the pre-established initial timetable is essential for service desirable schedules are one of the most challenging and 2 Journal of Advanced Transportation railway network are considered. We assume trains are difcult problems in freight railway. Except for very few applications, these tasks are usually performed by train held up for 14 minutes at Station A, where the initial timetable is represented by dotted lines, while the optimized dispatchers. Tis process is so-called train timetable rescheduling. Due to the complexity of rescheduling, dis- results are represented by solid lines. To simplify the ex- patchers utilize some simplifying rules to resolve conficts ample, the section running time for each train is 5 minutes, and implement their decisions accordingly. When while the dwell time is 2 minutes. Te minimum headway rescheduling, the primary responsibility of the train dis- between two adjacent trains arriving or leaving the station is patcher is to adjust the timetable into a confict-free one for 5 minutes. safety as quickly as possible by rescheduling strategies. Te (1) Case 1 in Figure 1(a): In the scenario of frst-in- main rescheduling measures mainly contain retiming frst-out (FIFO) strategy adherence to initial train (changing train arrival and departure times), rerouting order, all trains are designated to dwell at station A (selecting a new route from feasible routes), reordering for a minimum of 14 minutes, and a total of (changing train arrival or train orders), and canceling trains 42 minutes of delay are created in the system. [5]. Accordingly, reordering makes some trains stop on (2) Case 2 in Figure 1(b): In the efciency-oriented designated siding tracks to be overtaken and allow others to scenario for minimizing the delay, medium- pass without interruption, resulting in train delays. priority trains depart earlier than high-priority A general criterion for rescheduling is the train delay ones. Without considering the train priority, the time, which is the deviation between the actual and planned system has a 34-minute delay, while the delay for arrival time. Delay time assesses the trains’ overall lateness of a high-priority train is 5 minutes, and the delay times freight railway quantitatively, which is an indicator to for other trains are 5 and 24 minutes. Moreover, the measure rescheduling timetables from the perspective of objective of minimizing the total delay cannot refect system efectiveness and efciency [6]. Consequently, the diference between whether the low-priority or minimizing delays is importantly considered in studies when the high-priority train departs earlier in this case. making decisions about train orders for the railway system. However, most railroads operate a heterogeneous set of (3) Case 3 in Figure 1(c): In the equity-oriented scenario trains with diferent priorities, which are mostly given based for emphasizing the train priority, high-priority on commodities being carried. For example, an intermodal trains have absolute priority than the lower ones train (usually a high-priority train) must have a minimum when meeting conficts. In this condition, the high- delay compared to the tolerable delays for unit trains, in priority train departs from Station A earlier than the order to satisfy the expected delivery time agreed upon with others. As a result, the caused total delay is the shipper. Hence, in practice, the criteria for train order in 42 minutes, with the high-priority train contributing rescheduling include the priority of each train, current train 0 and the other two contributing 14 and 28 minutes, delays, and expected remaining overtake and crossing delays respectively. [7]. Briefy, the criteria for deciding train orders are not To conclude, the criteria for delay time and train priority straightforward and are the result of multifactorial opti- bring about the contradiction between efciency and equity. mization. Te only objective being the minimization of train For efciency, various aforementioned studies have used the delays for efciency ignores the train priority which may lead minimal delay as the most important indicator in to high-priority delays for low-priority trains in the rescheduling to make full use of resources and achieve rescheduling area. In addition, equity refers to the distri- system optimization. For equity, the priority of trains, which bution of impacts (benefts and costs) and whether that is an important auxiliary criterion in practice, cannot be distribution is considered fair and appropriate [8]. Ignoring neglected. the train priority which is assigned by railway authorities To incorporate the interaction between efciency and which divide the trains on the basis of the type of service may equity, we attempt to explore the relationship between delay lead to an equity issue. For equity in railways, the higher the time, train priority, and the optimal matching method of basic (or static) priority, the more favorable it is to the train them. It is especially critical because there are heterogeneous [9]. In detail, when there is a heterogeneous set of trains with priority trains running in a competitive resource in freight low or high priority, high-priority trains are expected to have railways. Inspired by Corman et al. [4], we make the train a smaller deviation [10]. priority evolutionary by establishing dynamic priority based An illustrative example is shown in Figure 1 to indicate on the delay time and static train priority. Te train priority the role of criteria in deciding train orders when resched- increases when the accumulated delay exceeds the allowed uling. Te frst-in-frst-out (FIFO) strategy, efciency- delay threshold. As displayed in Figure 1(d), the low-priority oriented strategy for minimizing the delay, equity- train is upgraded when delay time reaches a certain oriented strategy for emphasizing the train priority, and threshold, subsequently, making it as favorable as the the proposed strategy for trading of between efciency and medium-priority train in departure orders deciding. Tis equity are explored in Cases 1, 2, 3, and 4, respectively. Tree approach results in a 38-minute delay, with each lower trains with diferent priorities running in a fve-station Journal of Advanced Transportation 3 Station A Station B Station D Station E Station C 14 mins Station Station 24 mins 14 mins � Delay: 42 mins � Delay: 34 mins 5 mins 5 mins 14 mins 6:30 7:00 6:00 E E D D C C B B A Time A Time disturbance disturbance Low priority Low priority Medium priority Medium priority High priority High priority (a) (b) Station Station 19 mins 28 mins � Delay: 42 mins � Delay: 38 mins 14 mins 19 mins E E D D upgrade A Time disturbance Time A disturbance Low priority Low priority Medium priority Medium priority High priority High priority (c) (d) Optimized arrival time Initial departure Initial arrival time time Case 1 Case 2 Case 3 Case 4 Low-priority train 6:00 6:26 6:40 6:50 6:54 6:45 Medium-priority train 6:09 6:31 6:45 6:36 6:45 6:50 High-priority train 6:14 6:40 6:54 6:45 6:40 6:40 Figure 1: Cases to illustrate the criteria for deciding train orders in rescheduling. (a) Case 1: the timetable with no adjustment under disturbance. (b) Case 2: the optimized timetable with efciency orientation. (c) Case 3: the optimized timetable with equity orientation. (d) Case 4: the optimized timetable with dynamic train priority. priority trains contributing half of it. Compared with the low-priority trains is 14 and 28 minutes, respectively), the efciency-oriented strategy (34 minutes total delay and the proposed strategy achieves a relatively small delay while delay time for high-, medium-, and low-priority trains is 5, 5, ensuring that high-priority trains are favorable. and 24 minutes, respectively) and equity-oriented strategy In summary, we investigate an optimization model with (42 minutes total delay and the delay time for medium- and dynamic train priority to tradeof equity and efciency. Our 4 Journal of Advanced Transportation work makes the train priority evolutionary and to be Sama et al. [18] compared and analyzed the quality of upgraded when the delay time reaches the thresholds. To multiple objective function solutions. Aiming at minimal train delay, dwell time, and timetable deviation, Kumar and make the criteria for deciding on train order straightforward, the relationship between the train priority and delay time is Mishra [19] proposed GKACO to make optimal resched- discussed. Besides, using sidings fexibly for trains in both uling. To optimize the delay time and the number of delayed directions (as retrack) and considering the operation of trains, Zhou et al. [20] formulated an MILP model for high- inbound and outbound trains in a complex railway network speed railway timetable rescheduling in large disruptions. By are coordinated in the model. Furthermore, we proposed an dispatching strategies of retime and reorder, the bufer time integrated two-dimension genetic algorithm (ITGA) to solve is made full use of to generate the rescheduling scheme. the problem. Te presented ITGA approach provides an Te above studies did not involve the ability to tolerate efcient way to resolve the confict by encoding train order perturbations and resist their potential efects. In order to as chromosomes using a matrix representation. apply in real-life applications, some research followed Tis paper is organized as follows: In Section 2, we a similar line of robustness, which refers to the capability of avoiding delay propagation as much as possible [2]. For provide an overview of related literature and highlight our contributions to it. Section 3 introduces the problem example, Cavone et al. [21] presented a three-step decision- statement and summarizes the notations and assumptions. making procedure to minimize delays and maximize ro- In Section 4, we model the problem in detail and study the bustness. Combined with the online heuristics, this paper constraints. In Section 5, the ITGA approach is designed to identifed and solved all conficts of emergency and the address the timetable rescheduling problem. Section 6 de- ofine cross-efciency fuzzy data envelopment on the op- scribes a simple case and a real-world case to demonstrate erational cost and augmentation of service reliability. Meng the efectiveness of the proposed model. Finally, the con- and Zhou [22] studied the robustness of a disrupted single- clusions and future work are discussed in Section 7. track rail line against random variations both in running times and the duration of the disruption. A stochastic programming model is obtained to identify robust schedules 2. Literature Review in a rolling horizon framework. Larsen et al. [23] tackled the train operation optimization problem when the train run- Te train timetabling rescheduling (TTR) problem is a well- ning time and staying time at the station fuctuate within studied problem in freight railways. Te main purpose of a certain range under the infuence of random uncertain rescheduling is to apply control strategies to minimize the interference. Furthermore, Layeb et al. [24] designed the negative efects of perturbations in railway systems. Goals simulation model to efciently account for real stochastic and methods are the core components of rescheduling. As behavior with skewed continuous distributions. key factors in evaluating the quality of results and solutions, However, the research mentioned above can be sum- the works of literature are reviewed under the line of ob- marized as an efciency-oriented approach focusing on jective functions and algorithms. minimizing the derivation from the perspective of the railway system. In reality, the train priority is an issue that must be taken into account in rescheduling. Liu and Kozan 2.1. Objective Functions. Various objective functions are considered in rescheduling a railway system [11]. Te ob- [25] studied mixed passenger and freight trafc in a single- line rail network. Te no-wait approach without any in- jective functions refect how to evaluate the quality of the rescheduling result, thus describing the main factors con- terruption is applied for the prioritized trains such as express sidered in rescheduling. Te most commonly considered passenger trains. With analysis of the structural properties, factors are efciency-related factors such as minimal an innovative generic constructive algorithm is proposed to (weighted) delay time. Moreover, the factors derived from it construct a feasible train timetable efciently and eco- are considered in combination, i.e., minimizing the number nomically. However, passenger trains have the absolute of delayed trains, maximizing timetable robustness, etc. priority on departure orders over freight trains; this paper discussed a passenger and freight railroad rescheduling Besides, some studies take equity into account, examining the impact of train priority in the rescheduling decision- problem essentially. Focusing on the train priority rescheduling problem, in making process. It has been recognized that consistency with the initial 1998, considering four attributes as the basic priority, critical timetable is one of the key performance indicators in rail- ratio, delay at the myopic resolution, and a number of ways. Punctuality, which is the guarantee of system ef- potential conficts, Sahin [9] proposed a utility function of ciency, is usually defned as the probability that a train weighted attributes to model the dispatcher’s choice be- arrives less than x minutes late [12]. Te total delay is the havior. Te system approach is in the construction of the most common criterion for punctuality (also reliability or heuristic algorithm to modify existing plans in conficting regularity) [13–16]. Aiming to minimize the sum of weighted situations in a single-track railway. Corman et al. [4] pre- delays, Kroon et al. [17] described a two-stage stochastic sented a novel optimization framework for the multiclass rescheduling problem on an alternative graph formulation optimization model to improve the robustness of a periodic timetable. But the paper only allocated one rescheduling of the problem. Dynamic priority combines static and dy- namic classes of priority with a branch and bound procedure strategy as retime (time supplements and bufer times). Interested in implementing diferent types of objectives, based on the actual entrance time of each train in the Journal of Advanced Transportation 5 train dispatchers and optimal or near-optimal solutions in network. Huo et al. [26] formulated the train rescheduling problem by adjusting priorities and train sequences to a reasonable length of time. To resolve the conficts, sim- ulated annealing (SA) [29], ant colony optimization (ACO) minimize the train disorder, which is the diference in train order between the initial and optimized one in the railway [30], genetic algorithm (GA) [6], particle swarm algorithm network. Te paper proposed the concept of train-order [31], tabu search algorithm [32], heuristic greedy algorithm entropy, and a binary mixed-integer programming model [33], or hybrid algorithms are implemented. was used for dispatching with minimal train operation Among them, GA performs well to provide acceptable adjustment. Shakibayifar et al. [2] implemented means of solutions at reasonable times with the search space being heuristic dispatching rules to address the delay management huge and complex because of its potential parallelism and problem in rail networks under multiple disruptions. Te robustness [6]. Chung et al. [14] proposed a hybrid genetic dynamic priority dispatching rule was applied where train algorithm to address the train-sequencing problem in railways. Te proposed algorithm utilized a modifed elite priorities are dynamically adjusted in a way that they are continuously calculated before a confict between two trains group technique and was tested with real-world data from the Korean railway. Dundar ¨ and S¸ahin [6] developed genetic is resolved. However, the allowed delay is predetermined, and the priority of the trains increases when the accumulated algorithms (GAs) for confict resolution in a single-track delay exceeds it. Taslimi et al. [10] developed a novel mixed- railway. Aiming to minimize the total (weighted) delay, the integer programming model to estimate train travel time, paper made every possible meeting train pair be represented and the paper distinguished the high-priority trains from by a specifc gene, and each gene in a chromosome repre- lower ones in the dataset, but how to handle diferent classes sents the station/siding in which possible conficts are re- of trains is unclear. Note that some research may also solved for specifc train pairs. Due to confict resolutions, Wang et al. [28] studied an improved GA for dynamic consider the equity problem in passenger railways, such as Shang et al. [27] considered an oversaturated situation in fexible job shop scheduling. To generate a high-quality initial population, the paper designed a mix of random urban rail transit networks and Banerjee and Smilowitz [8] studied to reduce the disutility in the school bus scheduling initialization populations by combining initialization ma- chine and operation and used an elitist strategy to avoid problem. In previous research, methods such as utility function falling into the local optimal solution. Indeed, the genetic and multiple-stage are used to consider efciency and equity algorithm (GA) has been proven to be efcient in solving the in freight railway rescheduling. However, it is observed that TTR problem. most criteria are specifc or only suitable for special sce- However, GA has an obvious weakness, as the con- narios; for example, one type of train has absolute priority in ventional GA-based approach’s performance deteriorates the stage (two-stage method), and the dispatcher’s per- rapidly for complex problems, especially for rescheduling problems considering network characteristics, operational ception of delay is deterministic (utility function). However, the diferences and synergies between the delay time and constraints, limited capacities, and resource availability. Terefore, in this paper, the integrated two-dimension GA train priority have not been fully evaluated. Terefore, we intend to explore whether there is a better way to explain the with dynamic train priority is studied. In implementation, relationship between them. Inspired by Corman et al. [4], train orders are presented for the coding scheme of chro- dynamic train priority is presented to establish the re- mosomes to overcome the movement conficts easily. To be lationship between the delay time and train priority. specifc, each individual in the population is represented by Moreover, in contrast to the previous studies using a sim- a two-dimension matrix, whose array represents the train plifed version, this algorithm is able to deal with the order at all stations. Besides, the search space is limited for problem in a complex railway network that consists of each gene constricted to the train delay time. single-track, double-track, and quadruple-track sections. Te method attempts to provide dispatchers with a more 2.3. Contributions. Table 1 compares recent studies on the standard, practical, and convenient method for real-world TTR problem in the key dimensions of main decision rescheduling. variables, equity problem, efciency and equity relationship, railway network topology, fexible track utility for both 2.2. Algorithms. Restricted to network characteristics, op- inbound and outbound trains, and solution algorithms. To erational constraints, limited capacities, and resource conclude, the gap lies as follows: (1) Most research considers availability, train rescheduling is a large-scale, complex, and trains with diferent priorities as equal in rescheduling. dynamic problem. Hence, the algorithm is vital in attaining Although few studied the equity problem in the freight higher punctuality on railway trafc systems. railway system, it is static and only suitable for special scenarios. (2) Most research fxes the use of the tracks, not Te exact algorithm takes enormous computational ef- forts to solve them to optimality even with advanced so- considering fexible track utility for both inbound and outbound trains. Tis approach is a simplifcation of the lution algorithms, which hinders their applications in large- scale instances in the real world. For the increased com- fexible track utility in real-world rescheduling, which is not conducive to efciency. (3) Most studies used a simplifed putational time in an exponential manner for the exact algorithm [28], a stream of heuristic algorithms has been version of railway networks such as single-track or double- developed in order to obtain better confict solutions than track, and few studies address the problem with single-track, 6 Journal of Advanced Transportation Table 1: Te comparison of the current studies on the train timetable rescheduling problem. Main decision Efciency and Railway network Flexible track Publications Equity problem Solution algorithm variables equity relationship topology utility Meng et al. [31] T.T D H (particle swarm algorithm), C Corman et al. [4] T.R, T.T, T.O √ M √ B&B Meng and Zhou [15] T.R, T.T, T.O M LR, C Kang et al. [34] T.T √ D H (GA), C Huo et al. [26] T.T, T.O S H (depth-frst method) Cavone et al. [21] T.T M C Shakibayifar et al. [2] T.T, T.O √ S H (two-stage method) Altazin et al. [35] T.T M H (greedy heuristics) Zhou et al. [20] T.T, T.O D C (Cplex) Taslimi et al. [10] T.R, T.T, T.O √ M C (Gurobi) Reynolds and Maher [13] T.R, T.T, T.O M √ Branch-and-price algorithm Tis paper T.R, T.T, T.O √ √ M √ H (GA), C Symbol descriptions: main decision variables: train arrival and departure time (T.T)/train route (T.R)/train order (T.O). Solution algorithm: branch-and-bound (B&B)/Lagrangian relaxation (LR)/heuristics (H)/ commercial solver (C). Railway network topology: M (mixed track); D (just double tracks); S (single track). Flexible track utility: use track fexible (Y); use track fxed (N). Te bold value is to highlight the distinctive qualities of this study that diferentiate it from other works in the feld. Journal of Advanced Transportation 7 double-track, or quadruple-track networks. It is not in line same time for safety. At stations, there are tracks B for with reality and thus not capable to be applied in the overtaking activities and yard tracks for temporary train real world. storage. To conclude, this paper has a number of key contri- butions to the feld of rescheduling: 3.1.1. Operation. Each train has a predefned route in the (i) To resolve the train timetable rescheduling problem, network, and every station on the route is labeled as origin, an optimization model is formulated considering intermediate, stop, or destination. Te fxed routing policy is both efciency and equity. Te proposed model utilized for each train based on the rules. Trains traveling utilizes the combined strategies of retiming, reor- from origin to the destination pass the intermediate stations dering, and retracking considering network char- and stop at stop stations with fagged workings. Train i is acteristics, operational restraints, limited capacities, taken as an example, whose origin is station 1 and desti- and resource availability. Te model deals with the nation is station 7. At the origin o(i), the train couples with fexible track utility for both inbound and outbound the locomotive, and the route of the train j is listed as (1, 2, 3, trains in a complex railway network containing 4, 5, 6, and 7) to the destination d(i). Te train stopping at single-track, double-track, and quadruple-track predetermined stations is labeled as stops for working as sections. changing crew or pick-up/drop-of railcars, while passing through stations, it is labeled as intermediate. Te route (ii) To explore the relationship between efciency and refects section occupancy in operating, and multiple tracks equity in rescheduling, we make train priority in sections can be fexibly allocated for efciency. evolutionary and propose the dynamic train priority based on the delay time and static train priority. As an important factor in rescheduling, the threshold 3.1.2. Workings. Operational workings need to be com- to upgrade the train priority is analyzed in pleted at stations labeled as stop, which are predetermined. this paper. Trains have a mandatory stop and need to pick-up/drop-of ps crew (iii) To reobtain an optimized timetable of sufcient railcars, changing crew at fagged stations S and S , quality in a reasonable period, we propose an ef- respectively. Besides, the locomotives are to be coupled at the cient and fast heuristic algorithm to fnd the optimal origins. solution. We improved the general GA into an integrated two-dimension one, and the train orders 3.1.3. Priority. Each train has the initial characteristics of are presented for the coding scheme of chromo- high or low priority. Te train priority is an important somes to avoid spatiotemporal train confict. Nu- criterion in deciding train departure order; that is, a low- merical experiments demonstrate that our proposed priority train may stop on the sidings at the station and be approach is very efcient, obtaining a high-quality overtaken by a high-priority train. In this paper, the train rescheduling timetable for a complex mixed-track priority is evolutionary based on the delay time and static railway network in a reasonable amount of time. train priority to achieve equity. In this paper, the priority of the lower train is adjusted dynamically in the timetable 3. Problem Statement rescheduling process. It will be upgraded to m when the is delay time reaches a certain threshold. Besides, the threshold In this study, the rescheduling problem on a mixed-track is also analyzed in the paper. railway network is thoroughly discussed considering both equity and efciency. Section 3.1 describes the network topology and railway operation by an illustrative railway 3.1.4. Delay. Tree kinds of delays are taken into consid- network. Section 3.2 illustrates the notation in the model, eration caused by the unavailability of the locomotive at the while Section 3.3 presents the assumption. origin station, changing crew duty, or yard operations (pick-up or drop-of railcars). Te impact of delays on adjacent train timetables must be taken into account, and the 3.1.Description. We formulate the rescheduling problem on running time at section (s, p) and minimal dwell time for a mixed-track railway network, represented by a directed trains are determined according to the planned timetable. graph and denoted as G(V, E).E is a set of directed edges as tracks, and V is the set of nodes as stations where the track 3.2. Notations. All the notations and variables used in the merges or splits. As shown in Figure 2, there are parallel formulations are listed in Tables 2 and 3. tracks K among adjacent stations (s, p). In addition to the sp main tracks K , which are 1 for single track and 2 for double sp tracks, there are sidings K as auxiliary tracks in the net- sp 3.3. Assumptions. Te assumptions made to construct the work. All the main tracks are one-way for a predetermined mathematical model in this paper are as follows: running direction, while the sidings can be fexibly used and shared for inbound and outbound trains. Te tracks cannot (1) Te rescheduling approach is performed based on be occupied by two trains in diferent directions while a fxed-speed model; the section running time for satisfying the minimum headway in the same direction at the each train is fxed and predetermined. Te trains 8 Journal of Advanced Transportation single-track line double-track line four-track line siding industrial spur Station 1 Station 2 Station 3 Station 4 Station 5 Station 6 Station 7 Main Track Siding (An auxiliary track) (a) Station 6 Station 1 Station 2 Station 3 Station 4 Station 5 Station 7 Route Track Main Track Siding (An auxiliary track) (b) Figure 2: An example of freight railway network topology: (a) original track infrastructure; (b) vertex-edge topology graph. move at their maximum allowable speed on each 4.1. Constraints track which is limited to the permissible section 4.1.1. Departure Time Constraints. Constraint (1) ensures speed and train speed [10]. that the relationship guarantees the feasibility of the (2) Any track can only be occupied by one train at the rescheduled timetable. Besides, the departure time of the same time. Trains can access the siding, yard, and train i from the station s (the start time of occupying the other mainline tracks at the stations from any of the track k between the station s and station p) equals the actual mainline tracks using the appropriate crossover. dwell time of the train i at the station s plus the arrival time at Inbound and outbound trains can share the same the station s (the end time of the train i occupying the track k siding if it is achievable, but a track of a segment can between the station s and station p). Constraint (2) links the only be used by trains running in the same direction. arrival time, departure time, and dwell time at stations: (3) Te train occupying a siding or industrial spur will be charged an additional time. Te time is to wait for the 􏽘 t ≥ t ∀i ∈ I, ∀(s, p) ∈ S(s, p), ispk is sp (1) other train to pass, receive movement permission p∈S k ∈K sp sp from the dispatcher and return to the mainline at a low speed. a d 􏽘 􏽘 t � 􏽘 􏽘 t ispk ispk sp sp (4) Tere is no change in the train route and workings, p∈S p∈S k ∈K k ∈K sp sp sp sp (2) and the trains travel according to the previous route. + stop ∀i ∈ I, ∀(s, p) ∈ S(s, p). Because reroute is applied only when big in- terruptions like disruptions occur, it will make the Te impact of delays caused by the locomotive and yard midrailway carriage unreachable which is planned to unavailability on the arrival and departure time of trains are be picked up or dropped of at stop stations. illustrated in constraints (3) and (4). Te delay at the origin for each train, which is the deviation between the 4. Train Timetable Rescheduling (TTR) Model rescheduled and planned departure time, is presented in the form of probability statistics in this paper. Te delay is In this section, we introduce our train timetable resched- greater than a certain value with a confdence level (α) from uling (TTR) model considering both efciency and equity. historical data. Obeying the distribution of historical sta- Te constraints (1)–(15) are formulated with respect to tistics, the impact of locomotive-caused delay at origin is as network characteristics, operational restriction, limited ca- expressed in constraint (3). Similarly, the duration for the pacities, and resource availability. Te objective functions dwell time delay caused by the yard activity (pick-up/drop- equations (18)–(20) can be categorized into efciency- of) is stated in constraint (4): oriented and equity-oriented ones. Journal of Advanced Transportation 9 Table 2: List of notations used in the mathematical model. Notations Defnition Sets S Set of stations, S � {0, 1, . . . , |N|}, where |N| is the number of stations crew crew S Set of fagged stations for the crew change, S ∈ S l l ps ps S Set of fagged stations for picking up or dropping of railcars, S ∈ S l l S(s, p) Set of the adjacent stations between the station s and station p I Set of trains, I � {0, 1, . . . , |I|}, where |I| is the number of trains − − I Set of trains with low static train priority, I ∈ I + − B Set of all tracks of at station s, B � B ∪ B S S S S B Set of tracks at the station s, including sidings and yard tracks B Set of virtual tracks at the station s, which is sufcient for the train dwell at its origin + − K Set of all tracks between the station s and station p,K � K ∪ K sp sp sp sp + + K Set of main lines between the station s and station p, K � {1, 2} sp sp − − K Set of sidings between the station s and station p, K � 3, . . . , |K | − 2 􏽮 􏽯 sp sp sp Index i, j Index of trains s, p Index of stations o(i) Index of the origin station of the train i d(i) Index of the destination station of the train i b Index of tracks at the station s k Index of tracks between the station s and station sp Parameters Given binary parameter, the station sequence for train i in operation. r � 1, if the isp isp train i passes the section from station s to station p. r � 0, otherwise isp Given binary parameter, static level of train i. psl � 1, if the static level of the train i psl is high level, psl � 0, otherwise t Departure time of the train i at the station s in the initial timetable is t Arrival time of the train i at station s in the initial timetable is t Te delay time threshold to upgrade dynamic train priority from low to high t Te running time from the station s to the station p sp A time penalty of a train when a train occupying a siding, wye, or industrial spur at the station ts Te minimum dwell time of the train i at the station s in the initial timetable Te deviation in dwell time of the train i at the fagged station s due to delay caused tsc by crew change Te deviation in departure time of the train i at the origin station because of tdl locomotive unavailability Te deviation in the dwell time of the train i at the fagged station s due to delay tdp caused by a pick-up or drop-of activity in yard h Te minimum following headway to ensure safety fd Probability for the delay time because of locomotive unavailability, a pick-up/ α,β, c drop-of activity, and crew change, respectively τ Te weighted index based on the dynamic train priority is M A sufciently large number Auxiliary variables A A d t Arrival time of the train i at the station s, t � 􏽐 􏽐 t is is p∈S k ∈ k ipsk sp sp sp D D d t Departure time of the train i at the station s, t � 􏽐 􏽐 t is is p∈S k ∈ k ipsk sp sp sp Te dynamic train priority of the train i at the station s. m � psl + pdl pdl � 1, if is i is is is the delay time of the train i at the station s is larger than t . pdl � 0, otherwise r is 10 Journal of Advanced Transportation Table 3: Decision variables. Notations Defnition Decision variables m Binary variable, m � 1, if the train i occupies the track k in the section (s, p) ispk ispk z Binary variable, z � 1, if the train i occupies the track b at the station s isb isb S S Te train order of the train i and j in the section (s, p). y � 1, if the train i ijsp ijsp departures ahead of the train j in the section (s, p). y � 0, otherwise ijsp Te end time of the train i occupying the track k between the station s and station p ispk (arriving at the station s) Te start time of the train i occupying the track k between the station s and station p ispk (departing from station s) stop Te actual dwell time of the train i at the station s (except origins) d a 􏽘 t − 􏽘 t � t + t ∙ 􏽘 m ispk ispk sp r ispk a sp sp sp ⎛ ⎜⎛ ⎜ ⎞ ⎟ ⎞ ⎟ ⎜⎜ ⎟ ⎟ ⎝⎝ ⎠ ⎠ − − − Pr 􏽘 􏽘 t − t ≥ tdl k ∈K k ∈K k ∈K io(i)pk io(i) i sp sp sp sp sp sp sp (9) (3) p∈S k ∈K sp sp ∀i ∈ I, ∀(s, p) ∈ S(s, p). ≥α∀i ∈ I, ∀(s, p) ∈ S(s, p), 4.1.4. Section Route Selection Constraints. If the section a d s s ⎛ ⎜⎛ ⎜ ⎞ ⎟ ⎞ ⎟ ⎜⎜ ⎟ ⎟ ⎝⎝ ⎠ ⎠ Pr 􏽘 􏽘 t − 􏽘 􏽘 t − stop ≥ tdp ispk ispk i i sp sp (s, p) is on the route of the trains, then the only track in the p∈S k ∈K p∈S k ∈K sp sp sp sp section is to be occupied by the train. Constraint (10) ≥β∀i ∈ I, ∀(s, p) ∈ S(s, p). guarantees the uniqueness of track occupancy along the route for the train. Meanwhile, it ensures train continuity (4) and consistency at every station on the route from the Constraints (5) and (6) are utilized to specify all the predetermined origins to destinations: trains that travel on a designated route. If and only if the m � r ∀i ∈ I, ∀(s, p) ∈ S(s, p). ispk isp station is on the route, the departure and arrival time at the sp (10) k ∈K sp sp station exist, as imposed in constraints (5) and (6), sepa- rately. Otherwise, the departure or arrival time is nonexistent: 4.1.5. Section Route Occupation Constraints. For each pair of t ≤ M∙ m ∀i ∈ I, ∀(s, p) ∈ S(s, p), (5) ispk ispk sp sp trains at one station, deciding on the train order is com- pulsory for rescheduling considering various factors, and the t ≤ M∙ m ∀i ∈ I, ∀(s, p) ∈ S(s, p). (6) departure-sequence-based timetable is useful to avoid spa- ispk ispk sp sp tiotemporal conficts in the section. To specify the moving direction, the departure and arrival time between two trains of the same direction and opposite directions are demon- 4.1.2. Dwell Time Constraints. Te actual dwell time in the strated in constraints (11) and (12). Considering the train i rescheduled timetable should satisfy the standard work time departs earlier than the train j in the section (s, p) and y ijsp at every visited station on the route, as stated in constraint equals 1, only the train i leaves the track, the train j can enter (7). For the dwell time of trains in fagged stations with the track in the section (s, p). It also illustrates why we use changing crew duty, the delay is greater than a value with the start time and end time of occupying a track as a decision a confdence level from historical data. Constraint (8) ex- variable: presses the impact of crew-duty delay which obeys the a d distribution of historical statistics, resembling constraints t − t ≥ M∙ 􏼐1 − y 􏼑∀i, j ∈ I and i ≠ j, ijsp jspk ispk sp sp (11) (3) and (4): ∀(s, p) ∈ S(s, p), ∀k ∈ K , sp sp s s stop ≤ ts ∀i ∈ I, ∀s ∈ S, (7) i i a d t − t ≥ M∙ 1 − y ∀i, j ∈ I and i ≠ j, 􏼐 􏼑 s s crew jspk ispk ijsp sp sp Pr stop ≥ tsc 􏼁 ≥ c∀i ∈ I, ∀s ∈ S . (8) (12) i i l ∀(s, p) ∈ S(s, p), ∀k ∈ K . sp sp 4.1.3. Siding Occupation Constraints. Constraint (9) repre- sents that a time penalty is charged for a train entering the 4.1.6. Station Track Assignment Constraints. At stations, the sidings at particular stations. Te section running time, i.e., tracks are to be assigned and occupied for train temporary the time diference between the train leaving and entering storage or workings. Constraint (13) states that the train i the track, equals to the standard section running time plus and the train j can occupy one and only track at the station s penalty time for siding events: (except origins, which are assumed to have sufcient tracks Journal of Advanced Transportation 11 for temporary storage for coupling locomotive). Constraints requirement between the train i and the train j in the same (14) and (15) are used to satisfy the minimum headway direction: 􏽘 z � 1 and 􏽘 z � 1∀i, j ∈ I, ∀s ∈ , isb jsb (13) S S o(i) + + b ∈B b ∈B S S S S a d 􏽘 􏽘 t − 􏽘 􏽘 t ≥ h − M∙ 􏼐3 − y − z − z 􏼑∀i, j ∈ I and i ≠ j, ∀s ∈ S, fd ijsp isb jsb ispk jspk sp sp S S (14) p∈S p∈S k ∈K k ∈K sp sp sp sp a d 􏽘 􏽘 t − 􏽘 􏽘 t ≥ h − M∙ 􏼐3 − y − z − z 􏼑∀i, j ∈ I and i ≠ j, ∀s ∈ S. jspk ispk fd jisp isb jsb S S sp sp (15) p∈S k ∈K p∈S k ∈K sp sp sp sp 4.1.7. Train Priority Adjusting Constraints. Te train order where λ ,λ ,λ are the weights of the objectives, respectively, 1 2 3 depends on the delay time and train priorities. Constraints and λ ,λ ,λ ≥ 0. 1 2 3 (16) and (17) satisfy that the train priority is dynamically λ , λ , and λ are introduced to the ftness function, for 1 2 3 upgraded when the delay time of the train i at the station s there are diferent orders of magnitude among Z , Z , and 1 2 reaches the threshold: Z . Te values of them are obtained by (1) considering Z , 3 1 Z , and Z as ftness functions, respectively, and taking it as D D − 2 3 (16) t − t − t < M∙ pdl ∀i ∈ I , ∀s ∈ S, r is is is a single objective optimization problem, (2) obtaining the min min optimal values of the single objective problem as Z , Z , 1 2 D D − min (17) t − t − t ≥ M∙ pdl − 1 􏼁 ∀i ∈ I , ∀s ∈ S. and Z , and (3) calculating λ , λ , and λ according to r is is is 1 2 3 equations (22),–(24): min min Z ∙ Z 2 3 λ � , (22) 4.2. Objective Functions min min min min min min Z ∙ Z + Z ∙ Z + Z ∙ Z 1 2 1 3 2 3 4.2.1. Efciency-Oriented Objectives. When a delay occurs, it min min will propagate and afect the railway system’s efciency. Te Z ∙ Z 1 3 λ � , (23) min min min min min min primary purpose for efciency is to recover from the delay Z ∙ Z + Z ∙ Z + Z ∙ Z 1 2 1 3 2 3 and minimize the total arrival deviation, as shown in the following expression: min min Z ∙ Z 1 2 λ � . (24) A A ps crew min min min min min min min Z � 􏽘􏼐t − t 􏼑 s ∈ 􏼐S ∪ S 􏼑. 1 is is l Z ∙ Z + Z ∙ Z + Z ∙ Z l (18) 1 2 1 3 2 3 i∈I 5. Solution Approach 4.2.2. Equity-Oriented Objectives. Considering the dynamic Te application of mathematical modeling to train train priority, equation (19) is weighted to minimize the total rescheduling is usually considered by its complex and time- deviation. Furthermore, the dispatching disorder, which is consuming process [2]. It is well known that the model is far the diference in the train sequence between the initial and more difcult to solve optimally in a reasonable time by optimized one in the railway network, is used to highlight commercial solvers (i.e., Cplex). Hence, we propose a two- train priority as equation (20) referring to Huo et al. [26] dimension genetic algorithm integrated with uncertainty work: optimization transformation and search space reduction. D A min Z � 􏽘 􏽘􏼐􏼐t − t 􏼑∙τ 􏼑, 2 is is is (19) Te framework and methodology, especially the two- i∈I s∈S dimension coding strategy based on the train order, are 􏼌 􏼌 introduced in this section. 􏼌 􏼌 􏼌 􏼌 􏼌 􏼌 i ≠ j, (s, p) ∈ S(s, p). min Z � 􏽘 􏽘 􏽘 􏽘 y − y 􏼌 􏼌 3 ijsp ijsp i∈I j∈I s∈S p∈S 5.1. Framework. Te overview of the timetable rescheduling (20) framework is shown in Figure 3. Under the background of Te model to deal with multiple objectives is also de- the stochastic delays, this paper simulates the delay caused scribed to tradeof equity and efciency and manifest model by crew change, a pick-up/drop-of activity, and locomotive performance. An objective function deriving the evaluation unavailability with distributions calculated from historical values is manifested as follows: data. Based on the initial timetable, we propose the ITGA approach using the dispatching strategies as retime, reorder, Eva � λ ∙ Z + λ ∙ Z + λ ∙ Z λ + λ + λ � 1􏼁, (21) 1 1 2 2 3 3 1 2 3 and retrack. 12 Journal of Advanced Transportation infrastructure manager Initial timetable design Historical freight f low Disturbance in operation: train delay Historical delay record Adjust Initial timetable: Delay Delay time Trains rescheduling optimization distribution Simulation Generation Operational (1) Re-time constraints (2) Re-order (3) Re-track Equipment Quick solution constraints Rescheduled timetable infrastructure manager/dispatcher no minimize all Objective? yes The best rescheduled timetable Figure 3: Overview of the timetable rescheduling approach framework. 5.2. Methodology. Te rescheduled timetable should be represented by a two-dimension matrix, whose array generated within the required time to ensure the handover of with as many positions as pairs existing in the railway dispatcher responsibility to the next shift and timely op- scheduling problem is considered. To explain this issue, eration. To address the problem with efciency, the ITGA we take a four-train-four-station case on a single-track approach is proposed as follows: railway in Figure 4 as an example. Te number of the row i and the column j in Table 4 represents the chromosome (1) It stochastically simulates the delay and transforms coding as the train order of the train j at the station i. the uncertain constraint based on the equivalence Moreover, the crossover and mutation process in the use theorem based on the distribution function. of improving efciency and preventing local optimal is (2) It compresses the lower and upper bound of the train shown in Figures 5 and 6. order on each train at stations based on the generated Crossover: parent individuals selected in preceding order delay time, which limits the search space. are crossed to generate the ofspring individuals. To improve readability, we choose the frst three stations in the case. (3) It obtains initial feasible two-dimension chromo- somes and pivots the process of selection, crossover, Figures 5(a) and 5(b) show the parents and ofspring after random crossover, which is infeasible for trains that have the and mutation. same train order at one station. Followed by the rule of (4) It terminates only when the diference in the best taking the initial train order as a rearranged reference, the solutions between two generations is less than the updated feasible ofspring is shown in Figure 5(c). given parameter or reaches the maximum number of Mutation: the mutation is randomly applied to the two- iterations. dimensional chromosome with a given probability. Figur- Indeed, the coding strategy plays a signifcant role in es 6(a) and 6(b) show the parents and ofspring after mu- GA efciency. Tis paper adopted train orders for the tation, which confict at Station 3. Te chromosome would coding scheme of chromosomes to overcome movement be updated with the same rules as explained in the crossover conficts easily. Each individual in the population is phrase, and Figure 6(c) shows the updated timetable. Journal of Advanced Transportation 13 010 20 30 40 Station 1 Station 2 Station 3 Station 4 Train 1 Train 3 Train 2 Train 4 Figure 4: Timetable for 4 trains in single-track railway with 4 stations. Table 4: An illustrated example of the coding strategy based on train order. Train 1 Train 2 Train 3 Train 4 Station 1 1 3 2 4 Station 2 1 2 3 4 Station 3 2 1 4 3 Station 4 1 2 4 3 Gen:departure order 4 trains 2 1 3 4 1 2 3 4 1 2 3 4 2 1 4 3 parents Crossover point 2 1 3 4 3 2 1 4 (a) 1 3 2 4 1 2 3 4 After crossover 1 2 3 4 2 1 4 3 2 2 3 4 3 1 1 4 conflict conflict (b) Chenck and updata according to original departure sequence 1 3 2 4 1 2 3 4 1 2 3 4 2 1 4 3 Offspring 2 1 3 4 3 1 2 4 (c) Figure 5: Crossover operation for a two-dimension chromosome: the rules and the results. Exhibiting the coding strategy and update rules, now we characteristic is satisfying a defnite confdence level at least. move to a brief introduction on the addressing of the un- To handle the three kinds of uncertainty constraints, we certainty optimization and search space in ITGA. transform the uncertainty constraint into deterministic inequalities through a deterministic transformation as follows: 5.2.1. Transformation of the Uncertainty Optimization Problem. Uncertainty optimization is a theory that achieves Pr x ≥ξ􏼁 ≥α , (25) i i i the best under a certain probability, whose remarkable 3 stations 14 Journal of Advanced Transportation 1 2 3 4 1 2 3 4 After mutation 2 1 4 3 2 1 4 3 3 2 1 4 3 1 1 4 Lower bound Upper bound mutation (a) (b) Chenck and updata according to original departure sequence Train 1 Train 2 Train 3 Train 4 1 2 3 4 Station 1 1 3 2 4 Station 2 1 2 3 4 2 1 4 3 Station 3 2 1 4 3 Station 4 1 2 4 3 3 1 2 4 (c) Figure 6: Mutation operation for a two-dimension chromosome: the rules and the results. where α is the level of confdence, x is the decision variable, 6.1. An Illustrative Case. A simple case of three trains with i i and ξ is the random variable. four stations is set to illustrate the model. Te initial Kroon et al. [17] proved that exponential distribution timetable is shown in Table 5 and also displayed visually in can be applied to nonnegative train arrival and departure Figure 7(a), while the running time is fxed in the section for delay distribution. Te delay obeys logarithmic normal each train. Train 1 of low priority has predetermined distribution, and the parameters can be simulated by the working at Station B, and Train 2 of high priority has historical data. For ξ ∼ log N(μ,σ ), we can conduct that predetermined workings at Station B and C. Running in reverse, Train 3 of low priority has predetermined working at Y � LN(ξ ) ∼ (μ,σ ). Let the distribution function of Y be F , and there is Pr(h(y) ≥ Y) � F (h(y)) � ϕ[h(y) −μ Station C. 1 1 /σ] ≥α. We assume that two perturbations cause delays, where For the formula Pr(x ≥ K ) � α , there is always Train 1 is delayed for 23 minutes at Station B for a crew i a i a number making it true (choose the smaller one when K change, and Train 3 was delayed for 5 minutes at Station D has more than one numerical value). Since Z � LN(ξ ) for locomotive unavailability. Te consideration of limited i i obeys normal distribution, K can be obtained by the fol- resources of tracks is also required in the rescheduling lowing formula: problem. As shown in Figure 7(b), Train 3 needs to dwell at the former station (Station D) when considering the number − 1 h(y) ≥ K � σ + ϕ 1 − α􏼁 + μ (26) a i i i, of sidings. Te reason is that there is only one siding at Station C for trains to dwell as shown in Figure 7(d). Hence, where σ is the standard deviation and μ is the mean value. i i Figure 7(b) displays a feasible timetable not considering train order adjustment. In this case, a 90-minute delay is caused as displayed in Table 6, with Train 1, Train 2, and 5.2.2. Upper Bound and Lower Bound. Besides, the search space is limited for each gene constricted to the train delay Train 3 contributing to 35 minutes, 25 minutes, and 35 minutes, respectively. Te delay time is 3.21 times longer time. By using the train order as the decision variable, this paper reduces the number of decision variables and con- than the primary delay. However, the result of the ITGA solution when making straints compared with the model based on departure/arrival time. However, increasing the dimension of decision vari- the train priority evolutionary is shown in Figure 7(c). For reaching the threshold, Trains 1 and 3 of low priority are ables will also increase computational complexity. In order to ensure computational efciency, we set the lower and upgraded. In that case, the total delay is 46 minutes including upper bound of the train order based on the delay time to 23 minutes, 18 minutes, and 5 minutes for Train 1, 2, and 3, respectively. Te delay of the optimized results is only 51.1% limit the search space. compared with the unadjusted one as shown in Table 7. 6. Case Study For this section, a simple three-train-four-station case is 6.2. A Real-World Case constructed to illustrate the method in Section 6.1. More- over, a real-world railway case in the Netherlands with 62 6.2.1. Description of Instances. To evaluate our model, we stations and 254.9 km in length is given to test the perfor- use the test instance provided in the 2020 RAS problem mance and efciency of ITGA in Section 6.2. solving competition. It is a line going east-west with 62 Journal of Advanced Transportation 15 Table 5: Te initial timetable of the illustrative case. Train 1 Train 2 Train 3 Arrival Departure Arrival Departure Arrival Departure Station A — 7:00 — 7:20 8:20 — Station B 7:15 7:25 7:35 7:40 8:05 8:05 Station C 7:35 7:35 7:55 8:00 7:50 7:55 Station D 7:50 — 8:15 — — 7:35 Station D Station D Station C Station C Station B Station B Station A Station A 7:00 7:30 8:00 8:30 9:00 7:00 7:30 8:00 8:30 9:00 Train 1 Train 1 Train 2 Train 2 Train 3 Train 3 (a) (b) Station D Station C Station B Station A 7:00 7:30 8:00 8:30 9:00 Train 1 Train 2 Train 3 (c) Station C Station A Station B Station D Station D Station track crossover (d) Figure 7: An illustrative case of three trains in a double-track railway. (a) Te initial timetable. (b) Te feasible timetable without train order adjustment. (c) Te optimized timetable with train order adjustment. (d) Te railway network topology of the example. Table 6: Te feasible timetable without train order adjustment. Train 1 Train 2 Train 3 Arrival Departure Arrival Departure Arrival Departure Station A — 7:00 — 7:20 8:55 — Station B 7:15 8:00 7:35 7:40 8:40 8:40 Station C 8:10 8:10 7:55 8:25 8:25 8:30 Station D 8:25 — 8:40 — — 8:10 16 Journal of Advanced Transportation Table 7: Te optimized timetable with train order adjustment. Train 1 Train 2 Train 3 Arrival Departure Arrival Departure Arrival Departure Station A — 7:00 — 7:20 8:25 — Station B 7:15 7:48 7:35 7:58 8:10 8:10 Station C 7:58 7:58 8:13 8:18 7:55 8:00 Station D 8:13 — 8:33 — — 7:40 stations and 254.9 km in length on the Netherlands railway. a regular periodic operational diagram based on headway as Te topology of the railway line and the stations are shown shown in Figure 11. Under the extensive and stochastic in Figure 8. Te data on 405 trains for 2 days are given, delay, the optimized rescheduling timetable with the min- including the route, train priority (high or low), departure imized integrated total delay, the dwell time and the and arrival time, and specifed working (crew change and numbers of train sequence adjustments are shown in Fig- yard activity for picking up and dropping of railcars) at ure 12. Taking the frst train in blue line as an example, a 5- a predetermined station for each train, and the required minute delay occurs at the origin Station Ehv due to lo- comotive unavailability and 54-minute at Station Wt for travel time and dwell time of the train can be calculated from the initial data. yard activity. Te delay exceeds the threshold at Station Rm, and the train priority upgrades to departure early. Moreover, In addition, the historical data on the delays caused by crew change, locomotive unavailability, and yard activity are the topology of the railway network is precisely character- given. Te delays are concluded as logarithmic normal ized by the model. Tis can be verifed by the diference distributions, and we adopt 90% as a confdence level to between the time between two adjacent trains depart and run ensure the result’s adaptability under adverse conditions and in a quadruple-track section or a double-track section. Te evaluate model performance. Te simulated distribution rescheduled timetable for T517 and T519 at Station Ehv functions are calculated and displayed in Figure 9, and (heading to Station Ehs) is taken as an example. From Table 8 illustrates the parameter values used in this Figure 8, we can see that it is a quadruple-track section experiment. between Station Ehv and Station Ehs. Te rescheduled timetable shows that the approach fully utilized the in- frastructure resource while meeting the constraints. It can 6.2.2. Result of the ITGA Approach and Comparison. In this also prove the validity of the model. section, we test our model in the Netherlands railway using python 3.7 and carry it out on a computer with a 2.1 GHz of Intel(R) Core (TM) i7-12700F CPU and 16 GB RAM in 6.2.3. Sensitivity Analysis a Windows environment. As shown in Table 9, the result of the ITGA approach considering both efciency and equity is (1) Analysis of the Multiple Objectives. As mentioned in obtained within 43 s, while it takes 5 seconds for the FIFO Section 4.2, we use weighted objectives to solve the multiple- strategy. Te approach meets the requirements for gener- objective problem. Note that our problem can be extended to ating a rescheduled timetable. Moreover, the parameters that an efciency-oriented model by setting λ � 1. Table 12 need to be determined in ITGA are listed in Table 10, in- shows the total delay time to be 47956 when only consid- cluding the crossover rate, the mutation rate, and the ering minimizing the total delay time. Te gap in the delay population size. time between the weighted objective and the minimum- Te progressively stabilized optimizing results are shown delay-time objective is 4.44%. In conclusion, although the in Figure 10, and the total objective value of the proposed total delay time of all trains is increased in the proposed approach decreases with iterations increasing. When the model, the schedule is more in compliance with the indi- number of iterations increases to 100, the algorithm remains vidual train orders. Te loss of the total delay time is utilized stable, and the solution is 1623.50. to trade of balance between equity and efciency. In this As depicted in Table 11, compared with the frst-in- case, the high-priority train may overtake a low-priority frst-out (FIFO) strategy (no train order adjustment), the train with the consideration of both the current train delay total objective value is decreased by 18.8%. In detail, the total and dynamic train priority. delay is signifcantly reduced by 40.9% with the ITGA ap- proach, which proves the importance of the train order (2) Relationship Analysis on Dynamic Train Priority Ad- adjustment in delay recovery. Besides, the weighted dwell justment Treshold. Making the train priority evolutionary, time is reduced by 2.5%. Te optimization ratio also verifes the threshold of train priority upgrade is a critical factor in the indirect delay caused by delay propagation which is rescheduling. Hence, we applied a detailed sensitivity enormous and noticeable in rescheduling problems. analysis on the threshold to evaluate the impact and balance To explain the optimization solution in practice, some the train priority and the delay time to choose the optimized trains on the west-east line are selected and visualized with one. Figure 13 depicts the objective value decreases as the a rescheduling working diagram. Note that the selection is dynamic level adjustment threshold increases. Although for the readability of the timetable. Te initial timetable is there are several pick-ups of the total objective or Journal of Advanced Transportation 17 … … … … … … Vs Vss Mdb Tbu Tbge Tb Tba Btl Bet EHS EHV GP HMBV Vl Rm North Route 50 …… 57 …… 61 …… …… 39 49 02 …… 1 …… 23 26 …… 31 South Route Figure 8: Te illustrations of the railway network topology in the Netherlands. CREW_AVAIL LOCO_AVAIL YARD_AVAIL 0.6 1.0 0.5 0.5 0.8 0.4 0.4 0.6 0.3 0.3 0.4 0.2 0.2 0.2 0.1 0.1 0.0 0.0 0.0 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 (a) (b) (c) Figure 9: Te distribution functions of resource availability. (a) Te dwell time at the fagged station for the crew change. (b) Te delay from the planned departure time at the origin. (c) Te yard delay at fagged pickup and setof points. Table 8: Te distribution function of resources availability. Lower bound of Distribution function Random variables delay K (α � β � c � 90%) (unit: h) (unit: min) CREW_AVAIL X ∼ log N(0.1, 1) 18.40 LOCO_AVAIL X ∼ log N(0.25, 0.1) 51.37 YARD_AVAIL X ∼ log N(0.5, 0.25) 52.12 CREW_AVAIL: the dwell time of a train at fagged stations for the crew change; LOCO_AVAIL: the delay from the planned departure time at the point of origin because of locomotive unavailability; YARD_AVAIL: the yard delay at the fagged pick-up/drop-of station s in the train route. Table 9: Testing results of the example. Time window Te number of trains Computing time (m:s) ITGA [0, 240] 64 00:43 FIFO [0, 240] 64 00:05 the arrival delay of all trains at the destination. All the Table 10: Te determined value of parameters in ITGA. statistics indexes are shown in Table 13. When the threshold Parameters Value reaches 50 minutes, the destination delay is minimal. Population size 100 However, considering the comprehensive performance, Number of iterations 100 60 minutes is taken as the threshold of the dynamic level Crossover rate 0.7 adjustment in this paper, and the average delay of each train Mutation rate 0.3 under the optimal result is 210.9 minutes (approximately 3.5 hours) for this case in the 60 threshold. subobjective at a threshold of 40, they generally follow the Concerning the abovementioned experimental tests, we downward trend. draw conclusions as follows: (1) Te balance of the dynamic To choose the best-performed thresholds and tradeofs train priority and delay time is necessary for operation. between the individual train and railway system, we calculate Compared with the FIFO strategy, the total delay is y 18 Journal of Advanced Transportation 0 20 40 60 80 100 Number of iteration Figure 10: Optimization result of the total objective of the real-world case. Table 11: Te comparison of the ITGA and FIFO strategy. Total Weighted Te number of Objective value delay time (minutes) dwell time (minutes) train order adjustment ITGA 50086 28652 642 1623.5 FIFO 70580 29365 0 1928.3 Gaps 40.9% 2.5% — 18.8% Mt Bha Bde Bk Lut Luta Std Sm Ec Mbt Rm Hln Wt Mz Ohze Hze Gp Tgra Ehv Ehs Ehb At Bet Btl 5:00 6:00 7:00 8:00 9:00 10:00 11:00 Train number 512 517 513 518 514 519 515 2288 516 2286 Figure 11: Initial timetable for the real-world case. Total objective Journal of Advanced Transportation 19 Mt Bha Bde Bk Lut Luta Std Sm Ec Mbt Rm Hln Wt Mz Ohze Hze Gp Tgra Ehv Ehs Ehb At Bet Btl 5:00 6:00 7:00 8:00 9:00 10:00 11:00 12:00 13:00 14:00 15:00 Train number 512 517 513 518 514 519 515 2288 516 2286 Figure 12: Rescheduling timetable for the real-word case. Table 12: Te total delay time based on the diferent objectives. Gaps Weighted objectives Minimize delay time (%) Delay time 50086 47956 4.44 10 20 30 40 50 60 dynamic priority threshold (a) 51500 31000 10 20 30 40 50 60 dynamic priority threshold Objective 1 Objective 2 (b) Figure 13: Continued. Objective 1 Total objective Objective 2 20 Journal of Advanced Transportation 10 20 30 40 50 60 dynamic priority threshold (c) Figure 13: Sensitivity analysis on the threshold of dynamic level adjustment. (a) Total objective value under diferent threshold. (b) Objective 1 and objective 2 value under diferent thresholds. (c) Objective 3 value diferent thresholds. Table 13: Statistics of the delay at the destination (unit: minute). Treshold Statistics 10 20 30 40 50 60 Summary 15205 14053 13933 14919 13711 14575 Average 233.9 216.2 214.4 229.5 210.9 224.2 Max 379 350 380 384 336 378 Min 121 90 90 90 90 90 Standard deviation 47.9 51.9 56.5 58.5 57.6 56.9 signifcantly reduced by 40.9% and the weighted dwell time the train priority and delay time. Te result shows that is reduced by 2.5%, while the objective value is decreased by there is a synergy between the delay time and train priority, 18.8%. (2) Compared with the efciency-oriented objective where the threshold to upgrade the evolutionary train only considering total delay, the combined objective fuc- priority plays an important role. Hence, our work proves tuates as the threshold increases. Tis proves that there are that it is very meaningful and applicable to consider the synergies between efciency and equity, which is signifcant evolutionary train priority. Moreover, the algorithm takes in tradeof equity and efciency. (3) From the individual 43 s for the 4-hour computational result in a real-world perspective of a low-priority train, a lower threshold de- railway network with 62 stations and 254.9 km in length, which meets the requirements for rescheduling in the real creases the delay time at the destination. From the system perspective, the train delay time increases as the threshold world. Our work extends the rescheduling approach increases to some extent. Te threshold is important to considering both equity and efciency and provides aux- tradeof equity and efciency, and a threshold of 60 minutes iliary operation support for the dispatcher’s operation is suggested for timetable rescheduling. rescheduling. A future line of research to be considered in the next studies is to quantify the model in real-time rescheduling 7. Conclusion and Future Work with delay time estimation. First, the efciency of the al- To resolve the train timetable rescheduling problem with gorithm can also be improved further. For example, as is heterogeneous train priority considering both efciency and a population-based optimization strategy, the initial pop- equity in freight railway, this paper proposes an optimization ulation of GA can greatly improve the quality of the so- model for freight railway rescheduling and solves it with lution. Heuristics in generating the initial population with a novel GA solution (i.e., ITGA). We propose the dynamic chromosomes can be proposed instead of random gener- train priority based on the delay time and static train priority. ated within the up and low bound in this paper. Second, Based on the abovementioned content, the proposed model a simulation approach could be used to evaluate the po- utilizes integrated recovery strategies of retime, reorder, and tential delay in the dynamic rescheduling process. More- retrack in terms of adjusting dwell time, changing the meet- over, another possibility is to combine rescheduling pass plan, and fexible track use control in a complex railway strategies (e.g., route changes and speed profle) in big network containing single-track, double-track, and perturbations such as disruptions caused by a trafc ac- quadruple-track sections. Te model investigates railways cident or bad weather. restricted to network characteristics, operational restraints, limited capacities, and resource availability. To solve the Data Availability rescheduling problem efciently, a heuristic algorithm is proposed by integrated GA, using train order for a chromo- Te data that support the fndings of this study are openly some coding scheme to avoid spatiotemporal confict. available in the 2020 RAS Problem Solving Competition at Based on the implementation in the Netherlands’ real- https://connect.informs.org/railway-applications/new- world case, this study investigates the relationship between item3/problem-solving-competition681/new-item3867. Objective 3 Journal of Advanced Transportation 21 rescheduling,” Transportation Research Part B: Methodolog- Disclosure ical, vol. 63, pp. 15–37, 2014. [12] A. Ceder and S. Hassold, “Applied analysis for improving rail- Te authors presented their results for the competition and network operations,” Journal of Rail Transport Planning and won the frst prize. Management, vol. 5, no. 2, pp. 50–63, 2015. [13] E. Reynolds and S. J. Maher, “A data-driven, variable-speed Conflicts of Interest model for the train timetable rescheduling problem,” Com- puters and Operations Research, vol. 142, Article ID 105719, Te authors declare that there are no conficts of interest regarding the publication of this paper. [14] J. Chung, S. Oh, and I. Choi, “A hybrid genetic algorithm for train sequencing in the Korean railway,” Omega, vol. 37, no. 3, Acknowledgments pp. 555–565, 2009. [15] L. Meng and X. Zhou, “Simultaneous train rerouting and Te authors want to thank the INFORMS for holding the rescheduling on an N-track network: a model reformulation 2020 RAS Problem Solving Competition. Besides, the au- with network-based cumulative fow variables,” Trans- thors appreciate the chair: Jay Baillargeon (U.S. DOT) and portation Research Part B: Methodological, vol. 67, pp. 208– the problem owner: Krishna Jha (Optym) for their answers 234, 2014. to our questions. Tis work was supported by the China [16] J.-F. Cordeau, P. Toth, and D. Vigo, “A survey of optimization Academy of Engineering (Grant no. 2022-PP-06). Besides, models for train routing and scheduling,” Transportation the frst author was supported by the China Scholarship Science, vol. 32, no. 4, pp. 380–404, 1998. Council. [17] L. Kroon, G. Maroti, ´ M. R. Helmrich, M. Vromans, and R. Dekker, “Stochastic improvement of cyclic railway time- tables,” Transportation Research Part B: Methodological, References vol. 42, no. 6, pp. 553–570, 2008. [1] T. Robenek, S. S. Azadeh, Y. Maknoon, M. de Lapparent, and [18] M. Sama, ` C. Meloni, A. D’Ariano, and F. Corman, “A multi- M. Bierlaire, “Train timetable design under elastic passenger criteria decision support methodology for real-time train demand,” Transportation Research Part B: Methodological, scheduling,” Journal of Rail Transport Planning and Man- vol. 111, pp. 19–38, 2018. agement, vol. 5, no. 3, pp. 146–162, 2015. [2] M. Shakibayifar, A. Sheikholeslami, F. Corman, and [19] N. Kumar and A. Mishra, “A multi-objective and dictionary- E. Hassannayebi, “An integrated rescheduling model for based checking for efcient rescheduling trains,” Alexandria minimizing train delays in the case of line blockage,” Oper- Engineering Journal, vol. 60, no. 3, pp. 3233–3241, 2021. ational Research, vol. 20, no. 1, pp. 59–87, 2017. [20] M. Zhou, H. Dong, X. Liu, H. Zhang, and F. Y. Wang, [3] N. Kumar and A. Mishra, “An efcient method of disturbance “Integrated timetable rescheduling for multidispatching analysis and train rescheduling using MWDLNN and sections of high-speed railways during large-scale disrup- BMW-SSO algorithms,” Soft Computing, vol. 25, no. 18, tions,” IEEE Transactions on Computational Social Systems, pp. 12031–12041, 2021. vol. 9, no. 2, pp. 366–375, 2022. [4] F. Corman, A. D’Ariano, I. A. Hansen, and D. Pacciarelli, [21] G. Cavone, M. Dotoli, N. Epicoco, and C. Seatzu, “A decision “Optimal multi-class rescheduling of railway trafc,” Journal making procedure for robust train rescheduling based on of Rail Transport Planning and Management, vol. 1, no. 1, mixed integer linear programming and Data Envelopment pp. 14–24, 2011. Analysis,” Applied Mathematical Modelling, vol. 52, [5] P. Xu, D. Zhang, J. Guo, D. Liu, and H. Peng, “Integrated train pp. 255–273, 2017. rescheduling and rerouting during multidisturbances under [22] L. Meng and X. Zhou, “Robust single-track train dispatching a quasi-moving block system,” Journal of Advanced Trans- model under a dynamic and stochastic environment: a sce- portation, vol. 2021, Article ID 6652531, 15 pages, 2021. nario-based rolling horizon solution approach,” Trans- [6] S. Dundar ¨ and I. S¸ahin, “Train re-scheduling with genetic portation Research Part B: Methodological, vol. 45, no. 7, algorithms and artifcial neural networks for single-track pp. 1080–1102, 2011. railways,” Transportation Research Part C: Emerging Tech- [23] R. Larsen, M. Pranzo, A. D’Ariano, F. Corman, and nologies, vol. 27, pp. 1–15, 2013. D. Pacciarelli, “Susceptibility of optimal train schedules to [7] A. Higgins, E. Kozan, and L. Ferreira, “Optimal scheduling of stochastic disturbances of process times,” Flexible Services and trains on a single line track,” Transportation Research Part B: Manufacturing Journal, vol. 26, no. 4, pp. 466–489, 2013. Methodological, vol. 30, no. 2, pp. 147–161, 1996. [24] S. B. Layeb, A. Jaoua, A. Jbira, and Y. Makhlouf, “A [8] D. Banerjee and K. Smilowitz, “Incorporating equity into the simulation-optimization approach for scheduling in sto- school bus scheduling problem,” Transportation Research Part chastic freight transportation,” Computers and Industrial E: Logistics and Transportation Review, vol. 131, pp. 228–246, Engineering, vol. 126, pp. 99–110, 2018. [25] S. Q. Liu and E. Kozan, “Scheduling trains with priorities: [9] I. Sahin, “Railway trafc control and train scheduling based on a No-wait blocking parallel-machine job-shop scheduling inter-train confict management,” Transportation Research model,” Transportation Science, vol. 45, no. 2, pp. 175–198, Part B: Methodological, vol. 33, no. 7, pp. 511–534, 1999. [10] B. Taslimi, F. Babaie Sarijaloo, H. Liu, and P. M. Pardalos, “A [26] J. Huo, J. Wu, L. Kang, and B. Wang, “Railway timetable novel mixed integer programming model for freight train rescheduling based on priority and train order entropy,” travel time estimation,” European Journal of Operational Research, vol. 300, no. 2, pp. 676–688, 2022. Technical Papers, vol. 30, 2016. [27] P. Shang, R. Li, Z. Liu, L. Yang, and Y. Wang, “Equity-oriented [11] V. Cacchiani, D. Huisman, M. Kidd et al., “An overview of recovery models and algorithms for real-time railway skip-stopping schedule optimization in an oversaturated 22 Journal of Advanced Transportation urban rail transit network,” Transportation Research Part C: Emerging Technologies, vol. 89, pp. 321–343, 2018. [28] L. Wang, C. Luo, and J. Cai, “A variable interval rescheduling strategy for dynamic fexible job shop scheduling problem by improved genetic algorithm,” Journal of Advanced Trans- portation, vol. 2017, Article ID 1527858, 12 pages, 2017. [29] H. Zhang, S. Ni, and Y. Gao, “Train scheduling optimization for an urban rail transit line: a simulated-annealing algorithm using a large neighborhood search metaheuristic,” Journal of Advanced Transportation, vol. 2022, Article ID 9604362, 17 pages, 2022. [30] S. Fidanova, O. Roeva, and M. Ganzha, “Ant colony opti- mization algorithm for fuzzy transport modelling,” in Pro- ceedings of the 2020 Federated Conference on Computer Science and Information Systems, pp. 237–240, Sofa, Bulgaria, September 2020. [31] X. Meng, L. Jia, and Y. Qin, “Train timetable optimizing and rescheduling based on improved particle swarm algorithm,” Transportation Research Record: Journal of the Transportation Research Board, vol. 2197, no. 1, pp. 71–79, 2010. [32] F. Corman, A. D’Ariano, D. Pacciarelli, and M. Pranzo, “A tabu search algorithm for rerouting trains during rail oper- ations,” Transportation Research Part B: Methodological, vol. 44, no. 1, pp. 175–192, 2010. [33] J. To¨rnquist Krasemann, “Design of an efective algorithm for fast response to the re-scheduling of railway trafc during disturbances,” Transportation Research Part C: Emerging Technologies, vol. 20, no. 1, pp. 62–78, 2012. [34] L. Kang, J. Wu, H. Sun, X. Zhu, and B. Wang, “A practical model for last train rescheduling with train delay in urban railway transit networks,” Omega, vol. 50, pp. 29–42, 2015. [35] E. Altazin, S. Dauzere-P ` er ´ es, ` F. Ramond, and S. Trefond, ´ “A multi-objective optimization-simulation approach for real time rescheduling in dense railway systems,” European Journal of Operational Research, vol. 286, no. 2, pp. 662–672, http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Advanced Transportation Hindawi Publishing Corporation http://www.deepdyve.com/lp/hindawi-publishing-corporation/a-rescheduling-approach-for-freight-railway-considering-equity-and-VezwsdaASC

Loading next page...

References (35)

Shi Liu, E. Kozan (2011)
Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model
Transp. Sci., 45
Leo Kroon, G. Maróti, M. Helmrich, Michiel Vromans, R. Dekker (2006)
Stochastic Improvement of Cyclic Railway Timetables
European Economics: Microeconomics & Industrial Organization eJournal
Tomás Robenek, S. Azadeh, Yousef Maknoon, M. Lapparent, M. Bierlaire (2018)
Train timetable design under elastic passenger demand
Transportation Research Part B-methodological, 111
G. Cavone, M. Dotoli, Nicola Epicoco, C. Seatzu (2017)
A decision making procedure for robust train rescheduling based on mixed integer linear programming and Data Envelopment Analysis
Applied Mathematical Modelling, 52
J. Cordeau, P. Toth, D. Vigo (1998)
A Survey of Optimization Models for Train Routing and Scheduling
Transp. Sci., 32
Selim Dündar, I. Sahin (2013)
Train re-scheduling with genetic algorithms and artificial neural networks for single-track railways
Transportation Research Part C-emerging Technologies, 27
Johanna Krasemann (2012)
Design of an Effective Algorithm for Fast Response to the Rescheduling of Railway Traffic During Disturbances
Neeraj Kumar, A. Mishra (2021)
A multi-objective and dictionary-based checking for efficient rescheduling trains
alexandria engineering journal, 60
Dipayan Banerjee, K. Smilowitz (2018)
Incorporating equity into the school bus scheduling problem
Transportation Research Part E: Logistics and Transportation Review
A. Higgins, E. Kozan, L. Ferreira (1996)
Optimal scheduling of trains on a single line track
Xuelei Meng, L. Jia, Yong Qin (2010)
Train Timetable Optimizing and Rescheduling Based on Improved Particle Swarm Algorithm
Transportation Research Record, 2197
Valentina Cacchiani, D. Huisman, M. Kidd, L. Kroon, P. Toth, Lucas Veelenturf, J. Wagenaar (2014)
An overview of recovery models and algorithms for real-time railway rescheduling
Transportation Research Part B-methodological, 63
F. Corman, A. D’Ariano, D. Pacciarelli, M. Pranzo (2007)
A tabu search algorithm for rerouting trains during rail operations
Liujiang Kang, Jianjun Wu, Huijun Sun, Xiaoning Zhu, Bo Wang (2015)
A practical model for last train rescheduling with train delay in urban railway transit networks
Omega-international Journal of Management Science, 50
M. Samà, C. Meloni, A. D’Ariano, F. Corman (2015)
A multi-criteria decision support methodology for real-time train scheduling
J. Rail Transp. Plan. Manag., 5
Peijuan Xu, Dawei Zhang, Jingwei Guo, Dan Liu, Hui Peng (2021)
Integrated Train Rescheduling and Rerouting during Multidisturbances under a Quasi-Moving Block System
Journal of Advanced Transportation, 2021
S. Fidanova, O. Roeva, M. Ganzha (2020)
Ant Colony Optimization Algorithm for Fuzzy Transport Modelling
2020 15th Conference on Computer Science and Information Systems (FedCSIS)
L. Meng, Xuesong Zhou (2011)
Robust single-track train dispatching model under a dynamic and stochastic environment: a scenario-based rolling horizon solution approach
Hai Zhang, S. Ni (2022)
Train Scheduling Optimization for an Urban Rail Transit Line: A Simulated-Annealing Algorithm Using a Large Neighborhood Search Metaheuristic
Journal of Advanced Transportation
I. Sahin (1999)
Railway traffic control and train scheduling based oninter-train conflict management
Transportation Research Part B-methodological, 33
Neeraj Kumar, A. Mishra (2021)
An efficient method of disturbance analysis and train rescheduling using MWDLNN and BMW-SSO algorithms
Soft Computing, 25
Lei Wang, C. Luo, Jingcao Cai (2017)
A Variable Interval Rescheduling Strategy for Dynamic Flexible Job Shop Scheduling Problem by Improved Genetic Algorithm
Journal of Advanced Transportation, 2017
Rune Larsen, M. Pranzo, A. D’Ariano, F. Corman, D. Pacciarelli (2014)
Susceptibility of optimal train schedules to stochastic disturbances of process times
Flexible Services and Manufacturing Journal, 26
Ji-Won Chung, Seog-Moon Oh, I. Choi (2009)
A hybrid genetic algorithm for train sequencing in the Korean railway
Omega-international Journal of Management Science, 37
A. Ceder, Stephan Hassold (2015)
Applied analysis for improving rail-network operations
J. Rail Transp. Plan. Manag., 5
E. Reynolds, Stephen Maher (2022)
A data-driven, variable-speed model for the train timetable rescheduling problem
Comput. Oper. Res., 142
F. Corman, A. D’Ariano, I. Hansen, D. Pacciarelli (2011)
Optimal multi-class rescheduling of railway traffic
J. Rail Transp. Plan. Manag., 1
Min Zhou, Hai-rong Dong, Xuan Liu, Hongjie Zhang, Fei-Yue Wang (2022)
Integrated Timetable Rescheduling for Multidispatching Sections of High-Speed Railways During Large-Scale Disruptions
IEEE Transactions on Computational Social Systems, 9
Jia-Ling Huo, Jianjun Wu, Liujiang Kang, Bo Wang (2016)
Railway Timetable Rescheduling Based on Priority and Train Order Entropy
J. Comput. Civ. Eng., 30
L. Meng, Xuesong Zhou (2014)
Simultaneous train rerouting and rescheduling on an N-track network: A model reformulation with network-based cumulative flow variables
Transportation Research Part B-methodological, 67
Pan Shang, Ruimin Li, Zhiyong Liu, Liya Yang, Yuqiang Wang (2018)
Equity-oriented skip-stopping schedule optimization in an oversaturated urban rail transit network
Transportation Research Part C-emerging Technologies, 89
M. Shakibayifar, A. Sheikholeslami, F. Corman, E. Hassannayebi (2020)
An integrated rescheduling model for minimizing train delays in the case of line blockage
Operational Research, 20
Estelle Altazin, S. Dauzére-Pérés, François Ramond, Sabine Tréfond (2020)
A multi-objective optimization-simulation approach for real time rescheduling in dense railway systems
Eur. J. Oper. Res., 286
Safa Layeb, A. Jaoua, Asma Jbira, Yosra Makhlouf (2018)
A simulation-optimization approach for scheduling in stochastic freight transportation
Comput. Ind. Eng., 126
Bijan Taslimi, FarnazBabaie Sarijaloo, Hongcheng Liu, P. Pardalos (2021)
A novel mixed integer programming model for freight train travel time estimation
Eur. J. Oper. Res., 300

Publisher: Hindawi Publishing Corporation
ISSN: 0197-6729
eISSN: 2042-3195
DOI: 10.1155/2023/8989644
Publisher site: See Article on Publisher Site

Abstract

Hindawi Journal of Advanced Transportation Volume 2023, Article ID 8989644, 22 pages https://doi.org/10.1155/2023/8989644 Research Article A Rescheduling Approach for Freight Railway considering Equity and Efficiency by an Integrated Genetic Algorithm 1 2 3 4 1 Zhuotong Bai , Hui Wang , Lin Yang , Jiajie Li , and Huapu Lu Institute of Civil Engineering, Tsinghua University, Beijing 100084, China Department of Geography, Te University of Hong Kong, Pokfulam, Hong Kong SAR, China School of Management and Economics, Beijing Institute of Technology, Beijing 100081, China Key Laboratory of Advanced Public Transportation Science, China Academy of Transportation Sciences, Beijing 100029, China Correspondence should be addressed to Huapu Lu; luhp@mail.tsinghua.edu.cn Received 21 January 2023; Revised 6 April 2023; Accepted 10 May 2023; Published 25 May 2023 Academic Editor: Ren-Yong Guo Copyright © 2023 Zhuotong Bai et al. Tis is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Since unexpected event occurrences are inevitable, an efcient and efective rescheduling approach is critical in freight railway day-to-day operations. Represented by the minimal-delay objectives, the most commonly used efciency-oriented approach ignores the role of train priority and poses equity problems in rescheduling. For equity, diferent train priority also refects the preference in deciding train orders; i.e., the high-priority train is likely to be favorable. However, a confict may be laid between reducing delays and emphasizing train priority. Hence, it is critical to decide the criteria in train order for freight railway, especially with heterogeneous priority in a competitive resource. To make a tradeof between equity and efciency, this paper makes train priority evolutionary and proposed the dynamic train priority considering delay time and static priority. We formulate an optimization model based on the rescheduling strategies such as retime, reorder, and retrack in a complex railway network containing single-track, double-track, and quadruple-track sections. An integrated two-dimension genetic algorithm (ITGA) approach is developed to reobtain an optimized timetable of sufcient quality while meeting the time requirements for real-time rescheduling. In the experiment, the efectiveness of the ITGA approach was employed in a simple case and a real-world case in the Netherlands freight railway. Te result shows that there is a synergy between delay time and train priority, where the threshold to upgrade the evolutionary train priority plays an important role. Te proposed approach is compared with the benchmark solution frst-in-frst-out (FIFO) approach in a real-world case to verify the performance and efciency. Our work extends the rescheduling approach considering both equity and efciency and provides auxiliary operation support for the dispatcher’s operation rescheduling. reliability and carrier satisfaction in the freight railway 1. Introduction system. Freight railway holds an increasing market share in trans- Nevertheless, due to accidents such as rolling stock portation systems for high-efciency, large-volume, and eco- breakdown, driver behaviors, traveler behaviors, and even friendliness. In 2021, the Chinese freight railway volume the timetables’ quality together with extreme weather [3], the increased by 5.9% and completed a total of 4.774 billion tons. railway system sufers perturbations during real-time trafc Te timetable, which is defned as a set of arrival and de- management [4]. Tese unexpected events cause railway parture times of each train from each of its stopping stations infrastructure resources to be unavailable, resulting in trains [1], plays a vital role in guaranteeing freight railway ef- interfering with one another. To be specifc, it may cause ciency in day-to-day operations. Te design of a train train confict, which is two or more trains requesting to use timetable is a complex process subject to the capacity, safety, the same section simultaneously in operation. Detecting and resource constraints [2]. Performing in accordance with train conficts and resolving them to produce feasible and the pre-established initial timetable is essential for service desirable schedules are one of the most challenging and 2 Journal of Advanced Transportation railway network are considered. We assume trains are difcult problems in freight railway. Except for very few applications, these tasks are usually performed by train held up for 14 minutes at Station A, where the initial timetable is represented by dotted lines, while the optimized dispatchers. Tis process is so-called train timetable rescheduling. Due to the complexity of rescheduling, dis- results are represented by solid lines. To simplify the ex- patchers utilize some simplifying rules to resolve conficts ample, the section running time for each train is 5 minutes, and implement their decisions accordingly. When while the dwell time is 2 minutes. Te minimum headway rescheduling, the primary responsibility of the train dis- between two adjacent trains arriving or leaving the station is patcher is to adjust the timetable into a confict-free one for 5 minutes. safety as quickly as possible by rescheduling strategies. Te (1) Case 1 in Figure 1(a): In the scenario of frst-in- main rescheduling measures mainly contain retiming frst-out (FIFO) strategy adherence to initial train (changing train arrival and departure times), rerouting order, all trains are designated to dwell at station A (selecting a new route from feasible routes), reordering for a minimum of 14 minutes, and a total of (changing train arrival or train orders), and canceling trains 42 minutes of delay are created in the system. [5]. Accordingly, reordering makes some trains stop on (2) Case 2 in Figure 1(b): In the efciency-oriented designated siding tracks to be overtaken and allow others to scenario for minimizing the delay, medium- pass without interruption, resulting in train delays. priority trains depart earlier than high-priority A general criterion for rescheduling is the train delay ones. Without considering the train priority, the time, which is the deviation between the actual and planned system has a 34-minute delay, while the delay for arrival time. Delay time assesses the trains’ overall lateness of a high-priority train is 5 minutes, and the delay times freight railway quantitatively, which is an indicator to for other trains are 5 and 24 minutes. Moreover, the measure rescheduling timetables from the perspective of objective of minimizing the total delay cannot refect system efectiveness and efciency [6]. Consequently, the diference between whether the low-priority or minimizing delays is importantly considered in studies when the high-priority train departs earlier in this case. making decisions about train orders for the railway system. However, most railroads operate a heterogeneous set of (3) Case 3 in Figure 1(c): In the equity-oriented scenario trains with diferent priorities, which are mostly given based for emphasizing the train priority, high-priority on commodities being carried. For example, an intermodal trains have absolute priority than the lower ones train (usually a high-priority train) must have a minimum when meeting conficts. In this condition, the high- delay compared to the tolerable delays for unit trains, in priority train departs from Station A earlier than the order to satisfy the expected delivery time agreed upon with others. As a result, the caused total delay is the shipper. Hence, in practice, the criteria for train order in 42 minutes, with the high-priority train contributing rescheduling include the priority of each train, current train 0 and the other two contributing 14 and 28 minutes, delays, and expected remaining overtake and crossing delays respectively. [7]. Briefy, the criteria for deciding train orders are not To conclude, the criteria for delay time and train priority straightforward and are the result of multifactorial opti- bring about the contradiction between efciency and equity. mization. Te only objective being the minimization of train For efciency, various aforementioned studies have used the delays for efciency ignores the train priority which may lead minimal delay as the most important indicator in to high-priority delays for low-priority trains in the rescheduling to make full use of resources and achieve rescheduling area. In addition, equity refers to the distri- system optimization. For equity, the priority of trains, which bution of impacts (benefts and costs) and whether that is an important auxiliary criterion in practice, cannot be distribution is considered fair and appropriate [8]. Ignoring neglected. the train priority which is assigned by railway authorities To incorporate the interaction between efciency and which divide the trains on the basis of the type of service may equity, we attempt to explore the relationship between delay lead to an equity issue. For equity in railways, the higher the time, train priority, and the optimal matching method of basic (or static) priority, the more favorable it is to the train them. It is especially critical because there are heterogeneous [9]. In detail, when there is a heterogeneous set of trains with priority trains running in a competitive resource in freight low or high priority, high-priority trains are expected to have railways. Inspired by Corman et al. [4], we make the train a smaller deviation [10]. priority evolutionary by establishing dynamic priority based An illustrative example is shown in Figure 1 to indicate on the delay time and static train priority. Te train priority the role of criteria in deciding train orders when resched- increases when the accumulated delay exceeds the allowed uling. Te frst-in-frst-out (FIFO) strategy, efciency- delay threshold. As displayed in Figure 1(d), the low-priority oriented strategy for minimizing the delay, equity- train is upgraded when delay time reaches a certain oriented strategy for emphasizing the train priority, and threshold, subsequently, making it as favorable as the the proposed strategy for trading of between efciency and medium-priority train in departure orders deciding. Tis equity are explored in Cases 1, 2, 3, and 4, respectively. Tree approach results in a 38-minute delay, with each lower trains with diferent priorities running in a fve-station Journal of Advanced Transportation 3 Station A Station B Station D Station E Station C 14 mins Station Station 24 mins 14 mins � Delay: 42 mins � Delay: 34 mins 5 mins 5 mins 14 mins 6:30 7:00 6:00 E E D D C C B B A Time A Time disturbance disturbance Low priority Low priority Medium priority Medium priority High priority High priority (a) (b) Station Station 19 mins 28 mins � Delay: 42 mins � Delay: 38 mins 14 mins 19 mins E E D D upgrade A Time disturbance Time A disturbance Low priority Low priority Medium priority Medium priority High priority High priority (c) (d) Optimized arrival time Initial departure Initial arrival time time Case 1 Case 2 Case 3 Case 4 Low-priority train 6:00 6:26 6:40 6:50 6:54 6:45 Medium-priority train 6:09 6:31 6:45 6:36 6:45 6:50 High-priority train 6:14 6:40 6:54 6:45 6:40 6:40 Figure 1: Cases to illustrate the criteria for deciding train orders in rescheduling. (a) Case 1: the timetable with no adjustment under disturbance. (b) Case 2: the optimized timetable with efciency orientation. (c) Case 3: the optimized timetable with equity orientation. (d) Case 4: the optimized timetable with dynamic train priority. priority trains contributing half of it. Compared with the low-priority trains is 14 and 28 minutes, respectively), the efciency-oriented strategy (34 minutes total delay and the proposed strategy achieves a relatively small delay while delay time for high-, medium-, and low-priority trains is 5, 5, ensuring that high-priority trains are favorable. and 24 minutes, respectively) and equity-oriented strategy In summary, we investigate an optimization model with (42 minutes total delay and the delay time for medium- and dynamic train priority to tradeof equity and efciency. Our 4 Journal of Advanced Transportation work makes the train priority evolutionary and to be Sama et al. [18] compared and analyzed the quality of upgraded when the delay time reaches the thresholds. To multiple objective function solutions. Aiming at minimal train delay, dwell time, and timetable deviation, Kumar and make the criteria for deciding on train order straightforward, the relationship between the train priority and delay time is Mishra [19] proposed GKACO to make optimal resched- discussed. Besides, using sidings fexibly for trains in both uling. To optimize the delay time and the number of delayed directions (as retrack) and considering the operation of trains, Zhou et al. [20] formulated an MILP model for high- inbound and outbound trains in a complex railway network speed railway timetable rescheduling in large disruptions. By are coordinated in the model. Furthermore, we proposed an dispatching strategies of retime and reorder, the bufer time integrated two-dimension genetic algorithm (ITGA) to solve is made full use of to generate the rescheduling scheme. the problem. Te presented ITGA approach provides an Te above studies did not involve the ability to tolerate efcient way to resolve the confict by encoding train order perturbations and resist their potential efects. In order to as chromosomes using a matrix representation. apply in real-life applications, some research followed Tis paper is organized as follows: In Section 2, we a similar line of robustness, which refers to the capability of avoiding delay propagation as much as possible [2]. For provide an overview of related literature and highlight our contributions to it. Section 3 introduces the problem example, Cavone et al. [21] presented a three-step decision- statement and summarizes the notations and assumptions. making procedure to minimize delays and maximize ro- In Section 4, we model the problem in detail and study the bustness. Combined with the online heuristics, this paper constraints. In Section 5, the ITGA approach is designed to identifed and solved all conficts of emergency and the address the timetable rescheduling problem. Section 6 de- ofine cross-efciency fuzzy data envelopment on the op- scribes a simple case and a real-world case to demonstrate erational cost and augmentation of service reliability. Meng the efectiveness of the proposed model. Finally, the con- and Zhou [22] studied the robustness of a disrupted single- clusions and future work are discussed in Section 7. track rail line against random variations both in running times and the duration of the disruption. A stochastic programming model is obtained to identify robust schedules 2. Literature Review in a rolling horizon framework. Larsen et al. [23] tackled the train operation optimization problem when the train run- Te train timetabling rescheduling (TTR) problem is a well- ning time and staying time at the station fuctuate within studied problem in freight railways. Te main purpose of a certain range under the infuence of random uncertain rescheduling is to apply control strategies to minimize the interference. Furthermore, Layeb et al. [24] designed the negative efects of perturbations in railway systems. Goals simulation model to efciently account for real stochastic and methods are the core components of rescheduling. As behavior with skewed continuous distributions. key factors in evaluating the quality of results and solutions, However, the research mentioned above can be sum- the works of literature are reviewed under the line of ob- marized as an efciency-oriented approach focusing on jective functions and algorithms. minimizing the derivation from the perspective of the railway system. In reality, the train priority is an issue that must be taken into account in rescheduling. Liu and Kozan 2.1. Objective Functions. Various objective functions are considered in rescheduling a railway system [11]. Te ob- [25] studied mixed passenger and freight trafc in a single- line rail network. Te no-wait approach without any in- jective functions refect how to evaluate the quality of the rescheduling result, thus describing the main factors con- terruption is applied for the prioritized trains such as express sidered in rescheduling. Te most commonly considered passenger trains. With analysis of the structural properties, factors are efciency-related factors such as minimal an innovative generic constructive algorithm is proposed to (weighted) delay time. Moreover, the factors derived from it construct a feasible train timetable efciently and eco- are considered in combination, i.e., minimizing the number nomically. However, passenger trains have the absolute of delayed trains, maximizing timetable robustness, etc. priority on departure orders over freight trains; this paper discussed a passenger and freight railroad rescheduling Besides, some studies take equity into account, examining the impact of train priority in the rescheduling decision- problem essentially. Focusing on the train priority rescheduling problem, in making process. It has been recognized that consistency with the initial 1998, considering four attributes as the basic priority, critical timetable is one of the key performance indicators in rail- ratio, delay at the myopic resolution, and a number of ways. Punctuality, which is the guarantee of system ef- potential conficts, Sahin [9] proposed a utility function of ciency, is usually defned as the probability that a train weighted attributes to model the dispatcher’s choice be- arrives less than x minutes late [12]. Te total delay is the havior. Te system approach is in the construction of the most common criterion for punctuality (also reliability or heuristic algorithm to modify existing plans in conficting regularity) [13–16]. Aiming to minimize the sum of weighted situations in a single-track railway. Corman et al. [4] pre- delays, Kroon et al. [17] described a two-stage stochastic sented a novel optimization framework for the multiclass rescheduling problem on an alternative graph formulation optimization model to improve the robustness of a periodic timetable. But the paper only allocated one rescheduling of the problem. Dynamic priority combines static and dy- namic classes of priority with a branch and bound procedure strategy as retime (time supplements and bufer times). Interested in implementing diferent types of objectives, based on the actual entrance time of each train in the Journal of Advanced Transportation 5 train dispatchers and optimal or near-optimal solutions in network. Huo et al. [26] formulated the train rescheduling problem by adjusting priorities and train sequences to a reasonable length of time. To resolve the conficts, sim- ulated annealing (SA) [29], ant colony optimization (ACO) minimize the train disorder, which is the diference in train order between the initial and optimized one in the railway [30], genetic algorithm (GA) [6], particle swarm algorithm network. Te paper proposed the concept of train-order [31], tabu search algorithm [32], heuristic greedy algorithm entropy, and a binary mixed-integer programming model [33], or hybrid algorithms are implemented. was used for dispatching with minimal train operation Among them, GA performs well to provide acceptable adjustment. Shakibayifar et al. [2] implemented means of solutions at reasonable times with the search space being heuristic dispatching rules to address the delay management huge and complex because of its potential parallelism and problem in rail networks under multiple disruptions. Te robustness [6]. Chung et al. [14] proposed a hybrid genetic dynamic priority dispatching rule was applied where train algorithm to address the train-sequencing problem in railways. Te proposed algorithm utilized a modifed elite priorities are dynamically adjusted in a way that they are continuously calculated before a confict between two trains group technique and was tested with real-world data from the Korean railway. Dundar ¨ and S¸ahin [6] developed genetic is resolved. However, the allowed delay is predetermined, and the priority of the trains increases when the accumulated algorithms (GAs) for confict resolution in a single-track delay exceeds it. Taslimi et al. [10] developed a novel mixed- railway. Aiming to minimize the total (weighted) delay, the integer programming model to estimate train travel time, paper made every possible meeting train pair be represented and the paper distinguished the high-priority trains from by a specifc gene, and each gene in a chromosome repre- lower ones in the dataset, but how to handle diferent classes sents the station/siding in which possible conficts are re- of trains is unclear. Note that some research may also solved for specifc train pairs. Due to confict resolutions, Wang et al. [28] studied an improved GA for dynamic consider the equity problem in passenger railways, such as Shang et al. [27] considered an oversaturated situation in fexible job shop scheduling. To generate a high-quality initial population, the paper designed a mix of random urban rail transit networks and Banerjee and Smilowitz [8] studied to reduce the disutility in the school bus scheduling initialization populations by combining initialization ma- chine and operation and used an elitist strategy to avoid problem. In previous research, methods such as utility function falling into the local optimal solution. Indeed, the genetic and multiple-stage are used to consider efciency and equity algorithm (GA) has been proven to be efcient in solving the in freight railway rescheduling. However, it is observed that TTR problem. most criteria are specifc or only suitable for special sce- However, GA has an obvious weakness, as the con- narios; for example, one type of train has absolute priority in ventional GA-based approach’s performance deteriorates the stage (two-stage method), and the dispatcher’s per- rapidly for complex problems, especially for rescheduling problems considering network characteristics, operational ception of delay is deterministic (utility function). However, the diferences and synergies between the delay time and constraints, limited capacities, and resource availability. Terefore, in this paper, the integrated two-dimension GA train priority have not been fully evaluated. Terefore, we intend to explore whether there is a better way to explain the with dynamic train priority is studied. In implementation, relationship between them. Inspired by Corman et al. [4], train orders are presented for the coding scheme of chro- dynamic train priority is presented to establish the re- mosomes to overcome the movement conficts easily. To be lationship between the delay time and train priority. specifc, each individual in the population is represented by Moreover, in contrast to the previous studies using a sim- a two-dimension matrix, whose array represents the train plifed version, this algorithm is able to deal with the order at all stations. Besides, the search space is limited for problem in a complex railway network that consists of each gene constricted to the train delay time. single-track, double-track, and quadruple-track sections. Te method attempts to provide dispatchers with a more 2.3. Contributions. Table 1 compares recent studies on the standard, practical, and convenient method for real-world TTR problem in the key dimensions of main decision rescheduling. variables, equity problem, efciency and equity relationship, railway network topology, fexible track utility for both 2.2. Algorithms. Restricted to network characteristics, op- inbound and outbound trains, and solution algorithms. To erational constraints, limited capacities, and resource conclude, the gap lies as follows: (1) Most research considers availability, train rescheduling is a large-scale, complex, and trains with diferent priorities as equal in rescheduling. dynamic problem. Hence, the algorithm is vital in attaining Although few studied the equity problem in the freight higher punctuality on railway trafc systems. railway system, it is static and only suitable for special scenarios. (2) Most research fxes the use of the tracks, not Te exact algorithm takes enormous computational ef- forts to solve them to optimality even with advanced so- considering fexible track utility for both inbound and outbound trains. Tis approach is a simplifcation of the lution algorithms, which hinders their applications in large- scale instances in the real world. For the increased com- fexible track utility in real-world rescheduling, which is not conducive to efciency. (3) Most studies used a simplifed putational time in an exponential manner for the exact algorithm [28], a stream of heuristic algorithms has been version of railway networks such as single-track or double- developed in order to obtain better confict solutions than track, and few studies address the problem with single-track, 6 Journal of Advanced Transportation Table 1: Te comparison of the current studies on the train timetable rescheduling problem. Main decision Efciency and Railway network Flexible track Publications Equity problem Solution algorithm variables equity relationship topology utility Meng et al. [31] T.T D H (particle swarm algorithm), C Corman et al. [4] T.R, T.T, T.O √ M √ B&B Meng and Zhou [15] T.R, T.T, T.O M LR, C Kang et al. [34] T.T √ D H (GA), C Huo et al. [26] T.T, T.O S H (depth-frst method) Cavone et al. [21] T.T M C Shakibayifar et al. [2] T.T, T.O √ S H (two-stage method) Altazin et al. [35] T.T M H (greedy heuristics) Zhou et al. [20] T.T, T.O D C (Cplex) Taslimi et al. [10] T.R, T.T, T.O √ M C (Gurobi) Reynolds and Maher [13] T.R, T.T, T.O M √ Branch-and-price algorithm Tis paper T.R, T.T, T.O √ √ M √ H (GA), C Symbol descriptions: main decision variables: train arrival and departure time (T.T)/train route (T.R)/train order (T.O). Solution algorithm: branch-and-bound (B&B)/Lagrangian relaxation (LR)/heuristics (H)/ commercial solver (C). Railway network topology: M (mixed track); D (just double tracks); S (single track). Flexible track utility: use track fexible (Y); use track fxed (N). Te bold value is to highlight the distinctive qualities of this study that diferentiate it from other works in the feld. Journal of Advanced Transportation 7 double-track, or quadruple-track networks. It is not in line same time for safety. At stations, there are tracks B for with reality and thus not capable to be applied in the overtaking activities and yard tracks for temporary train real world. storage. To conclude, this paper has a number of key contri- butions to the feld of rescheduling: 3.1.1. Operation. Each train has a predefned route in the (i) To resolve the train timetable rescheduling problem, network, and every station on the route is labeled as origin, an optimization model is formulated considering intermediate, stop, or destination. Te fxed routing policy is both efciency and equity. Te proposed model utilized for each train based on the rules. Trains traveling utilizes the combined strategies of retiming, reor- from origin to the destination pass the intermediate stations dering, and retracking considering network char- and stop at stop stations with fagged workings. Train i is acteristics, operational restraints, limited capacities, taken as an example, whose origin is station 1 and desti- and resource availability. Te model deals with the nation is station 7. At the origin o(i), the train couples with fexible track utility for both inbound and outbound the locomotive, and the route of the train j is listed as (1, 2, 3, trains in a complex railway network containing 4, 5, 6, and 7) to the destination d(i). Te train stopping at single-track, double-track, and quadruple-track predetermined stations is labeled as stops for working as sections. changing crew or pick-up/drop-of railcars, while passing through stations, it is labeled as intermediate. Te route (ii) To explore the relationship between efciency and refects section occupancy in operating, and multiple tracks equity in rescheduling, we make train priority in sections can be fexibly allocated for efciency. evolutionary and propose the dynamic train priority based on the delay time and static train priority. As an important factor in rescheduling, the threshold 3.1.2. Workings. Operational workings need to be com- to upgrade the train priority is analyzed in pleted at stations labeled as stop, which are predetermined. this paper. Trains have a mandatory stop and need to pick-up/drop-of ps crew (iii) To reobtain an optimized timetable of sufcient railcars, changing crew at fagged stations S and S , quality in a reasonable period, we propose an ef- respectively. Besides, the locomotives are to be coupled at the cient and fast heuristic algorithm to fnd the optimal origins. solution. We improved the general GA into an integrated two-dimension one, and the train orders 3.1.3. Priority. Each train has the initial characteristics of are presented for the coding scheme of chromo- high or low priority. Te train priority is an important somes to avoid spatiotemporal train confict. Nu- criterion in deciding train departure order; that is, a low- merical experiments demonstrate that our proposed priority train may stop on the sidings at the station and be approach is very efcient, obtaining a high-quality overtaken by a high-priority train. In this paper, the train rescheduling timetable for a complex mixed-track priority is evolutionary based on the delay time and static railway network in a reasonable amount of time. train priority to achieve equity. In this paper, the priority of the lower train is adjusted dynamically in the timetable 3. Problem Statement rescheduling process. It will be upgraded to m when the is delay time reaches a certain threshold. Besides, the threshold In this study, the rescheduling problem on a mixed-track is also analyzed in the paper. railway network is thoroughly discussed considering both equity and efciency. Section 3.1 describes the network topology and railway operation by an illustrative railway 3.1.4. Delay. Tree kinds of delays are taken into consid- network. Section 3.2 illustrates the notation in the model, eration caused by the unavailability of the locomotive at the while Section 3.3 presents the assumption. origin station, changing crew duty, or yard operations (pick-up or drop-of railcars). Te impact of delays on adjacent train timetables must be taken into account, and the 3.1.Description. We formulate the rescheduling problem on running time at section (s, p) and minimal dwell time for a mixed-track railway network, represented by a directed trains are determined according to the planned timetable. graph and denoted as G(V, E).E is a set of directed edges as tracks, and V is the set of nodes as stations where the track 3.2. Notations. All the notations and variables used in the merges or splits. As shown in Figure 2, there are parallel formulations are listed in Tables 2 and 3. tracks K among adjacent stations (s, p). In addition to the sp main tracks K , which are 1 for single track and 2 for double sp tracks, there are sidings K as auxiliary tracks in the net- sp 3.3. Assumptions. Te assumptions made to construct the work. All the main tracks are one-way for a predetermined mathematical model in this paper are as follows: running direction, while the sidings can be fexibly used and shared for inbound and outbound trains. Te tracks cannot (1) Te rescheduling approach is performed based on be occupied by two trains in diferent directions while a fxed-speed model; the section running time for satisfying the minimum headway in the same direction at the each train is fxed and predetermined. Te trains 8 Journal of Advanced Transportation single-track line double-track line four-track line siding industrial spur Station 1 Station 2 Station 3 Station 4 Station 5 Station 6 Station 7 Main Track Siding (An auxiliary track) (a) Station 6 Station 1 Station 2 Station 3 Station 4 Station 5 Station 7 Route Track Main Track Siding (An auxiliary track) (b) Figure 2: An example of freight railway network topology: (a) original track infrastructure; (b) vertex-edge topology graph. move at their maximum allowable speed on each 4.1. Constraints track which is limited to the permissible section 4.1.1. Departure Time Constraints. Constraint (1) ensures speed and train speed [10]. that the relationship guarantees the feasibility of the (2) Any track can only be occupied by one train at the rescheduled timetable. Besides, the departure time of the same time. Trains can access the siding, yard, and train i from the station s (the start time of occupying the other mainline tracks at the stations from any of the track k between the station s and station p) equals the actual mainline tracks using the appropriate crossover. dwell time of the train i at the station s plus the arrival time at Inbound and outbound trains can share the same the station s (the end time of the train i occupying the track k siding if it is achievable, but a track of a segment can between the station s and station p). Constraint (2) links the only be used by trains running in the same direction. arrival time, departure time, and dwell time at stations: (3) Te train occupying a siding or industrial spur will be charged an additional time. Te time is to wait for the 􏽘 t ≥ t ∀i ∈ I, ∀(s, p) ∈ S(s, p), ispk is sp (1) other train to pass, receive movement permission p∈S k ∈K sp sp from the dispatcher and return to the mainline at a low speed. a d 􏽘 􏽘 t � 􏽘 􏽘 t ispk ispk sp sp (4) Tere is no change in the train route and workings, p∈S p∈S k ∈K k ∈K sp sp sp sp (2) and the trains travel according to the previous route. + stop ∀i ∈ I, ∀(s, p) ∈ S(s, p). Because reroute is applied only when big in- terruptions like disruptions occur, it will make the Te impact of delays caused by the locomotive and yard midrailway carriage unreachable which is planned to unavailability on the arrival and departure time of trains are be picked up or dropped of at stop stations. illustrated in constraints (3) and (4). Te delay at the origin for each train, which is the deviation between the 4. Train Timetable Rescheduling (TTR) Model rescheduled and planned departure time, is presented in the form of probability statistics in this paper. Te delay is In this section, we introduce our train timetable resched- greater than a certain value with a confdence level (α) from uling (TTR) model considering both efciency and equity. historical data. Obeying the distribution of historical sta- Te constraints (1)–(15) are formulated with respect to tistics, the impact of locomotive-caused delay at origin is as network characteristics, operational restriction, limited ca- expressed in constraint (3). Similarly, the duration for the pacities, and resource availability. Te objective functions dwell time delay caused by the yard activity (pick-up/drop- equations (18)–(20) can be categorized into efciency- of) is stated in constraint (4): oriented and equity-oriented ones. Journal of Advanced Transportation 9 Table 2: List of notations used in the mathematical model. Notations Defnition Sets S Set of stations, S � {0, 1, . . . , |N|}, where |N| is the number of stations crew crew S Set of fagged stations for the crew change, S ∈ S l l ps ps S Set of fagged stations for picking up or dropping of railcars, S ∈ S l l S(s, p) Set of the adjacent stations between the station s and station p I Set of trains, I � {0, 1, . . . , |I|}, where |I| is the number of trains − − I Set of trains with low static train priority, I ∈ I + − B Set of all tracks of at station s, B � B ∪ B S S S S B Set of tracks at the station s, including sidings and yard tracks B Set of virtual tracks at the station s, which is sufcient for the train dwell at its origin + − K Set of all tracks between the station s and station p,K � K ∪ K sp sp sp sp + + K Set of main lines between the station s and station p, K � {1, 2} sp sp − − K Set of sidings between the station s and station p, K � 3, . . . , |K | − 2 􏽮 􏽯 sp sp sp Index i, j Index of trains s, p Index of stations o(i) Index of the origin station of the train i d(i) Index of the destination station of the train i b Index of tracks at the station s k Index of tracks between the station s and station sp Parameters Given binary parameter, the station sequence for train i in operation. r � 1, if the isp isp train i passes the section from station s to station p. r � 0, otherwise isp Given binary parameter, static level of train i. psl � 1, if the static level of the train i psl is high level, psl � 0, otherwise t Departure time of the train i at the station s in the initial timetable is t Arrival time of the train i at station s in the initial timetable is t Te delay time threshold to upgrade dynamic train priority from low to high t Te running time from the station s to the station p sp A time penalty of a train when a train occupying a siding, wye, or industrial spur at the station ts Te minimum dwell time of the train i at the station s in the initial timetable Te deviation in dwell time of the train i at the fagged station s due to delay caused tsc by crew change Te deviation in departure time of the train i at the origin station because of tdl locomotive unavailability Te deviation in the dwell time of the train i at the fagged station s due to delay tdp caused by a pick-up or drop-of activity in yard h Te minimum following headway to ensure safety fd Probability for the delay time because of locomotive unavailability, a pick-up/ α,β, c drop-of activity, and crew change, respectively τ Te weighted index based on the dynamic train priority is M A sufciently large number Auxiliary variables A A d t Arrival time of the train i at the station s, t � 􏽐 􏽐 t is is p∈S k ∈ k ipsk sp sp sp D D d t Departure time of the train i at the station s, t � 􏽐 􏽐 t is is p∈S k ∈ k ipsk sp sp sp Te dynamic train priority of the train i at the station s. m � psl + pdl pdl � 1, if is i is is is the delay time of the train i at the station s is larger than t . pdl � 0, otherwise r is 10 Journal of Advanced Transportation Table 3: Decision variables. Notations Defnition Decision variables m Binary variable, m � 1, if the train i occupies the track k in the section (s, p) ispk ispk z Binary variable, z � 1, if the train i occupies the track b at the station s isb isb S S Te train order of the train i and j in the section (s, p). y � 1, if the train i ijsp ijsp departures ahead of the train j in the section (s, p). y � 0, otherwise ijsp Te end time of the train i occupying the track k between the station s and station p ispk (arriving at the station s) Te start time of the train i occupying the track k between the station s and station p ispk (departing from station s) stop Te actual dwell time of the train i at the station s (except origins) d a 􏽘 t − 􏽘 t � t + t ∙ 􏽘 m ispk ispk sp r ispk a sp sp sp ⎛ ⎜⎛ ⎜ ⎞ ⎟ ⎞ ⎟ ⎜⎜ ⎟ ⎟ ⎝⎝ ⎠ ⎠ − − − Pr 􏽘 􏽘 t − t ≥ tdl k ∈K k ∈K k ∈K io(i)pk io(i) i sp sp sp sp sp sp sp (9) (3) p∈S k ∈K sp sp ∀i ∈ I, ∀(s, p) ∈ S(s, p). ≥α∀i ∈ I, ∀(s, p) ∈ S(s, p), 4.1.4. Section Route Selection Constraints. If the section a d s s ⎛ ⎜⎛ ⎜ ⎞ ⎟ ⎞ ⎟ ⎜⎜ ⎟ ⎟ ⎝⎝ ⎠ ⎠ Pr 􏽘 􏽘 t − 􏽘 􏽘 t − stop ≥ tdp ispk ispk i i sp sp (s, p) is on the route of the trains, then the only track in the p∈S k ∈K p∈S k ∈K sp sp sp sp section is to be occupied by the train. Constraint (10) ≥β∀i ∈ I, ∀(s, p) ∈ S(s, p). guarantees the uniqueness of track occupancy along the route for the train. Meanwhile, it ensures train continuity (4) and consistency at every station on the route from the Constraints (5) and (6) are utilized to specify all the predetermined origins to destinations: trains that travel on a designated route. If and only if the m � r ∀i ∈ I, ∀(s, p) ∈ S(s, p). ispk isp station is on the route, the departure and arrival time at the sp (10) k ∈K sp sp station exist, as imposed in constraints (5) and (6), sepa- rately. Otherwise, the departure or arrival time is nonexistent: 4.1.5. Section Route Occupation Constraints. For each pair of t ≤ M∙ m ∀i ∈ I, ∀(s, p) ∈ S(s, p), (5) ispk ispk sp sp trains at one station, deciding on the train order is com- pulsory for rescheduling considering various factors, and the t ≤ M∙ m ∀i ∈ I, ∀(s, p) ∈ S(s, p). (6) departure-sequence-based timetable is useful to avoid spa- ispk ispk sp sp tiotemporal conficts in the section. To specify the moving direction, the departure and arrival time between two trains of the same direction and opposite directions are demon- 4.1.2. Dwell Time Constraints. Te actual dwell time in the strated in constraints (11) and (12). Considering the train i rescheduled timetable should satisfy the standard work time departs earlier than the train j in the section (s, p) and y ijsp at every visited station on the route, as stated in constraint equals 1, only the train i leaves the track, the train j can enter (7). For the dwell time of trains in fagged stations with the track in the section (s, p). It also illustrates why we use changing crew duty, the delay is greater than a value with the start time and end time of occupying a track as a decision a confdence level from historical data. Constraint (8) ex- variable: presses the impact of crew-duty delay which obeys the a d distribution of historical statistics, resembling constraints t − t ≥ M∙ 􏼐1 − y 􏼑∀i, j ∈ I and i ≠ j, ijsp jspk ispk sp sp (11) (3) and (4): ∀(s, p) ∈ S(s, p), ∀k ∈ K , sp sp s s stop ≤ ts ∀i ∈ I, ∀s ∈ S, (7) i i a d t − t ≥ M∙ 1 − y ∀i, j ∈ I and i ≠ j, 􏼐 􏼑 s s crew jspk ispk ijsp sp sp Pr stop ≥ tsc 􏼁 ≥ c∀i ∈ I, ∀s ∈ S . (8) (12) i i l ∀(s, p) ∈ S(s, p), ∀k ∈ K . sp sp 4.1.3. Siding Occupation Constraints. Constraint (9) repre- sents that a time penalty is charged for a train entering the 4.1.6. Station Track Assignment Constraints. At stations, the sidings at particular stations. Te section running time, i.e., tracks are to be assigned and occupied for train temporary the time diference between the train leaving and entering storage or workings. Constraint (13) states that the train i the track, equals to the standard section running time plus and the train j can occupy one and only track at the station s penalty time for siding events: (except origins, which are assumed to have sufcient tracks Journal of Advanced Transportation 11 for temporary storage for coupling locomotive). Constraints requirement between the train i and the train j in the same (14) and (15) are used to satisfy the minimum headway direction: 􏽘 z � 1 and 􏽘 z � 1∀i, j ∈ I, ∀s ∈ , isb jsb (13) S S o(i) + + b ∈B b ∈B S S S S a d 􏽘 􏽘 t − 􏽘 􏽘 t ≥ h − M∙ 􏼐3 − y − z − z 􏼑∀i, j ∈ I and i ≠ j, ∀s ∈ S, fd ijsp isb jsb ispk jspk sp sp S S (14) p∈S p∈S k ∈K k ∈K sp sp sp sp a d 􏽘 􏽘 t − 􏽘 􏽘 t ≥ h − M∙ 􏼐3 − y − z − z 􏼑∀i, j ∈ I and i ≠ j, ∀s ∈ S. jspk ispk fd jisp isb jsb S S sp sp (15) p∈S k ∈K p∈S k ∈K sp sp sp sp 4.1.7. Train Priority Adjusting Constraints. Te train order where λ ,λ ,λ are the weights of the objectives, respectively, 1 2 3 depends on the delay time and train priorities. Constraints and λ ,λ ,λ ≥ 0. 1 2 3 (16) and (17) satisfy that the train priority is dynamically λ , λ , and λ are introduced to the ftness function, for 1 2 3 upgraded when the delay time of the train i at the station s there are diferent orders of magnitude among Z , Z , and 1 2 reaches the threshold: Z . Te values of them are obtained by (1) considering Z , 3 1 Z , and Z as ftness functions, respectively, and taking it as D D − 2 3 (16) t − t − t < M∙ pdl ∀i ∈ I , ∀s ∈ S, r is is is a single objective optimization problem, (2) obtaining the min min optimal values of the single objective problem as Z , Z , 1 2 D D − min (17) t − t − t ≥ M∙ pdl − 1 􏼁 ∀i ∈ I , ∀s ∈ S. and Z , and (3) calculating λ , λ , and λ according to r is is is 1 2 3 equations (22),–(24): min min Z ∙ Z 2 3 λ � , (22) 4.2. Objective Functions min min min min min min Z ∙ Z + Z ∙ Z + Z ∙ Z 1 2 1 3 2 3 4.2.1. Efciency-Oriented Objectives. When a delay occurs, it min min will propagate and afect the railway system’s efciency. Te Z ∙ Z 1 3 λ � , (23) min min min min min min primary purpose for efciency is to recover from the delay Z ∙ Z + Z ∙ Z + Z ∙ Z 1 2 1 3 2 3 and minimize the total arrival deviation, as shown in the following expression: min min Z ∙ Z 1 2 λ � . (24) A A ps crew min min min min min min min Z � 􏽘􏼐t − t 􏼑 s ∈ 􏼐S ∪ S 􏼑. 1 is is l Z ∙ Z + Z ∙ Z + Z ∙ Z l (18) 1 2 1 3 2 3 i∈I 5. Solution Approach 4.2.2. Equity-Oriented Objectives. Considering the dynamic Te application of mathematical modeling to train train priority, equation (19) is weighted to minimize the total rescheduling is usually considered by its complex and time- deviation. Furthermore, the dispatching disorder, which is consuming process [2]. It is well known that the model is far the diference in the train sequence between the initial and more difcult to solve optimally in a reasonable time by optimized one in the railway network, is used to highlight commercial solvers (i.e., Cplex). Hence, we propose a two- train priority as equation (20) referring to Huo et al. [26] dimension genetic algorithm integrated with uncertainty work: optimization transformation and search space reduction. D A min Z � 􏽘 􏽘􏼐􏼐t − t 􏼑∙τ 􏼑, 2 is is is (19) Te framework and methodology, especially the two- i∈I s∈S dimension coding strategy based on the train order, are 􏼌 􏼌 introduced in this section. 􏼌 􏼌 􏼌 􏼌 􏼌 􏼌 i ≠ j, (s, p) ∈ S(s, p). min Z � 􏽘 􏽘 􏽘 􏽘 y − y 􏼌 􏼌 3 ijsp ijsp i∈I j∈I s∈S p∈S 5.1. Framework. Te overview of the timetable rescheduling (20) framework is shown in Figure 3. Under the background of Te model to deal with multiple objectives is also de- the stochastic delays, this paper simulates the delay caused scribed to tradeof equity and efciency and manifest model by crew change, a pick-up/drop-of activity, and locomotive performance. An objective function deriving the evaluation unavailability with distributions calculated from historical values is manifested as follows: data. Based on the initial timetable, we propose the ITGA approach using the dispatching strategies as retime, reorder, Eva � λ ∙ Z + λ ∙ Z + λ ∙ Z λ + λ + λ � 1􏼁, (21) 1 1 2 2 3 3 1 2 3 and retrack. 12 Journal of Advanced Transportation infrastructure manager Initial timetable design Historical freight f low Disturbance in operation: train delay Historical delay record Adjust Initial timetable: Delay Delay time Trains rescheduling optimization distribution Simulation Generation Operational (1) Re-time constraints (2) Re-order (3) Re-track Equipment Quick solution constraints Rescheduled timetable infrastructure manager/dispatcher no minimize all Objective? yes The best rescheduled timetable Figure 3: Overview of the timetable rescheduling approach framework. 5.2. Methodology. Te rescheduled timetable should be represented by a two-dimension matrix, whose array generated within the required time to ensure the handover of with as many positions as pairs existing in the railway dispatcher responsibility to the next shift and timely op- scheduling problem is considered. To explain this issue, eration. To address the problem with efciency, the ITGA we take a four-train-four-station case on a single-track approach is proposed as follows: railway in Figure 4 as an example. Te number of the row i and the column j in Table 4 represents the chromosome (1) It stochastically simulates the delay and transforms coding as the train order of the train j at the station i. the uncertain constraint based on the equivalence Moreover, the crossover and mutation process in the use theorem based on the distribution function. of improving efciency and preventing local optimal is (2) It compresses the lower and upper bound of the train shown in Figures 5 and 6. order on each train at stations based on the generated Crossover: parent individuals selected in preceding order delay time, which limits the search space. are crossed to generate the ofspring individuals. To improve readability, we choose the frst three stations in the case. (3) It obtains initial feasible two-dimension chromo- somes and pivots the process of selection, crossover, Figures 5(a) and 5(b) show the parents and ofspring after random crossover, which is infeasible for trains that have the and mutation. same train order at one station. Followed by the rule of (4) It terminates only when the diference in the best taking the initial train order as a rearranged reference, the solutions between two generations is less than the updated feasible ofspring is shown in Figure 5(c). given parameter or reaches the maximum number of Mutation: the mutation is randomly applied to the two- iterations. dimensional chromosome with a given probability. Figur- Indeed, the coding strategy plays a signifcant role in es 6(a) and 6(b) show the parents and ofspring after mu- GA efciency. Tis paper adopted train orders for the tation, which confict at Station 3. Te chromosome would coding scheme of chromosomes to overcome movement be updated with the same rules as explained in the crossover conficts easily. Each individual in the population is phrase, and Figure 6(c) shows the updated timetable. Journal of Advanced Transportation 13 010 20 30 40 Station 1 Station 2 Station 3 Station 4 Train 1 Train 3 Train 2 Train 4 Figure 4: Timetable for 4 trains in single-track railway with 4 stations. Table 4: An illustrated example of the coding strategy based on train order. Train 1 Train 2 Train 3 Train 4 Station 1 1 3 2 4 Station 2 1 2 3 4 Station 3 2 1 4 3 Station 4 1 2 4 3 Gen:departure order 4 trains 2 1 3 4 1 2 3 4 1 2 3 4 2 1 4 3 parents Crossover point 2 1 3 4 3 2 1 4 (a) 1 3 2 4 1 2 3 4 After crossover 1 2 3 4 2 1 4 3 2 2 3 4 3 1 1 4 conflict conflict (b) Chenck and updata according to original departure sequence 1 3 2 4 1 2 3 4 1 2 3 4 2 1 4 3 Offspring 2 1 3 4 3 1 2 4 (c) Figure 5: Crossover operation for a two-dimension chromosome: the rules and the results. Exhibiting the coding strategy and update rules, now we characteristic is satisfying a defnite confdence level at least. move to a brief introduction on the addressing of the un- To handle the three kinds of uncertainty constraints, we certainty optimization and search space in ITGA. transform the uncertainty constraint into deterministic inequalities through a deterministic transformation as follows: 5.2.1. Transformation of the Uncertainty Optimization Problem. Uncertainty optimization is a theory that achieves Pr x ≥ξ􏼁 ≥α , (25) i i i the best under a certain probability, whose remarkable 3 stations 14 Journal of Advanced Transportation 1 2 3 4 1 2 3 4 After mutation 2 1 4 3 2 1 4 3 3 2 1 4 3 1 1 4 Lower bound Upper bound mutation (a) (b) Chenck and updata according to original departure sequence Train 1 Train 2 Train 3 Train 4 1 2 3 4 Station 1 1 3 2 4 Station 2 1 2 3 4 2 1 4 3 Station 3 2 1 4 3 Station 4 1 2 4 3 3 1 2 4 (c) Figure 6: Mutation operation for a two-dimension chromosome: the rules and the results. where α is the level of confdence, x is the decision variable, 6.1. An Illustrative Case. A simple case of three trains with i i and ξ is the random variable. four stations is set to illustrate the model. Te initial Kroon et al. [17] proved that exponential distribution timetable is shown in Table 5 and also displayed visually in can be applied to nonnegative train arrival and departure Figure 7(a), while the running time is fxed in the section for delay distribution. Te delay obeys logarithmic normal each train. Train 1 of low priority has predetermined distribution, and the parameters can be simulated by the working at Station B, and Train 2 of high priority has historical data. For ξ ∼ log N(μ,σ ), we can conduct that predetermined workings at Station B and C. Running in reverse, Train 3 of low priority has predetermined working at Y � LN(ξ ) ∼ (μ,σ ). Let the distribution function of Y be F , and there is Pr(h(y) ≥ Y) � F (h(y)) � ϕ[h(y) −μ Station C. 1 1 /σ] ≥α. We assume that two perturbations cause delays, where For the formula Pr(x ≥ K ) � α , there is always Train 1 is delayed for 23 minutes at Station B for a crew i a i a number making it true (choose the smaller one when K change, and Train 3 was delayed for 5 minutes at Station D has more than one numerical value). Since Z � LN(ξ ) for locomotive unavailability. Te consideration of limited i i obeys normal distribution, K can be obtained by the fol- resources of tracks is also required in the rescheduling lowing formula: problem. As shown in Figure 7(b), Train 3 needs to dwell at the former station (Station D) when considering the number − 1 h(y) ≥ K � σ + ϕ 1 − α􏼁 + μ (26) a i i i, of sidings. Te reason is that there is only one siding at Station C for trains to dwell as shown in Figure 7(d). Hence, where σ is the standard deviation and μ is the mean value. i i Figure 7(b) displays a feasible timetable not considering train order adjustment. In this case, a 90-minute delay is caused as displayed in Table 6, with Train 1, Train 2, and 5.2.2. Upper Bound and Lower Bound. Besides, the search space is limited for each gene constricted to the train delay Train 3 contributing to 35 minutes, 25 minutes, and 35 minutes, respectively. Te delay time is 3.21 times longer time. By using the train order as the decision variable, this paper reduces the number of decision variables and con- than the primary delay. However, the result of the ITGA solution when making straints compared with the model based on departure/arrival time. However, increasing the dimension of decision vari- the train priority evolutionary is shown in Figure 7(c). For reaching the threshold, Trains 1 and 3 of low priority are ables will also increase computational complexity. In order to ensure computational efciency, we set the lower and upgraded. In that case, the total delay is 46 minutes including upper bound of the train order based on the delay time to 23 minutes, 18 minutes, and 5 minutes for Train 1, 2, and 3, respectively. Te delay of the optimized results is only 51.1% limit the search space. compared with the unadjusted one as shown in Table 7. 6. Case Study For this section, a simple three-train-four-station case is 6.2. A Real-World Case constructed to illustrate the method in Section 6.1. More- over, a real-world railway case in the Netherlands with 62 6.2.1. Description of Instances. To evaluate our model, we stations and 254.9 km in length is given to test the perfor- use the test instance provided in the 2020 RAS problem mance and efciency of ITGA in Section 6.2. solving competition. It is a line going east-west with 62 Journal of Advanced Transportation 15 Table 5: Te initial timetable of the illustrative case. Train 1 Train 2 Train 3 Arrival Departure Arrival Departure Arrival Departure Station A — 7:00 — 7:20 8:20 — Station B 7:15 7:25 7:35 7:40 8:05 8:05 Station C 7:35 7:35 7:55 8:00 7:50 7:55 Station D 7:50 — 8:15 — — 7:35 Station D Station D Station C Station C Station B Station B Station A Station A 7:00 7:30 8:00 8:30 9:00 7:00 7:30 8:00 8:30 9:00 Train 1 Train 1 Train 2 Train 2 Train 3 Train 3 (a) (b) Station D Station C Station B Station A 7:00 7:30 8:00 8:30 9:00 Train 1 Train 2 Train 3 (c) Station C Station A Station B Station D Station D Station track crossover (d) Figure 7: An illustrative case of three trains in a double-track railway. (a) Te initial timetable. (b) Te feasible timetable without train order adjustment. (c) Te optimized timetable with train order adjustment. (d) Te railway network topology of the example. Table 6: Te feasible timetable without train order adjustment. Train 1 Train 2 Train 3 Arrival Departure Arrival Departure Arrival Departure Station A — 7:00 — 7:20 8:55 — Station B 7:15 8:00 7:35 7:40 8:40 8:40 Station C 8:10 8:10 7:55 8:25 8:25 8:30 Station D 8:25 — 8:40 — — 8:10 16 Journal of Advanced Transportation Table 7: Te optimized timetable with train order adjustment. Train 1 Train 2 Train 3 Arrival Departure Arrival Departure Arrival Departure Station A — 7:00 — 7:20 8:25 — Station B 7:15 7:48 7:35 7:58 8:10 8:10 Station C 7:58 7:58 8:13 8:18 7:55 8:00 Station D 8:13 — 8:33 — — 7:40 stations and 254.9 km in length on the Netherlands railway. a regular periodic operational diagram based on headway as Te topology of the railway line and the stations are shown shown in Figure 11. Under the extensive and stochastic in Figure 8. Te data on 405 trains for 2 days are given, delay, the optimized rescheduling timetable with the min- including the route, train priority (high or low), departure imized integrated total delay, the dwell time and the and arrival time, and specifed working (crew change and numbers of train sequence adjustments are shown in Fig- yard activity for picking up and dropping of railcars) at ure 12. Taking the frst train in blue line as an example, a 5- a predetermined station for each train, and the required minute delay occurs at the origin Station Ehv due to lo- comotive unavailability and 54-minute at Station Wt for travel time and dwell time of the train can be calculated from the initial data. yard activity. Te delay exceeds the threshold at Station Rm, and the train priority upgrades to departure early. Moreover, In addition, the historical data on the delays caused by crew change, locomotive unavailability, and yard activity are the topology of the railway network is precisely character- given. Te delays are concluded as logarithmic normal ized by the model. Tis can be verifed by the diference distributions, and we adopt 90% as a confdence level to between the time between two adjacent trains depart and run ensure the result’s adaptability under adverse conditions and in a quadruple-track section or a double-track section. Te evaluate model performance. Te simulated distribution rescheduled timetable for T517 and T519 at Station Ehv functions are calculated and displayed in Figure 9, and (heading to Station Ehs) is taken as an example. From Table 8 illustrates the parameter values used in this Figure 8, we can see that it is a quadruple-track section experiment. between Station Ehv and Station Ehs. Te rescheduled timetable shows that the approach fully utilized the in- frastructure resource while meeting the constraints. It can 6.2.2. Result of the ITGA Approach and Comparison. In this also prove the validity of the model. section, we test our model in the Netherlands railway using python 3.7 and carry it out on a computer with a 2.1 GHz of Intel(R) Core (TM) i7-12700F CPU and 16 GB RAM in 6.2.3. Sensitivity Analysis a Windows environment. As shown in Table 9, the result of the ITGA approach considering both efciency and equity is (1) Analysis of the Multiple Objectives. As mentioned in obtained within 43 s, while it takes 5 seconds for the FIFO Section 4.2, we use weighted objectives to solve the multiple- strategy. Te approach meets the requirements for gener- objective problem. Note that our problem can be extended to ating a rescheduled timetable. Moreover, the parameters that an efciency-oriented model by setting λ � 1. Table 12 need to be determined in ITGA are listed in Table 10, in- shows the total delay time to be 47956 when only consid- cluding the crossover rate, the mutation rate, and the ering minimizing the total delay time. Te gap in the delay population size. time between the weighted objective and the minimum- Te progressively stabilized optimizing results are shown delay-time objective is 4.44%. In conclusion, although the in Figure 10, and the total objective value of the proposed total delay time of all trains is increased in the proposed approach decreases with iterations increasing. When the model, the schedule is more in compliance with the indi- number of iterations increases to 100, the algorithm remains vidual train orders. Te loss of the total delay time is utilized stable, and the solution is 1623.50. to trade of balance between equity and efciency. In this As depicted in Table 11, compared with the frst-in- case, the high-priority train may overtake a low-priority frst-out (FIFO) strategy (no train order adjustment), the train with the consideration of both the current train delay total objective value is decreased by 18.8%. In detail, the total and dynamic train priority. delay is signifcantly reduced by 40.9% with the ITGA ap- proach, which proves the importance of the train order (2) Relationship Analysis on Dynamic Train Priority Ad- adjustment in delay recovery. Besides, the weighted dwell justment Treshold. Making the train priority evolutionary, time is reduced by 2.5%. Te optimization ratio also verifes the threshold of train priority upgrade is a critical factor in the indirect delay caused by delay propagation which is rescheduling. Hence, we applied a detailed sensitivity enormous and noticeable in rescheduling problems. analysis on the threshold to evaluate the impact and balance To explain the optimization solution in practice, some the train priority and the delay time to choose the optimized trains on the west-east line are selected and visualized with one. Figure 13 depicts the objective value decreases as the a rescheduling working diagram. Note that the selection is dynamic level adjustment threshold increases. Although for the readability of the timetable. Te initial timetable is there are several pick-ups of the total objective or Journal of Advanced Transportation 17 … … … … … … Vs Vss Mdb Tbu Tbge Tb Tba Btl Bet EHS EHV GP HMBV Vl Rm North Route 50 …… 57 …… 61 …… …… 39 49 02 …… 1 …… 23 26 …… 31 South Route Figure 8: Te illustrations of the railway network topology in the Netherlands. CREW_AVAIL LOCO_AVAIL YARD_AVAIL 0.6 1.0 0.5 0.5 0.8 0.4 0.4 0.6 0.3 0.3 0.4 0.2 0.2 0.2 0.1 0.1 0.0 0.0 0.0 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 (a) (b) (c) Figure 9: Te distribution functions of resource availability. (a) Te dwell time at the fagged station for the crew change. (b) Te delay from the planned departure time at the origin. (c) Te yard delay at fagged pickup and setof points. Table 8: Te distribution function of resources availability. Lower bound of Distribution function Random variables delay K (α � β � c � 90%) (unit: h) (unit: min) CREW_AVAIL X ∼ log N(0.1, 1) 18.40 LOCO_AVAIL X ∼ log N(0.25, 0.1) 51.37 YARD_AVAIL X ∼ log N(0.5, 0.25) 52.12 CREW_AVAIL: the dwell time of a train at fagged stations for the crew change; LOCO_AVAIL: the delay from the planned departure time at the point of origin because of locomotive unavailability; YARD_AVAIL: the yard delay at the fagged pick-up/drop-of station s in the train route. Table 9: Testing results of the example. Time window Te number of trains Computing time (m:s) ITGA [0, 240] 64 00:43 FIFO [0, 240] 64 00:05 the arrival delay of all trains at the destination. All the Table 10: Te determined value of parameters in ITGA. statistics indexes are shown in Table 13. When the threshold Parameters Value reaches 50 minutes, the destination delay is minimal. Population size 100 However, considering the comprehensive performance, Number of iterations 100 60 minutes is taken as the threshold of the dynamic level Crossover rate 0.7 adjustment in this paper, and the average delay of each train Mutation rate 0.3 under the optimal result is 210.9 minutes (approximately 3.5 hours) for this case in the 60 threshold. subobjective at a threshold of 40, they generally follow the Concerning the abovementioned experimental tests, we downward trend. draw conclusions as follows: (1) Te balance of the dynamic To choose the best-performed thresholds and tradeofs train priority and delay time is necessary for operation. between the individual train and railway system, we calculate Compared with the FIFO strategy, the total delay is y 18 Journal of Advanced Transportation 0 20 40 60 80 100 Number of iteration Figure 10: Optimization result of the total objective of the real-world case. Table 11: Te comparison of the ITGA and FIFO strategy. Total Weighted Te number of Objective value delay time (minutes) dwell time (minutes) train order adjustment ITGA 50086 28652 642 1623.5 FIFO 70580 29365 0 1928.3 Gaps 40.9% 2.5% — 18.8% Mt Bha Bde Bk Lut Luta Std Sm Ec Mbt Rm Hln Wt Mz Ohze Hze Gp Tgra Ehv Ehs Ehb At Bet Btl 5:00 6:00 7:00 8:00 9:00 10:00 11:00 Train number 512 517 513 518 514 519 515 2288 516 2286 Figure 11: Initial timetable for the real-world case. Total objective Journal of Advanced Transportation 19 Mt Bha Bde Bk Lut Luta Std Sm Ec Mbt Rm Hln Wt Mz Ohze Hze Gp Tgra Ehv Ehs Ehb At Bet Btl 5:00 6:00 7:00 8:00 9:00 10:00 11:00 12:00 13:00 14:00 15:00 Train number 512 517 513 518 514 519 515 2288 516 2286 Figure 12: Rescheduling timetable for the real-word case. Table 12: Te total delay time based on the diferent objectives. Gaps Weighted objectives Minimize delay time (%) Delay time 50086 47956 4.44 10 20 30 40 50 60 dynamic priority threshold (a) 51500 31000 10 20 30 40 50 60 dynamic priority threshold Objective 1 Objective 2 (b) Figure 13: Continued. Objective 1 Total objective Objective 2 20 Journal of Advanced Transportation 10 20 30 40 50 60 dynamic priority threshold (c) Figure 13: Sensitivity analysis on the threshold of dynamic level adjustment. (a) Total objective value under diferent threshold. (b) Objective 1 and objective 2 value under diferent thresholds. (c) Objective 3 value diferent thresholds. Table 13: Statistics of the delay at the destination (unit: minute). Treshold Statistics 10 20 30 40 50 60 Summary 15205 14053 13933 14919 13711 14575 Average 233.9 216.2 214.4 229.5 210.9 224.2 Max 379 350 380 384 336 378 Min 121 90 90 90 90 90 Standard deviation 47.9 51.9 56.5 58.5 57.6 56.9 signifcantly reduced by 40.9% and the weighted dwell time the train priority and delay time. Te result shows that is reduced by 2.5%, while the objective value is decreased by there is a synergy between the delay time and train priority, 18.8%. (2) Compared with the efciency-oriented objective where the threshold to upgrade the evolutionary train only considering total delay, the combined objective fuc- priority plays an important role. Hence, our work proves tuates as the threshold increases. Tis proves that there are that it is very meaningful and applicable to consider the synergies between efciency and equity, which is signifcant evolutionary train priority. Moreover, the algorithm takes in tradeof equity and efciency. (3) From the individual 43 s for the 4-hour computational result in a real-world perspective of a low-priority train, a lower threshold de- railway network with 62 stations and 254.9 km in length, which meets the requirements for rescheduling in the real creases the delay time at the destination. From the system perspective, the train delay time increases as the threshold world. Our work extends the rescheduling approach increases to some extent. Te threshold is important to considering both equity and efciency and provides aux- tradeof equity and efciency, and a threshold of 60 minutes iliary operation support for the dispatcher’s operation is suggested for timetable rescheduling. rescheduling. A future line of research to be considered in the next studies is to quantify the model in real-time rescheduling 7. Conclusion and Future Work with delay time estimation. First, the efciency of the al- To resolve the train timetable rescheduling problem with gorithm can also be improved further. For example, as is heterogeneous train priority considering both efciency and a population-based optimization strategy, the initial pop- equity in freight railway, this paper proposes an optimization ulation of GA can greatly improve the quality of the so- model for freight railway rescheduling and solves it with lution. Heuristics in generating the initial population with a novel GA solution (i.e., ITGA). We propose the dynamic chromosomes can be proposed instead of random gener- train priority based on the delay time and static train priority. ated within the up and low bound in this paper. Second, Based on the abovementioned content, the proposed model a simulation approach could be used to evaluate the po- utilizes integrated recovery strategies of retime, reorder, and tential delay in the dynamic rescheduling process. More- retrack in terms of adjusting dwell time, changing the meet- over, another possibility is to combine rescheduling pass plan, and fexible track use control in a complex railway strategies (e.g., route changes and speed profle) in big network containing single-track, double-track, and perturbations such as disruptions caused by a trafc ac- quadruple-track sections. Te model investigates railways cident or bad weather. restricted to network characteristics, operational restraints, limited capacities, and resource availability. To solve the Data Availability rescheduling problem efciently, a heuristic algorithm is proposed by integrated GA, using train order for a chromo- Te data that support the fndings of this study are openly some coding scheme to avoid spatiotemporal confict. available in the 2020 RAS Problem Solving Competition at Based on the implementation in the Netherlands’ real- https://connect.informs.org/railway-applications/new- world case, this study investigates the relationship between item3/problem-solving-competition681/new-item3867. Objective 3 Journal of Advanced Transportation 21 rescheduling,” Transportation Research Part B: Methodolog- Disclosure ical, vol. 63, pp. 15–37, 2014. [12] A. Ceder and S. Hassold, “Applied analysis for improving rail- Te authors presented their results for the competition and network operations,” Journal of Rail Transport Planning and won the frst prize. Management, vol. 5, no. 2, pp. 50–63, 2015. [13] E. Reynolds and S. J. Maher, “A data-driven, variable-speed Conflicts of Interest model for the train timetable rescheduling problem,” Com- puters and Operations Research, vol. 142, Article ID 105719, Te authors declare that there are no conficts of interest regarding the publication of this paper. [14] J. Chung, S. Oh, and I. Choi, “A hybrid genetic algorithm for train sequencing in the Korean railway,” Omega, vol. 37, no. 3, Acknowledgments pp. 555–565, 2009. [15] L. Meng and X. Zhou, “Simultaneous train rerouting and Te authors want to thank the INFORMS for holding the rescheduling on an N-track network: a model reformulation 2020 RAS Problem Solving Competition. Besides, the au- with network-based cumulative fow variables,” Trans- thors appreciate the chair: Jay Baillargeon (U.S. DOT) and portation Research Part B: Methodological, vol. 67, pp. 208– the problem owner: Krishna Jha (Optym) for their answers 234, 2014. to our questions. Tis work was supported by the China [16] J.-F. Cordeau, P. Toth, and D. Vigo, “A survey of optimization Academy of Engineering (Grant no. 2022-PP-06). Besides, models for train routing and scheduling,” Transportation the frst author was supported by the China Scholarship Science, vol. 32, no. 4, pp. 380–404, 1998. Council. [17] L. Kroon, G. Maroti, ´ M. R. Helmrich, M. Vromans, and R. Dekker, “Stochastic improvement of cyclic railway time- tables,” Transportation Research Part B: Methodological, References vol. 42, no. 6, pp. 553–570, 2008. [1] T. Robenek, S. S. Azadeh, Y. Maknoon, M. de Lapparent, and [18] M. Sama, ` C. Meloni, A. D’Ariano, and F. Corman, “A multi- M. Bierlaire, “Train timetable design under elastic passenger criteria decision support methodology for real-time train demand,” Transportation Research Part B: Methodological, scheduling,” Journal of Rail Transport Planning and Man- vol. 111, pp. 19–38, 2018. agement, vol. 5, no. 3, pp. 146–162, 2015. [2] M. Shakibayifar, A. Sheikholeslami, F. Corman, and [19] N. Kumar and A. Mishra, “A multi-objective and dictionary- E. Hassannayebi, “An integrated rescheduling model for based checking for efcient rescheduling trains,” Alexandria minimizing train delays in the case of line blockage,” Oper- Engineering Journal, vol. 60, no. 3, pp. 3233–3241, 2021. ational Research, vol. 20, no. 1, pp. 59–87, 2017. [20] M. Zhou, H. Dong, X. Liu, H. Zhang, and F. Y. Wang, [3] N. Kumar and A. Mishra, “An efcient method of disturbance “Integrated timetable rescheduling for multidispatching analysis and train rescheduling using MWDLNN and sections of high-speed railways during large-scale disrup- BMW-SSO algorithms,” Soft Computing, vol. 25, no. 18, tions,” IEEE Transactions on Computational Social Systems, pp. 12031–12041, 2021. vol. 9, no. 2, pp. 366–375, 2022. [4] F. Corman, A. D’Ariano, I. A. Hansen, and D. Pacciarelli, [21] G. Cavone, M. Dotoli, N. Epicoco, and C. Seatzu, “A decision “Optimal multi-class rescheduling of railway trafc,” Journal making procedure for robust train rescheduling based on of Rail Transport Planning and Management, vol. 1, no. 1, mixed integer linear programming and Data Envelopment pp. 14–24, 2011. Analysis,” Applied Mathematical Modelling, vol. 52, [5] P. Xu, D. Zhang, J. Guo, D. Liu, and H. Peng, “Integrated train pp. 255–273, 2017. rescheduling and rerouting during multidisturbances under [22] L. Meng and X. Zhou, “Robust single-track train dispatching a quasi-moving block system,” Journal of Advanced Trans- model under a dynamic and stochastic environment: a sce- portation, vol. 2021, Article ID 6652531, 15 pages, 2021. nario-based rolling horizon solution approach,” Trans- [6] S. Dundar ¨ and I. S¸ahin, “Train re-scheduling with genetic portation Research Part B: Methodological, vol. 45, no. 7, algorithms and artifcial neural networks for single-track pp. 1080–1102, 2011. railways,” Transportation Research Part C: Emerging Tech- [23] R. Larsen, M. Pranzo, A. D’Ariano, F. Corman, and nologies, vol. 27, pp. 1–15, 2013. D. Pacciarelli, “Susceptibility of optimal train schedules to [7] A. Higgins, E. Kozan, and L. Ferreira, “Optimal scheduling of stochastic disturbances of process times,” Flexible Services and trains on a single line track,” Transportation Research Part B: Manufacturing Journal, vol. 26, no. 4, pp. 466–489, 2013. Methodological, vol. 30, no. 2, pp. 147–161, 1996. [24] S. B. Layeb, A. Jaoua, A. Jbira, and Y. Makhlouf, “A [8] D. Banerjee and K. Smilowitz, “Incorporating equity into the simulation-optimization approach for scheduling in sto- school bus scheduling problem,” Transportation Research Part chastic freight transportation,” Computers and Industrial E: Logistics and Transportation Review, vol. 131, pp. 228–246, Engineering, vol. 126, pp. 99–110, 2018. [25] S. Q. Liu and E. Kozan, “Scheduling trains with priorities: [9] I. Sahin, “Railway trafc control and train scheduling based on a No-wait blocking parallel-machine job-shop scheduling inter-train confict management,” Transportation Research model,” Transportation Science, vol. 45, no. 2, pp. 175–198, Part B: Methodological, vol. 33, no. 7, pp. 511–534, 1999. [10] B. Taslimi, F. Babaie Sarijaloo, H. Liu, and P. M. Pardalos, “A [26] J. Huo, J. Wu, L. Kang, and B. Wang, “Railway timetable novel mixed integer programming model for freight train rescheduling based on priority and train order entropy,” travel time estimation,” European Journal of Operational Research, vol. 300, no. 2, pp. 676–688, 2022. Technical Papers, vol. 30, 2016. [27] P. Shang, R. Li, Z. Liu, L. Yang, and Y. Wang, “Equity-oriented [11] V. Cacchiani, D. Huisman, M. Kidd et al., “An overview of recovery models and algorithms for real-time railway skip-stopping schedule optimization in an oversaturated 22 Journal of Advanced Transportation urban rail transit network,” Transportation Research Part C: Emerging Technologies, vol. 89, pp. 321–343, 2018. [28] L. Wang, C. Luo, and J. Cai, “A variable interval rescheduling strategy for dynamic fexible job shop scheduling problem by improved genetic algorithm,” Journal of Advanced Trans- portation, vol. 2017, Article ID 1527858, 12 pages, 2017. [29] H. Zhang, S. Ni, and Y. Gao, “Train scheduling optimization for an urban rail transit line: a simulated-annealing algorithm using a large neighborhood search metaheuristic,” Journal of Advanced Transportation, vol. 2022, Article ID 9604362, 17 pages, 2022. [30] S. Fidanova, O. Roeva, and M. Ganzha, “Ant colony opti- mization algorithm for fuzzy transport modelling,” in Pro- ceedings of the 2020 Federated Conference on Computer Science and Information Systems, pp. 237–240, Sofa, Bulgaria, September 2020. [31] X. Meng, L. Jia, and Y. Qin, “Train timetable optimizing and rescheduling based on improved particle swarm algorithm,” Transportation Research Record: Journal of the Transportation Research Board, vol. 2197, no. 1, pp. 71–79, 2010. [32] F. Corman, A. D’Ariano, D. Pacciarelli, and M. Pranzo, “A tabu search algorithm for rerouting trains during rail oper- ations,” Transportation Research Part B: Methodological, vol. 44, no. 1, pp. 175–192, 2010. [33] J. To¨rnquist Krasemann, “Design of an efective algorithm for fast response to the re-scheduling of railway trafc during disturbances,” Transportation Research Part C: Emerging Technologies, vol. 20, no. 1, pp. 62–78, 2012. [34] L. Kang, J. Wu, H. Sun, X. Zhu, and B. Wang, “A practical model for last train rescheduling with train delay in urban railway transit networks,” Omega, vol. 50, pp. 29–42, 2015. [35] E. Altazin, S. Dauzere-P ` er ´ es, ` F. Ramond, and S. Trefond, ´ “A multi-objective optimization-simulation approach for real time rescheduling in dense railway systems,” European Journal of Operational Research, vol. 286, no. 2, pp. 662–672,

Journal

Journal of Advanced Transportation – Hindawi Publishing Corporation

Published: May 25, 2023

Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A Rescheduling Approach for Freight Railway considering Equity and Efficiency by an Integrated Genetic Algorithm

A Rescheduling Approach for Freight Railway considering Equity and Efficiency by an Integrated Genetic Algorithm

Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A Rescheduling Approach for Freight Railway considering Equity and Efficiency by an Integrated Genetic Algorithm

A Rescheduling Approach for Freight Railway considering Equity and Efficiency by an Integrated Genetic Algorithm

References (35)

Abstract

Journal

Recommended Articles

There are no references for this article.

Our policy towards the use of cookies