Branch-and-Bound-Based Local Search Heuristics for Train Timetabling on Single-Track Railway Network

Abstract

The modified formulation and two branch-and-bound-based local search heuristic algorithms for train timetabling in single-track railway network in the planning application are proposed. The original local search heuristic is modified such that when a neighbor of a currently tested resolved conflict for improvement is evaluated, the depth-first search branch-and-bound algorithm is employed with two branching rules: least-lower-bound and least-delay-time. The detailed implementation of the proposed heuristic algorithms are described, including the neighborhood definitions of overtaking and crossing conflicts, the procedure to detect overtaking and crossing conflicts, and a recursive procedure for the depth-first search branch-and-bound algorithm. The proposed heuristic algorithms, the original heuristic, the equivalent manual solution method and the exact solution method are compared using a toy problem and four problems (26-train, 50-train, 76-train and 108-train) in the Thailand Southern line railway network, which consisted of 266 single-track segments, 15 double-track segments, 282 stations/sidings, and total distance of 1577 km. The proposed heuristic algorithm with the least-lower-bound branching rule outperforms the other heuristics in terms of the solution quality with up to 2.827 % improvement over the equivalent manual solution method and less than 8 % optimality gap. The proposed heuristic algorithms require longer time to terminate than the original heuristic. The proposed heuristic algorithm with the least-lower-bound branching rule converges faster than that with the least-delay-time branching rule in all test problems. Based on the empirical results, the proposed heuristic algorithms are solvable in polynomial time. Furthermore, the proposed heuristic algorithm with the least-lower-bound branching rule is enhanced by embedding a uniform sampling strategy, and it is found that the total CPU time can be saved by about 50 % with marginally worse solution quality.

1 Introduction

Rail transportation is an efficient and economic transportation mode for passengers and goods. Train schedules are important in the decision-making process of passengers and freight carriers. Train schedules are the basis for locomotive and crew scheduling, and the quality of train schedules affects the investments and operating costs. Essentially, train schedule optimization can help the railway industries increase revenues and decrease costs.

In our view, the contributions of our work are threefold. First, the formulation for a single-track line in Higgins et al. (1996a) is extended to accommodate the railway network, and implemented in IBM ILOG CPLEX Optimization Studio IDE Version 12.6 in order to determine the exact solution as well as the best lower bound. The best lower bound can be used to calculate the optimality gap of heuristic solutions. Second, the local search heuristic in Higgins et al. (1997) is modified so that the depth-first-search branch-and-bound algorithm is used to generate the initial solution and embedded in the local search heuristic algorithm. Two branching rules (least-lower-bound and least-delay-time) are considered in the branch-and-bound-based local search heuristic, which results in two proposed heuristics. The neighborhoods, which account for the segment type (single-track or double-track), for the resolved overtaking and crossing conflicts are explicitly defined. Furthermore, we demonstrate that the total computational time of the proposed heuristics can significantly be improved by incorporating uniform sampling strategies. Third, a real-world problem, i.e., the Southern Line Railway Network in Thailand, which has never been used in the literature, is presented as a benchmark problem.

In the next section, the literature review is provided, followed by the modified formulation and the description of the branch-and-bound-based local search heuristics. The computational results of the real-world case study in Thailand are then shown.

2 Literature Review

The comprehensive surveys of the train-scheduling problem and its inherent connection to other railroad-routing and -scheduling problems are found in Cordeau et al. (1998), Newman et al. (2002) and Meng et al. (2015). The literature on train scheduling can be classified into two categories (Zhou and Zhong 2005): planning and real-time. In planning applications, train scheduling generates train timetables to minimize the overall operational costs and satisfy the passenger and freight traffic demands. The recent advancements of traffic demand models can be found in Karoonsoontawong and Lin (2015), Liu and Huang (2015) and Xiao and Lo (2014), and those of freight transportation modeling can be found in Han et al. (2015), Karoonsoontawong (2015), Karoonsoontawong and Heebkhoksung (2015) and Karoonsoontawong and Unnikrishnan (2013). The train scheduling in planning applications can further be classified into two classes: line planning and schedule generation. In line-planning applications, the train routes, frequencies, and scheduled stop times are determined. Assad (1980) provided a comprehensive review on the line-planning applications. Bussieck et al. (1997) proposed an integer program for line planning in a railroad network. Chang et al. (2000) proposed a multi-objective linear programming formulation to determine the stop and frequency schedules. Li et al. (2011) developed a local search algorithm to optimize train routing on railway network. In schedule generation, the arrival and departure times of each train at passing stations or sidings are determined. In the pioneering paper of Szpigel (1973), the problem of scheduling trains on a single-track line to minimize the total travel time was modeled as a job shop scheduling problem and solved using a branch-and-bound algorithm in Greenberg (1968). The exact solution methods were proposed in the following works: the operational train scheduling problem that minimized the deviation from the planned schedules (Kraay and Harker 1995), lower-bound estimation procedure for the branch-and-bound algorithm (Higgins et al. 1996a), Lagrangian relaxation methods (Brannlund et al. 1998), and branch-and-bound algorithm with effective dominance rules to generate Pareto solutions for the bicriteria train-scheduling problem for high-speed passenger railroad planning (Zhou and Zhong 2005). Our work belongs to the schedule generation category in the planning application. In real-time applications, train scheduling adjusts the daily and hourly train operation timetables to enhance the on-time performance and reliability. Two features are discussed in the literature: efficient heuristic methods (e.g., Adenso-Diaz et al. 1999; Sahin 1999; D’Ariano et al. 2007; D’Ariano and Pranzo 2009; Albrecht 2009) and train schedule reliability (e.g., Kraay and Harker 1995; Higgins and Kozan 1998; Higgins et al. 1996b). Higgins and Kozan (1998), Higgins et al. (1996b), Ma et al. (2002), Zhou and Zhong (2005) and Khan and Zhou (2010) examined the multi-criteria train-scheduling problem.

The train-scheduling problem is non-deterministic polynomial-time hard (NP-hard) (Cai et al. 1998; Caprara et al. 2002); thus, a heuristic approach is typically adopted to generate feasible and suboptimal solutions in large-scale and complex instances. The literature on the mathematical-programming-based solution methods includes the branch-and-bound algorithms (Szpigel 1973; Jovanovic and Harker 1991; Higgins et al. 1996a) and decomposition algorithms (Caprara et al. 2002; Carey 1994a, b; Carey and Lockwood 1995; Brannlund et al. 1998; Zhou and Zhong 2005, 2007). The literature on heuristic solution methods may be classified into two categories: priority rules and complex search procedure. The priority-rule-based heuristics consider the total delay to minimize the travel time (Petersen et al. 1986; Kraay and Harker 1995), schedule deviation and tightness to minimize the deviation (Chen and Harker 1990), train priorities (Petersen et al. 1986) and the number of transported passengers (Adenso-Diaz et al. 1999). The complex search procedures are backtracking search (Adenso-Diaz et al. 1999), look-ahead search (Sahin 1999), and metaheuristic algorithms (Higgins et al. 1996a, 1997; Jong et al. 2013). Our proposed solution method belongs to the complex-search-procedure heuristic category.

Meng and Zhou (2014) systematically classified the studies of train timetabling and train dispatching according to four criteria: scheduling strategy, scheduling measure, formulation type and solution algorithm. First, simultaneous scheduling strategy determines both train route and arrival/departure times of trains, whereas sequential scheduling strategy first specifies train routes and then determine the arrival/departure times of each train. Second, scheduling measure includes time, order, track, route, re-time, re-order, re-track (or local re-route) and re-route (or global re-route). Third, formulation type includes integer programming, mixed integer programming (MIP) and simulation-based model. Solution algorithm includes branch-and-bound (B&B), branch-and-cut-and-price (BCP), alternative graphs (AG), Lagrangian relaxation (LR), heuristics (H), dynamic programming (DP), local search (LS), practical rules (PR), bisection method (BS), column generation (CG) and commercial solver (CS). Table 1 shows the systematic classification of train scheduling literature according to problem type (train time tabling or train dispatching), type of objective (single or multiple) and the above-mentioned four criteria.

Table 1 Classification of train scheduling literature (After Meng and Zhou 2014)

As shown in Table 1, our work belongs to the class of train time tabling, sequential scheduling strategy, schedule measures of time and order, single objective, mixed integer program and the solution algorithm of branch-and-bound-based local search. To our knowledge, our work is the first to embed the branch-and-bound algorithm into the local search heuristic. Our proposed work is based on Higgins et al. (1996a, 1997). Higgins et al. (1996a) developed a mathematical model to optimize train schedules on single-line rail corridors, and the depth-first-search branch-and-bound algorithm. At a node of the branch-and-bound tree, which corresponds to an unresolved train schedule, the first conflict in time with two involved trains is selected, and two branches are possible from this node: (i) a train involved in the conflict is delayed, and (ii) the other train is delayed. For each possible branch, the lower bound is determined, and the branching rule is to select the branch with the minimal lower bound (i.e., the least-lower-bound branching rule). Higgins et al. (1997) proposed the local search heuristic that used the depth-first-search branch-and-bound algorithm to determine the initial solution. The local search heuristic repeatedly shifts the position of a resolved conflict to its neighbors, and any new conflicts resulted from these moves are resolved to the nearest sidings (i.e., the least-delay-time branching rule).

3 Modified Formulation

Higgins et al. (1996a) and Zhou and Zhong (2007) proposed a mixed integer linear program for train scheduling on a single-track rail line. We modify the formulation in Higgins et al. (1996a) for a railway network. The model assumes the followings:

• The railway network is divided into segments, which are separated with sidings or stations.

• Trains can follow one another on a track segment with the minimum distance headway equal to the track length; i.e., only one train is permitted on any track segment.

• For double-track segments, one lane is allocated for inbound trains, and the other lane is allocated for outbound trains.

• Overtaking can occur at any siding or double-track rail segments; crossing can occur at any single-track rail segments.

• Scheduled stops are permitted at intermediate station/siding for any train (Assume that the length of siding track at any station/siding is longer than the length of any train.)

• Each train traverses on a single pre-specified path.

• There is not a segment with more than two tracks.

• There are two tracks at sidings/stations.

The sets, parameters, decision variables, objective function and constraints are described as follows.

3.1 Sets

I :

set of trains

P :

set of rail segments

P ^same_d(i, j):

set of common rail segments for trains i and j, which traverse in the same direction

P(i):

ordered set of rail segments traversed by train i (i.e., the route for train i)

Q :

set of stations/sidings (In this paper, “station” and “siding” are used interchangeably.)

Q(i):

ordered set of stations/sidings traversed by train i (i.e., the route for train i)

P ₁ :

set of single-track segments

P ^opp_d₁ (i, j):

set of common single-track segments for trains i and j, which traverse in opposite directions

P ₂ :

set of double-track segments

D :

set of segment directions (inbound and outbound)

3.2 Parameters

q ₁(p, d):

beginning siding/station of segment p in direction d

q ₂(p, d):

terminal siding/station of segment p in direction d

d _i,p :

direction that train i ∈ I traverses segment p ∈ P(i)

h ^i,j_1,p :

minimum safety headway between trains i, j ∈ I traversing in the same direction on p ∈ P

h ^i,j_2,p :

minimum safety headway between trains i, j ∈ I traveling in opposite directions on p ∈ P ₁

l _p :

length of segment p ∈ P

Y ⁱ _dO :

earliest departure time of train i ∈ I from its origin station

${\underline{v}}_p^i$ :

minimum allowable average velocity of train i ∈ I on segment p ∈ P(i)

${\overline{v}}_p^i$ :

maximum achievable average velocity of train i ∈ I on segment p ∈ P(i) (${\underline{v}}_p^i$ and ${\overline{v}}_p^i$ depend on the physical characteristics of the track segment and the train.)

W _i :

priority weight of train i ∈ I (a higher priority corresponds to a larger priority weight)

S ⁱ _q :

scheduled stop time for train i ∈ I at station q ∈ Q(i)

M :

sufficiently large constant to satisfy the crossing and overtaking constraints

3.3 Decision Variables

A _ijp :

1 if train i ∈ I traverses track segment p ∈ P ^same_d(i, j) before train j ∈ I when trains i and j traverse track segment p in the same direction; 0 otherwise.

B _ijp :

1 if train i ∈ I traverses track segment p ∈ P ^opp_d₁ (i, j) before train j ∈ I when trains i and j traverse track segment p in opposite directions; 0 otherwise.

X ⁱ _a,q :

arrival time of train i ∈ I at station/siding q ∈ Q(i)

X ⁱ _d,q :

departure time of train i ∈ I from station/siding q ∈ Q(i)

X ⁱ _dO :

departure time of train i ∈ I from its origin station

X ⁱ _aD :

arrival time of train i ∈ I at its destination station

z :

objective function value

3.4 Objective Function

$$ \min z={\displaystyle \sum_{i\in I}{W}_i}\left({X}_{aD}^i-{Y}_{dO}^i\right) $$

(1.1)

3.5 Constraints

$$ \begin{array}{cc}\hfill M\cdot {A}_{ijp}+{X}_{d,{q}_1\left(p,{d}_{i,p}\right)}^i\ge {X}_{a,{q}_2\left(p,{d}_{j,p}\right)}^j+{h}_{1,p}^{i,j}\hfill & \hfill \forall i\ne j\in I,p\in {P}^{same\_d}\left(i,j\right)\hfill \end{array} $$

(1.2)

$$ \begin{array}{cc}\hfill M\cdot \left(1-{A}_{ijp}\right)+{X}_{d,{q}_1\left(p,{d}_{j,p}\right)}^j\ge {X}_{a,{q}_2\left(p,{d}_{i,p}\right)}^i+{h}_{1,p}^{i,j}\hfill & \hfill \forall i\ne j\in I,p\in {P}^{same\_d}\left(i,j\right)\hfill \end{array} $$

(1.3)

$$ \begin{array}{cc}\hfill M\cdot {B}_{ijp}+{X}_{d,{q}_1\left(p,{d}_{i,p}\right)}^i\ge {X}_{a,{q}_2\left(p,{d}_{j,p}\right)}^j+{h}_{2,p}^{i,j}\hfill & \hfill \forall i\ne j\in I,p\in {P}_1^{opp\_d}\left(i,j\right)\hfill \end{array} $$

(1.4)

$$ \begin{array}{cc}\hfill M\cdot \left(1-{B}_{ijp}\right)+{X}_{d,{q}_1\left(p,{d}_{j,p}\right)}^j\ge {X}_{a,{q}_2\left(p,{d}_{i,p}\right)}^i+{h}_{2,p}^{i,j}\hfill & \hfill \forall i\ne j\in I,p\in {P}_1^{opp\_d}\left(i,j\right)\hfill \end{array} $$

(1.5)

$$ \begin{array}{cc}\hfill \frac{l_p}{{\overline{v}}_p^i}\le {X}_{a,{q}_2\left(p,{d}_{i,p}\right)}^i-{X}_{d,{q}_1\left(p,{d}_{i,p}\right)}^i\le \frac{l_p}{{\underline{v}}_p^i}\hfill & \hfill \forall i\in I,p\in P(i)\hfill \end{array} $$

(1.6)

$$ \begin{array}{cc}\hfill {X}_{dO}^i\ge {Y}_{dO}^i\hfill & \hfill \forall i\in I\hfill \end{array} $$

(1.7)

$$ \begin{array}{cc}\hfill {X}_{a,q}^i+{S}_q^i\le {X}_{d,q}^i\hfill & \hfill \forall i\in I;q\in Q(i)\hfill \end{array} $$

(1.8)

The objective (1.1) minimizes the weighted sum of the train travel times. Constraint sets (1.2)–(1.3) enforce that for any two trains i and j traversing the same segment p in the same direction, the value of A _ijp is equal to zero if and only if train j traverses segment p before train i, and train j must leave the segment p for the period of h ^i,j_1,p before train i can enter it; i.e., ${X}_{d,{q}_1\left(p,{d}_{i,p}\right)}^i\ge {X}_{a,{q}_2\left(p,{d}_{j,p}\right)}^j+{h}_{1,p}^{i,j}$. Constraint sets (1.2)-(1.3) also enforce that A _ijp  = 1 if and only if train traverses segment p before train j. Constraint sets (1.4)–(1.5) ensure that for any two trains i and j traversing the same single-track segment p in opposite directions, the value of B _ijp is equal to one if and only if train i traverses segment p before train j with the time headway greater than or equal to the minimum safety headway; i.e., ${X}_{d,{q}_1\left(p,{d}_{j,p}\right)}^j\ge {X}_{a,{q}_2\left(p,{d}_{i,p}\right)}^i+{h}_{2,p}^{i,j}$. Constraint sets (1.4)–(1.5) also ensures that B _ijp is equal to zero if and only if train j traverses segment p before train i with the time headway greater than or equal to the minimum safety headway. Constraint set (1.6) ensures that the train travel times on any rail segment are within the corresponding upper and lower limits. Constraint set (1.7) allows the train departure times from their origin stations to be greater than or equal to their earliest departure times. Constraint set (1.8) states that a train departs a station/siding after it arrives at this station and stops there for at least the scheduled stop time.

Figure 1 illustrates a rail network example to clarify certain notations. Given the known routes for trains i and j (i.e., known P(i) and P(i)), the set P ^same_d(i, j) includes all common rail segments (single-track or double-track) for trains i and j, where an overtaking conflict may occur. The set P ^opp_d₁ (i, j) includes all common single-track rail segments for trains i and j where a crossing conflict may occur. Then, the proposed formulation can capture possible crossing and overtaking conflicts in the railway network. The objective function compresses the timetable to maximize the effective capacity of the infrastructure, but it may lead to a less robust timetable. One may obtain a more robust timetable by using the underestimated average train velocities, so that the resulted train timetable is more flexible.

Fig. 1

Rail network example

Specifically, the modifications to the original formulation are the addition of the following notations: P(i), Q(i), P ^same_d(i, j), P ^opp_d₁ (i, j), d _i,p , q ₁(p, d), and q ₂(p, d). P(i) and Q(i) are used to store the path of each train i. P ^same_d(i, j), P ^opp_d₁ (i, j), d _i,p , q ₁(p, d) and q ₂(p, d) are used to efficiently define the constraint sets (1.2)–(1.6). The modifications also change the following notations: h ^i,j_1,p , h ^i,j_2,p , A _ijp and B _ijp . In the original formulation, the headway parameters (h _p ) depend on only the rail segment p. In the modified formulation, the headway parameters (h ^i,j_1,p and h ^i,j_2,p ) can vary and depend on the train pairs and train directions. In the original formulation, the binary decision variables A _ijp (for inbound trains i and j), B _ijp (for inbound train i and outbound train j) and C _ijp (for outbound trains i and j) are used to determine which train first traverses segment p. In the modified formulation, A _ijp is used to determine which train traverses first when trains i and j traverse in the same direction on segment p, and B _ijp is used when trains i and j traverse in opposite directions on segment p; therefore, C _ijp is eliminated. Lastly, the modified formulation guarantees that only a train can traverse a track segment in the same direction, whereas in the original formulation, more than one train can traverse the same segment in the same direction.

4 Branch-and-Bound-Based Local Search Heuristics

Higgins et al. (1997) proposed a local search heuristic, which is a basis of the proposed branch-and-bound-based local search heuristics in this paper. Basically, the local search heuristic considers shifting a resolved conflict to its neighbors and updates the currently best solution. This process iterates until convergence. We make the following major modifications. When evaluating a neighbor of a resolved conflict that is currently tested for improvement, the proposed heuristic uses the depth-first search branch-and-bound algorithm in Higgins et al. (1996a) to obtain the first feasible train schedule with two possible branching rules (least-lower-bound and least-delay-time). The branch-and-bound-based local search heuristic with the least-lower-bound branching rule is denoted as BBLSH-LLB; the heuristic with the least-delay-time branching rule is denoted as BBLSH-LDT. The proposed heuristics require that the resolved conflicts, which occur after the currently considered conflict, are canceled. In contrast, the original local search heuristic (LSH) maintains all other resolved conflicts unchanged and resolves any new conflict to the nearest siding when it evaluates a neighbor of the currently considered conflict. Furthermore, we provide the detailed implementation of the branch-and-bound-based local search heuristic algorithms that explicitly shows (i) the neighborhood definitions of overtaking and crossing conflicts, (ii) the procedure to check whether any two trains traversing a common segment are in an overtaking or crossing conflict, and (iii) a branch-and-bound-based recursive procedure to generate a feasible train schedule.

The additional notations are provided, followed by the basic modules. The generation of an initial resolved train schedule and the branch-and-bound-based local search heuristic are presented.

4.1 Additional Notations

4.1.1 Sets

C :

set of (unresolved or resolved) conflicts

4.1.2 Parameters

num_line _p :

1 for single-track line; 2 for double-track line

h ^i,j_1,p :

safety headway between trains i, j ∈ I traversing in the same direction on segment p ∈ P

h ^i,j_2,p :

safety headway between trains i, j ∈ I traversing in opposite directions on segment p ∈ P ₁

4.1.3 Decision Variables

ES ⁱ _q :

extra stop time for train i ∈ I at station q ∈ Q(i) (The extra stop times are used to delay trains at stations/sidings to resolve conflicts.)

v ⁱ _p :

average velocity of train i ∈ I on segment p ∈ P(i)

resolved _c :

1 if conflict c ∈ C is resolved; 0 otherwise

type _c :

conflict type (1 for overtaking and 2 for crossing)

time _c :

conflict time (For unresolved conflicts, time _c= minimum of the departure times of two trains from the origin sidings of the conflict segment; for resolved conflicts, time _c= arrival time of the delayed train at the conflict siding plus the scheduled stop time)

train1 _c , train2 _c :

two trains involved in conflict c ∈ C

t1 _c , t2 _c :

delay times associated with train1 _c , train2 _c , respectively, to resolve conflict c

segment _c :

segment where conflict c occurs (the two trains intersect)

d_train1 _c , d_train2 _c :

directions of the two trains at c ∈ C on the conflict segment

siding _c :

siding where the delayed train is delayed because of c ∈ C

num_resolved_c :

number of resolved conflicts

ROW_train _c :

train with right-of-way involved in c ∈ C

Delayed_train _c :

delayed train involved in c ∈ C

d_ROW_train _c :

direction of the right-of-way train involved in c ∈ C on the conflict segment

d_Delayed_train _c :

direction of the delayed train involved in c ∈ C on the conflict segment

z ^LB :

lower bound of the optimal objective value

z ^UB :

upper bound of the optimal objective value

z ^best :

objective value of the currently best solution

4.2 Basic Modules

Three basic modules are described: Determine_Schedule, Find_Conflicts, and Find_and_Resolve_Conflicts.

4.2.1 Determine_Schedule Module

For each train i ∈ I, the departure time from its origin station is X ⁱ _dO , train i traverses along rail segments p ∈ P(i) with velocity v ⁱ _p , and the stop time duration for train i at each siding/station q ∈ Q(i) is S ⁱ _q  + ES ⁱ _q . The resulting train schedule is the set of train departure times from and arrival times at sidings/stations, i.e., {{X ⁱ _a,q }, {X ⁱ _d,q }}. This module returns the objective value z, which is an upper bound of the optimal objective value when the resolved schedule is obtained or a lower bound of the optimal objective value for an unresolved schedule. Figure 2 shows the pseudo-code of this module.

Fig. 2

Determine_Schedule module

4.2.2 Find_Conflicts Module

This module determines the two trains (train1 _c and train2 _c ) involved in each conflict c, conflict type (type _c=1 for overtaking, 2 for crossing), conflict time (time _c ), conflict segment (segment _c ), delayed time t1 _c (t2 _c ) when train1 _c (train2 _c ) is delayed and train2 _c (train1 _c ) has the right-of-way as illustrated in Fig. 3, and directions of the two trains on the conflict segment. Specifically, the pseudo-code of this module is given in Fig. 4. This module determines all possible pairs of conflicts. For example, if three trains are involved in a conflict (trains A, B and C) at the same rail segment, this module will determine three conflicts at this rail segment: (i) trains A and B, (ii) A and C and (iii) B and C.

Fig. 3

Delay times t1 and t2 for resolving overtaking conflict and crossing conflict

Fig. 4

Find_Conflicts module

4.2.3 Find_and_Resolve_Conflicts Module

This module resolves one unresolved conflict at a time in ascending order of conflict time with two possible branching rules until it obtains a resolved train schedule. In each iteration of the recursion, after calling the Find_Conflicts module, the earliest conflict is selected with the two trains i ₁ ∈ I; i ₂ ∈ I and the segment p ∈ P where the conflict occurs. If the two trains have different priorities, the train with the higher priority always has the right-of-way, and the train with the lower priority is delayed. The module solves the relaxed program composed of (1.1), (1.6)–(1.8), and the appropriate subset of fixed binary variables from (1.2)–(1.5). The optimal objective value is a lower bound, and the current unresolved train plan is updated.

If the two trains have the same priority, two branching rules are considered: least-lower-bound (Higgins et al. 1996a) and least-delay-time (Higgins et al. 1997). In the least-lower-bound branching rule, two alternatives are considered: (i) train i ₁ ∈ I is delayed, and train i ₂ ∈ I has the right-of-way, and (ii) train i ₂ ∈ I is delayed, and train i ₁ ∈ I has the right-of-way. For each alternative, the module solves the relaxed program composed of (1.1), (1.6)–(1.8), and the appropriate subset of fixed binary variables from (1.2)–(1.5). The optimal objective values are lower bounds: z _case1 and z _case2 . The alternative with the least lower bound is selected as the current unresolved train plan.

In the least-delay-time branching rule, the alternative with the least delay time (min{t1 _c , t2 _c }) is selected, and the train associated with min{t1 _c , t2 _c } is delayed. The module solves the relaxed program composed of (1.1), (1.6)–(1.8), and the appropriate subset of fixed binary variables from (1.2)–(1.5). The optimal objective value is a lower bound, and the current unresolved train plan is updated.

To solve the relaxed program, which is composed of (1.1), (1.6)–(1.8), and the appropriate subset of fixed binary variables from (1.2)–(1.5), the following procedure can be used instead of directly using a mathematical solver. The delayed train and right-of-way train in a resolving conflict c are determined. The extra stop time of the delayed train at the conflict siding is increased by the corresponding delay time (t1 _c or t2 _c ) plus an appropriate safety headway. Then, the Determine_Schedule module is performed to update the train schedule and determine the lower bound (z ^LB) of the optimal objective.

During the recursion, the Find_and_Resolve_Conflicts module can terminate when it obtains a resolved train schedule or when it finds that the lower bound z ^LB is greater than or equal to the best obtained objective z ^best. In the latter case, the module terminates before obtaining a feasible train schedule because the current unresolved train schedule cannot yield a better solution than the currently best schedule. Figure 5 shows the pseudo-code of this module. It is noted that the priority weight plays a role in the Find_and_Resolve_Conflicts module and the Determine_Schedule module. As long as the higher priority train is assigned a larger priority weight, the train with the larger priority weight always has the right-of-way in resolving a conflict. Different priority weights affect the objective function calculated in the Determine_Schedule module. In this paper, the lowest priority is assigned a priority weight of one, and the priority weight increment is one.

Fig. 5

Find_and_Resolve_Conflicts module

4.3 Initial Resolved Train Scheduling Procedure

The procedure is based on the depth-first search branch-and-bound algorithm in Higgins et al. (1996a). We provide the detailed implementation.

• Step 1: Solve the relaxed program composed of (1.1) and (1.6)–(1.8) to obtain an unresolved train plan. Alternatively, the unresolved train plan can be obtained from the Determine_Schedule module by setting all extra stop times to zero (i.e., ES ⁱ _q  = 0 ∀ i ∈ I, q ∈ Q(i)), all velocities to their maximum achievable average velocities (i.e., $\begin{array}{ccc}\hfill {v}_p^i={\overline{v}}_p^i\hfill & \hfill \forall i\in I,\hfill & \hfill p\in P(i)\hfill \end{array}$), and the departure times from their origin equal to their earliest departure times (i.e., X ⁱ _dO  = Y ⁱ _dO ∀ i ∈ I).

• Step 2: Call the Find_and_Resolve_Conflicts Module.

• Step 3: The resulted resolved train plan is an initial solution of the branch-and-bound-based local search heuristics. Set the best obtained objective (z ^best) to the objective value of the initial resolved train schedule.

4.4 Branch-and-Bound-Based Local Search Heuristic Pseudo-Code (BBLSH-LLB and BBLSH-LDT)

BBLSH-LLB and BBLSH-LDT share the same algorithmic steps as follows. A resolved train schedule is represented by the set of resolved conflicts C = {C ₁, C ₂, …, C _|C|} in ascending order of conflict time, where C _c  ∈ C is the c ^th resolved conflict. At the c ^th resolved conflict, C _c  = {Delayed_train _c , ROW_train _c , d_Delayed_train _c , d_ROW_train _c , segment _c , siding _c , type _c , time _c }. The value |C| represents the total number of resolved conflicts in the schedule. BBLSH-LLB and BBLSH-LDT consider changing a resolved conflict to its neighbors, and the other conflicts that occur after the considered resolved conflict are canceled. Then, the Find_and_Resolve_Conflicts module is used to resolve the remaining conflicts. If a neighbor of the considered resolved conflict yields a lower objective value than the best obtained objective (z ^best), the currently best solution is updated and the ordinal number of the considered resolved conflict is stored in ${\widehat{c}}_{z^{best}}$. In the successive iteration, the proposed local search heuristic starts examining the ${\widehat{c}}_{z^{best}}$ resolved conflict, which is the resolved conflict in C whose neighbor generates the best solution found in the previous iteration. Unlike the original local search heuristic that examines every resolved conflict, the proposed local search heuristic cannot find a better solution in examining the first resolved conflict to the ${\widehat{c}}_{z^{best}}$ resolved conflict (these are already examined in the previous iteration). This is because the original local search heuristic does not cancel any resolved conflicts in the examination of a resolved conflict, whereas the proposed local search heuristic cancels all resolved conflicts that take place after the examined resolved conflict. Specifically, the pseudo-code of BBLSH-LLB and BBLSH-LDT is given in Fig. 6.

Fig. 6

Pseudo-code of BBLSH-LLB and BBLSH-LDT

Two neighbors are associated with a resolved conflict. For an overtaking conflict (Fig. 7a–c), the first neighbor must shift the delayed train to be delayed at the immediately preceding siding on the route of the delayed train. The second neighbor must shift the delayed train to be delayed at the immediately successive siding on the route of the delayed train. For example, in the resolved overtaking conflict in Fig. 7a, the delayed train is delayed at siding q. The first neighbor of this resolved overtaking conflict must shift the delayed train to be delayed at siding q-1 as shown in Fig. 7b. The second neighbor must shift the delayed train to be delayed at siding q + 1 as shown in Fig. 7c. Specifically, the two neighbors of a resolved overtaking conflict can be achieved using the two following moves.

Fig. 7

Neighborhood definitions for resolved overtaking conflict and resolved crossing conflict

• Move 1 for a Resolved Overtaking Conflict ĉ (Fig. 7b)

  Update '${X}_{a,q}^{ROW\_ trai{n}_{\widehat{c}}},{X}_{d,q}^{ROW\_ trai{n}_{\widehat{c}}},{X}_{a,q}^{Delayed\_ trai{n}_{\widehat{c}}},{X}_{d,q}^{Delayed\_ trai{n}_{\widehat{c}}}$.

  $$ E{S}_{sidin{g}_{\widehat{c}}-1}^{Delayed\_ trai{n}_{\widehat{c}}}+={X}_{a, sidin{g}_{\widehat{c}}}^{ROW\_ trai{n}_{\widehat{c}}}-{X}_{d, sidin{g}_{\widehat{c}}-1}^{Delayed\_ trai{n}_{\widehat{c}}}+ safety\_{h}_{1, segmen{t}_{\widehat{c}}-1}^{Delayed\_ trai{n}_{\widehat{c}}, ROW\_ trai{n}_{\widehat{c}}} $$

  (Note that x + = y means assigning x + y to the value of x.)

  Set $\begin{array}{c}\hfill sidin{g}_{\widehat{c}}= sidin{g}_{\widehat{c}}-1,tim{e}_{\widehat{c}}={X}_{a, sidin{g}_{\widehat{c}}}^{Delayed\_ trai{n}_{\widehat{c}}}+{S}_{sidin{g}_{\widehat{c}}}^{Delayed\_ trai{n}_{\widehat{c}}}, segmen{t}_{\widehat{c}}= segmen{t}_{\widehat{c}}-1,\hfill \\ {}\hfill d\_ ROW\_ trai{n}_{\widehat{c}}={d}_{ROW\_ trai{n}_{\widehat{c}}, segmen{t}_{\widehat{c}}}\mathrm{and}\ d\_ Delayed\_ trai{n}_{\widehat{c}}={d}_{Delayed\_ trai{n}_{\widehat{c}}, segmen{t}_{\widehat{c}}}\hfill \end{array}$.

• Move 2 for a Resolved Overtaking Conflict ĉ (Fig. 7c)

  Update ${X}_{a,q}^{Delayed\_ trai{n}_{\widehat{c}}},{X}_{d,q}^{Delayed\_ trai{n}_{\widehat{c}}}$. Determine the average velocity of the right-of-way train on segment segment _ĉ  − 1 as shown in Fig. 7c, and update ${X}_{a,q}^{ROW\_ trai{n}_{\widehat{c}}},{X}_{d,q}^{ROW\_ trai{n}_{\widehat{c}}}$.

  $$ E{S}_{sidin{g}_{\widehat{c}}+1}^{Delayed\_ trai{n}_{\widehat{c}}}+={X}_{a, sidin{g}_{\widehat{c}}+2}^{ROW\_ trai{n}_{\widehat{c}}}-{X}_{d, sidin{g}_{\widehat{c}}+1}^{Delayed\_ trai{n}_{\widehat{c}}}+ safety\_{h}_{1, segmen{t}_{\widehat{c}}+1}^{Delayed\_ trai{n}_{\widehat{c}}, ROW\_ trai{n}_{\widehat{c}}}. $$

  Set siding _ĉ  = siding _ĉ  + 1 and segment _ĉ  = segment _ĉ  + 1. Update time _ĉ , d_ROW_train _ĉ , d_Delayed_train _ĉ accordingly.

For a crossing conflict (Fig. 7d–g), the first neighbor must shift the delayed train to be delayed at the immediately preceding siding on the route of the delayed train. The second neighbor must delay the currently right-of-way train at the immediately preceding siding of the conflict segment on the route of the currently right-of-way train, whereas the currently delayed train becomes the right-of-way train. For example, in the resolved crossing conflict in Fig. 7d, the delayed train is delayed at siding q. The first neighbor of this resolved crossing conflict must shift the delayed train to be delayed at siding q-1 as shown in Fig. 7e and f. The second neighbor must delay the right-of-way train in Fig. 7d at siding q + 1, and the delayed train in Fig. 7d becomes the right-of-way train at the second neighbor as shown in Fig. 7g. Specifically, the two neighbors for a resolved crossing conflict can be achieved using the two following moves.

• Move 1 for Resolved Crossing Conflict ĉ (Fig. 7e and f)

  If segment p-1 is single-track (Fig. 7e),

  $$ E{S}_{sidin{g}_{\widehat{c}}-1}^{Delayed\_ trai{n}_{\widehat{c}}}+={X}_{a, sidin{g}_{\widehat{c}}-1}^{ROW\_ trai{n}_{\widehat{c}}}-{X}_{d, sidin{g}_{\widehat{c}}-1}^{Delayed\_ trai{n}_{\widehat{c}}}+ safety\_{h}_{2, segmen{t}_{\widehat{c}}-1}^{Delayed\_ trai{n}_{\widehat{c}}, ROW\_ trai{n}_{\widehat{c}}}. $$

  If segment p-1 is double-track or single-track but non-common for the two trains (Fig. 7f), $E{S}_{sidin{g}_{\widehat{c}}-1}^{Delayed\_ trai{n}_{\widehat{c}}}+={X}_{a, sidin{g}_{\widehat{c}}}^{ROW\_ trai{n}_{\widehat{c}}}-{X}_{d, sidin{g}_{\widehat{c}}-1}^{Delayed\_ trai{n}_{\widehat{c}}}$.

  Set segment _ĉ  = segment _ĉ  − 1 and siding _ĉ  = siding _ĉ  − 1. Update time _ĉ , d_ROW_train _ĉ , d_Delayed_train _ĉ accordingly.

• Move 2 for Resolved Crossing Conflict ĉ (Fig. 7g)

  Swap the delayed train and the ROW train for conflict ĉ.

  Update ${X}_{a,q}^{ROW\_ trai{n}_{\widehat{c}}},{X}_{d,q}^{ROW\_ trai{n}_{\widehat{c}}},{X}_{a,q}^{Delayed\_ trai{n}_{\widehat{c}}},{X}_{d,q}^{Delayed\_ trai{n}_{\widehat{c}}}$.

  $$ E{S}_{sidin{g}_{\widehat{c}}+1}^{Delayed\_ trai{n}_{\widehat{c}}}+={X}_{a, sidin{g}_{\widehat{c}}+1}^{ROW\_ trai{n}_{\widehat{c}}}-{X}_{d, sidin{g}_{\widehat{c}}+1}^{Delayed\_ trai{n}_{\widehat{c}}}+ safety\_{h}_{2, segmen{t}_{\widehat{c}}}^{Delayed\_ trai{n}_{\widehat{c}}, ROW\_ trai{n}_{\widehat{c}}} $$

  Set siding _ĉ  = siding _ĉ  + 1. Update time _ĉ accordingly (segment _ĉ , d_ROW_train _ĉ and d_Delayed_train _ĉ remain unchanged).

5 Computational Results

BBLSH-LLB, BBLSH-LDT, LSH and the equivalent manual solution method are implemented in Eclipse Java EE IDE. The manual solution method (without optimization), which is currently adopted at the State Railway of Thailand and is equivalent to the generation of an initial resolved train schedule with the least-delay-time branching rule. The proposed mathematical program is coded in IBM ILOG CPLEX Optimization Studio IDE Version 12.6, which solves the problem with the branch-and-bound algorithm. The CPLEX commercial solver is employed to solve the modified formulation with the relative MIP gap tolerance of 0.000001. This tolerance sets a relative tolerance on the gap between the best integer objective and the objective of the best node remaining (i.e., best lower bound). These run on a computer with 2.50 GHz Intel Core i7-3537U processor and 8 GB of RAM under Windows 8.1. Two test problems are employed: toy problem and Thailand Southern line railway network. The data are first described; then, the computational results are discussed.

5.1 Data

Two test networks are considered: toy network and Thailand Southern line railway network.

5.1.1 Toy Network Data

A toy problem is a railway line composed of three trains, five rail segments and six stations. Table 2 shows the data for the toy problem.

Table 2 Data for toy problem

5.1.2 Thailand Southern Line Railway Network Data

Thailand has 4431 km of meter gauge railway tracks (excluding mass transit lines) managed by the State Railway of Thailand. There are four main lines: Northern Line, Northeastern Line, Eastern Line, and Southern Line. Most railway tracks are single-track; in the Southern line railway network (our case study), the double-track distance is 64 km, which is 4.07 % of the total distance (1577 km). The test network is the Southern Line Railway Network in Thailand, as shown in Fig. 8. The network is composed of 266 single-track segments, 15 double-track segments, and 282 stations/sidings, and the total distance is 1577 km. Table 3 shows the rail segment data. Table 4 shows the train data. There are four train classes. The priority weight of four denotes the highest priority, and the priority weight of one denotes the lowest priority. The maximum achievable average velocity of the trains (${\overline{v}}_p^i$) is determined from the following equation, which is used by experienced staffs at the State Railway of Thailand: ${\overline{v}}_p^i=\frac{l_p}{l_p/{v}_p^{i, \max }+ acceleration\_tim{e}_p^i+ deceleration\_tim{e}_p^i}$, where v ^i,max _p is the maximum velocity of the train, and acceleration_time ⁱ _p and deceleration_time ⁱ _p are the acceleration and deceleration times for train i on segment p, respectively. The scheduled stop times at stations/sidings vary from zero to 2 min (because of the space limit, these values are not shown). The minimum achievable average velocities (${\underline{v}}_p^i$) are assumed to be zero. We assume that h ^i,j_1,p  = h ^i,j_2,p  = 3 sec onds. Four test problems are considered with different numbers of trains: 26 trains (the first 26 trains in Table 4), 50 trains (the first 50 trains in Table 4), 76 trains (the first 76 trains in Table 4) and 108 trains. There are four train classes.

Fig. 8

Thailand southern line railway network

Table 3 Rail segment data for Thailand southern line railway network

Table 4 Train data for Thailand southern line railway network

5.2 Experimental Results

The exact solution method (CPLEX solver), the equivalent manual solution method, LSH, BBLSH-LLB and BBLSH-LDT are performed in the toy, 26-train, 50-train, 76-train and 108-train problems. Table 5 shows the best objective values, improvement percentage (compared with the equivalent manual solution), optimality gap (compared with the best lower bound from the CPLEX solver), total travel time, total travel time saving (compared with the equivalent manual solution), total CPU time and number of heuristic iterations on the five test problems. Figure 9 illustrates the best resolved train schedule for the 76-train problem from BBLSH-LLB. Note that the improvement percentage, the optimality gap and the total travel time saving are calculated using the equation:

Table 5 Best obtained solutions by exact solution method, equivalent manual solution method, LSH, BBLSH-LLB and BBLSH-LDT for toy problem and Thailand southern line railway network

Fig. 9

Best resolved train schedule found in 76-train test problem

$$ \begin{array}{l}\%\mathrm{improvement}=\frac{100\times \left(\mathrm{best}\ \mathrm{o}\mathrm{b}\mathrm{j}\ \mathrm{f}\mathrm{rom}\ \mathrm{heuristic}-\mathrm{best}\ \mathrm{o}\mathrm{b}\mathrm{j}\ \mathrm{f}\mathrm{rom}\ \mathrm{equivalent}\ \mathrm{manual}\ \mathrm{method}\right)}{\mathrm{best}\ \mathrm{o}\mathrm{b}\mathrm{j}\ \mathrm{f}\mathrm{rom}\ \mathrm{equivalent}\ \mathrm{manual}\ \mathrm{method}}\hfill \\ {}\%\mathrm{optimality}\ \mathrm{gap}=\frac{100\times \left(\mathrm{best}\ \mathrm{o}\mathrm{b}\mathrm{j}\ \mathrm{f}\mathrm{rom}\ \mathrm{heuristic}-\mathrm{best}\ \mathrm{lower}\ \mathrm{b}\mathrm{o}\mathrm{und}\ \mathrm{f}\mathrm{rom}\ \mathrm{CPLEX}\right)}{\mathrm{best}\ \mathrm{lower}\ \mathrm{b}\mathrm{o}\mathrm{und}\ \mathrm{f}\mathrm{rom}\ \mathrm{CPLEX}}\hfill \\ {}\begin{array}{l}\mathrm{Total}\ \mathrm{Travel}\ \mathrm{Time}\ \mathrm{Saving}=\mathrm{Total}\ \mathrm{Travel}\ \mathrm{Time}\ \mathrm{o}\mathrm{f}\ \mathrm{the}\ \mathrm{Equivalent}\ \mathrm{Manual}\ \mathrm{Solution}\ \\ {}\kern11.25em -\mathrm{Total}\ \mathrm{Travel}\ \mathrm{Time}\ \mathrm{o}\mathrm{f}\ \mathrm{Heuristic}\end{array}\hfill \end{array} $$

In terms of computational time, the equivalent manual solution method takes the shortest total computational time for all test problems. The exact solution method takes the longest CPU time (4.72 × 10⁻⁵, 3.409, 5.278, 21.425 and 25.339 h) to terminate at the optimality gaps of 0, 2.283, 3.150, 4.594 and 8.387 % for the five problems, respectively. LSH takes the same order of magnitude of total CPU time as the equivalent manual method. BBLSH-LLB and BBLSH-LDT require much longer total CPU times to terminate. The largest computational burden for BBLSH-LLB and BBLSH-LDT is from the recursive sub-procedure Find_and_Resolve_Conflicts. LSH takes fewer heuristic iterations to terminate (1, 1, 2, 5 and 6 iterations for the five test problems) than BBLSH-LLB (2, 6, 6, 4 and 7 iterations) and BBLSH-LDT (2, 6, 6, 5 and 7 iterations). Thus, the branch-and-bound-based local search heuristics find better solution with the sacrifice of longer total CPU time when compared with the LSH and the equivalent manual solution method.

In terms of solution quality, the equivalent manual solution method has the worst performance for all test problems. LSH yields its best solutions with 0, 0, 0.00129, 0.02408 and 0.04298 % improvement (the total travel time savings were 0, 0, 1.166, 32.963 and 62.717 min) and 3.165, 3.690, 4.213, 5.823 and 8.796 % optimality gap for the toy, 26-train, 50-train, 76-train and 108-train problems, respectively. BBLSH-LLB and BBLSH-LDT yield the same best solutions with 2.827, 0.7248 and 0.6328 % improvement (the total travel time savings were 28.00, 355.33 and 388.50 min) and 0.2484, 2.939 and 3.555 % optimality gap for the toy, 26-train and 50-train problems, respectively. For the 76-train problem, BBLSH-LLB (with 0.5659 % improvement, 5.249 % optimality gap, total travel time saving = 372.7 min, and total CPU time =2.548 h) outperforms BBLSH-LDT (with 0.5275 % improvement, 5.290 % optimality gap, total travel time saving = 354.67 min and total CPU time = 2.578 h) on both solution quality and total CPU time. Similarly, for the 108-train problem, BBLSH-LLB (with 0.80752 % improvement, 7.963 % optimality gap, total travel time saving = 885.27 min and total CPU time = 12.442 h) outperforms BBLSH-LDT (with 0.61497 % improvement, 8.173 % optimality gap, total travel time saving = 642.42 min and total CPU time = 13.160 h) on both solution quality and total CPU time. Figure 10 shows the convergence characteristics of the exact solution method and the three heuristics for the 26-train, 50-train, 76-train and 108-train problems. For all test problems, LSH converges notably fast to worse solutions than BBLSH-LLB and BBLSH-LDT. BBLSH-LLB converges faster than BBLSH-LDT on all test problems. By the time BBLSH-LLB and BBLSH-LDT converge, the CPLEX solver just finds much worse solutions. Figure 11 shows the relationships of the total CPU time and problem size for LSH, BBLSH-LLB and BBLSH-LDT. From our empirical results, BBLSH-LLB and BBLSH-LDT appear to be of polynomial time because the total CPU time is a polynomial expression in terms of the problem size.

Fig. 10

Convergence characteristics of exact solution method (CPLEX Solver), local search heuristic and two branch-and-bound-based local search heuristics in 26-train, 50-train, 76-train and 108-train problems

Fig. 11

Relationships of total CPU time and problem size for local search heuristic and two branch-and-bound-based local search heuristics

The computational time of the branch-and-bound-based local search heuristics in the 108-train problem may be improved with the trade-off of the solution quality. Two sampling strategies for selecting the resolved conflicts to be tested for improvement in BBLSH-LLB (Step 2 in Fig. 6) are considered. First, BBLSH-LLB-ES denotes the BBLSH-LLB algorithm that selects every second resolved conflict in the main iteration of local search heuristic. The sampling strategy in BBLSH-LLB-ES allows the algorithm to examine only half of the resolved conflicts from the uniform distribution. Second, BBLSH-LLB-ET denotes the BBLSH-LLB algorithm that selects every third resolved conflict in the main iteration of local search heuristic. BBLSH-LLB-ET examines one-third of the resolved conflicts from the uniform distribution. Table 6 shows the results of BBLSH-LLB-ES and BBLSH-LLB-ET in the 108-train problem. As expected, the total CPU time (6.504 h) by BBLSH-LLB-ES is decreased by approximately half of that (12.442) by BBLSH-LLB. The solution quality (8.070 % optimality gap) by BBLSH-LLB-ES is slightly worse than that (7.963 % optimality gap) by BBLSH-LLB. Interestingly, BBLSH-LLB-ET yields marginally worse solution than BBLSH-LLB-ES, whereas BBLSH-LLB-ET can save the total CPU time by 1.022 h. It is noted that the abbreviations for different local search heuristic algorithms developed in this article are summarized in Table 7.

Table 6 Best obtained solutions by BBLSH-LLB-ES and BBLSH-LLB-ET for 108-train problem

Table 7 Abbreviations for different local search heuristic algorithms

6 Summary and Conclusions

We consider the train-scheduling problem in a single-track railway network in the planning application. The formulation for a rail line in Higgins et al. (1996a) was modified to accommodate a railway network. Two proposed branch-and-bound-based local search heuristic algorithms are based on the respective least-lower-bound branching rule (Higgins et al. 1996a) and least-delay-time branching rule (Higgins et al. 1997). The proposed branch-and-bound-based local search heuristic algorithms consider changing a resolved conflict to its neighbors, and the other conflicts that occur after the considered resolved conflict are canceled. Then, the proposed algorithms resolve the remaining conflicts with the two branching rules. In resolving any conflict between trains i and j with the least-lower-bound branching rule, two cases (case 1: delayed i and right-of-way j; case 2: delayed j and right-of-way i) are assessed in terms of the lower bound of objective function. The case with delayed i and right-of-way j is chosen if the lower bound of objective function associated with delaying train i is less than the lower bound associated with delaying train j. On the other hand, in resolving a conflict with the least-delay-time branching rule, the two cases are assessed in terms of local delay time. The case with delayed i and right-of-way j is chosen if the local delay time associated with delaying train i is less than that associated with delaying train j; i.e., a conflict is resolved to the nearest siding. The detailed implementation of the two proposed heuristic algorithms is presented. The test networks are the toy network and the southern line railway network in Thailand, which is composed of 266 single-track segments, 15 double-track segments, 282 stations/sidings and a total distance of 1577 km. Four test problems on the Thailand southern line railway network are considered with different numbers of multi-class trains: 26-train, 50-train, 76-train and 108-train. The exact solution method (CPLEX solver), the two proposed heuristic algorithms, the original local search heuristic, and the equivalent manual solution method used in the State Railway of Thailand are performed for the five test problems. The results are compared in terms of the solution quality, computational time, and convergence speed.

In terms of computational time, the equivalent manual solution method and the original local search heuristic take the same order of magnitude of total CPU time. The proposed heuristic algorithms require longer total CPU time and more heuristic iterations to terminate than the original local search heuristic, which allows the proposed heuristic algorityms to find better solution with the sacrifice of longer total CPU time. The exact solution method spends the longest time to determine solutions with the known optimality gaps. In terms of solution quality, the original local search heuristic yields its best solutions with up to 0.04298 % improvement and up to 8.796 % optimality gap compared to the equivalent manual solutions for the five problems. The proposed heuristic algorithm with the least-lower-bound branching rule yields its best solutions with up to 2.827 % improvement and up to 7.963 % optimality gap. The proposed heuristic algorithm with the least-delay-time branching rule yields its best solutions with up to 2.827 % improvement and up to 8.173 % optimality gap. For all test problems, the proposed heuristic algorithm with the least-lower-bound branching rule converges faster than that with the least-delay-time branching rule. From the empirical results, the proposed heuristic algorithms appear to be solvable in polynomial time.

Two sampling strategies based on the uniform distribution are incorporated into the proposed heuristic algorithm with the least-lower-bound branching rule in order to shorten the computational time. The first sampling strategy allows the algorithm to examine only half of the resolved conflicts from the uniform distribution; i.e., the algorithm examines every second resolved conflict in the local search iteration. The second sampling strategy allows the algorithm to examine one-third of the resolved conflicts from the uniform distribution; i.e., the algorithm examines every third resolved conflict in the local search iteration. The proposed heuristic algorithm with the least-lower-bound branching rule and the two sampling strategies is performed in the 108-train problem. The best solutions from the two sampling strategies are almost the same, and slightly worse than the algorithm without a sampling strategy. The two sampling strategies can save the total CPU time by about 50 % when compared with the algorithm without a sampling strategy.

This paper can be extended in multiple directions. The immediate improvement of the proposed formulation is to consider that trains can be delayed at a feasible siding/station within the maximum allowable extra delayed times. In the proposed formulation and heuristics, two parameters may be used: δ ⁱ _q  = 1 if train i ∈ I can be delayed at station q ∈ Q(i) and 0 otherwise; UB_ES ⁱ _q  = maximum allowable extra stop time for train i ∈ I at station q ∈ Q(i). Then, the constraint set (1.8) may be replaced by the following constraints:

$$ \begin{array}{cc}\hfill {X}_{a,q}^i+{S}_q^i+E{S}_q^i={X}_{d,q}^i\hfill & \hfill \forall i\in I;q\in Q\hfill \end{array}(i) $$

(1.9)

$$ \begin{array}{cc}\hfill 0\le E{S}_q^i\le {\delta}_q^i\cdot UB\_E{S}_q^i\hfill & \hfill \forall i\in I;q\in Q(i)\hfill \end{array} $$

(1.10)

Constraint set (1.9) states that the train departure time from a station/siding is equal to the summation of the train arrival time, scheduled stop time and extra stop time at this station. Constraint set (1.10) enforces that the extra stop time is non-negative and may not be greater than the maximum allowable extra stop time. If train i cannot be delayed at station/siding q, then δ ⁱ _q is equal to zero, which yields ES ⁱ _q  = 0. If train i can be delayed at station/siding q, then δ ⁱ _q is one, which yields ES ⁱ _q  ≤ UB_ES ⁱ _q . The proposed branch-and-bound-based local search heuristics can be modified to accommodate the additional constraints. The branch-and-bound-based local search heuristics may be used as a sub-procedure in a metaheuristic algorithm. The extension can be made for the multi-criteria train timetabling problem.