# A Branch and Bound Algorithm and Iterative Reordering Strategies for Inserting Additional Trains in Real Time: A Case Study in Germany

Authors: Yuyan Tan; Zhibin Jiang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

With the aim of supporting the process of adapting railway infrastructure and future traffic needs, we have developed a method to insert additional trains efficiently to an existing timetable without introducing large consecutive delays to scheduled trains. In this work, the problem is characterized as a job-shop scheduling problem. In order to meet the limited time requirement and minimize deviations to the existing timetable, the modification that consists of retiming or reordering trains is implemented if and only if it potentially leads to a better solution. With these issues in mind, the problem of adding train paths is decomposed into two subproblems. One is finding the optimal insertion for a fixed order timetable and the other is reordering trains. The two subproblems are solved iteratively until no improvement is possible within a time limit of computation. An innovative branch and bound algorithm and iterative reordering strategy are proposed to solve this problem in real time. Unoccupied capacities are utilized as primary resources for additional trains and the transfer connections for passengers can be guaranteed in the new timetable. From numerical investigations, the proposed framework and associated techniques are tested and shown to be effective.


---

## Body

## 1. Introduction and Literature Review

This paper will give an account of how to reconstruct an existing train schedule by inserting additional train services. This timetable-based extra train paths inserting (TETPI) problem is an integration of railway dispatching and scheduling. Train dispatcher both modifies the given timetable to manage delay in the running operation and establishes schedules for extra trains.


### 1.1. Background

The primary motivation of this research occurs as a result of the following application areas.(1)  The Demands of Extra Trains for Train Operating Companies in European Railways. Pachl [1] describes the open access networks in European railways. In the train paths management, the train operating companies order train paths from the infrastructure operator, and then the infrastructure operator allocates these train paths on its lines in accordance with the orders of the train operating companies. From the view of scheduling, there is a distinction between regular trains and extra trains. Regular trains are all trains that have a schedule in the yearly timetable. Train paths for regular trains have to be ordered several months before the yearly timetable comes into effect. Extra trains are trains that have no schedule in the yearly timetable. Train paths for extra trains can be ordered at any time. Thus, when establishing the yearly timetable, a lot of traffic is not yet known. It contains only a part of the real traffic, mainly passenger trains and freight trains that run on a regular basis. Nowadays, in order to meet the needs of the shippers, an increasing share of freight trains runs as extra trains. Train paths for many freight trains, which do often not even appear in the scheduling systems, are ordered in a very short time in advance, sometimes just a few hours [1]. For this reason, the train operating companies have to rise to the challenge that establishing conflict-free train paths for these trains in a short time and keeping the disruptions to regular trains minimised or similarly within acceptable levels.(2)  A key Concept for Noncyclic Timetable in China Railway System. The cyclic timetable has been widely adopted on high-speed railways because of its obvious advantages in transport marketing and train operation. However, it is not wise to apply the complete cyclic timetable model on Chinese railway due to its own features. Recently, researchers have shown an increased interest in an incomplete cyclic timetable model, an integration model of cyclic and noncyclic timetables, on China high-speed railways, such as [2, 3]. When constructing incomplete cyclic timetables, the trains of short (or medium long) distances and high frequencies are scheduled as cyclic trains, and then trains of long distances or low frequencies need to be inserted into the planned cyclic timetable as extra acyclic trains. Nowadays, the cyclic timetable models have been well developed, and the time-based train insertion technique without breaking the original cyclic structure is still a significant demand for research.In this paper, the TETPI problem via a job shop scheduling approach is considered. More specifically the purpose of the TETPI problem in this paper is to establish a new conflict-free timetable for additional trains in a short time, guarantee the necessary transfer connections between passenger trains, and aim to minimize the delays incurred by additional trains, where delay is defined as deviation of actual service schedules and the initial schedules.In order to meet the limited time requirement and minimize deviations to the existing timetable, in practice it is not necessary to take all of the scheduled trains into consideration. The modification which usually consists of retiming or reordering trains is implemented if and only if it potentially leads to a better solution. With these issues in mind the following process is possible for solving the TETPI problem.Phase 1 (FX strategy).
Fix all previously scheduled services.Phase 2 (RM strategy).
The scheduled services can be retimed, but the relative order between trains is kept.Phase 3 (RO strategy).
The scheduled services can be reordered.Note that the TETPI process does not necessarily have to be applied in the order shown above since not every phase is required. For instance when track infrastructure utilisation is light then Phase1 would be applied. When track capacity is already heavily utilised, additional trains can only be inserted by disrupting existing services. Phase 1 will be inappropriate and Phase 2 should be applied. In both Phase 1 and Phase 2, additional train services may be added using a constructive algorithm. In Phase 3, a decision is taken in this phase to restate a priority order between trains, competing for the same single track section, in order to get a better solution.Based on the above analysis, the contributions of this paper are as follows.(1)
An iterative procedure for inserting extra trains to an existing timetable is defined in this paper. The TETPI problem is decomposed into two subproblems; one is finding the optimal insertion for a fixed order timetable (Phase1 and Phase 2) and the other is reordering trains (Phase 3). The two subproblems are solved iteratively until no improvement is possible within a time limit of computation.(2)
An innovative branch and bound search algorithm is introduced to solve the first subproblem. In this step, the additional trains mainly utilize the unoccupied capacities to be inserted in order to minimise the deviations to existing trains.(3)
The order between trains is restated based on dispatching rules to get a better solution. Note that only the change between train services which occur in thecritical path is propitious to decrease the makespan (i.e., objective in the model) of the alternative graph.


### 1.2. Review of the Related Literature

#### 1.2.1. Literature Review on Scheduling and Rescheduling Problem

The TETPI problem is related to a variety of topics in the literature. The first and foremost is rail timetable optimization. Recently, train scheduling and rescheduling problems have a great deal of attention. Corman et al. [4], for example, present a list of foremost papers published on this area between 1999 and 2007. There are varied models for formulating train operation problem. Since then we have observed the following papers based ongraph theory to solve these problems efficiently: D’Ariano et al. [5] propose a fixed speed model and variable speed model to find a conflict-free timetable in real time after train operations are perturbed. D’Ariano et al. [6] consider the problem of managing disturbance in real time. In this paper, a real-time traffic management system called Railway traffic Optimization by means of alternative graph (ROMA) is introduced. They model the railway traffic optimization based no-store alternative graph, including constraints of rolling stock and passenger connections. This problem is decomposed into two subproblems, one is reordering which is solved by branch and bound algorithm and the other is rerouting which is solved by a local search algorithm. The two subproblems are then solved iteratively. Cacchiani et al. [7] deal with the problem of timetabling noncyclic trains. A mixed-integer programming model (MIP) is proposed to look for the maximum-weight path in a comparability graph. Schachtebeck [8] considers the delay management in public transportation. Based on graph theory he uses integer programming model (IP) formulation and suggests various heuristic solution approaches to solve large-scale real-world instances to optimality. In addition, papers such as [9–13] also present innovative models which are of certain reference value in the field of railway operation optimization.Furthermore, there are indications that some of the previous models and techniques in job shop scheduling could be modified and adapted to solve the TETPI problem. For instance, Kis and Hertz [14] give for the classical job shop a polyhedral description of the feasible job insertions and use it to derive a lower bound for the minimum makespan job insertion problem. Gröflin et al. investigate [15, 16] insertion problems in a general disjunctive scheduling framework capturing a variety of job shop scheduling problems and inserting types. They propose a short cycle property for job insertion problem. A polyhedral description of all the feasible job insertions is derived to find the lower and upper bound for the minimum makespan.


#### 1.2.2. Literature Review on Problem of Adding Train Paths

Although the adding extra train paths technology is very important, there has been few direct related discussion about adding paths problem. The only papers to our knowledge are presented in Table1 which summarizes the studies, like ours, dealing with inserting passenger or freight trains into an exiting timetable.Table 1
Characteristics of adding paths problem and solution approaches.
Publication
Background
Model
Objective
Solution
Real  time
Connection
Problem size evaluated for
[17]
(F)
ILP
Maximizes the number of additional trains and minimize the violations to the ideal insertion
(HA)
No
No
679/202/24-48-96, 520/202/24-48-96, 0/202/188-338-554-64
[18]
(P)
MIP
Minimizes the total weighted time window violations and the makespan
(CA), (HA)
No
No
6/3/1-5, 6/5/1-5, 10/10/1-5, 24/10/1-5, 15/5/1-5, 54/30/1-5, 20/20/1-5, 20/12/1-5, 20/24/1-5
[19]
(F/P)
CSM
Minimizes the average traversal time of new train
(DP), (PR)
No
No
81/65/20
[20]
(F/P)
LPM,  CSM
Support railway planners by computing a set of Pareto optimal solutions with respect to travel time and expected delay to additional trains
(SP)
No
No
—/—/1
Our paper
(F/P)
MIP
Minimizes consecutive delay to existing timetable
(BB), (AG),(SP), (PR)
Yes
Yes
36/60/1-15
(i) Background: passenger trains insertion (P); freight trains insertion (F).
(ii) Model: mixed integer programming (MIP); computer simulation model (CSM); integer linear programming (ILP); linear regression model (LPM).
(iii) Solution: constructive algorithm (CA); alternative graphs (AG); shortest path algorithm (SP); branch-and-bound (BB); heuristics algorithm (HA); dynamic programming (DP); local search (LS); practical rules (PR).
(iv) Problem size evaluated for number of initial trains/number of stations or block sections/number of additional trains. —: between double / means missing the information.References [17, 19] solve the problem of inserting freights trains with assumption that all of the initial trains can not be changed. In [17], the additional trains are inserted with predefined ideal departure/arrival time and minimum stopping time at each station that must visit; meanwhile, alternative routes are taken into account. In [19], additional trains are inserted at a randomly fixed time belonging to the time window at each iteration and priority rule is predefined for each overtaking and meeting. Reference [20] computes a set of Pareto optimal train schedules with respect to risk and travel time. Their method aims to find robust train paths in the sense that the additional train has a low risk of delay upon arrival at its final station and supporting railway planners by computing a set of recommended train paths for a given train request.Our study is different from the previous ones in two things. Firstly, we guarantee the transfer connections during insertion. Secondly, we solve the problem of adding train paths in real time. The difficulty in this paper is that the timetable scheduling and rescheduling are considered as two complex and time-consuming problems and usually researched independently. However, as introduced in Section1.1, the problem of adding train paths, an integration of railway scheduling and rescheduling problem, is often required to be solved within a short time in Germany.The format of the paper in the following sections is as follows. The model and algorithms for the TETPI problem are described in Section2. The details of a novel bound search algorithm and an iterative reordering structure are presented to get optimal decision. Numerical investigations and case studies then demonstrate in Section 3 the quality of solutions that are obtained from the proposed approaches. In Section 4, the outcomes and the significance of the paper are summarized and the future research directions are given.


## 1.1. Background

The primary motivation of this research occurs as a result of the following application areas.(1)  The Demands of Extra Trains for Train Operating Companies in European Railways. Pachl [1] describes the open access networks in European railways. In the train paths management, the train operating companies order train paths from the infrastructure operator, and then the infrastructure operator allocates these train paths on its lines in accordance with the orders of the train operating companies. From the view of scheduling, there is a distinction between regular trains and extra trains. Regular trains are all trains that have a schedule in the yearly timetable. Train paths for regular trains have to be ordered several months before the yearly timetable comes into effect. Extra trains are trains that have no schedule in the yearly timetable. Train paths for extra trains can be ordered at any time. Thus, when establishing the yearly timetable, a lot of traffic is not yet known. It contains only a part of the real traffic, mainly passenger trains and freight trains that run on a regular basis. Nowadays, in order to meet the needs of the shippers, an increasing share of freight trains runs as extra trains. Train paths for many freight trains, which do often not even appear in the scheduling systems, are ordered in a very short time in advance, sometimes just a few hours [1]. For this reason, the train operating companies have to rise to the challenge that establishing conflict-free train paths for these trains in a short time and keeping the disruptions to regular trains minimised or similarly within acceptable levels.(2)  A key Concept for Noncyclic Timetable in China Railway System. The cyclic timetable has been widely adopted on high-speed railways because of its obvious advantages in transport marketing and train operation. However, it is not wise to apply the complete cyclic timetable model on Chinese railway due to its own features. Recently, researchers have shown an increased interest in an incomplete cyclic timetable model, an integration model of cyclic and noncyclic timetables, on China high-speed railways, such as [2, 3]. When constructing incomplete cyclic timetables, the trains of short (or medium long) distances and high frequencies are scheduled as cyclic trains, and then trains of long distances or low frequencies need to be inserted into the planned cyclic timetable as extra acyclic trains. Nowadays, the cyclic timetable models have been well developed, and the time-based train insertion technique without breaking the original cyclic structure is still a significant demand for research.In this paper, the TETPI problem via a job shop scheduling approach is considered. More specifically the purpose of the TETPI problem in this paper is to establish a new conflict-free timetable for additional trains in a short time, guarantee the necessary transfer connections between passenger trains, and aim to minimize the delays incurred by additional trains, where delay is defined as deviation of actual service schedules and the initial schedules.In order to meet the limited time requirement and minimize deviations to the existing timetable, in practice it is not necessary to take all of the scheduled trains into consideration. The modification which usually consists of retiming or reordering trains is implemented if and only if it potentially leads to a better solution. With these issues in mind the following process is possible for solving the TETPI problem.Phase 1 (FX strategy).
Fix all previously scheduled services.Phase 2 (RM strategy).
The scheduled services can be retimed, but the relative order between trains is kept.Phase 3 (RO strategy).
The scheduled services can be reordered.Note that the TETPI process does not necessarily have to be applied in the order shown above since not every phase is required. For instance when track infrastructure utilisation is light then Phase1 would be applied. When track capacity is already heavily utilised, additional trains can only be inserted by disrupting existing services. Phase 1 will be inappropriate and Phase 2 should be applied. In both Phase 1 and Phase 2, additional train services may be added using a constructive algorithm. In Phase 3, a decision is taken in this phase to restate a priority order between trains, competing for the same single track section, in order to get a better solution.Based on the above analysis, the contributions of this paper are as follows.(1)
An iterative procedure for inserting extra trains to an existing timetable is defined in this paper. The TETPI problem is decomposed into two subproblems; one is finding the optimal insertion for a fixed order timetable (Phase1 and Phase 2) and the other is reordering trains (Phase 3). The two subproblems are solved iteratively until no improvement is possible within a time limit of computation.(2)
An innovative branch and bound search algorithm is introduced to solve the first subproblem. In this step, the additional trains mainly utilize the unoccupied capacities to be inserted in order to minimise the deviations to existing trains.(3)
The order between trains is restated based on dispatching rules to get a better solution. Note that only the change between train services which occur in thecritical path is propitious to decrease the makespan (i.e., objective in the model) of the alternative graph.


## 1.2. Review of the Related Literature

### 1.2.1. Literature Review on Scheduling and Rescheduling Problem

The TETPI problem is related to a variety of topics in the literature. The first and foremost is rail timetable optimization. Recently, train scheduling and rescheduling problems have a great deal of attention. Corman et al. [4], for example, present a list of foremost papers published on this area between 1999 and 2007. There are varied models for formulating train operation problem. Since then we have observed the following papers based ongraph theory to solve these problems efficiently: D’Ariano et al. [5] propose a fixed speed model and variable speed model to find a conflict-free timetable in real time after train operations are perturbed. D’Ariano et al. [6] consider the problem of managing disturbance in real time. In this paper, a real-time traffic management system called Railway traffic Optimization by means of alternative graph (ROMA) is introduced. They model the railway traffic optimization based no-store alternative graph, including constraints of rolling stock and passenger connections. This problem is decomposed into two subproblems, one is reordering which is solved by branch and bound algorithm and the other is rerouting which is solved by a local search algorithm. The two subproblems are then solved iteratively. Cacchiani et al. [7] deal with the problem of timetabling noncyclic trains. A mixed-integer programming model (MIP) is proposed to look for the maximum-weight path in a comparability graph. Schachtebeck [8] considers the delay management in public transportation. Based on graph theory he uses integer programming model (IP) formulation and suggests various heuristic solution approaches to solve large-scale real-world instances to optimality. In addition, papers such as [9–13] also present innovative models which are of certain reference value in the field of railway operation optimization.Furthermore, there are indications that some of the previous models and techniques in job shop scheduling could be modified and adapted to solve the TETPI problem. For instance, Kis and Hertz [14] give for the classical job shop a polyhedral description of the feasible job insertions and use it to derive a lower bound for the minimum makespan job insertion problem. Gröflin et al. investigate [15, 16] insertion problems in a general disjunctive scheduling framework capturing a variety of job shop scheduling problems and inserting types. They propose a short cycle property for job insertion problem. A polyhedral description of all the feasible job insertions is derived to find the lower and upper bound for the minimum makespan.


### 1.2.2. Literature Review on Problem of Adding Train Paths

Although the adding extra train paths technology is very important, there has been few direct related discussion about adding paths problem. The only papers to our knowledge are presented in Table1 which summarizes the studies, like ours, dealing with inserting passenger or freight trains into an exiting timetable.Table 1
Characteristics of adding paths problem and solution approaches.
Publication
Background
Model
Objective
Solution
Real  time
Connection
Problem size evaluated for
[17]
(F)
ILP
Maximizes the number of additional trains and minimize the violations to the ideal insertion
(HA)
No
No
679/202/24-48-96, 520/202/24-48-96, 0/202/188-338-554-64
[18]
(P)
MIP
Minimizes the total weighted time window violations and the makespan
(CA), (HA)
No
No
6/3/1-5, 6/5/1-5, 10/10/1-5, 24/10/1-5, 15/5/1-5, 54/30/1-5, 20/20/1-5, 20/12/1-5, 20/24/1-5
[19]
(F/P)
CSM
Minimizes the average traversal time of new train
(DP), (PR)
No
No
81/65/20
[20]
(F/P)
LPM,  CSM
Support railway planners by computing a set of Pareto optimal solutions with respect to travel time and expected delay to additional trains
(SP)
No
No
—/—/1
Our paper
(F/P)
MIP
Minimizes consecutive delay to existing timetable
(BB), (AG),(SP), (PR)
Yes
Yes
36/60/1-15
(i) Background: passenger trains insertion (P); freight trains insertion (F).
(ii) Model: mixed integer programming (MIP); computer simulation model (CSM); integer linear programming (ILP); linear regression model (LPM).
(iii) Solution: constructive algorithm (CA); alternative graphs (AG); shortest path algorithm (SP); branch-and-bound (BB); heuristics algorithm (HA); dynamic programming (DP); local search (LS); practical rules (PR).
(iv) Problem size evaluated for number of initial trains/number of stations or block sections/number of additional trains. —: between double / means missing the information.References [17, 19] solve the problem of inserting freights trains with assumption that all of the initial trains can not be changed. In [17], the additional trains are inserted with predefined ideal departure/arrival time and minimum stopping time at each station that must visit; meanwhile, alternative routes are taken into account. In [19], additional trains are inserted at a randomly fixed time belonging to the time window at each iteration and priority rule is predefined for each overtaking and meeting. Reference [20] computes a set of Pareto optimal train schedules with respect to risk and travel time. Their method aims to find robust train paths in the sense that the additional train has a low risk of delay upon arrival at its final station and supporting railway planners by computing a set of recommended train paths for a given train request.Our study is different from the previous ones in two things. Firstly, we guarantee the transfer connections during insertion. Secondly, we solve the problem of adding train paths in real time. The difficulty in this paper is that the timetable scheduling and rescheduling are considered as two complex and time-consuming problems and usually researched independently. However, as introduced in Section1.1, the problem of adding train paths, an integration of railway scheduling and rescheduling problem, is often required to be solved within a short time in Germany.The format of the paper in the following sections is as follows. The model and algorithms for the TETPI problem are described in Section2. The details of a novel bound search algorithm and an iterative reordering structure are presented to get optimal decision. Numerical investigations and case studies then demonstrate in Section 3 the quality of solutions that are obtained from the proposed approaches. In Section 4, the outcomes and the significance of the paper are summarized and the future research directions are given.


## 1.2.1. Literature Review on Scheduling and Rescheduling Problem

The TETPI problem is related to a variety of topics in the literature. The first and foremost is rail timetable optimization. Recently, train scheduling and rescheduling problems have a great deal of attention. Corman et al. [4], for example, present a list of foremost papers published on this area between 1999 and 2007. There are varied models for formulating train operation problem. Since then we have observed the following papers based ongraph theory to solve these problems efficiently: D’Ariano et al. [5] propose a fixed speed model and variable speed model to find a conflict-free timetable in real time after train operations are perturbed. D’Ariano et al. [6] consider the problem of managing disturbance in real time. In this paper, a real-time traffic management system called Railway traffic Optimization by means of alternative graph (ROMA) is introduced. They model the railway traffic optimization based no-store alternative graph, including constraints of rolling stock and passenger connections. This problem is decomposed into two subproblems, one is reordering which is solved by branch and bound algorithm and the other is rerouting which is solved by a local search algorithm. The two subproblems are then solved iteratively. Cacchiani et al. [7] deal with the problem of timetabling noncyclic trains. A mixed-integer programming model (MIP) is proposed to look for the maximum-weight path in a comparability graph. Schachtebeck [8] considers the delay management in public transportation. Based on graph theory he uses integer programming model (IP) formulation and suggests various heuristic solution approaches to solve large-scale real-world instances to optimality. In addition, papers such as [9–13] also present innovative models which are of certain reference value in the field of railway operation optimization.Furthermore, there are indications that some of the previous models and techniques in job shop scheduling could be modified and adapted to solve the TETPI problem. For instance, Kis and Hertz [14] give for the classical job shop a polyhedral description of the feasible job insertions and use it to derive a lower bound for the minimum makespan job insertion problem. Gröflin et al. investigate [15, 16] insertion problems in a general disjunctive scheduling framework capturing a variety of job shop scheduling problems and inserting types. They propose a short cycle property for job insertion problem. A polyhedral description of all the feasible job insertions is derived to find the lower and upper bound for the minimum makespan.


## 1.2.2. Literature Review on Problem of Adding Train Paths

Although the adding extra train paths technology is very important, there has been few direct related discussion about adding paths problem. The only papers to our knowledge are presented in Table1 which summarizes the studies, like ours, dealing with inserting passenger or freight trains into an exiting timetable.Table 1
Characteristics of adding paths problem and solution approaches.
Publication
Background
Model
Objective
Solution
Real  time
Connection
Problem size evaluated for
[17]
(F)
ILP
Maximizes the number of additional trains and minimize the violations to the ideal insertion
(HA)
No
No
679/202/24-48-96, 520/202/24-48-96, 0/202/188-338-554-64
[18]
(P)
MIP
Minimizes the total weighted time window violations and the makespan
(CA), (HA)
No
No
6/3/1-5, 6/5/1-5, 10/10/1-5, 24/10/1-5, 15/5/1-5, 54/30/1-5, 20/20/1-5, 20/12/1-5, 20/24/1-5
[19]
(F/P)
CSM
Minimizes the average traversal time of new train
(DP), (PR)
No
No
81/65/20
[20]
(F/P)
LPM,  CSM
Support railway planners by computing a set of Pareto optimal solutions with respect to travel time and expected delay to additional trains
(SP)
No
No
—/—/1
Our paper
(F/P)
MIP
Minimizes consecutive delay to existing timetable
(BB), (AG),(SP), (PR)
Yes
Yes
36/60/1-15
(i) Background: passenger trains insertion (P); freight trains insertion (F).
(ii) Model: mixed integer programming (MIP); computer simulation model (CSM); integer linear programming (ILP); linear regression model (LPM).
(iii) Solution: constructive algorithm (CA); alternative graphs (AG); shortest path algorithm (SP); branch-and-bound (BB); heuristics algorithm (HA); dynamic programming (DP); local search (LS); practical rules (PR).
(iv) Problem size evaluated for number of initial trains/number of stations or block sections/number of additional trains. —: between double / means missing the information.References [17, 19] solve the problem of inserting freights trains with assumption that all of the initial trains can not be changed. In [17], the additional trains are inserted with predefined ideal departure/arrival time and minimum stopping time at each station that must visit; meanwhile, alternative routes are taken into account. In [19], additional trains are inserted at a randomly fixed time belonging to the time window at each iteration and priority rule is predefined for each overtaking and meeting. Reference [20] computes a set of Pareto optimal train schedules with respect to risk and travel time. Their method aims to find robust train paths in the sense that the additional train has a low risk of delay upon arrival at its final station and supporting railway planners by computing a set of recommended train paths for a given train request.Our study is different from the previous ones in two things. Firstly, we guarantee the transfer connections during insertion. Secondly, we solve the problem of adding train paths in real time. The difficulty in this paper is that the timetable scheduling and rescheduling are considered as two complex and time-consuming problems and usually researched independently. However, as introduced in Section1.1, the problem of adding train paths, an integration of railway scheduling and rescheduling problem, is often required to be solved within a short time in Germany.The format of the paper in the following sections is as follows. The model and algorithms for the TETPI problem are described in Section2. The details of a novel bound search algorithm and an iterative reordering structure are presented to get optimal decision. Numerical investigations and case studies then demonstrate in Section 3 the quality of solutions that are obtained from the proposed approaches. In Section 4, the outcomes and the significance of the paper are summarized and the future research directions are given.


## 2. Model and Algorithms for the TETPI Problem

The job shop scheduling models with blocking and no-store constraints have been used by many authors to formulate the problem of scheduling train movements in railway networks. With this model the sequence of block sections traversed by a train is viewed as a set of machines in a job shop problem, where trains correspond to jobs and the usage of a block section by a train is called an operation.


### 2.1. Basic Railway Scheduling Model

For a basic railway scheduling problem, its corresponding alternative graph model is usually defined as a tripleG=(V,A,E), where nodes set V refers to a finite set of nodes, which correspond to operations. A is a set of direct conjunctive arcs modeling a precedence relation between two consecutive operations. E is a set of pairs ofalternative arcs representing all the potential permutations of trains in common sections.In Figure1(a), operations i and j represent trains Ta and Tb entering the same section s. σ(i) and σ(j) are referred to the subsequent operations of i and j, respectively. Conjunctive arcs are depicted with solid arrows, which are weighted with running times pi and pj of the associated operations i and j, respectively. A conjunctive arc restricts the starting time for an operation with respect to the starting of its predecessor operation; that is,(1)tσi≥ti+pi,tσj≥tj+pj.Figure 1
Two train operations to be processed on the same section.In a fixed block safety system, each block section can host at most one train at a time; otherwise, some potential conflicts occur whenever two or more trains require the same block section. Therefore, after processing, every train has to wait on the current section and blocks it until the subsequent section becomes available, thus preventing other trains from entering the same section at the same time. This constraint is formulated by a pair of alternative arcs which defines different processing order for every two trains in the common section. A pair of alternative arcsσj,i,σi,j are represented with dashed lines in Figure 1(a). If σj,i is selected, Tb precedes Ta. Conversely, if σi,j is selected, Ta precedes Tb. The conflict between Ta and Tb must be solved choosing exactly one of the two arcs. In practice, an additional safety margin E, referred to in this paper assetup time, is introduced to every alternative arc. It is a permutation based constant. Then the alternative arcs can be formulated as follows:(2)tσi≥tj+pj+Ejiortσj≥ti+pi+Eij.However, for fast trains, the model is slightly different. Note that a fast train in a fixed safety system is only allowed to enter a block section if the next two block sections are not occupied by other trains. As shown in Figure1(b), the corresponding pair of alternative arcs lead to σi,j,σj,φi, where φi and φj are the predecessor operations of faster operation i and slower operation j, respectively [21]. This can be seen as a multiprocessor job scheduling problem, where operations have to be processed simultaneously on a set of dedicated machines instead of a single machine.


### 2.2. Model for the TETPI Problem

In this section, the TETPI problem is formulated by means of an alternative graph model. Combining the description of the basic scheduling model and the features of inserting problem, the conjunctive arcsA and alternative arcs E for the TETPI problem are defined as follows:(i)
Conjunctive arcs set A=AO∪AN is composed of original conjunctive arcs set AO, which belongs to existing trains, and new conjunctive arcs set AN, which belongs to additional trains. A is fixed when train routes are defined.(ii)
Alternative arcs set E=EO∪EN, where EO represents permutation of original trains and predefined sequence between additional trains and EN represents all of the possible insertions for new trains set N. In the TETPI problem, even though EO is settled, it is still a set of variables when some trains need to be reordered, and then selection of EN depends on the choice of EO.For example, an alternative graph for a part of railway lines is presented in Figure2. It contains 10 block sections numbered from m1 to m10. Two existing trains labeled Ta and Tb are using this part of tracks. The routes of trains Ta and Tb, respectively, are as follows:(3)Ta:m4⟶m5⟶m3⟶m6⟶m7⟶m10Tb:m1⟶m2⟶m3⟶m6⟶m7⟶m10.Figure 2
An alternative graph for the TETPI problem.One additional train denotedTn with the route(4)Tn:m4⟶m5⟶m8⟶m9⟶m7⟶m10needs to be inserted. Let σ and τ be dummy start and finish operations, having to be performed before and after all operations, respectively. For the sake of clarity, the weights of arcs which represent minimum running time and dwell time of the associated operations are not showed.In this alternative graph,A is represented with solid arrows, while EO and EN are depicted with dash-dotted arrows and dashed arrows, respectively. To differ in that a precedence constraint in A always must hold, while an arc in E must be selected if its corresponding alternative arc does not hold. Aselection in graph G is an arbitrary subset of alternative arcs; that is, S⊆E. If for every alternative pair at least one arc is selected, we called that S iscomplete in G. S is anacyclic selection if the graph GV,A∪S, denoted by G(S), contains no positive length cycles. Finally, S is a feasible selection if it is complete and acyclic. In fact, a positive length cycle causes a deadlock in a graph, which is infeasible. So the TETPI problem is equivalent to the following problem: given a set of trains T and a selection SO that is feasible for all trains of T-N, where N is a set of additional trains, then find a selection SN of alternative arcs incident to N such that among all feasible selections selection S=SO∪SN minimizes the length of the longest path π from σ to τ in graph G(S).Furthermore, D’Ariano et al. [6] use an innovative way to represent the maximum consecutive delay with the makespan of the associated alternative graph by introducing the weights of entry time and negative exit time on the start and end operations, respectively. In this way, the objective for the TETPI model is changed into minimizing consecutive delay.In practice, extra freight trains may be set flexibly when they will enter the planned system, but at most of time passenger trains have to be set at predefined time or meet transfer requirements with existing trains, and moreover some trains may already be partly within the system at the start of the schedule. In such cases, strategies like retiming and reordering existing trains are unavoidable which may cause scheduled connections to be dismissed. In order to guarantee some scheduled connections or orders, the corresponding alternative arcs inEO should not be changed. Meanwhile, for the purpose of new connections between additional trains and scheduled trains, the corresponding alternative arcs in EN should be preselected. A set of these preselected and preforbidden alternative arcs are referred to Q and F, respectively, in this paper.Then the basic constrained TETPI problem based on alternative graph can be formulated as the model (M1):(5)(M1):min⁡⁡tτ-tσtj-ti≥pi∀i,j∈V,(i,j)∈Atj-ti≥pi+Eijortk-th≥ph+Ehk∀i,j,k,h∈V,i,j,h,k∈Etj-ti≥pi+Eij∀i,j∈V,(i,j)∈Qtj-ti≤pi+Eij∀i,j∈V,i,j∈F.Besides the above constraints, the alternative graph allows formulation of situations more general that the ones we have mentioned. For example, Strotmann [21] introduces additional constraints modeled in terms of the alternative graph model, including connection constraints between trains, out-of-service intervals for certain block sections and so on.


### 2.3. Algorithms for the TETPI Problem

In our definition, the TETPI problem is asked to develop a new conflict-free plan compatible with the strict time limit for some real-time traffic situations and modify the scheduled requests as little as possible, including reordering as few as possible. In order to meet these minimum deviation and limited time requirements, it is not necessary to take all the scheduled arcsEO into consideration, because only the change of alternative arcs occurring in thecritical path is propitious to decrease the makespan of alternative graph. In this section, the TETPI problem is decomposed into two subproblems:(1)
find the optimal insertion for a fixed order timetable: in this phase, the additional services mainly utilize unoccupied capacities to process. By this means, it can not only minimize the deviation of scheduled timetable, but also keep the existing transfer plans to the fullest extent;(2)
give a solution to subproblem (1) and define new sequence ofEO potentially leading to better schedules. In this phase, unavoidable permutation changes are introduced in order to set more additional restricted services without leading to large deviation or consecutive delay to the existing timetable.These two subproblems are then iteratively solved until no improvement is possible within a time limit of computation. The architecture of this inserting procedure is represented in Figure3.Figure 3
Architecture of insertion.


#### 2.3.1. Branch and Bound Search Algorithm with Fixed Permutation

Let the lengthπS(σ,τ) be the critical path of the graph G(S). This value can be reduced either by modifying the location of the new trains SN or reordering the original train sequencing SO. In this subsection, we start from G(V,A∪SO) with fixed permutation of original trains SO and then derive a polyhedral description of all feasible insertions SN for the TETPI problem.In order to formulate this problem, we will use the following definitions and notions. For any directed arce=v,w, te=v is the tail node of arc e and he=w is the head node. Given an existing timetable GV,A∪SO, insert all operations of train set N into this schedule simultaneously. A family of alternative arc pairs EN which are incident with N are composed of two distinct alternative edge sets EN- and EN+, respectively, entering and leaving N; that is, EN=EN-∪EN+, where(6)EN-=e∈EN,t(e)∉N,h(e)∈NEN+=f∈EN,t(f)∈N,h(f)∉N.Insertion problem concerning how to reallocate the resources then can be produced on determining which arc should be selected from each pair of alternative arcs. Each arc in the pair represents mutually exclusive permutation between two operations. A core concept in the reduction of the computational effort of the algorithm introduced in this paper is the characterization ofincompatible arcspairs.Proposition 1.
Given a TETPI problem, for any selectionS∈E, if G(S) contains a cycle, then the selection S must contain at least one arce∈EN- entering to and one arcf∈EN+ leaving from the additional operations. This arcs pair e,f isincompatible in afeasible inserting selection [15].Proof.
Given an operation path in graphG, let VN and VO denote the additional and exiting train operation sets, respectively. Since existing timetable and additional timetable are feasible separately, there is no cycle in VN or VO. If a cycle arises in the given path (see Figure 4 as a simple example), it must contain at least one arc e entering v1 from w1 and simultaneously at least one arc f leaving v2 to w2, where v1,v2∈VN and w1,w2∈VO. For this reason, the corresponding alternative arc pair e,f which composes a cycle is incompatible in a feasible selection SN.Figure 4
Arbitrary operation path with a cycle, wherev1,v2∈OpN and w1,w2∈OpO.Based on Proposition1, let U be the collection of all such positive cyclic selections that visit additional trains N exactly once. For example, in Figure 2,(7)EN-=a5,n4,a3,n5,a10,n7,b10,n7indicates that existing trains precede additional trains in common sections, while(8)EN+=n5,a4,n8,a5,n10,a7,n10,b7represents that an additional train goes first and then an existing train follows. Then the family of alternative arcs pair is ξ=e,e¯:e∈EN-,e¯∈EN+, where(9)ξ=a5,n4,n5,a4∪a3,n5,n8,a5mn∪a10,n7,n10,a7∪b10,n7,n10,b7.According to the definition of U, then(10)U=ξ∪(a3,n5),(n5,a4)mmmn∪a5,n4,n8,a5∪b10,n7,n10,a7.Cleary,U is incompatible arc pairs set. Exactly only one arc in each pair of ξ must be chosen in a feasible selection and at most one arc (may be none of arc) could be selected in each pair of U/ξ. Let xe be a binary variable to identify whether arc e is chosen or not; that is,(11)xe=1ifarceischosen,0otherwise.Then the TETPI problem can be described as model (M2): (12)(M2):min⁡⁡Cxe+xf≤1∀e∈EN-,f∈EN+,e,f∈Uxe+xe¯=1∀e∈ENxe=1∀e∈Qxe=0∀e∈Fxe=0,1∀e∈EN-Q-Fπx≤C.Since the critical pathπ(x) of the new timetable is nonlinear in x, huge computational effort will be taken to solve (M2). However, it can be observed that there are three different circumstances for π(x) in an arbitrary feasible insertion [16].(1)
Ifπ(x) contains no operations of additional trains N, the corresponding makespan for the new graph holds π0=πστ, where πστ is the makespan for existing timetable.(2)
Ifπ(x) contains exactly one arc in EN, the corresponding makespan for the new graph satisfies π1=πσ,t(e)+Ce+πh(e),τ, where πij is the longest path fromnodei tonodej and Ci is the weight of arc i.(3)
Ifπ(x) contains exactly e∈EN- and f∈EN+, the corresponding makespan for the new graph is π2=πσ,te+Ce+πhe,tf+Cf+πhf,τ.Letπ′x denote the maximum length path for these three circumstances. Clearly, π′x≤πx≤C. Then, the (M2) can be released into(13)(M3):min⁡⁡Cxe+xf≤1∀e∈EN-,f∈EN+,e,f∈Uxe+xe¯=1∀e∈ENxe=1∀e∈Qxe=0∀e∈Fxe=0,1∀e∈EN-Q-Fπ0≤Cπ1xe≤C∀e∈EN-∪EN+π2xe+xf-1≤C∀e∈EN-,f∈EN+.Proposition 2.
Given a TETPI problem with the makespanC for the optimal insertion, if e,e¯ is a pair of alternative arcs and π1=πσ,t(e)+Ce+πh(e),τ>C, then e is forbidden and e¯ is implied by theoptimal inserting selection. In particular, xe=0 and xe¯=1, when π1>C [5].Proposition 3.
Given a TETPI problem with the makespanC for the optimal insertion, if there exists a path π2 that contains arcse and f and π2=πσ,t(e)+Ce+πh(e),t(f)+Cf+πh(f),τ>C, then arcs pair e,f is incompatible in theoptimal inserting selection. In particular, xe+xf≤1, when π2>C.Proof.
Suppose thate and f are selected simultaneously in the optimal selection SN and there exists a path π2=πσ,te+Ce+πhe,tf+Cf+πhf,τ. The makespan C, the longest path in this inserting alternative graph, should satisfy C≥π2, but then it is a contradiction to π2>C.Based on Propositions2 and 3, let(14)Uc=e:e∈EN,π1>C∪e,f:e∈E-N,f∈E+N,π2>C.Then (M3) can be changed into(15)(M4):min⁡⁡Cxe+xf≤1∀e∈EN-,f∈EN+,e,f∈U∪Ucxe+xe¯=1∀e∈ENxe=1∀e∈Qxe=0∀e∈F∪Ucxe=0,1∀e∈EN-Q-F.Then the lower bound LB for the TETPI problem can be relaxed into finding a minimumC to make (M4) have existence of solution; that is, Cmin⁡=LB. It is evident that LB is tight if and only if there is a critical path that contains exactly one arc leaving N and one arc entering N. The procedure of inserting algorithm with fixed train permutation is showed in Procedure 1.Procedure 1:Lower bound and critical path.
Input: existing timetable G(VO,AO,EO)
Output: lower bound and critical path
(1)Begin
(2)    calculate reachable matrixRO and RN for original and additional operation respectively, where 1/0 represents that it
is (not) reachable from nodei to node,
(3)while   se≠Last_section   do
(4)OO=Get_operation(TO,se), ON=Get_operation(TN,se)
(5)for   OO and ON   do
(6)σ(OO)=Get_operation(OO), σ(OO)=Get_operation(ON)
(7)e=e∪(σ(OO),ON), f=f∪(σ(ON),OO)
(8)end for
(9)se=se+1
(10)end while
(11)for  all   e and f   do
(12)if   RO(h(f),t(e))=1 & RN(h(e),t(f))=1   then
(13)U(e,f)=1, i.e. e and f are incompatible arcs
(14)end if
(15)end for
(16)for   all   U≠1   do
(17)π1(e)=πσ,t(e)+pe+πh(e),τ, π1(f)=πσ,t(f)+pf+πh(f),τ
(18)if   RN(h(e),t(f))=1   then
(19)π2(e,f)=πσ,t(e)+pe+πh(e),t(f)+pf+πh(f),τ
(20)else  if   RO(h(f),t(e))=1
(21)π2(f,e)=πσ,t(f)+pf+πh(f),t(e)+pe+πh(f),τ
(22)end if
(23)end for
(24)C1=πσ,τ,   C2=max⁡(π1,π2), C=C1, Uc=U
(25)while   C1≠C2   do
(26)if   π2(e,f)≤C   then
(27)Uc(e,f)=1, that is e and f are incompatible arcs
(28)end if
(29)if   π1(e)>C & Uc(e-,f)=1   then
(30)e-,f∈Select_f_Nr
(31)end if
(32)if   π1(f)>C & Uc(e,f-)=1   then
(33)e,f-∈Select_f_Nr
(34)end if
(35)if   Select_e_Nr∩Select_f_Nr=∅   then
(36)CLB=C, C2=C, C=(C1+C2)/2
(37)end if
(38)if   C1=C   then
(39)C=(C1+C2)/2
(40)end if
(41)end while
(42)Return   CLB and πAccording to the above three propositions, letQ* denote arcs implied by the optimal insertion based on Propositions 2 and 3 and let H be a set of alternative arc pairs which are still not determined. Then insertion Q*∪H- and Q*∪H+ are two feasible inserting selections; for example, if (n5,a4) and (n8,a5) are implied in Figure 2, selections(16)Q*∪H-=n5,a4,n8,a5,b10,n7,a10,n7,Q*∪H+=n5,a4,n8,a5,n10,n7,n10,a7,are two feasible insert solutions. The better solution of the two insertions yields an upper bound UB for this TETPI problem, denoted by SUB.


#### 2.3.2. Iteration of Reordering Optimization

The evaluation and choice of a reordering neighbor ofSO are solved by a local search approach. The sequence of operations which compose critical path is modified if the new solution improves the objective function.It should be noticed that, in the circumstance of inserting trains one by one, there are two types of orders to be exchanged, which occur between two original trains or between one additional train and one original train. When inserting trains simultaneously, rough permutation of additional trains should be drafted based on predefined time and transfer requirements. Then, besides orders between two original trains, the order of additional trains also should be taken into consideration.Normally, the guarantee of original orders and connections plays an important factor in minimum consecutive delay to existing timetable and in convenience for passengers. It means that if there is no improvement found by exchanging orders of additional trains, then switch between two original trains is executed. Automatische Rijweg Instelling (ARI) is used as a dispatching rule in this paper. This rule is used in The Netherlands and is briefly introduced in Corman et al. [4]. Procedure 2 represents the iterative optimization procedure.Procedure 2:Local search and iterative step.
Input: SLB, CLB and critical path π
Output: best solution found
(1)while (time limit not reached) & (consecutive delay > 0)   do
(2)  Reorder the permutation of operations on critical path according to the dispatching rules (ARI) in Section2.3.2,
getSO′
(3)Do Procedure 1 Lowerbound & Criticalpath, get SLB′ and CLB′
(4)if   CLB′<CLB   then
(5)SO=SO′, CLB=CLB′, CLB=CLB′, SLB=SLB′
(6)end if
(7)end while
(8)calculate   SN according to the current SLB
(9)Return   S=SO∪SN


## 2.1. Basic Railway Scheduling Model

For a basic railway scheduling problem, its corresponding alternative graph model is usually defined as a tripleG=(V,A,E), where nodes set V refers to a finite set of nodes, which correspond to operations. A is a set of direct conjunctive arcs modeling a precedence relation between two consecutive operations. E is a set of pairs ofalternative arcs representing all the potential permutations of trains in common sections.In Figure1(a), operations i and j represent trains Ta and Tb entering the same section s. σ(i) and σ(j) are referred to the subsequent operations of i and j, respectively. Conjunctive arcs are depicted with solid arrows, which are weighted with running times pi and pj of the associated operations i and j, respectively. A conjunctive arc restricts the starting time for an operation with respect to the starting of its predecessor operation; that is,(1)tσi≥ti+pi,tσj≥tj+pj.Figure 1
Two train operations to be processed on the same section.In a fixed block safety system, each block section can host at most one train at a time; otherwise, some potential conflicts occur whenever two or more trains require the same block section. Therefore, after processing, every train has to wait on the current section and blocks it until the subsequent section becomes available, thus preventing other trains from entering the same section at the same time. This constraint is formulated by a pair of alternative arcs which defines different processing order for every two trains in the common section. A pair of alternative arcsσj,i,σi,j are represented with dashed lines in Figure 1(a). If σj,i is selected, Tb precedes Ta. Conversely, if σi,j is selected, Ta precedes Tb. The conflict between Ta and Tb must be solved choosing exactly one of the two arcs. In practice, an additional safety margin E, referred to in this paper assetup time, is introduced to every alternative arc. It is a permutation based constant. Then the alternative arcs can be formulated as follows:(2)tσi≥tj+pj+Ejiortσj≥ti+pi+Eij.However, for fast trains, the model is slightly different. Note that a fast train in a fixed safety system is only allowed to enter a block section if the next two block sections are not occupied by other trains. As shown in Figure1(b), the corresponding pair of alternative arcs lead to σi,j,σj,φi, where φi and φj are the predecessor operations of faster operation i and slower operation j, respectively [21]. This can be seen as a multiprocessor job scheduling problem, where operations have to be processed simultaneously on a set of dedicated machines instead of a single machine.


## 2.2. Model for the TETPI Problem

In this section, the TETPI problem is formulated by means of an alternative graph model. Combining the description of the basic scheduling model and the features of inserting problem, the conjunctive arcsA and alternative arcs E for the TETPI problem are defined as follows:(i)
Conjunctive arcs set A=AO∪AN is composed of original conjunctive arcs set AO, which belongs to existing trains, and new conjunctive arcs set AN, which belongs to additional trains. A is fixed when train routes are defined.(ii)
Alternative arcs set E=EO∪EN, where EO represents permutation of original trains and predefined sequence between additional trains and EN represents all of the possible insertions for new trains set N. In the TETPI problem, even though EO is settled, it is still a set of variables when some trains need to be reordered, and then selection of EN depends on the choice of EO.For example, an alternative graph for a part of railway lines is presented in Figure2. It contains 10 block sections numbered from m1 to m10. Two existing trains labeled Ta and Tb are using this part of tracks. The routes of trains Ta and Tb, respectively, are as follows:(3)Ta:m4⟶m5⟶m3⟶m6⟶m7⟶m10Tb:m1⟶m2⟶m3⟶m6⟶m7⟶m10.Figure 2
An alternative graph for the TETPI problem.One additional train denotedTn with the route(4)Tn:m4⟶m5⟶m8⟶m9⟶m7⟶m10needs to be inserted. Let σ and τ be dummy start and finish operations, having to be performed before and after all operations, respectively. For the sake of clarity, the weights of arcs which represent minimum running time and dwell time of the associated operations are not showed.In this alternative graph,A is represented with solid arrows, while EO and EN are depicted with dash-dotted arrows and dashed arrows, respectively. To differ in that a precedence constraint in A always must hold, while an arc in E must be selected if its corresponding alternative arc does not hold. Aselection in graph G is an arbitrary subset of alternative arcs; that is, S⊆E. If for every alternative pair at least one arc is selected, we called that S iscomplete in G. S is anacyclic selection if the graph GV,A∪S, denoted by G(S), contains no positive length cycles. Finally, S is a feasible selection if it is complete and acyclic. In fact, a positive length cycle causes a deadlock in a graph, which is infeasible. So the TETPI problem is equivalent to the following problem: given a set of trains T and a selection SO that is feasible for all trains of T-N, where N is a set of additional trains, then find a selection SN of alternative arcs incident to N such that among all feasible selections selection S=SO∪SN minimizes the length of the longest path π from σ to τ in graph G(S).Furthermore, D’Ariano et al. [6] use an innovative way to represent the maximum consecutive delay with the makespan of the associated alternative graph by introducing the weights of entry time and negative exit time on the start and end operations, respectively. In this way, the objective for the TETPI model is changed into minimizing consecutive delay.In practice, extra freight trains may be set flexibly when they will enter the planned system, but at most of time passenger trains have to be set at predefined time or meet transfer requirements with existing trains, and moreover some trains may already be partly within the system at the start of the schedule. In such cases, strategies like retiming and reordering existing trains are unavoidable which may cause scheduled connections to be dismissed. In order to guarantee some scheduled connections or orders, the corresponding alternative arcs inEO should not be changed. Meanwhile, for the purpose of new connections between additional trains and scheduled trains, the corresponding alternative arcs in EN should be preselected. A set of these preselected and preforbidden alternative arcs are referred to Q and F, respectively, in this paper.Then the basic constrained TETPI problem based on alternative graph can be formulated as the model (M1):(5)(M1):min⁡⁡tτ-tσtj-ti≥pi∀i,j∈V,(i,j)∈Atj-ti≥pi+Eijortk-th≥ph+Ehk∀i,j,k,h∈V,i,j,h,k∈Etj-ti≥pi+Eij∀i,j∈V,(i,j)∈Qtj-ti≤pi+Eij∀i,j∈V,i,j∈F.Besides the above constraints, the alternative graph allows formulation of situations more general that the ones we have mentioned. For example, Strotmann [21] introduces additional constraints modeled in terms of the alternative graph model, including connection constraints between trains, out-of-service intervals for certain block sections and so on.


## 2.3. Algorithms for the TETPI Problem

In our definition, the TETPI problem is asked to develop a new conflict-free plan compatible with the strict time limit for some real-time traffic situations and modify the scheduled requests as little as possible, including reordering as few as possible. In order to meet these minimum deviation and limited time requirements, it is not necessary to take all the scheduled arcsEO into consideration, because only the change of alternative arcs occurring in thecritical path is propitious to decrease the makespan of alternative graph. In this section, the TETPI problem is decomposed into two subproblems:(1)
find the optimal insertion for a fixed order timetable: in this phase, the additional services mainly utilize unoccupied capacities to process. By this means, it can not only minimize the deviation of scheduled timetable, but also keep the existing transfer plans to the fullest extent;(2)
give a solution to subproblem (1) and define new sequence ofEO potentially leading to better schedules. In this phase, unavoidable permutation changes are introduced in order to set more additional restricted services without leading to large deviation or consecutive delay to the existing timetable.These two subproblems are then iteratively solved until no improvement is possible within a time limit of computation. The architecture of this inserting procedure is represented in Figure3.Figure 3
Architecture of insertion.


### 2.3.1. Branch and Bound Search Algorithm with Fixed Permutation

Let the lengthπS(σ,τ) be the critical path of the graph G(S). This value can be reduced either by modifying the location of the new trains SN or reordering the original train sequencing SO. In this subsection, we start from G(V,A∪SO) with fixed permutation of original trains SO and then derive a polyhedral description of all feasible insertions SN for the TETPI problem.In order to formulate this problem, we will use the following definitions and notions. For any directed arce=v,w, te=v is the tail node of arc e and he=w is the head node. Given an existing timetable GV,A∪SO, insert all operations of train set N into this schedule simultaneously. A family of alternative arc pairs EN which are incident with N are composed of two distinct alternative edge sets EN- and EN+, respectively, entering and leaving N; that is, EN=EN-∪EN+, where(6)EN-=e∈EN,t(e)∉N,h(e)∈NEN+=f∈EN,t(f)∈N,h(f)∉N.Insertion problem concerning how to reallocate the resources then can be produced on determining which arc should be selected from each pair of alternative arcs. Each arc in the pair represents mutually exclusive permutation between two operations. A core concept in the reduction of the computational effort of the algorithm introduced in this paper is the characterization ofincompatible arcspairs.Proposition 1.
Given a TETPI problem, for any selectionS∈E, if G(S) contains a cycle, then the selection S must contain at least one arce∈EN- entering to and one arcf∈EN+ leaving from the additional operations. This arcs pair e,f isincompatible in afeasible inserting selection [15].Proof.
Given an operation path in graphG, let VN and VO denote the additional and exiting train operation sets, respectively. Since existing timetable and additional timetable are feasible separately, there is no cycle in VN or VO. If a cycle arises in the given path (see Figure 4 as a simple example), it must contain at least one arc e entering v1 from w1 and simultaneously at least one arc f leaving v2 to w2, where v1,v2∈VN and w1,w2∈VO. For this reason, the corresponding alternative arc pair e,f which composes a cycle is incompatible in a feasible selection SN.Figure 4
Arbitrary operation path with a cycle, wherev1,v2∈OpN and w1,w2∈OpO.Based on Proposition1, let U be the collection of all such positive cyclic selections that visit additional trains N exactly once. For example, in Figure 2,(7)EN-=a5,n4,a3,n5,a10,n7,b10,n7indicates that existing trains precede additional trains in common sections, while(8)EN+=n5,a4,n8,a5,n10,a7,n10,b7represents that an additional train goes first and then an existing train follows. Then the family of alternative arcs pair is ξ=e,e¯:e∈EN-,e¯∈EN+, where(9)ξ=a5,n4,n5,a4∪a3,n5,n8,a5mn∪a10,n7,n10,a7∪b10,n7,n10,b7.According to the definition of U, then(10)U=ξ∪(a3,n5),(n5,a4)mmmn∪a5,n4,n8,a5∪b10,n7,n10,a7.Cleary,U is incompatible arc pairs set. Exactly only one arc in each pair of ξ must be chosen in a feasible selection and at most one arc (may be none of arc) could be selected in each pair of U/ξ. Let xe be a binary variable to identify whether arc e is chosen or not; that is,(11)xe=1ifarceischosen,0otherwise.Then the TETPI problem can be described as model (M2): (12)(M2):min⁡⁡Cxe+xf≤1∀e∈EN-,f∈EN+,e,f∈Uxe+xe¯=1∀e∈ENxe=1∀e∈Qxe=0∀e∈Fxe=0,1∀e∈EN-Q-Fπx≤C.Since the critical pathπ(x) of the new timetable is nonlinear in x, huge computational effort will be taken to solve (M2). However, it can be observed that there are three different circumstances for π(x) in an arbitrary feasible insertion [16].(1)
Ifπ(x) contains no operations of additional trains N, the corresponding makespan for the new graph holds π0=πστ, where πστ is the makespan for existing timetable.(2)
Ifπ(x) contains exactly one arc in EN, the corresponding makespan for the new graph satisfies π1=πσ,t(e)+Ce+πh(e),τ, where πij is the longest path fromnodei tonodej and Ci is the weight of arc i.(3)
Ifπ(x) contains exactly e∈EN- and f∈EN+, the corresponding makespan for the new graph is π2=πσ,te+Ce+πhe,tf+Cf+πhf,τ.Letπ′x denote the maximum length path for these three circumstances. Clearly, π′x≤πx≤C. Then, the (M2) can be released into(13)(M3):min⁡⁡Cxe+xf≤1∀e∈EN-,f∈EN+,e,f∈Uxe+xe¯=1∀e∈ENxe=1∀e∈Qxe=0∀e∈Fxe=0,1∀e∈EN-Q-Fπ0≤Cπ1xe≤C∀e∈EN-∪EN+π2xe+xf-1≤C∀e∈EN-,f∈EN+.Proposition 2.
Given a TETPI problem with the makespanC for the optimal insertion, if e,e¯ is a pair of alternative arcs and π1=πσ,t(e)+Ce+πh(e),τ>C, then e is forbidden and e¯ is implied by theoptimal inserting selection. In particular, xe=0 and xe¯=1, when π1>C [5].Proposition 3.
Given a TETPI problem with the makespanC for the optimal insertion, if there exists a path π2 that contains arcse and f and π2=πσ,t(e)+Ce+πh(e),t(f)+Cf+πh(f),τ>C, then arcs pair e,f is incompatible in theoptimal inserting selection. In particular, xe+xf≤1, when π2>C.Proof.
Suppose thate and f are selected simultaneously in the optimal selection SN and there exists a path π2=πσ,te+Ce+πhe,tf+Cf+πhf,τ. The makespan C, the longest path in this inserting alternative graph, should satisfy C≥π2, but then it is a contradiction to π2>C.Based on Propositions2 and 3, let(14)Uc=e:e∈EN,π1>C∪e,f:e∈E-N,f∈E+N,π2>C.Then (M3) can be changed into(15)(M4):min⁡⁡Cxe+xf≤1∀e∈EN-,f∈EN+,e,f∈U∪Ucxe+xe¯=1∀e∈ENxe=1∀e∈Qxe=0∀e∈F∪Ucxe=0,1∀e∈EN-Q-F.Then the lower bound LB for the TETPI problem can be relaxed into finding a minimumC to make (M4) have existence of solution; that is, Cmin⁡=LB. It is evident that LB is tight if and only if there is a critical path that contains exactly one arc leaving N and one arc entering N. The procedure of inserting algorithm with fixed train permutation is showed in Procedure 1.Procedure 1:Lower bound and critical path.
Input: existing timetable G(VO,AO,EO)
Output: lower bound and critical path
(1)Begin
(2)    calculate reachable matrixRO and RN for original and additional operation respectively, where 1/0 represents that it
is (not) reachable from nodei to node,
(3)while   se≠Last_section   do
(4)OO=Get_operation(TO,se), ON=Get_operation(TN,se)
(5)for   OO and ON   do
(6)σ(OO)=Get_operation(OO), σ(OO)=Get_operation(ON)
(7)e=e∪(σ(OO),ON), f=f∪(σ(ON),OO)
(8)end for
(9)se=se+1
(10)end while
(11)for  all   e and f   do
(12)if   RO(h(f),t(e))=1 & RN(h(e),t(f))=1   then
(13)U(e,f)=1, i.e. e and f are incompatible arcs
(14)end if
(15)end for
(16)for   all   U≠1   do
(17)π1(e)=πσ,t(e)+pe+πh(e),τ, π1(f)=πσ,t(f)+pf+πh(f),τ
(18)if   RN(h(e),t(f))=1   then
(19)π2(e,f)=πσ,t(e)+pe+πh(e),t(f)+pf+πh(f),τ
(20)else  if   RO(h(f),t(e))=1
(21)π2(f,e)=πσ,t(f)+pf+πh(f),t(e)+pe+πh(f),τ
(22)end if
(23)end for
(24)C1=πσ,τ,   C2=max⁡(π1,π2), C=C1, Uc=U
(25)while   C1≠C2   do
(26)if   π2(e,f)≤C   then
(27)Uc(e,f)=1, that is e and f are incompatible arcs
(28)end if
(29)if   π1(e)>C & Uc(e-,f)=1   then
(30)e-,f∈Select_f_Nr
(31)end if
(32)if   π1(f)>C & Uc(e,f-)=1   then
(33)e,f-∈Select_f_Nr
(34)end if
(35)if   Select_e_Nr∩Select_f_Nr=∅   then
(36)CLB=C, C2=C, C=(C1+C2)/2
(37)end if
(38)if   C1=C   then
(39)C=(C1+C2)/2
(40)end if
(41)end while
(42)Return   CLB and πAccording to the above three propositions, letQ* denote arcs implied by the optimal insertion based on Propositions 2 and 3 and let H be a set of alternative arc pairs which are still not determined. Then insertion Q*∪H- and Q*∪H+ are two feasible inserting selections; for example, if (n5,a4) and (n8,a5) are implied in Figure 2, selections(16)Q*∪H-=n5,a4,n8,a5,b10,n7,a10,n7,Q*∪H+=n5,a4,n8,a5,n10,n7,n10,a7,are two feasible insert solutions. The better solution of the two insertions yields an upper bound UB for this TETPI problem, denoted by SUB.


### 2.3.2. Iteration of Reordering Optimization

The evaluation and choice of a reordering neighbor ofSO are solved by a local search approach. The sequence of operations which compose critical path is modified if the new solution improves the objective function.It should be noticed that, in the circumstance of inserting trains one by one, there are two types of orders to be exchanged, which occur between two original trains or between one additional train and one original train. When inserting trains simultaneously, rough permutation of additional trains should be drafted based on predefined time and transfer requirements. Then, besides orders between two original trains, the order of additional trains also should be taken into consideration.Normally, the guarantee of original orders and connections plays an important factor in minimum consecutive delay to existing timetable and in convenience for passengers. It means that if there is no improvement found by exchanging orders of additional trains, then switch between two original trains is executed. Automatische Rijweg Instelling (ARI) is used as a dispatching rule in this paper. This rule is used in The Netherlands and is briefly introduced in Corman et al. [4]. Procedure 2 represents the iterative optimization procedure.Procedure 2:Local search and iterative step.
Input: SLB, CLB and critical path π
Output: best solution found
(1)while (time limit not reached) & (consecutive delay > 0)   do
(2)  Reorder the permutation of operations on critical path according to the dispatching rules (ARI) in Section2.3.2,
getSO′
(3)Do Procedure 1 Lowerbound & Criticalpath, get SLB′ and CLB′
(4)if   CLB′<CLB   then
(5)SO=SO′, CLB=CLB′, CLB=CLB′, SLB=SLB′
(6)end if
(7)end while
(8)calculate   SN according to the current SLB
(9)Return   S=SO∪SN


## 2.3.1. Branch and Bound Search Algorithm with Fixed Permutation

Let the lengthπS(σ,τ) be the critical path of the graph G(S). This value can be reduced either by modifying the location of the new trains SN or reordering the original train sequencing SO. In this subsection, we start from G(V,A∪SO) with fixed permutation of original trains SO and then derive a polyhedral description of all feasible insertions SN for the TETPI problem.In order to formulate this problem, we will use the following definitions and notions. For any directed arce=v,w, te=v is the tail node of arc e and he=w is the head node. Given an existing timetable GV,A∪SO, insert all operations of train set N into this schedule simultaneously. A family of alternative arc pairs EN which are incident with N are composed of two distinct alternative edge sets EN- and EN+, respectively, entering and leaving N; that is, EN=EN-∪EN+, where(6)EN-=e∈EN,t(e)∉N,h(e)∈NEN+=f∈EN,t(f)∈N,h(f)∉N.Insertion problem concerning how to reallocate the resources then can be produced on determining which arc should be selected from each pair of alternative arcs. Each arc in the pair represents mutually exclusive permutation between two operations. A core concept in the reduction of the computational effort of the algorithm introduced in this paper is the characterization ofincompatible arcspairs.Proposition 1.
Given a TETPI problem, for any selectionS∈E, if G(S) contains a cycle, then the selection S must contain at least one arce∈EN- entering to and one arcf∈EN+ leaving from the additional operations. This arcs pair e,f isincompatible in afeasible inserting selection [15].Proof.
Given an operation path in graphG, let VN and VO denote the additional and exiting train operation sets, respectively. Since existing timetable and additional timetable are feasible separately, there is no cycle in VN or VO. If a cycle arises in the given path (see Figure 4 as a simple example), it must contain at least one arc e entering v1 from w1 and simultaneously at least one arc f leaving v2 to w2, where v1,v2∈VN and w1,w2∈VO. For this reason, the corresponding alternative arc pair e,f which composes a cycle is incompatible in a feasible selection SN.Figure 4
Arbitrary operation path with a cycle, wherev1,v2∈OpN and w1,w2∈OpO.Based on Proposition1, let U be the collection of all such positive cyclic selections that visit additional trains N exactly once. For example, in Figure 2,(7)EN-=a5,n4,a3,n5,a10,n7,b10,n7indicates that existing trains precede additional trains in common sections, while(8)EN+=n5,a4,n8,a5,n10,a7,n10,b7represents that an additional train goes first and then an existing train follows. Then the family of alternative arcs pair is ξ=e,e¯:e∈EN-,e¯∈EN+, where(9)ξ=a5,n4,n5,a4∪a3,n5,n8,a5mn∪a10,n7,n10,a7∪b10,n7,n10,b7.According to the definition of U, then(10)U=ξ∪(a3,n5),(n5,a4)mmmn∪a5,n4,n8,a5∪b10,n7,n10,a7.Cleary,U is incompatible arc pairs set. Exactly only one arc in each pair of ξ must be chosen in a feasible selection and at most one arc (may be none of arc) could be selected in each pair of U/ξ. Let xe be a binary variable to identify whether arc e is chosen or not; that is,(11)xe=1ifarceischosen,0otherwise.Then the TETPI problem can be described as model (M2): (12)(M2):min⁡⁡Cxe+xf≤1∀e∈EN-,f∈EN+,e,f∈Uxe+xe¯=1∀e∈ENxe=1∀e∈Qxe=0∀e∈Fxe=0,1∀e∈EN-Q-Fπx≤C.Since the critical pathπ(x) of the new timetable is nonlinear in x, huge computational effort will be taken to solve (M2). However, it can be observed that there are three different circumstances for π(x) in an arbitrary feasible insertion [16].(1)
Ifπ(x) contains no operations of additional trains N, the corresponding makespan for the new graph holds π0=πστ, where πστ is the makespan for existing timetable.(2)
Ifπ(x) contains exactly one arc in EN, the corresponding makespan for the new graph satisfies π1=πσ,t(e)+Ce+πh(e),τ, where πij is the longest path fromnodei tonodej and Ci is the weight of arc i.(3)
Ifπ(x) contains exactly e∈EN- and f∈EN+, the corresponding makespan for the new graph is π2=πσ,te+Ce+πhe,tf+Cf+πhf,τ.Letπ′x denote the maximum length path for these three circumstances. Clearly, π′x≤πx≤C. Then, the (M2) can be released into(13)(M3):min⁡⁡Cxe+xf≤1∀e∈EN-,f∈EN+,e,f∈Uxe+xe¯=1∀e∈ENxe=1∀e∈Qxe=0∀e∈Fxe=0,1∀e∈EN-Q-Fπ0≤Cπ1xe≤C∀e∈EN-∪EN+π2xe+xf-1≤C∀e∈EN-,f∈EN+.Proposition 2.
Given a TETPI problem with the makespanC for the optimal insertion, if e,e¯ is a pair of alternative arcs and π1=πσ,t(e)+Ce+πh(e),τ>C, then e is forbidden and e¯ is implied by theoptimal inserting selection. In particular, xe=0 and xe¯=1, when π1>C [5].Proposition 3.
Given a TETPI problem with the makespanC for the optimal insertion, if there exists a path π2 that contains arcse and f and π2=πσ,t(e)+Ce+πh(e),t(f)+Cf+πh(f),τ>C, then arcs pair e,f is incompatible in theoptimal inserting selection. In particular, xe+xf≤1, when π2>C.Proof.
Suppose thate and f are selected simultaneously in the optimal selection SN and there exists a path π2=πσ,te+Ce+πhe,tf+Cf+πhf,τ. The makespan C, the longest path in this inserting alternative graph, should satisfy C≥π2, but then it is a contradiction to π2>C.Based on Propositions2 and 3, let(14)Uc=e:e∈EN,π1>C∪e,f:e∈E-N,f∈E+N,π2>C.Then (M3) can be changed into(15)(M4):min⁡⁡Cxe+xf≤1∀e∈EN-,f∈EN+,e,f∈U∪Ucxe+xe¯=1∀e∈ENxe=1∀e∈Qxe=0∀e∈F∪Ucxe=0,1∀e∈EN-Q-F.Then the lower bound LB for the TETPI problem can be relaxed into finding a minimumC to make (M4) have existence of solution; that is, Cmin⁡=LB. It is evident that LB is tight if and only if there is a critical path that contains exactly one arc leaving N and one arc entering N. The procedure of inserting algorithm with fixed train permutation is showed in Procedure 1.Procedure 1:Lower bound and critical path.
Input: existing timetable G(VO,AO,EO)
Output: lower bound and critical path
(1)Begin
(2)    calculate reachable matrixRO and RN for original and additional operation respectively, where 1/0 represents that it
is (not) reachable from nodei to node,
(3)while   se≠Last_section   do
(4)OO=Get_operation(TO,se), ON=Get_operation(TN,se)
(5)for   OO and ON   do
(6)σ(OO)=Get_operation(OO), σ(OO)=Get_operation(ON)
(7)e=e∪(σ(OO),ON), f=f∪(σ(ON),OO)
(8)end for
(9)se=se+1
(10)end while
(11)for  all   e and f   do
(12)if   RO(h(f),t(e))=1 & RN(h(e),t(f))=1   then
(13)U(e,f)=1, i.e. e and f are incompatible arcs
(14)end if
(15)end for
(16)for   all   U≠1   do
(17)π1(e)=πσ,t(e)+pe+πh(e),τ, π1(f)=πσ,t(f)+pf+πh(f),τ
(18)if   RN(h(e),t(f))=1   then
(19)π2(e,f)=πσ,t(e)+pe+πh(e),t(f)+pf+πh(f),τ
(20)else  if   RO(h(f),t(e))=1
(21)π2(f,e)=πσ,t(f)+pf+πh(f),t(e)+pe+πh(f),τ
(22)end if
(23)end for
(24)C1=πσ,τ,   C2=max⁡(π1,π2), C=C1, Uc=U
(25)while   C1≠C2   do
(26)if   π2(e,f)≤C   then
(27)Uc(e,f)=1, that is e and f are incompatible arcs
(28)end if
(29)if   π1(e)>C & Uc(e-,f)=1   then
(30)e-,f∈Select_f_Nr
(31)end if
(32)if   π1(f)>C & Uc(e,f-)=1   then
(33)e,f-∈Select_f_Nr
(34)end if
(35)if   Select_e_Nr∩Select_f_Nr=∅   then
(36)CLB=C, C2=C, C=(C1+C2)/2
(37)end if
(38)if   C1=C   then
(39)C=(C1+C2)/2
(40)end if
(41)end while
(42)Return   CLB and πAccording to the above three propositions, letQ* denote arcs implied by the optimal insertion based on Propositions 2 and 3 and let H be a set of alternative arc pairs which are still not determined. Then insertion Q*∪H- and Q*∪H+ are two feasible inserting selections; for example, if (n5,a4) and (n8,a5) are implied in Figure 2, selections(16)Q*∪H-=n5,a4,n8,a5,b10,n7,a10,n7,Q*∪H+=n5,a4,n8,a5,n10,n7,n10,a7,are two feasible insert solutions. The better solution of the two insertions yields an upper bound UB for this TETPI problem, denoted by SUB.


## 2.3.2. Iteration of Reordering Optimization

The evaluation and choice of a reordering neighbor ofSO are solved by a local search approach. The sequence of operations which compose critical path is modified if the new solution improves the objective function.It should be noticed that, in the circumstance of inserting trains one by one, there are two types of orders to be exchanged, which occur between two original trains or between one additional train and one original train. When inserting trains simultaneously, rough permutation of additional trains should be drafted based on predefined time and transfer requirements. Then, besides orders between two original trains, the order of additional trains also should be taken into consideration.Normally, the guarantee of original orders and connections plays an important factor in minimum consecutive delay to existing timetable and in convenience for passengers. It means that if there is no improvement found by exchanging orders of additional trains, then switch between two original trains is executed. Automatische Rijweg Instelling (ARI) is used as a dispatching rule in this paper. This rule is used in The Netherlands and is briefly introduced in Corman et al. [4]. Procedure 2 represents the iterative optimization procedure.Procedure 2:Local search and iterative step.
Input: SLB, CLB and critical path π
Output: best solution found
(1)while (time limit not reached) & (consecutive delay > 0)   do
(2)  Reorder the permutation of operations on critical path according to the dispatching rules (ARI) in Section2.3.2,
getSO′
(3)Do Procedure 1 Lowerbound & Criticalpath, get SLB′ and CLB′
(4)if   CLB′<CLB   then
(5)SO=SO′, CLB=CLB′, CLB=CLB′, SLB=SLB′
(6)end if
(7)end while
(8)calculate   SN according to the current SLB
(9)Return   S=SO∪SN


## 3. Computational Tests

We report on our computational experiments on a real-life scenario. The experiments are based on the dispatching area of Hannover-Braunschweig. The primary aim of the numerical investigations is to identify whether good solutions can be obtained using the methodology and techniques proposed in this paper. The bound search and permutation refinement algorithms are implemented in MATLAB R2010b and executed on a laptop equipped with a processor Intel Core 2 Duo (2.4 GHZ), 2 GB Ram. Computational time and delays are always expressed in seconds.


### 3.1. Description of Instances

The Hannover-Braunschweig railway area consists of double tracks divided into one long corridor for each traffic direction, one dedicated stop for freight trains, and seven passenger stations, see Figure5. We evaluate a four-hour (8:00 am–12:00 pm) timetable of the year 2003 in the direction of Braunschweig to Hannover. In this experimental study, 9 freight trains and 27 passenger trains, including 17 intercity trains and 10 regional trains, are scheduled in 60 blocking sections in the existing timetable. The total number of exiting operations is 2064. A setup time Eij is set to a constant of 120 seconds for simplification.Figure 5
Hannover-Braunschweig railway area.This insertion problem increases in the number of additional trains which contain a mixture of 120, 160, and 180 km/h trains in order to make the problem more challenging. In particular, the instances of simultaneity inserting 1 to 15 additional trains with various speed are tested in this section.For each instance, unoccupied capacity is used as main resource for additional trains. If and only if consecutive delays are inevitable, then iterative reordering optimizations are executed within a computational time limit in order to minimize consecutive delays to the existing timetable.In this section, computational tests impose a strict time limit of 90 seconds, which will be attained limiting the execution of the iterative reordering optimizations and the number of reordering possibilities.


### 3.2. Computational Results

The results for inserting additional trains to the existing timetable are summarized in Table2. In this phase, the relative order of exiting trains is not allowed to change; that is, EO are fixed, as described in subproblem (1) in Section 2.3. Each row of Table 2 reports the results for the insertion of one to fifteen additional trains, respectively. It describes the performance of the innovative search method in terms of lower bound, upper bound for consecutive delay of exiting trains, percentage of essential selected arcs, and computation time.Table 2
Results of inserting additional trains to a fixed order timetable (subproblem 1).
Number of additional trains
Lower bound (LB)
Upper bound (UB)
Percentage ofQ* in EN
Time
1
0
0
100
0.02
2
0
0
100
0.26
3
0
0
100
0.27
4
0
0
100
0.29
5
0
0
100
1.26
6
0
0
100
1.56
7
0
0
100
1.93
8
0
0
100
2.90
9
0
0
100
3.38
10
1
143
87.22
3.67
11
1
143
87.29
4.14
12
1
143
87.37
4.62
13
1
423
93.10
16.20
14
2
423
92.91
17.82
15
2
423
93.00
24.17In particular, the percentage of essential selected arcs implies the decrease of search space for an optimal solution. It evaluates the proportion of the edgesQ* in the initial edges EN which need to be decided for an optimal insertion. Q* is the set of edges that must be selected and calculated with the methodology proposed in this paper. It is calculated by (17)PercentageofQ*inEN=thenumberofQ*thenumberofEN×100.Clearly, it is equal to 100% when all of the arcs EN are determined in this phase. In such a case, there is no difference between lower and upper bounds, which represents that the bounds are tight and the exactly optimal insertion is SUB.In the instances of inserting 1–9 trains, the search technique proposed in this paper allows these additional trains to utilize the unoccupied capacities to be inserted without introducing any consecutive delay to the existing timetable. The optimal insertion does not introduce any disturbance to the exiting timetable and it can be got in 0.02 seconds for inserting a train and within 3.5 seconds even when 9 additional trains are added simultaneously.For the scenarios of inserting 10–15 trains, iterative permutation optimizations are executed for decreasing consecutive delays to existing timetable and for narrowing the search range for optimal insertion, as described in subproblem (2) in Section2.3. In each reordering iteration, a pair of trains occurring on the critical path is exchanged and a new graph is computed to find new feasible insertions.Table3 presents the results after reordering within the time limits of 90 seconds. It is apparent that, in the instance of 10 additional trains, the algorithm allows us to find the best solution within 10 seconds and only a pair of additional trains is exchanged to avoid delay for scheduled timetable. For inserting 11 and 12 trains, the best insertions without any consecutive delay also can be calculated efficiently within 20 seconds and two pairs of additional trains are exchanged. The instances for adding 13 to 15 trains are significantly harder. This result may be explained by two factors. Firstly, the computational time required for bound search in each iteration increased with the number of trains to be inserted, as indicated in Table 2. Secondly, as previously analyzed in Section 2, the lower bound is tight if and only if the longest path consists of at most one alternative arc which entering the additional trains N and at most one alternative arc which leaving the additional trains N. With the increase of N, namely, the difference between the number of additional and existing operations becoming smaller, critical path for the new graph G which consists of existing and additional operations has more complicated status. Then the time for the iteration of reorder also increased with the number of trains which are inserted simultaneously. However, we can get a good feasible solution SUB in a short time, which is very important in real-time inserting. On the other hand, since more than 87% of arcs are already determined by the lower bound, the optimal insertions for instances 13–15 can be found with minimal additional effort.Table 3
Results for the scenarios from Table1 with Reordering strategy (sub-problem 2).
Number of additional trains
Total number of changed orders
Lower bound (LB)
Upper bound (UB)
Objective value1
Time2
10
1
0
0
0
10.00
11
2
0
0
0
12.31
12
2
0
0
0
18.65
13
3
0
75
(75)
(90)
14
3
0
75
(75)
(90)
15
3
0
75
(75)
(90)
1The numbers in the parentheses refer to the current best feasible solution (SUB) found when the time limit of 90 seconds was exceeded without an optimal solution being verified.
2The numbers in the parentheses refer to exceed the time limit of 90 seconds.Figures6 and 7 give a detailed view on the performance of iteration procedure for inserting 10 to 15 trains. The upper and lower bounds decrease with the iteration of reordering.Figure 6
The decrease of upper bound.Figure 7
The decrease of lower bound.


## 3.1. Description of Instances

The Hannover-Braunschweig railway area consists of double tracks divided into one long corridor for each traffic direction, one dedicated stop for freight trains, and seven passenger stations, see Figure5. We evaluate a four-hour (8:00 am–12:00 pm) timetable of the year 2003 in the direction of Braunschweig to Hannover. In this experimental study, 9 freight trains and 27 passenger trains, including 17 intercity trains and 10 regional trains, are scheduled in 60 blocking sections in the existing timetable. The total number of exiting operations is 2064. A setup time Eij is set to a constant of 120 seconds for simplification.Figure 5
Hannover-Braunschweig railway area.This insertion problem increases in the number of additional trains which contain a mixture of 120, 160, and 180 km/h trains in order to make the problem more challenging. In particular, the instances of simultaneity inserting 1 to 15 additional trains with various speed are tested in this section.For each instance, unoccupied capacity is used as main resource for additional trains. If and only if consecutive delays are inevitable, then iterative reordering optimizations are executed within a computational time limit in order to minimize consecutive delays to the existing timetable.In this section, computational tests impose a strict time limit of 90 seconds, which will be attained limiting the execution of the iterative reordering optimizations and the number of reordering possibilities.


## 3.2. Computational Results

The results for inserting additional trains to the existing timetable are summarized in Table2. In this phase, the relative order of exiting trains is not allowed to change; that is, EO are fixed, as described in subproblem (1) in Section 2.3. Each row of Table 2 reports the results for the insertion of one to fifteen additional trains, respectively. It describes the performance of the innovative search method in terms of lower bound, upper bound for consecutive delay of exiting trains, percentage of essential selected arcs, and computation time.Table 2
Results of inserting additional trains to a fixed order timetable (subproblem 1).
Number of additional trains
Lower bound (LB)
Upper bound (UB)
Percentage ofQ* in EN
Time
1
0
0
100
0.02
2
0
0
100
0.26
3
0
0
100
0.27
4
0
0
100
0.29
5
0
0
100
1.26
6
0
0
100
1.56
7
0
0
100
1.93
8
0
0
100
2.90
9
0
0
100
3.38
10
1
143
87.22
3.67
11
1
143
87.29
4.14
12
1
143
87.37
4.62
13
1
423
93.10
16.20
14
2
423
92.91
17.82
15
2
423
93.00
24.17In particular, the percentage of essential selected arcs implies the decrease of search space for an optimal solution. It evaluates the proportion of the edgesQ* in the initial edges EN which need to be decided for an optimal insertion. Q* is the set of edges that must be selected and calculated with the methodology proposed in this paper. It is calculated by (17)PercentageofQ*inEN=thenumberofQ*thenumberofEN×100.Clearly, it is equal to 100% when all of the arcs EN are determined in this phase. In such a case, there is no difference between lower and upper bounds, which represents that the bounds are tight and the exactly optimal insertion is SUB.In the instances of inserting 1–9 trains, the search technique proposed in this paper allows these additional trains to utilize the unoccupied capacities to be inserted without introducing any consecutive delay to the existing timetable. The optimal insertion does not introduce any disturbance to the exiting timetable and it can be got in 0.02 seconds for inserting a train and within 3.5 seconds even when 9 additional trains are added simultaneously.For the scenarios of inserting 10–15 trains, iterative permutation optimizations are executed for decreasing consecutive delays to existing timetable and for narrowing the search range for optimal insertion, as described in subproblem (2) in Section2.3. In each reordering iteration, a pair of trains occurring on the critical path is exchanged and a new graph is computed to find new feasible insertions.Table3 presents the results after reordering within the time limits of 90 seconds. It is apparent that, in the instance of 10 additional trains, the algorithm allows us to find the best solution within 10 seconds and only a pair of additional trains is exchanged to avoid delay for scheduled timetable. For inserting 11 and 12 trains, the best insertions without any consecutive delay also can be calculated efficiently within 20 seconds and two pairs of additional trains are exchanged. The instances for adding 13 to 15 trains are significantly harder. This result may be explained by two factors. Firstly, the computational time required for bound search in each iteration increased with the number of trains to be inserted, as indicated in Table 2. Secondly, as previously analyzed in Section 2, the lower bound is tight if and only if the longest path consists of at most one alternative arc which entering the additional trains N and at most one alternative arc which leaving the additional trains N. With the increase of N, namely, the difference between the number of additional and existing operations becoming smaller, critical path for the new graph G which consists of existing and additional operations has more complicated status. Then the time for the iteration of reorder also increased with the number of trains which are inserted simultaneously. However, we can get a good feasible solution SUB in a short time, which is very important in real-time inserting. On the other hand, since more than 87% of arcs are already determined by the lower bound, the optimal insertions for instances 13–15 can be found with minimal additional effort.Table 3
Results for the scenarios from Table1 with Reordering strategy (sub-problem 2).
Number of additional trains
Total number of changed orders
Lower bound (LB)
Upper bound (UB)
Objective value1
Time2
10
1
0
0
0
10.00
11
2
0
0
0
12.31
12
2
0
0
0
18.65
13
3
0
75
(75)
(90)
14
3
0
75
(75)
(90)
15
3
0
75
(75)
(90)
1The numbers in the parentheses refer to the current best feasible solution (SUB) found when the time limit of 90 seconds was exceeded without an optimal solution being verified.
2The numbers in the parentheses refer to exceed the time limit of 90 seconds.Figures6 and 7 give a detailed view on the performance of iteration procedure for inserting 10 to 15 trains. The upper and lower bounds decrease with the iteration of reordering.Figure 6
The decrease of upper bound.Figure 7
The decrease of lower bound.


## 4. Conclusions

The problem of real-time scheduling additional trains without leading to large deviation is considered in this paper. An innovative branch and bound search method and an iterative reordering structure have been developed for this aim. In the fixed permutations phase, the additional trains are inserted using unoccupied capacities to minimize deviation and keep connections of scheduled trains. In the reordering phase, certain permutations are exchanged to insert more trains with acceptable consecutive delays to existing trains.From numerical investigations on a real-life study, it is observed that the lower bounds and upper bounds are very tight for inserting a certain amount of trains simultaneously relative to the number of existing trains. For relative large number of additional trains, moderate amounts of reordering actions are sufficient to handle the disturbances in the reference test cases, and the technique reduces the search space allowing us to solve real and complex problems efficiently.Further research is required on a number of issues. From the computational point of view, the development of bound search and iterative reordering algorithms, which enable finding the optimal solutions for large instances within acceptable computation time, is worthwhile. For the theoretical and practical points of view, it would also be interesting to be combined with rerouting strategies. This can be modeled based on flexible job-shop problem which involves many additional alternative machines and requires more computational effort.



---

*Source: 289072-2015-03-22.xml*