Optimization Model for Rail Line Crossover Design Considering the Cost of Delay

Abstract

In this study, we introduce a method to optimally select the crossover locations of an independent rail line from a set of possible crossover locations considering a fixed number of crossovers that must be used in the design. This optimal selection aims to minimize the cost of passenger delay. Previous research showed that including passenger delay in the decision of rail design choices could be beneficial from economic and societal perspectives. However, those studies were only able to evaluate a few alternatives, because the degraded schedules had to be determined manually. In this research, we introduced an integer nonlinear model to find the best crossover design. We further developed an algorithm to evaluate a set of crossovers and determine the cost of delays for all segments on a rail line given a set of potential disruptions. The monetized cost of passenger delays was used to analyze the tradeoff between the unreliability costs emerging from the delay of passengers in the case of disruptions, and the total number of required crossovers. Our model was applied on a light rail line in Bergen (Norway) resulting in 10% reduction in relation to passenger delays without increasing the number of crossovers; thus, ensuring that there were no additional costs.

Rail transport is becoming increasingly important in many countries. Owing to the increase in train travelers, increasing numbers of trains operate on the same infrastructure ( 1 ). This results in a smaller headway among successive trains and, thus, unexpected events, such as a switch failure, might have a significant impact on rail operations. An unexpected event, for example, may cause severe delays to a significant number of travelers. Because of this pressure, rail infrastructure managers strive to minimize the total impact of service disruptions. One possible action is to design the infrastructure in a reliable manner by installing a limited number of risky rail parts (e.g., level crossings and switches), and by placing those parts at optimal locations to ensure sufficient detour possibilities. To provide an indication of the failure probability of different elements, Moridpour and Hesami, using data from Melbourne, Australia, showed that more than 12% of crossings, 8% of crossovers (pairs of switches), and 3% of straight track segments exceeded their maintenance limit within a 4-year period ( 2 ). Because of operational pressures, it is of paramount importance to design railway infrastructure with an optimal number of crossovers, tracks, and level crossings and the ensure the placement of risky rail parts at optimal locations.

This study focuses on the optimization of crossovers on a independent, double-track rail line. These simple rail lines do not have the option to reroute vehicles via another part of the network. There is only one option when operating the line in the case of disruptions: splitting the line into two circuits. The best method to split the line depends on the locations of the crossovers and of the disrupted track part. An example of a degraded mode on an independent, double-track rail line split into two circuits is shown in Figure 1. In relation to terminology, a crossover is a pair of switches that connects two parallel rail tracks, allowing a train on one track to cross over to the other. A switch or turnout is a mechanical installation enabling railway trains to be guided from one track to another. The term crossing is also used to indicate the common point of two rails.

Figure 1.

Example of an alternative operation schedule in the case of disruption.

In this paper, we introduce a method to determine the circuits that emerge in the case of a disruption. This research aimed to develop a decision support model to determine the optimal placement strategy for several crossovers.

The location and number of crossovers are optimized by minimizing passenger delay considering the possible disruptions that typically appear in the network. To this end, an algorithm was developed to determine the best degraded schedule for all disruption scenarios. In this work, the reliability cost of a rail line was the total monetized cost of delay, which was defined as the difference between the scheduled and actual travel time for all passengers. In an optimal design, the purchase and maintenance costs of an extra crossover should be justified by the benefits of improved reliability in the case of disruptions. Multiple performance indicators from previous research are used to evaluate the suggested designs and to compare them to the actual design.

The remainder of this study is structured as follows: we first review the past literature and detail the contributions that our work affords. Second, the methodology of our study is presented. Third, the results of our case study concerning a light rail line in Bergen (Norway) are described. Finally, the conclusions and recommendations of this study are provided.

Literature Review

In this literature review, we first present the state of the art for indicators that assess disturbance impact on rail networks. After that, we review infrastructure design methods and highlight the tradeoff between infrastructure cost and flexibility. This clarifies the benefit of including passenger delay in the design choices of rail projects. The literature review ends by detailing the contribution of our work.

Disturbance Impact on Public Transport Networks and the Role of Crossovers

The impact of disturbances on public transport (PT) operators can be analyzed by treating the service timetable as a variable and incorporating the delays in the performance measures ( 3 , 4 ). In a more holistic approach, Quaglietta and Punzo applied the Sobol variance-based method to identify a configuration of the infrastructure components (e.g., number of rail tracks) and the operational schedule to improve different key performance indicators, such as the level of capacity, the punctuality of the service, and energy savings ( 5 ). These planning approaches strive to consider the impact of disturbances on the long-term performance of the transportation system. Corman and D’Ariano evaluated several adaptation strategies to respond to travel time and delay propagation because of disturbances (e.g., cancellation of services, rerouting, and shuttles) ( 6 ). In particular, the concept of bus bridging as an effective measure during rail disturbances has been investigated in several past studies ( 7 – 11 ). Of particular interest is the work of Pender et al. that investigated the importance of rail crossover placements to the supporting bus services that can be used for bridging ( 8 ).

Disturbances in PT networks can be caused by recurrent or nonrecurrent events. Recurrent events occur because of normal PT demand variations, different driver behaviors, traffic signals, and so on. It is not possible to use crossovers to reduce the delay impacts of these variations. Nonrecurrent events occur from failures of an infrastructure component, failures in operator service, irregular demand fluctuations, bad weather, incidents, roadworks, and public events ( 12 – 16 ). Nonrecurrent disturbances reduce infrastructure availability and lead to adjustments in the supplied PT services. Crossovers might help to reduce the disturbance impact of nonrecurrent disruptions because they can facilitate the deployment of flexible schedules on the rail network.

To determine the disruption probability of a rail segment for nonrecurrent disruptions, it is important to know the frequency of breakdown of rail infrastructure components and the duration of these disruption events. These two combined are called exposure ( 17 ). The frequency and duration of disruptions are factors that determine risk in a railway line. In rail networks, signal, switch, and power supply failures are the most critical infrastructure disruption components ( 18 ). However, a lot of disruptions are caused by noninfrastructure-related disturbances such as suicide attempts, vehicle breakdowns, and blockages. Existing research has used historical data from a set of disruption events to predict disruption probability and duration distributions ( 18 , 19 ). When a link on a rail network is blocked, an alternative schedule can be used to circumvent the disrupted link. However, the possibility of implementing an alternative schedule depends on the availability of links in the network (e.g., if we have more switches, there are more possibilities for implementing alternative schedules). Thus, to increase alternative schedule options, operators can use additional crossovers.

When a disruption occurs, there is a transition phase before a disruption-tailored timetable can be operational (e.g., vehicles and drivers have to be moved to particular locations) ( 20 ). This process of disruption schedules and transition phases is called the “bathtub” model. While the bathtub model is widely known and used to conceptualize traffic states during disruptions, only limited research efforts have been devoted to analyzing and modeling railway disruption management. Ghaemi et al. provide a review of rescheduling models for disruptions, and conclude that only a few studies consider all three phases (namely, the first phase is the transition plan from the original timetable to the disruption timetable, the second phase is the disruption timetable, and the third phase is the transition plan from the disruption timetable to the original timetable) ( 21 ). The transition phases are often neglected when the network is small and service frequencies are high.

Generally, PT operators prefer extra travelers to bolster their revenues. Van Loon et al. showed that small reliability improvements on some lines in the Netherlands were able to increase ridership by 10% ( 22 ). Because of the importance of reliability, one might wonder why railway designs do not have as many crossovers as possible to increase network flexibility in the case of disruptions. The main reason is that crossovers are also vulnerable: they break down often, and their purchase and maintenance costs are high.

Modeling the Tradeoff of Infrastructure Cost and Flexibility

To tackle the aforementioned tradeoff of crossover flexibility versus cost, research has investigated the usefulness of crossovers in rail networks. During a network’s design, one could consider removing a crossover or placing it at a different location. Asset management studies are often used to determine the crossover cost factor of the aforementioned tradeoff. However, there is a lot of variation in these costs. Crossover-related costs depend on several factors, such as network design, maintenance frequency, operation schedules, and rolling stock properties. Therefore, complex models are needed to calculate these costs.

The costs and benefits in relation to network flexibility when we add crossovers are also difficult to calculate. Costs could be addressed from a passenger point of view (demand side) or a railway manager point of view (supply side). Concerning the supply side point of view, there are several network connectivity indicators linked to the design of crossovers ( 23 ). Nieminen proposed a connectivity indicator that simply counts the number of direct connections to the node ( 24 ). Another supply-based approach to evaluate the benefits of a crossover is to count the number of times that the crossover is used per year in disruption schedules ( 25 ).

Previous research can also determine the impact of disruptions on infrastructure networks by addressing the reliability of a rail network. Zhang et al. investigated the contribution of a node to network connectivity to calculate the cost of disruptions by using the repair cost, other disruption costs, and lost ticket sales ( 26 ). More advanced studies calculated the impact on all vehicles in the network ( 27 – 31 ). Another way to express the impact of disruptions is to calculate the percentage of vehicle schedule deviations within a certain bandwidth. Using this method, only trains delayed more than a predetermined number of minutes are considered to be delayed. This could be monetized by giving a penalty to those trains. When assuming that the examined period is homogeneous (for instance, peak hour on working days in a month), the passenger demand pattern on the line is fixed and all passengers can board the first arriving vehicle, passenger waiting times can be defined as half the headway ( 32 – 36 ). Assuming this, delays can be calculated for networks with multiple lines, as in research undertaken by Landex and Nielsen ( 37 ). More specifically, Landex and Nielsen modeled train delays with simulations for a network with four rail lines by excluding the rerouting choices of the passengers (e.g., passengers wait until the train moves again) ( 37 ). However, the disruption impact depends on the rescheduling options for passengers. In addition, the number of affected passengers is important. Therefore, standalone supply-based research is not the most unbiased option to assess the performance of rail line designs.

Research has also included passenger-based indicators to investigate the tradeoff of crossover placement (e.g., a possible way of addressing the tradeoff is by summing the impact of disruptions to all passengers [26, 35, 38–41]). Considering the impact of a disruption to all passengers requires more data, but it is a fairer way of assessing the reliability impact. Under this consideration, higher priority is placed on increasing the design flexibility for areas with more travelers, which means that the total societal and economic benefits are higher.

In a railway network reliability study, Yap et al. addressed the tradeoff of crossover flexibility versus -cost, by calculating the total delay cost for all passengers ( 19 ). To consider the tradeoff between purchase/scheduled maintenance costs and the unreliability impact, Yap et al. compared the unreliability costs to the life cycle costs of a railway project via a cost–benefit analysis ( 19 ). The vulnerability of the links was modeled using a Monte Carlo simulation. The objective function included investment costs, reduced comfort costs, costs for unserved demand, and cancellation costs. Tahmasseby et al. used more advanced factors by using an objective function with the following cost factors: travel costs including regular travel time variations, service operation costs, infrastructure investment and maintenance costs, extra travel costs in nonrecurrent conditions, trip cancellation costs in nonrecurrent conditions, extra operation costs in nonrecurrent conditions, and extra investment costs for building infrastructure shortcut possibilities for detours ( 40 ). Because of the model’s complexity owing to the high number of cost components, Tahmasseby et al. only evaluated a couple of bypass measures; they calculated the robustness of adding a bypass railway in The Hague ( 40 ). The complexity of this work would make it hard to use as an optimization model for a set of crossovers and the disruption scenarios were defined manually.

Contribution

Although extensive research has been carried out on the performance of rail networks considering crossover flexibility and crossover-related costs, to the best of the authors’ knowledge, no studies include passenger delays in an optimization problem for the choice of crossover locations. Previous research showed that including passenger delay in design choices can be beneficial for passengers, operators, and railway project clients, and introduced methods to calculate passenger delay.

To fill this research gap, our research introduces a crossover location choice optimization model that considers passenger delays. The explicit contributions of this study include

• a novel optimization model for the choice of crossover locations from a passenger point of view by considering passenger delays;

• analysis of the tradeoff between the unreliability costs emerging from passenger delays in the case of disruptions and the total number of required crossovers; and

• an algorithm to automatically determine the degraded schedules after any disruption.

Methodology

Assumptions

The following assumptions were made in the modeling of this work:

• (A1) Multiple disruptions do not occur at the same time;

• (A2) Capacity constraints of all PT vehicles are neglected, as in Yap et al. ( 42 );

• (A3) Transition phases from the regular schedule to the degraded schedule and back to the regular schedule are neglected, which is only possible for high-frequency rail lines (i.e., a vehicle every 5 to 10 min), because more drivers and vehicles are available on all segments of such lines ( 20 , 21 );

• (A4) In the case of disruption, passengers do not cancel their trip and they do not use private vehicles;

• (A5) Regular, alternative PT options exist for all station pairs.

One can identify four types of crossovers, as presented in Figure 2. Type 1 is placed in the facing position. At facing points, one line splits into two in the direction of travel. Type 2 is placed in the trailing direction. At trailing points, two tracks merge into one in the direction of travel ( 43 ). Types 3 and 4 are tail track crossovers, which can be used to turn rolling stock in the other direction or to park a vehicle.

Figure 2.

Crossover types: facing crossover, trailing crossover, tail track (outbound), tail track crossover (inbound).

Let us consider an independent rail line with two tracks. Figure 3 represents a schematic overview of a fictitious rail line with four crossovers and five stations. The two fixed crossovers near the end of line stations are necessary for the regular timetable and they cannot be removed. The two possible crossovers are design choices and could be added if they were deemed beneficial when running our model. That is, the goal of our model is to find the optimal crossovers from the set of available design choices (possible crossovers).

Figure 3.

Representation of a rail line with two tracks: stations, fixed (necessary) crossovers (in black), and possible crossovers (in purple) that could be included in our design.

Modeling the Degraded Schedules in the Case of Disruptions

For each of the disruptions, $k\in K$ , the degraded schedule with its circuits has to be determined. A degraded schedule is based on operating the line without using the disrupted track section. If the crossover design, $x=(x_1,...,x_i,...,x_{|I|})$ , changes, the degraded schedule changes as well, because more stations might be reachable. That is, there is a specific degraded schedule in the case of a disruption, $k\in K$ , corresponding to a crossover design, $x$ . To find this degraded schedule, our algorithm was based on the ideas expressed in the work of Neves ( 44 ). Figure 4 shows a flow chart of the overall logic of our proposed model. We start with a given set, $\mathcal{F}$ , of feasible crossovers designs, $x\in \mathcal{F}$ . For instance, the feasible set, $\mathcal{F}$ , might include all potential crossover designs that include up to $\gamma$ additional crossover locations. Then, for each crossover design, $x\in \mathcal{F}$ , we determine its degraded schedule for any disruption, $k\in K$ , and we compute the incurred passenger delay costs given an occurrence probability, $r_k$ , and duration, $v_k$ , for this disruption. In the end, we select the crossover design, $x\in \mathcal{F}$ , with the lowest passenger delays.

Figure 4.

Flowchart of the methodology.

Our model is able to determine the degraded schedule for an independent, double-track line that operates under high frequency. The transition phases were not modeled as they have minor influence on lines with a small headway ( 20 ). The degraded schedule consists of two circuits (one serving the line segment before the disruption and another one serving the line segment after it). In case it is not possible to use two circuits for a specific disruption, we used only one.

Table 1 presents the possible turning options for degraded operation schedules. If one of the two track directions is unavailable, the track direction could be alternated to make sure both directions could still be operated. However, because one track has to be used in two directions, the vehicle headway is limited by the ride times. The turning options in Table 1 are commonly used for light rail and trams ( 44 ).

Table 1.

Turning Options for Degraded Operation Schedules: The Different Options are Visualized for Circuit 1. Circuit 2 has the Same Degraded Schedule in All Situations

Degraded operation options on a rail line
Regular operation and legend Regular operation and legend
A: Turning on a crossover beyond the station
B: Turning on a regular crossover ahead of the station
C: Turning on a regular crossover ahead of the station and ride further
D: Avoid the disrupted track and facilitate a transfer possibility
E: Single track operation between two stations, without using crossovers

To find the degraded schedule for all disruptions, $k\in K$ , for a given crossover combination setting, $x$ , we introduced the algorithm presented in the flowchart of Figure 5 making use of crossover Types 1 and 2 presented in Figure 2. This rule-based algorithm is applicable for rail lines that do not share lanes with road vehicles. The algorithm in Figure 5 tries to determine the circuits in the case of a disruption, $k\in K$ , following the sequence presented in Table 1. First, it tries to find a route by turning beyond the station on a tail track or regular crossover (Table 1, Situation A). If this is not possible, the algorithm tries to find a crossover ahead of the last reachable station (Table 1, Situation B). More stations can be reached by riding in two directions on a single track (Table 1, Situation C). If only one track is blocked, it is sometimes possible to connect all stations by facilitating a transfer (Table 1, Situation D). If the stations are still not connected, a single track operation service is an option by using only one of the two tracks (Table 1, Situation E). This option has a disadvantage: only one vehicle can be used because passing is not possible. Therefore, the waiting times for passengers might be high. If the disruption occurs at the beginning or the end of the line, it is possible that only one circuit would be used on one side of the disruption. The output of the algorithm is the information about the optimal circuits for a particular disruption: the stations that can be reached and the crossovers used.

Figure 5.

Flowchart that returns the disruption schedules for the circuit ahead of the disruption for disruption scenarios in $k\in K$ , for a given crossover design, x. The circuit beyond the disruption is calculated in the same way, but in the opposite direction. NaN stands for not a number.

Before proceeding to the modeling, we introduce the nomenclature in Table 2.

Table 2.

Nomenclature

Sets
$I$	Set of potential (possible) crossovers, $I=〈1,...i,...,|I|〉$ ;
$F$	Set of fixed crossovers needed to operate the line in normal conditions, $F=〈1,...f,...,|F|〉$ ;
$O$	Set of stations of the rail line, $O=〈1,...o,...,|O|〉$ ;
$K$	Set of disruption scenarios, $K=〈1,...k,...,|K|〉$ ;
Parameters
$t_k^{\mathrm{start}}$	The starting location of a disruption, $k$ , relative to the first station of the line;
$t_k^{\mathrm{end}}$	The location where disruption $k$ ends;
$t_k^{\mathrm{track}}$	Parameter indicating the disrupted track owing to disruption scenario $k$ (outbound track = 1, inbound track = 2, both tracks = 3);
$y_{o,d}^{\mathrm{walk}}$	The travel time on foot from $o$ to $d$ , where $o\in O$ and $d\in O$ ;
$y_{o,d}^{\mathrm{reg}}$	The travel time using the rail line in normal operations from $o\in O$ to $d\in O$ ;
$y_{o,d}^{\mathrm{pt}}$	$y_{o,d}^{\mathrm{pt},\mathrm{mp}},y_{o,d}^{\mathrm{pt},\mathrm{ap}},y_{o,d}^{\mathrm{pt},\mathrm{re}}$ : the travel time from $o\in O$ to $d\in O$ using an alternative public transport mode for different periods of the day (mp: morning peak; ap: afternoon peak; re: outside peak hours);
$y_{o,d,i}^{\mathrm{cross}}$	The extra riding time from $o$ to $d$ over the rail line when riding over crossover $i$ with a reduced speed, relative to the regular ride time without crossovers;
$b_{o,i}$	The ride time from crossover $i$ to station $o$ and back to $i$ . This is needed to calculate the headway if one track is (partly) used for two directions in the circuit;
$r_k$	The probability (per year) for disruption scenario $k$ to occur;
$v_k$	The average duration of disruption scenario $k$ ;
$j_{o,d}$	The average demand from $o$ to $d$ for our rail line;
$n_i$	The crossover type information for crossover $i\in I$ ;
$e_i$	The distance from the beginning of the line to the crossover $i$ ;
$g_o$	The distance from the beginning of the line to the station, $o\in O$ ;
$\gamma$	Number of crossovers that must be used in the design ( $\gamma \in \mathbb{N}$ and $\gamma \le |I|$ );
$\beta$	Value of time (VoT) associated with the passengers’ delay time;
$h^{\mathrm{base}}$	Headway in regular operations;
${\mu }^{\mathrm{mp}}$	Percentage of morning peak hours relative to the total operating hours in a week (%);
${\mu }^{\mathrm{ap}}$	Percentage of afternoon peak hours relative to the total operating hours in a week (%);
$\theta$	Percentage of demand during peak hours relative to the total demand (%);
$M$	A large positive number;
Decision variables
x	$|I|$ -valued vector where each $x_i\in$ x can take a binary value {0,1} with $x_i=1$ denoting that the $i$ -th crossover is included in the design;
Variables
$h_k^1$	The resulting headway in the circuit ahead of the disruption during disruption scenario $k$ ;
$h_k^2$	The resulting headway in the circuit beyond the disruption during disruption scenario $k$ ;
$c_k^1$	Dummy variable corresponding to the required crossover ahead of disruption $k$ (if a crossover is not needed, $c_k^1=0$ );
$c_k^2$	Dummy variable corresponding to the required crossover beyond disruption $k$ (if a crossover is not needed, $c_k^2=0$ );
$s_k^1$	The last station that can be reached ahead of the disruption relative to the first station of the line, in disruption scenario $k$ ;
$s_k^2$	The first station that can be reached beyond the disruption relative to the last station of the line, in disruption scenario $k$ ;
$a_k^1$	Binary variable where $a_k^1=1$ if crossover $c_k^1$ lies beyond $s_k^1$ in the degraded schedule in disruption scenario $k$ ;
$a_k^2$	Binary variable where $a_k^2=1$ if crossover $c_k^2$ lies ahead of $s_k^2$ in the degraded schedule in disruption scenario $k$ ;
$y_{o,d,k}^{\mathrm{rail}}$	The travel time using the rail line from $o$ to $d$ during disruption $k$ ;
$z_{o,d,k}$	$z_{o,d,k}^{\mathrm{mp}},z_{o,d,k}^{\mathrm{ap}},z_{o,d,k}^{\mathrm{re}}$ are the delays for passengers traveling from $o$ to $d$ during the morning peak (mp), afternoon peak (ap) or outside of peak hours (re) during disruption scenario $k$ . This delay is calculated by computing the quickest transport option.

To calculate the waiting time of the passengers during disruption $k$ , the headways for the two circuits are calculated as follows:

$$h_k^1\stackrel{\Delta }{=}\{\begin{array}{c}\max (h^{\mathrm{base}},b_{s_k^1,c_k^1}),\mathrm{if}{g}_{s_k^1}>e_{c_k^1}\hfill \\ \multicolumn{1}{c}{h^{\mathrm{base}},\mathrm{otherwise}}\end{array}\forall k\in K$$

(1)

$$h_k^2\stackrel{\Delta }{=}\{\begin{array}{c}\max (h^{\mathrm{base}},b_{s_k^2,c_k^2}),\mathrm{if}{g}_{s_k^2}>e_{c_k^2}\hfill \\ \multicolumn{1}{c}{h^{\mathrm{base}},\mathrm{otherwise}}\end{array}\forall k\in K$$

(2)

In Equations 1 and 2, the upper condition checks whether the degraded schedule uses a single track for both directions. If so, the headway is limited by the time it takes to ride the single track segment in two directions, and by the time for the driver to move to the other driver’s cabin of the train. If the headway is smaller than the regular headway, the value of $h_k^1$ (or $h_k^2$ ) is equal to $h^{\mathrm{base}}$ because the regular number of trains per hour will be used in this degraded schedule. Note that the service headways are such that track capacity is not exceeded.

Concerning the values of the binary variables $a_k^1$ and $a_k^2$ , they are equal to 1 if the crossover is used ahead of the last-to-reach station (with passengers on the train), and 0 if the crossover is used beyond the last-to-reach station (without passengers on the train). These conditions are stated in Equations 3 and 4.

$$a_k^1\stackrel{\Delta }{=}\{\begin{array}{cc}1,\hfill & \mathrm{if}{e}_{c_k^1}<g_{s_k^1}\hfill \\ \multicolumn{1}{c}{0,}& \mathrm{otherwise}\hfill \end{array}\forall k\in K$$

(3)

$$a_k^2\stackrel{\Delta }{=}\{\begin{array}{cc}1,\hfill & \mathrm{if}{e}_{c_k^2}>g_{s_k^2}\hfill \\ \multicolumn{1}{c}{0,}& \mathrm{otherwise}\hfill \end{array}\forall k\in K$$

(4)

The used crossovers ( $c_k^1$ and $c_k^2$ ), the stations that are still connected during disruption scenario $k$ ( $s_k^1$ and $s_k^2,$ ), the headways on the two circuits ( $h_k^1$ and $h_k^2$ ), and the degraded operation binary values ( $a_k^1$ and $a_k^2$ ) are then used in Equation 5 to calculate the travel time from $o\in O$ to $d\in O$ using the rail line during disruption $k$ .

$$y_{o,d,k}^{\mathrm{rail}}\stackrel{\Delta }{=}\{\begin{array}{cc}M,\mathrm{if}{s}_k^1<s_k^2\mathrm{and}(d>s_k^1\hfill & \mathrm{and}o\le s_k^2)\mathrm{or}(o>s_k^1\mathrm{and}d\le s_k^2)\hfill \\ \multicolumn{1}{c}{y_{o,d}^{\mathrm{reg}}+a_k^1·y_{o,d,c_k^1}^{\mathrm{cross}}+a_k^2·y_{o,d,c_k^2}^{\mathrm{cross}}+(\frac{1}{2}·h_k^2),}& \mathrm{if}{s}_k^1=s_k^2\mathrm{and}(o<s_k^1\mathrm{and}d>s_k^2)\hfill \\ \multicolumn{1}{c}{y_{o,d}^{\mathrm{reg}}+a_k^1·y_{o,d,c_k^1}^{\mathrm{cross}}+a_k^2·y_{o,d,c_k^2}^{\mathrm{cross}}+(\frac{1}{2}·h_k^1),}& \mathrm{if}{s}_k^1=s_k^2\mathrm{and}(o>s_k^2\mathrm{and}d<s_k^1)\hfill \\ \multicolumn{1}{c}{y_{o,d}^{\mathrm{reg}}+a_k^1·y_{o,d,c_k^1}^{\mathrm{cross}}+a_k^2·y_{o,d,c_k^2}^{\mathrm{cross}},}& \mathrm{otherwise}\hfill \end{array}$$

(5)

If two stations $(o,d)$ do not have a connection in the degraded schedule for disruption scenario $k$ , the corresponding travel time is infinitely high ( $y_{o,d,k}^{\mathrm{rail}}=M$ ). If a transfer from the first circuit to the second circuit is needed to travel from $o$ to $d$ , the condition in the second line in Equation 5 calculates the travel time: a transfer time of half the headway of the second circuit ( $h_k^2$ ) is calculated as the average waiting time. If a transfer from the second circuit to the first circuit is needed to travel from $o$ to $d$ , the condition in the third line in Equation 5 calculates the travel time. If a transfer is not needed and stations $o$ and $d$ are connected during disruption $k$ , the fourth line in Equation 5 calculates the travel time by using the regular travel time of the rail line ( $y_{o,d,k}^{\mathrm{rail}}$ ). $a_k^1$ or $a_k^2$ determines whether the extra time of riding over a crossover is added to the regular travel time of the rail line.

Fastest Route With Bridging Options

As presented in Equation 5, the travel time from an origin, $o$ , to a destination, $d$ , using the rail line during disruption scenario, $k$ , can be significantly increased and it might even be impossible to travel from $o$ to $d$ with the rail line. For this reason, travelers should also evaluate the travel times of alternative bridging services when making a decision to travel from $o$ to $d$ during a disruption, $k$ . To this end, we considered the travel time $y_{a,d}^{\mathrm{pt}}$ of the fastest alternative PT mode when traveling from an intermediate location, $a$ , in the path from $o$ to $d$ to the final destination, $d$ . We also considered the respective travel time $y_{a,d}^{\mathrm{walk}}$ when walking from $a$ to $d$ .

Algorithm 1 presents our method for calculating the delay of passengers traveling from station $o$ to station $d$ during disruption $k$ considering that part or the entire trip from $o$ to d can be performed by the rail line. Similarly, part of that trip might be performed by an alternative PT service or by walking, as described in Algorithm 1. Algorithm 1 tries to find the fastest route from $o$ to $d$ during the disruption. This route

• might partly use the circuits of the disrupted rail line and combine them with walking or the fastest alternative PT line;

• might entirely use the disrupted rail line; or

• might entirely use the fastest alternative PT line or walking.

To this end, the travel time from the origin station, $o$ , to $d$ is split by adding a station, $a$ , between the origin and destination station. For all possible $a$ (all stations between $o$ and $d$ ), it was calculated whether walking or using the fastest alternative PT mode yielded a quicker option.

Objective Function and Mathematical Program

The goal of the objective function is to find a combination of crossovers that minimizes the total delay of all passengers for a given number of crossovers that can be used in the design. This yields an objective function ( 6 ) that minimizes the delay minutes of all passengers per year. Since Equation 6 minimizes passenger delay, in the remainder of this paper our model will be called the “unreliability cost (UC) model.” Note that our UC model will decide about the crossover design, considering the crossovers from the set of optional crossovers, $I$ . In future, if some crossovers need repair, one might even consider modifying the original design by selecting other crossovers from set $I$ , provided that this is beneficial based on the updated information.

$$\min \sum _{k=1}^{|K|}\left[r_k{v}_k\sum _{o=1}^{|O|}\sum _{d=1}^{|O|}(j_{o,d}·(\frac{\theta }{2}{\mu }^{\mathrm{mp}}{z}_{o,d,k}^{\mathrm{mp}}+\frac{\theta }{2}{\mu }^{\mathrm{ap}}{z}_{o,d,k}^{\mathrm{ap}}+(1-\theta )(1-{\mu }^{\mathrm{mp}}-{\mu }^{\mathrm{ap}})z_{o,d,k}^{\mathrm{re}}))\right]$$

(6)

$$\mathrm{s}.\mathrm{t}.\sum _{i=1}^{|I|}{x}_i=\gamma$$

(7)

$$x_i\in \{0,1\},\forall i\in I$$

(8)

The objective function includes a summation of all disruption scenarios, $k$ , and all station-to-station combinations, $o$ to $d$ . The objective function consists of three factors: morning peak delays, afternoon peak delays, and the delays outside of peak hours, with their corresponding demand and time percentage. The disruption periods (expressed in minutes per year, $r_k·v_k$ ) are multiplied by the delays for the o-d pair and the average demand per minute. The total delay minutes expressed in the objective function can be multiplied by a VoT factor, $\beta$ , to translate the passenger delay into costs. The first constraint controls the total number of crossovers. The second constraint ensures that selecting a possible crossover is a binary decision. Our mathematical program is an integer nonlinear program with a black box objective function because the values of $z_{o,d,k}^{\mathrm{mp}},z_{o,d,k}^{\mathrm{ap}},z_{o,d,k}^{\mathrm{re}}$ for each design, $x$ , are determined after running Algorithm 1. All combinations of crossovers are independent, so the best setting of x can only be found by evaluating all possible combinations of x. If $\gamma$ is fixed, the number of combinations that need to be evaluated is given from the standard formula for combinations with not permitted repetition (see Arsham [ 45 ]),

Algorithm 1 determines the quickest route from $o$ to $d$ in the case of disruption scenario $k$ ( $\forall o\in O,d\in O,k\in K$ ), for crossover set x

input $y_{o,d,k}^{\mathrm{rail}},y_{o,d}^{\mathrm{pt},\mathrm{mp}},y_{o,d}^{\mathrm{pt},\mathrm{ap}},y_{o,d}^{\mathrm{pt},\mathrm{re}},y_{o,d}^{\mathrm{walk}},y_{o,d}^{\mathrm{reg}},v_k,h_k^1,h_k^2$  1: for all $\tau$ in $(\mathrm{mp},\mathrm{ap},\mathrm{re})$ doamutha morning peak, afternoon peak, rest  2:    $z_{o,d,k}^{\tau }\leftarrow$ min $(y_{o,d,k}^{\mathrm{rail}},y_{o,d}^{\mathrm{pt},\tau },y_{o,d}^{\mathrm{walk}},y_{o,d}^{\mathrm{reg}}+v_k)-y_{o,d,k}^{\mathrm{reg}}$  3:   if $o<d$ then  4:    for all $a\in 〈o+1,o+2,...,d-1〉$ do  5:     if $y_{o,a,k}^{\mathrm{rail}}+\min (y_{a,d}^{\mathrm{pt},\tau },y_{a,d}^{\mathrm{walk}})+\frac{1}{2}{h}_k^2-y_{o,d,k}^{\mathrm{reg}}<z_{o,d,k}$ then  6:       $z_{o,d,k}^{\tau }\leftarrow y_{o,a,k}^{\mathrm{rail}}+\min (y_{a,d}^{\mathrm{pt},\tau },y_{a,d}^{\mathrm{walk}})+\frac{1}{2}{h}_k^2-y_{o,d,k}^{\mathrm{reg}}$  7:     end if  8:     if $\min (y_{o,a}^{\mathrm{pt},\tau },y_{o,a}^{\mathrm{walk}})+y_{a,d,k}^{\mathrm{rail}}+\frac{1}{2}{h}_k^1-y_{o,d,k}^{\mathrm{reg}}<z_{o,d,k}$ then  9:       $z_{o,d,k}^{\tau }\leftarrow \min (y_{o,a}^{\mathrm{pt},\tau },y_{o,a}^{\mathrm{walk}})+y_{a,d,k}^{\mathrm{rail}}+\frac{1}{2}{h}_k^1-y_{o,d,k}^{\mathrm{reg}}$  10:     end if  11:    end for  12:   end if  13: end for  14: return $z_{o,d,k}^{\mathrm{mp}},z_{o,d,k}^{\mathrm{ap}},z_{o,d,k}^{\mathrm{re}}$

$$\mathrm{potential}\mathrm{solutions}=\frac{|I|!}{\gamma !(|I|-\gamma )!}$$

(9)

To demonstrate the computational complexity in practical problem instances, we implemented our model on a PC with an Intel Core i5-6300 CPU @ 2.40 GHz 8.00 GB RAM processor. The computation times for different problem sizes are presented in Figure 6. It is worth noting that, all things being equal, the computation costs increase with the increase of possible crossover options $|I|$ . Additionally, for a specific number of possible crossover options, $|I|$ , the computation costs reduce for $\gamma \to 0$ and $\gamma \to |I|$ . Notably, the computation time is zero for $\gamma =|I|$ because in such case we are forced to use all possible crossovers, $I$ , and we do not need to perform optimization since we have only one feasible solution.

Figure 6.

Estimated computational time for different values of $\gamma$ and $|I|$ .

Case Study

Our UC model was tested on a light rail line in Bergen (Norway). This line was suitable as a case study for our model because

• this line is independent and detours via other lines are not possible, and

• its scheduled headway is 5 min. Therefore, the transition phases can be neglected because this is a high-frequency line.

Case Study Area and Input Data

The case study line is a light rail line in Bergen (Norway) consisting of nine stations and six fixed crossovers (see Figure 7). The construction of this line started recently and is therefore in the design phase. Slopes, station locations, and maximum speed information were obtained from the design reports of the line carried out by Sweco ( 46 ). The locations of crossings, switches, and crossovers were also obtained from these documents. The passenger demand matrix was provided by Mortensen ( 47 ). The expected percentage of demand during peak hours was $\theta =60\%$ . The new rail line will operate 19 h per day. The expected morning peak hour is from 07:00 to 09:00 a.m., 5 days per week, and the afternoon peak hour is from 3:00 to 6:00 p.m., 5 days per week. Therefore, ${\mu }^{\mathrm{mp}}=7.5\%$ and ${\mu }^{\mathrm{ap}}=11.3\%$ .

Figure 7.

Potential locations of crossovers on the Bergen light rail line. The direction of the bottom track is from left to right and the top track from right to left.

The travel times for the alternative PT lines were calculated in Python 3.6 using the Google Maps plugin. $y^{\mathrm{pt},\mathrm{mp}}$ was defined as 8:00 a.m., ${\mathrm{y}}^{\mathrm{pt},\mathrm{ap}}$ was defined as 4:30 p.m., and ${\mathrm{y}}^{\mathrm{pt},\mathrm{re}}$ as noon. Two bus lines will be abolished when the new tram line is finished: Lines 3 and 9 between Kronstad and Bergen Sentrum ( 47 ). The travel times between Kronstad and Mollendal will be adjusted manually in ${\mathrm{y}}^{\mathrm{pt},\mathrm{mp}}$ , ${\mathrm{y}}^{\mathrm{pt},\mathrm{ap}}$ , and ${\mathrm{y}}^{\mathrm{pt},\mathrm{re}}$ . The travel time from Haukeland Sykehus to Kronstad and the city center will stay the same because bus Line 2 will still operate in the new schedule.

The frequency and duration of disruptions were obtained from the Reliability–Availability–Maintainability–Safety (RAMS) study of the project. From the RAMS study, we obtained switch, tunnel, power, and road crossing failure probabilities. For vehicle breakdowns, the values from Yap ( 19 ) were used. One type of rolling stock has been ordered for this line: a 38 Variobahn seven-car (42-m) vehicle from Stadler. The length, acceleration, and deceleration properties of this rolling stock type were used.

One track has been designed for both directions. For the first and last station, a crossover is needed to turn rolling stock in the opposite direction (Locations 70, 300, and 8800). Moreover, a crossover is needed at Kronstad (at Location 3700 m) to make it possible to move the rolling stock to the maintenance building.

VoT, $\beta$ , was obtained from a study undertaken on behalf of the Ministry of Transport ( 48 ). The VoT for passenger delays was largely assumed to be the same for business and nonbusiness passengers (122 Norwegian Krones). Corrected for inflation between 1997 and 2020 ( 49 ), which was 59%, the VoT for 1 h delay was 194 Norwegian Krones. As a reference, at the time of this study, 1 Norwegian Krone corresponds to 0.11 U.S. dollars and 0.095 euros. The list of possible disruptions was created using the RAMS study ( 50 – 53 ). Vehicle breakdowns are not included in these documents, so these values were obtained from Yap et al. ( 42 ). With these data sources, our UC model was executed to derive the optimal crossover locations.

Optimal Crossover Location Strategy of the UC Model

The actual design included the six fixed crossovers from Figure 7 and three additional crossovers. These three additionally planned crossovers are presented in Figure 8. Our UC model can produce designs with different numbers of crossovers by changing the value of $\gamma$ in the optimization model. In our experiments, we had $|I|=20$ possible crossovers (see Figure 7) and we found the optimal crossover solution for different scenarios with $\gamma =0,1,2,3,4,5,6,7$ .

Figure 8.

The actual design plan of the Bergen light rail. The direction of the bottom track is from left to right and the top track from right to left.

Figure 9 presents the UCs of our globally optimal crossover solution for scenarios with different numbers of possible crossovers allowed in the final design ( $\gamma$ ). In this figure, we also show the unreliability cost of the actual design that includes three crossovers. For $\gamma =3$ , our UC design performed 9.8% better than the actual design.

Figure 9.

Passenger delay cost of the actual design and passenger delay cost of the optimal crossover combination according to the unreliability cost (UC) model for different values of $\gamma$ .

From Figure 9, one can note that when the number of allowed crossovers increases from zero to two we had a significant improvement in unreliability costs (14% and 16%, respectively). Adding a third, fourth, or fifth crossover led to a lower benefit (approximately 2%). The optimal locations of the crossovers for $0\le \gamma \le 7$ are reported in Figure 10.

Figure 10.

Optimal crossover location design strategy for different values of $\gamma$ according to our unreliability cost (UC) model. The direction of the bottom track is from left to right and the top track from right to left.

Performance Evaluation of the Crossover Designs in Randomized Scenarios

Here we compare the performance of three crossover design strategies,

• (1) the optimal crossover location strategy according to our UC model;

• (2) the optimal crossover location strategy according to the crossover performance (CP) model that aims to maximize the number of times a crossover is used in the disruption schedules (see Hoeffelman [25]); and

• (3) the actual crossover location strategy in the design that is currently being constructed in Bergen.

Note that our UC model sums the total delay of all passengers, whereas the CP model sums the crossover usages. Therefore, the main difference between the two models is that the UC model is passenger-based, whereas the CP model is network-based and does not consider the passenger demand, VoT, or travel times of other transport modes. Because the actual design contains three possible crossovers, we compared the optimal solutions of all strategies for $\gamma =3$ . These solutions are presented in Figure 11, including four fixed crossovers and three additional crossover selections.

Figure 11.

Optimal crossover location strategy according to the unreliability cost (UC) model, the crossover performance (CP) model, and the actual design. The direction of the bottom track is from left to right and the top track from right to left.

To test the performance of the three designs (Figure 11) in the case of uncertainty, we investigated the performance sensitivity of the designs to disruption scenarios with random failure probabilities. In more detail, for any predetermined disruption type at any location, we randomly selected its duration from a uniform distribution. The passenger demand between o-d pairs was also allowed to vary between −20% and +20% of its mean. We then generated 30 random scenarios with randomly sampled disruption duration and passenger demand from the corresponding probability distributions and compared the performances of the three crossover designs. In this comparison, four key performance indicators were used:

• (I1) Delay minutes

• The sum of the delay of all passengers per year.

• (I2) Crossover annual usage

• The expected usage per year of all crossovers.

• (I3) Network connectivity

• The connectivity indicator from Nieminen ( 24 ) indicating how many stations a station is connected to during a disruption.

• (I4) Number of passengers delayed by more than 5 min

• The number of passengers with a delay of more than the scheduled headway of 5 min.

Note that the actual design includes a tail track crossover that can be used to turn the trams around in the case of disruptions. During this process, there are no passengers inside the tram. Passengers who wish to continue their trip beyond the location of the tail track crossover have to either walk or use another PT mode. Their delay is calculated according to the assumption that they select the quickest route based on the available modes, since the tram will turn around and does not serve the area beyond the tail track (see Figure 12).

Figure 12.

Example of degraded operation options on an independent rail line with a tail track.

The performances of the three crossover designs in each one of the 30 random scenarios are presented in Figure 13. From the results, one can conclude that for all scenarios the UC design had the lowest delay, the best connectivity value, and the lowest number of passengers with a delay of more than 5 min. The CP design had a better crossover performance in most scenarios. The difference between the UC- and the CP design was very small in most scenarios, however, there was a significant difference between the UC- and the actual design in all scenarios. Obviously, the CP design is optimized for crossover performance and thus performed better in this metric (I2). Because the CP design contains crossovers that are used as many times as possible in the case of disruptions, in some disruptions a crossover might be used but this does not necessarily mean that more stations are connected during the disruption.

Figure 13.

Performance of the unreliability cost (UC), crossover performance (CP), and actual designs at each one of the 30 random scenarios. For indicators (I1) and (I4) lower values are better. For (I2) and (I3) higher values are better.

Our experiments showed that the UC model yielded a more robust design compared with the CP model and the actual design. Three of the four key performance indicators (passenger delay, connectivity, passengers delayed more than 5 min) were improved when applying the UC design. Crossover performance was higher for the CP design in most scenarios, but the difference was very small and a higher crossover performance is not necessarily beneficial for passengers, operators, or local authorities.

Concerning the results of our performance evaluation, it should be noted that these were based on the assumptions that passengers will not use their private vehicles in the case of disruptions and that the planned capacity of the PT lines is sufficient to accommodate passenger demand. These assumptions were used when comparing the performances of all design strategies: our UC model, the CP model, and the actual crossover design.

Our light rail line was of high frequency, therefore it was safe to assume that vehicles were evenly distributed across the line to perform a regular service and that the transition phases from the regular schedule to the degraded schedule and back to the regular schedule were very short.

Conclusion and Recommendations

This study proposed an algorithm to automatically calculate disruption schedules for any double-track railway line that does not share lanes with road traffic. In addition, we developed a UC model to produce optimal crossover designs by taking into consideration passenger delays resulting from disruptions that can occur on a yearly basis. Experiments in our case study in Bergen (Norway) showed that our passenger-based UC design performed better than the actual design or the design produced by the network-based CP model. The UC design performed better for different key performance indicators: the crossover performance, average line connectivity, and the number of passengers having a delay of more than 5 min. Specifically, the UC design resulted in a reduction in unreliability costs of 9.8% while using the same number of crossovers as the actual design.

Our UC model has computation limitations in relation to the set sizes of potential crossover locations because the number of combinations rises significantly when an extra potential crossover location is added to the set. The maximum set sizes are large enough to evaluate a larger network than the one selected in this study. However, it would not be possible to optimize the crossover locations of the rail network of an entire country. In future research, logical constraints could be added to prune the solution space and reduce computation times. In addition, further constraints could be added to our UC model to increase the crossover functions (i.e., add constraints to ensure that a facing crossover is needed between two stations). Finally, a sensitivity analysis could be performed to investigate the potential performance changes in the case of variations in the model parameters, such as passenger demand, travel times of alternative PT lines, the frequency and duration of disruptions, timetable frequencies, and the value of passengers’ time.