# A Mixed Integer Linear Programming Model for Rolling Stock Deadhead Routing before the Operation Period in an Urban Rail Transit Line

Authors: Qingwei Zhong; Yongxiang Zhang; Dian Wang; Qinglun Zhong; Chao Wen; Qiyuan Peng
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

In an urban rail transit line, train services are performed by the rolling stocks that are initially stored at depots. Before the start of the operation period, rolling stocks consecutively leave the depots and run without passengers (deadhead routing) to the origin station of their corresponding first departure train service in an operation day (first train service) using either direct or indirect routes. This paper investigates the rolling stock deadhead routing problem in an urban transit line with multiple circulation plans, depots, and rolling stock types. Given the rolling stock circulation plans, the problem is to identify a deadhead route for the rolling stock required by the train services to cover the initial operation. By pregenerating all direct and indirect candidate deadhead routes in a polynomial manner, the problem is then nicely formulated as a mixed integer linear programming (MILP) model to minimize the total deadhead mileages. A real-world case from the urban rail transit line 3 of Chongqing in China is adopted to test the proposed method. Computational results demonstrate that the problems of large-scale instances can be quickly solved to optimality by commercial optimization solvers on a personal computer. In addition, our optimization method is better than the empirical practices in terms of the solution quality. Meanwhile, alternative measures can further decrease the total deadhead mileages according to the proposed model, e.g., opening idle switch stations and prolonging the time that is used for the rolling stock departure. Finally, the model is further extended to consider operating costs, and more computation cases are tested for better adapting to the practical operating conditions.


---

## Body

## 1. Introduction

With the increasing coverage and density of urban mobility, public transport has become an important means of daily urban trips. As one of the main public transport modes, the urban rail transit is recently undergoing a rapid development around the world due to its high capacity, safety, and reliability [1, 2]. Urban rail transit lines have relatively short station spacing and high service frequency. Hence, the operation of urban rail transit lines is different from that of conventional railways. Generally speaking, the organization and management of an urban rail transit line involve several difficult combinatorial optimization problems, e.g., line planning, train timetabling, rolling stock scheduling, and crew scheduling (see, e.g., [3, 4]). Among them, the rolling stock scheduling problem is an important tactical problem, which is considered after the line planning and train timetabling stages. Given a timetable, the main task of the rolling stock scheduling problem is to assign different rolling stocks stored at depots to the train services in the timetable, such that each train service can be assigned a required type of rolling stock. The result is a technical document called the rolling stock circulation plan, and it specifies the number of required rolling stock types and the task of each rolling stock. Each circulation plan is carried out by only one specific rolling stock, which departs firstly from its depot to an initial station, performs a series of train services, and returns to its depot thereafter. For the train timetabling and rolling stock scheduling problems in the conventional railways, we refer the readers to the studies by Zhang et al. [5] and Zhong et al. [6].The rolling stock scheduling problem for an urban rail transit line is complicated due to the infrastructure layout and operation rules. Specifically, an urban rail transit line usually has multiple depots and operates multiple circulation plans in which trains originate and terminate at different stations. The origin station of a train is not necessarily the station adjacent to a depot, where a rolling stock has to run a certain mileage to the origin station of its dispatched first train service. Meanwhile, an urban rail transit line does not operate in 24 hours, and all rolling stocks must return to depots by the end of the operation. In order to satisfy the passenger flow at the beginning of the operation period, which is usually a peak time for one operation day, the rolling stocks for many first train services are arranged at different stations in advance. Otherwise, the first train services at some stations can be very late due to the rolling stocks in need of travelling a long distance along the line from the depot, which may cause a large backlog of passenger flow at those stations within a short period. Accordingly, there is an initial period before the operation on the next day, during which rolling stocks consecutively leave the depots and run to the origin station of their corresponding first train services using either direct routes without switch stations or indirect routes via switch stations. We call this process deadheading, which has a significant impact on the deadhead mileage and energy consumption of rolling stocks. Therefore, it is necessary to optimize the deadhead routes to improve the utilization efficiency of rolling stocks, which is essentially a kind of the operational train routing selection problem [7].We consider the problem of rolling stock deadhead routing before the operation period of an urban rail transit line. Given the rolling stock circulation plan of the line, the main decision of the problem is to select an optimal deadhead route for each required type of rolling stock to perform the train services. The timetable systems used in the urban rail transit line do not contain the function that automatically generates the real-time deadhead route according to the corresponding train timetable. Motivated by this, the aim of the paper is to develop a sound and practical model for the rolling stock deadhead routing in an urban rail transit line with multiple circulation plans, depots, and rolling stock types that can be solved efficiently with very short computation times. By generating explicitly all candidate direct and indirect deadhead routes, we formulate the problem as a mixed integer linear program, which minimizes the total rolling stock deadhead mileages. The size of the model increases polynomially with respect to the numbers of depots, switch stations, and train services, and the model can be quickly solved to optimality by using the state-of-the-art commercial optimization solvers on a personal computer. A real-world case based on an urban rail transit line 3 of Chongqing in China is used to verify the feasibility and practicality of the proposed model. Sensitivity analysis is also conducted to aid the transit operator, seeking effective measures to further decrease the total deadhead mileages.The rest of the paper is organized as follows. We present a quick literature review in Section2. A formal problem description is given in Section 3. In Section 4, the problem is formulated as a mixed integer linear programming model. Section 5 provides computational results and sensitivity analysis results for a real-world case of the urban rail transit line 3 of Chongqing in China. Moreover, an extended model and its corresponding computation tests are provided in Section 5. Finally, we conclude the paper and provide future research directions in Section 6.


## 2. Literature Review

Since the rolling stock scheduling problem is critical in the operational level of one railway company, it has attracted much attention for the last decades. Many researchers study this issue from a different point of view, e.g., Fioole et al. [8]; Wagenaar et al. [9]; Lusby et al. [10]; Zhong et al. [6]; and Cacchiani et al. [11]. As a result, it is not difficult to find that most of the works related to rolling stock scheduling problems focus on conventional railways, where there are still some major differences from the rapid or urban rail transit. Then, we mainly review existing studies on rolling stock scheduling problems for the rapid or urban rail transit systems that are most relevant to our problem.Several studies have been carried out on the rolling stock scheduling problems in a rapid or urban rail transit line. In particular, Cadarso and Marín [12–14] systematically investigated the robust rolling stock scheduling problem which was decomposed into the circulation and routing subproblems. Cadarso and Marín [13] provided a robust model for the rolling stock circulation problem by considering many practical issues and introducing several robustness measurements. Cadarso and Marín [12] studied the robust rolling stock routing problem. A generalized robust assignment model was formulated to obtain robust routing plans. Cadarso and Marín [14] presented a large-scale robust model to integrate the rolling stock scheduling problem. The Benders decomposition method was utilized to solve the model. Andrés et al. [15] formulated the rolling stock maintenance routing problem as an optimization model which was solved by a branch-and-price approach. Canca et al. [16] proposed a comprehensive optimization model to develop long-term rolling stock circulation plans under a rotating maintenance scheme. Thorlacius et al. [17] proposed an integrated rolling stock planning model for the suburban passenger train of Copenhagen, and a high climbing heuristic was adopted to solve the model. Since the rolling stock scheduling process is usually affected by the former train scheduling processes, some researchers start to explore the integration of these two processes. For instance, Yue et al. [18] proposed a bilevel programming model, where the upper level model was designed for the train scheduling problem, while the low level model was developed to schedule the rolling stocks. Wang et al. [3] also integrated the train scheduling and the rolling stock circulation planning problems considering different practical operational attributes, e.g., the time-varying passenger demand. Mo et al. [4] investigated a collaborative optimization for the energy-efficient train schedule and rolling stock circulation plan in off-peak hours, and a linear programming approach was developed to formulate the problem with several practical constraints. Table 1 summarizes the related studies in terms of problem description (i.e., depot capacity, rolling stock type, line structure, and deadhead routing), mathematical formulations (i.e., model structure and objectives), and solution algorithms.Table 1
Summary of relevant studies on rolling stock scheduling in a rapid or urban trail transit systems.
Publication
Depot capacity
Rolling stock type
Line structure
Deadhead routing
Model structure
Objective(s)
Solution algorithms
Cadarso and Marin [12]
Yes
Yes
Bi-dire,
D-oper
MINLP
Delay propagation, crew requirements
CPLEX
M-dep
Cadarso and Marin [13]
Yes
Yes
Bi-dire,
D-oper
MILP
Cost of train services, empty movements, shunning,
CPLEX
M-dep
cost of leasing material from other lines
Cadarso and Marin [14]
Yes
Yes
Bi-dire,
D-oper
MILP
Operating costs, unattended passenger,
B&D
M-dep
shunting costs, expected delay
Andres et al. [15]
Yes
Yes
Bi-dire,
D-oper
MILP
Operating costs,
B&B, C&G
M-dep
penalties of waiting times, maintenance
Canca et al. [16]
Yes
No
Network,
D-oper
MILP
The fleet size,
B&C
S-dep
total length traversed
Thorlacius et al. [17]
Yes
Yes
Network,
—
MILP
Operational cost,
Hill climbing
M-dep
penalties awarded for undesirable features
Yue et al. [18]
Yes
No
Bi-direc
—
MILP
Numbers of waiting passengers, train services, infeasible train paths
S&A, N&S, CPLEX
M-dep
Wang et al. [3]
Yes
No
Bi-direc
—
MINLP
Headway variations, load factor variations,
Iterative approach, CPLEX
S-dep
number of depot operations
Mo et al. [4]
Yes
No
Bi-direc
—
MILP
Brake-traction overlapping time, number of turn-around operations
CPLEX
M-dep
This paper
Yes
Yes
Bi-direc
B-oper
MILP
Deadhead mileage, operational cost
CPLEX
M-dep
Bi-direc: bidirection single line; M-dep: multiple depots; B-oper: before the operation period; D-oper: during the operation period; MILP: mixed integer linear programming; MINLP: mixed integer nonlinear programming; B&D: benders decomposition; B&B: branch and bound; B&C: branch and cut; S&A: simulated annealing; N&S: neighborhood search; C&G: column generation.In summary, the studies in Table1 have made great contributions to the rolling stock scheduling problem in rapid or urban rail systems, and many important practical factors have been considered, such as the robustness, delay, maintenance, passenger, and energy consumption. To the best of our knowledge, the rolling stock deadhead routing problem before the operation period of an urban rail transit line has not attracted much attention. Most of the literature aims at developing rolling stock circulation plans within the operation period, in which the exit and entrance deadhead routes of rolling stocks between depots and stations are predetermined. More specifically, the deadhead movements are only used to build a feasible connection during the operation period. In addition, some previous research studies do not consider the deadhead movements when optimizing the rolling stock scheduling problem, which could be not suitable for some rapid or urban rail systems.As mentioned earlier, according to the practical passenger flow, there can be several stations in one rapid or urban rail line that needs rolling stocks at the beginning of one day’s operation. Since not every station is connected with a depot, the deadheading movement is unavoidable. Also, for a short time period after the beginning of the operation, multiple rolling stocks can be needed for one circulation plan at a station due to the small headway time. For this case, the rolling stock needs to consecutively deadhead from depot through two flexible (direct and indirect) routes. In addition, there are more and more rapid or urban rail lines that are connected with multiple depots and served by different types of rolling stocks. Thus, it is necessary to consider these practical conditions. In order to explore the rolling stock deadhead routing before the operation period, we propose a MILP model to minimize the total deadhead mileages. Then, the sensitivity analysis is applied to explore the factors that influence the total deadhead mileages. Finally, based on the sensitivity analysis, an extended model considering the impact of operating costs is also proposed.Since the rolling stock scheduling process is closely related to the train timetabling process, it is also essential to generate the corresponding rolling stock deadhead timetable. For the train timetabling problem in a rapid or urban transit system, we refer the readers to Albrecht [19]; Niu and Zhou [20, 21]; Sun et al. [22]; and Barrena et al. [23, 24]. The integrated model considering both the rolling stock deadhead routing and train timetabling problems will be the best way to solve this practical problem. However, when considering the train timetabling problem, the original rolling stock deadhead routing model will be more complicated. Thus, it can be expected that more sophisticated and efficient solution algorithms would be required to deal with the integrated model, especially when dealing with the whole day’s train operation plan, which is beyond the scope of this paper. In this paper, the proposed model aims at generating real-time deadhead routes for these first train services based on the infrastructure, which must also satisfy all the involved operational constraints. Moreover, a heuristic approach based on the results of our model is also proposed, which can quickly obtain a feasible timetable if it is necessary.


## 3. Problem Description

An urban rail transit line with 6 stations, 2 depots, and 4 switch stations is shown in Figure1 to illustrate the problem in the paper. The stations are numbered along the upside direction from stations s1 to s6, and stations s2 and s5 are adjacent to the two depots d1 and d2, respectively. Stations s1, s2, s4, and s6 are switch stations. In particular, stations s1 and s2 are the upside switch stations where the running direction of trains can be switched from the downside direction to the upside direction, while stations s4 and s6 are the downside switch stations. The transit line operates two circulation plans l1 and l2, where train i1 represents part of the train services of circulation plan l1 and train i2 shows part of the train services of circulation plan l2. Moreover, it is assumed that the initiation period for the rolling stock departure is from 5:30 am to 6:30 am and the transit service starts at 6:30 am. At the beginning of the operation period, trains i1 and i2 need to be served by the rolling stocks stored at either depots d1 or d2. Train i1 is a downside train of circulation plan l1 which originates at station s4 and terminates at stations s1, while train i2 is a partial upside train of circulation plan l2 and it originates and terminates at stations s3 and s6.Figure 1
Illustration of rolling stock deadhead routing in the initiation period.In Figure1, the assigned rolling stock for train service i1 has several possible deadhead routes, and three of them are illustrated as thick dashed lines. Besides, we first neglect the capacity constraints of the depot and switch station. For the deadhead route r1, the rolling stock departs from depot d2 and arrives at the origin station s4 of train i1 via depot station s5. For the deadhead route r2, the rolling stock departs from depot d1 and arrives at the origin station s4 of train i1, where it switches to the downside direction to undertake train i1. For the last deadhead route r3, the rolling stock departs from depot d2 and arrives at station s6, where it switches to the downside direction via depot station s6 and finally arrives at the origin station s4 of train i1. In particular, we define the deadhead route r1 as the direct route and the deadhead routes r2 and r3 as the indirect route. Similarly, three possible candidate deadhead routes of train i2 are also given, including the direct route r4 and indirect routes r5 and r6, which are indicated as the thick solid lines in Figure 1. Therefore, it can be shown that there can be many possible direct/indirect routes for a rapid or urban transit line with multiple circulation plans, depots, and rolling stock types in practice. The direct and indirect routes could result in different deadhead mileages, and the deadhead mileage of a direct route is usually smaller than that of an indirect one. However, the direct routes are not always feasible due to the depot and station capacity limitations, and the indirect routes are alternatives to insufficient capacity.To summarize, we define the rolling stock deadhead routing problem in an urban rail transit line as follows. Given the locations of depots and switch stations and the rolling stock circulation plan of the urban rail transit line, the deadhead routing problem is to determine either a direct or an indirect deadhead route for each rolling stock circulation during the initial operation period of the urban rail transit line. The goal is to minimize the total rolling stock deadhead mileages while addressing all of the rolling stock circulations and respecting the depot storage and departure capacities as well as switch station capacity. It is worth noting that the rolling stock deadhead routes in practice are still empirically determined. The empirical method resembles a heuristic approach and does not consider incurred effectiveness. In this paper, we aim at determining optimal deadhead routes by solving a compact MILP model to achieve the automatic deadhead routing optimization, which decreases the total deadhead mileages of rolling stocks.


## 4. Model Formulation

### 4.1. Modeling Assumptions

Without loss of generality, the following assumptions are introduced to facilitate the model formulation process.(i)
Each depot is assumed to be adjacent to only one endpoint station or an intermediate station in the urban rail transit line. Note that the model proposed in the paper can be easily extended to describe more complicated layouts with connection tracks between depots and stations.(ii)
The train timetable along with the corresponding rolling stock circulation plan for the operation of the urban rail transit line is given. The train services that need to be performed by a rolling stock stored at the depot(s) are clarified.(iii)
Rolling stocks consecutively leave depots via either a direct route or an indirect route in the initiation period. Each rolling stock starts from its depot, carries no passengers en route, and runs as quickly as possible to the origin station of its served train service.(iv)
The deadhead movement of rolling stocks must be completed in the initiation period, and depots and switch stations have limited capacities.(v)
When optimizing the deadhead routes, the deadhead timetable specifying the arrival and departure times of each rolling stock at each visited station along its selected deadhead route is not considered.We formulate the rolling stock deadhead routing problem as a MILP model by pregenerating explicitly all candidate deadhead direct routes and indirect deadhead routes. The notations used in the model are introduced in Tables2 and 3.Table 2
Definitions of sets, indices, parameters, and decision variables.
Symbol
Definition
S
Set of stations, which are numbered along the upside direction,s∈S
D
Set of depots,d∈D
K
Set of switch stations,k∈K
I
Set of train services to be performed by the rolling stocks parking at depots in the initiation period,i∈I
W
Set of rolling stock running directions,W=0,1, where 0 and 1 represent the upside and downside directions, respectively
V
Set of rolling stock types, which are distinguished by the number of carriages of the rolling stocks; the setV is numbered in an ascending order according to the number of carriages, v∈V
I
d
Set of train services which can be performed by a rolling stock that departs from depotd using a direct route, Id=i∈Ibod,qi=ui⊂I
V
d
Set of rolling stock types which can be parked in depotd, Vd⊂V
D
i
Set of depots from which a rolling stock can depart to perform the train servicei using a direct route, Di=d∈Dbod,qi=ui⊂D
K
i
,
d
Set of switch stations which can be used for a rolling stock that departs from depotd using an indirect route to serve train i, Ki,d=k∈Kbod,pk=1−ui,bpk,qi=ui⊂K
l
s
′
Distance between stationss and s′
b
s
s
′
Running direction of a rolling stock from stations to s′bss′=0,1, where 0 and 1 represent the upside and downside directions, respectively
o
d
Depot station that is adjacent to depotd
g
d
,
v
Maximum number of rolling stocks of typev that can be accommodated at depot d
a
d
,
v
Number of train services specified to be performed by the rolling stocks of typev that depart from depot d during the operation period; the value of the parameter ad,v is determined by the rolling stock circulation plans
e
d
,
w
Maximum number of rolling stocks which can depart from depotd in the direction w; the value of ed,w is estimated by the available departure period (i.e., the initiation period) and safety headway of the same direction
n
d
Maximum number of rolling stocks which can depart from depotd in both directions; the value of nd is estimated by the available departure period (the initiation period) and safety headway of opposite directions
f
d
,
w
Departure distance of rolling stocks running from depotd to its depot station in the direction w
p
k
Station where switch stationk is located
r
k
,
w
Maximum number of rolling stocks that can be switched from direction1−w to w at the switch station k; the value of rk,w can be estimated by the available switch period (the initiation period) and switch headway
h
k
,
w
Switch distance of the rolling stocks by switching from direction1−w to w at the switch station k
q
i
Origin station of a train servicei
u
i
Running direction of a train serviceiui=0,1, where 0 and 1 represent the upside and downside directions, respectively
t
i
Required rolling stock type of a train serviceiTable 3
Definitions of decision variables.
Symbol
Definition
x
i
.
d
0-1 variable, 1 if train servicei is performed by a rolling stock which departs from depot d using a direct route, 0 otherwise
y
d
,
k
i
0-1 variable, 1 if train servicei is performed by a rolling stock which departs from depot d using an indirect route via switch station k, 0 otherwise
c
i
,
d
Continuous variable, representing the deadhead mileages of a rolling stock that travels from depotd to the origin station of the train service i


### 4.2. Objective Function

Rolling stocks usually do not carry passengers before the operation period, and they need to run quickly to the origin stations of their served train services. In this paper, the deadhead routing problem tries to minimize the total deadhead mileages to reduce the operation costs and improve the utilization efficiency of rolling stocks, which can be formulated as in the following equation:(1)minZ=∑i∈I∑d∈Dci,d,where variable ci,d represents the deadhead mileages of a rolling stock that travels from depot d to the origin station of train service i. The value of the variable ci,d depends on the type of deadhead route used by the rolling stock, the departure distance of the depot, and the switch distance of the switch station:(2)ci,d=fd,ui+lod,qi⋅xi,d+∑k∈Ki,dfd,1−ui+lod,pk+hk,ui+lpk,qi⋅yd,ki.In equation (2), if train service i is performed by a rolling stock that departs from depot d using a direct route, i.e., xi,d=1, the deadhead mileages ci,d are equal to the summation of the departure distance fd,ui in the same direction of train service i at depot d and the distance lod,qi between the station od that is adjacent to depot d and the origin station qi of train service i. Otherwise, if train service i is performed by a rolling stock that departs from depot d using an indirect route via a switch station k∗, i.e., yd,k∗i=1, the deadhead mileages ci,d consists of four parts. The first part is the departure distance fd,1−ui in the opposite direction of train service i at depot d. The second part represents the distance lod,pk∗ between the station od that is adjacent to depot station d and the switch station k∗. The last two parts express the switch distance hk∗,ui in the same direction of train service i at switch station k∗ and the distance lpk∗,qi from the switch station k∗ to the origin station qi of train service i.


### 4.3. Constraints

#### 4.3.1. Uniqueness of Deadhead Routes

To obtain practically feasible rolling stock deadhead routes in the initiation period, constraint (3) enforces that the rolling stock required by each train service must choose either one direct or one indirect route, and the rolling stock must depart from the depot which accommodates it:(3)∑d∈Dti∈Vdxi,d+∑d∈Dti∈Vd∑k∈Ki,dyd,ki=1,∀i∈I.


#### 4.3.2. Feasibility of Deadhead Routes

An urban rail transit line usually consists of two main tracks: one is for the upside direction and the other for the downside direction. Except for the depot stations and switch stations, other stations do not have additional sidings other than the main tracks. Therefore, the direct and indirect deadhead routes do not exist simultaneously for any pair of depots and train services. Depending on the direction of the train services, the locations of the origin stations of the train services, and the station that is adjacent to the depot, 4 feasible deadhead routes can be obtained, as shown in Figure2:(i)
In Figure2(a), train service i is in the upside direction. If depot d is located after the origin station of train service i along the upside direction, train service i can be served by a rolling stock that departs from depot d using a direct route. Otherwise, there is no direct route between train service i and depot d, i.e., if d∉Di, we have xi,d=0.(ii)
In Figure2(b), train service i is in the upside direction. If depot d is located after the origin station of train service i, and there are also nonempty switch stations Ki,d after depot d, train service i can be performed by a rolling stock that departs from depot d using indirect routes via any switch station in Ki,d, which is depicted as the thick dashed lines in Figure 2(b). Otherwise, if depot d is located before the origin station of train service i, and nonempty switch stations Ki,d can be found after depot d, there are also indirect routes via any switch station in Ki,d between the train service i and depot d, which is denoted as the thick solid lines in Figure 2(b). However, if Ki,d=∅, we have yd,ki=0.(iii)
Train servicei is in the downside direction, as in Figure 2(c). If depot d is located after the origin station of train service i, train service i cannot be performed by the rolling stock from depot d using a direct route, i.e., if d∉Di, we have xi,d=0.(iv)
Train servicei is in the downside direction, as in Figure 2(d). Regardless of the locations of depot d and train service i, train service i cannot be performed by the rolling stock from depot d using an indirect route when no switch stations Ki,d are located before depot d, i.e., if Ki,d=∅, we have yd,ki=0.Figure 2
Illustration of feasible rolling stock deadhead routes. (a) Direct route for a upside train service line. (b) Indirect route for a upside train service line. (c) Direct route for a downside train service line. (d) Indirect route for a downside train service line.
(a)
(b)
(c)
(d)


#### 4.3.3. Storage Capacity of Depots

An urban rail transit line usually operates only one type of rolling stock, however, with different numbers of carriages. In this paper, the rolling stock is distinguished by the number of carriages. Typical compositions of rolling stocks are 4 carriages, 6 carriages, and 8 carriages. A depot has a limited storage capacity for the rolling stocks due to the limited number and length of parking tracks. Note that one rolling stock can be accommodated on a parking track that is constructed for the longer rolling stocks. Hence, the depot has different capacity constraints for the rolling stocks with different carriage compositions.Meanwhile, the storage capacity of a depot is usually reserved for two kinds of rolling stocks. One kind is the rolling stocks that consecutively depart from the depot to serve the train services before the operation period. The other kind is the rolling stocks that discretely depart from the depot during the operation period to serve the peak-hour train services during the off-to-peak transition period. Hence, constraint (4) specifies that the storage capacity ad,v reserved for the second kind of rolling stocks should be deducted from the overall depot storage capacity gd,v to acquire the reserved depot storage capacity for the first kind of rolling stocks:(4)∑i∈Idti≤vxi,d+∑i∈Iti≤v∑k∈Ki,dyd,ki≤gd,v−ad,v,∀d∈D,v∈V.


#### 4.3.4. Departure Capacity of Depots

The depots and their adjacent stations of an urban rail transit line are usually connected by the exit and entrance tracks. Note that both the exit and entrance tracks can be used for the departure of rolling stocks before the operation period, but each of them can only serve one departure direction. Moreover, due to the restrictions of the signal and interlocking equipment, the departure of two adjacent rolling stocks in the opposite directions should satisfy a minimum departure headway. Meanwhile, rolling stocks can depart from depots only after the start of working time, and they must arrive at the corresponding origin stations of their assigned train services before the start of the operation period. Therefore, an available departure period of limited duration can be obtained for each depot. Given the available departure period and minimum departure headway, constraint (6) requires that each depot should satisfy a restricted departure capacity in each direction.(5)∑i∈Idui=wxi,d+∑i∈Iui=1−w∑k∈Ki,dyd,ki≤ed,w,∀d∈D,w∈W.In addition, constraint (6) also restricts the total departure capacity of each depot in both directions.(6)∑i∈Idxi,d+∑i∈I∑k∈Ki,dyd,ki≤nd,∀d∈D.


#### 4.3.5. Capacity of Switch Stations

For the convenience of daily operation and scheduling, an urban rail transit line has several switch stations along the line. At a switch station, rolling stocks can switch their running directions to the opposite directions using crossing tracks that are located immediately before or after the corresponding switch station. Depending on the locations of depots as well as the signal and interlocking equipment settings, most of the switch stations can allow the rolling stocks to switch from one direction to another direction, while the rolling stocks cannot switch their running directions conversely. As a result, the switch operations of rolling stocks at the switch stations are complicated and could interrupt the normal operations at the switch stations. Therefore, two adjacent rolling stocks that need to switch their running directions at a switch station should be separated by a minimum switch headway. Meanwhile, only a limited period is available for the switch operations between the start of working time and the start of the operation period for each switch station. Therefore, constraint (7) ensures that the number of rolling stocks switching their running directions from 1−w to w at a switch station cannot exceed the capacity of the switch station in the direction w:(7)∑i∈Iui=w∑d∈Dk∈Ki,dyd,ki≤rk,w,∀k∈K,w∈W.


#### 4.3.6. Domain of Decision Variables

Constraints (8) and (9) restrict the domain of decision variables xi,d and yd,ki, where both the variables xi,d and yd,ki are binary variables:(8)xi,d=0,1,∀i∈I,d∈Di,(9)yd,ki=0,1,∀i∈I,d∈D,k∈Ki,d.


### 4.4. Mathematical Model Complexity Analysis

Given all candidate direct and indirect deadhead routes that can be generated in a polynomial time, the rolling stock deadhead routing problem can be formulated as a MILP model, which minimizes the total deadhead mileages in the objective function (1) while respecting the deadhead route selection as well as depot and switch station capacity constraints from (2) to (7).The problem is obviously NP-hard as it can be reduced to the multicommodity network flow problem with node capacity constraints which is a classical NP-hard problem (see, e.g., [25]). For an NP-hard problem, the existing complexity theory has already proven that it is generally difficult to find an exact optimal solution within polynomial time. However, even though the proposed model is a MILP model, it can be further transformed into a pure 0-1 linear programming model. Moreover, the model contains D×K×I variables and D×V+D×W+D+K×W constraints in the worst case, which only increase polynomially concerning the numbers of depots, switch stations, and trains on the transit line. In particular, preliminary computational tests demonstrate that state-of-the-art commercial optimization solvers can solve large-scale instances to optimality quickly on a personal computer. Hence, we directly utilize the commercial optimization solver to optimize the rolling stock deadhead routing problem in this paper.


## 4.1. Modeling Assumptions

Without loss of generality, the following assumptions are introduced to facilitate the model formulation process.(i)
Each depot is assumed to be adjacent to only one endpoint station or an intermediate station in the urban rail transit line. Note that the model proposed in the paper can be easily extended to describe more complicated layouts with connection tracks between depots and stations.(ii)
The train timetable along with the corresponding rolling stock circulation plan for the operation of the urban rail transit line is given. The train services that need to be performed by a rolling stock stored at the depot(s) are clarified.(iii)
Rolling stocks consecutively leave depots via either a direct route or an indirect route in the initiation period. Each rolling stock starts from its depot, carries no passengers en route, and runs as quickly as possible to the origin station of its served train service.(iv)
The deadhead movement of rolling stocks must be completed in the initiation period, and depots and switch stations have limited capacities.(v)
When optimizing the deadhead routes, the deadhead timetable specifying the arrival and departure times of each rolling stock at each visited station along its selected deadhead route is not considered.We formulate the rolling stock deadhead routing problem as a MILP model by pregenerating explicitly all candidate deadhead direct routes and indirect deadhead routes. The notations used in the model are introduced in Tables2 and 3.Table 2
Definitions of sets, indices, parameters, and decision variables.
Symbol
Definition
S
Set of stations, which are numbered along the upside direction,s∈S
D
Set of depots,d∈D
K
Set of switch stations,k∈K
I
Set of train services to be performed by the rolling stocks parking at depots in the initiation period,i∈I
W
Set of rolling stock running directions,W=0,1, where 0 and 1 represent the upside and downside directions, respectively
V
Set of rolling stock types, which are distinguished by the number of carriages of the rolling stocks; the setV is numbered in an ascending order according to the number of carriages, v∈V
I
d
Set of train services which can be performed by a rolling stock that departs from depotd using a direct route, Id=i∈Ibod,qi=ui⊂I
V
d
Set of rolling stock types which can be parked in depotd, Vd⊂V
D
i
Set of depots from which a rolling stock can depart to perform the train servicei using a direct route, Di=d∈Dbod,qi=ui⊂D
K
i
,
d
Set of switch stations which can be used for a rolling stock that departs from depotd using an indirect route to serve train i, Ki,d=k∈Kbod,pk=1−ui,bpk,qi=ui⊂K
l
s
′
Distance between stationss and s′
b
s
s
′
Running direction of a rolling stock from stations to s′bss′=0,1, where 0 and 1 represent the upside and downside directions, respectively
o
d
Depot station that is adjacent to depotd
g
d
,
v
Maximum number of rolling stocks of typev that can be accommodated at depot d
a
d
,
v
Number of train services specified to be performed by the rolling stocks of typev that depart from depot d during the operation period; the value of the parameter ad,v is determined by the rolling stock circulation plans
e
d
,
w
Maximum number of rolling stocks which can depart from depotd in the direction w; the value of ed,w is estimated by the available departure period (i.e., the initiation period) and safety headway of the same direction
n
d
Maximum number of rolling stocks which can depart from depotd in both directions; the value of nd is estimated by the available departure period (the initiation period) and safety headway of opposite directions
f
d
,
w
Departure distance of rolling stocks running from depotd to its depot station in the direction w
p
k
Station where switch stationk is located
r
k
,
w
Maximum number of rolling stocks that can be switched from direction1−w to w at the switch station k; the value of rk,w can be estimated by the available switch period (the initiation period) and switch headway
h
k
,
w
Switch distance of the rolling stocks by switching from direction1−w to w at the switch station k
q
i
Origin station of a train servicei
u
i
Running direction of a train serviceiui=0,1, where 0 and 1 represent the upside and downside directions, respectively
t
i
Required rolling stock type of a train serviceiTable 3
Definitions of decision variables.
Symbol
Definition
x
i
.
d
0-1 variable, 1 if train servicei is performed by a rolling stock which departs from depot d using a direct route, 0 otherwise
y
d
,
k
i
0-1 variable, 1 if train servicei is performed by a rolling stock which departs from depot d using an indirect route via switch station k, 0 otherwise
c
i
,
d
Continuous variable, representing the deadhead mileages of a rolling stock that travels from depotd to the origin station of the train service i


## 4.2. Objective Function

Rolling stocks usually do not carry passengers before the operation period, and they need to run quickly to the origin stations of their served train services. In this paper, the deadhead routing problem tries to minimize the total deadhead mileages to reduce the operation costs and improve the utilization efficiency of rolling stocks, which can be formulated as in the following equation:(1)minZ=∑i∈I∑d∈Dci,d,where variable ci,d represents the deadhead mileages of a rolling stock that travels from depot d to the origin station of train service i. The value of the variable ci,d depends on the type of deadhead route used by the rolling stock, the departure distance of the depot, and the switch distance of the switch station:(2)ci,d=fd,ui+lod,qi⋅xi,d+∑k∈Ki,dfd,1−ui+lod,pk+hk,ui+lpk,qi⋅yd,ki.In equation (2), if train service i is performed by a rolling stock that departs from depot d using a direct route, i.e., xi,d=1, the deadhead mileages ci,d are equal to the summation of the departure distance fd,ui in the same direction of train service i at depot d and the distance lod,qi between the station od that is adjacent to depot d and the origin station qi of train service i. Otherwise, if train service i is performed by a rolling stock that departs from depot d using an indirect route via a switch station k∗, i.e., yd,k∗i=1, the deadhead mileages ci,d consists of four parts. The first part is the departure distance fd,1−ui in the opposite direction of train service i at depot d. The second part represents the distance lod,pk∗ between the station od that is adjacent to depot station d and the switch station k∗. The last two parts express the switch distance hk∗,ui in the same direction of train service i at switch station k∗ and the distance lpk∗,qi from the switch station k∗ to the origin station qi of train service i.


## 4.3. Constraints

### 4.3.1. Uniqueness of Deadhead Routes

To obtain practically feasible rolling stock deadhead routes in the initiation period, constraint (3) enforces that the rolling stock required by each train service must choose either one direct or one indirect route, and the rolling stock must depart from the depot which accommodates it:(3)∑d∈Dti∈Vdxi,d+∑d∈Dti∈Vd∑k∈Ki,dyd,ki=1,∀i∈I.


### 4.3.2. Feasibility of Deadhead Routes

An urban rail transit line usually consists of two main tracks: one is for the upside direction and the other for the downside direction. Except for the depot stations and switch stations, other stations do not have additional sidings other than the main tracks. Therefore, the direct and indirect deadhead routes do not exist simultaneously for any pair of depots and train services. Depending on the direction of the train services, the locations of the origin stations of the train services, and the station that is adjacent to the depot, 4 feasible deadhead routes can be obtained, as shown in Figure2:(i)
In Figure2(a), train service i is in the upside direction. If depot d is located after the origin station of train service i along the upside direction, train service i can be served by a rolling stock that departs from depot d using a direct route. Otherwise, there is no direct route between train service i and depot d, i.e., if d∉Di, we have xi,d=0.(ii)
In Figure2(b), train service i is in the upside direction. If depot d is located after the origin station of train service i, and there are also nonempty switch stations Ki,d after depot d, train service i can be performed by a rolling stock that departs from depot d using indirect routes via any switch station in Ki,d, which is depicted as the thick dashed lines in Figure 2(b). Otherwise, if depot d is located before the origin station of train service i, and nonempty switch stations Ki,d can be found after depot d, there are also indirect routes via any switch station in Ki,d between the train service i and depot d, which is denoted as the thick solid lines in Figure 2(b). However, if Ki,d=∅, we have yd,ki=0.(iii)
Train servicei is in the downside direction, as in Figure 2(c). If depot d is located after the origin station of train service i, train service i cannot be performed by the rolling stock from depot d using a direct route, i.e., if d∉Di, we have xi,d=0.(iv)
Train servicei is in the downside direction, as in Figure 2(d). Regardless of the locations of depot d and train service i, train service i cannot be performed by the rolling stock from depot d using an indirect route when no switch stations Ki,d are located before depot d, i.e., if Ki,d=∅, we have yd,ki=0.Figure 2
Illustration of feasible rolling stock deadhead routes. (a) Direct route for a upside train service line. (b) Indirect route for a upside train service line. (c) Direct route for a downside train service line. (d) Indirect route for a downside train service line.
(a)
(b)
(c)
(d)


### 4.3.3. Storage Capacity of Depots

An urban rail transit line usually operates only one type of rolling stock, however, with different numbers of carriages. In this paper, the rolling stock is distinguished by the number of carriages. Typical compositions of rolling stocks are 4 carriages, 6 carriages, and 8 carriages. A depot has a limited storage capacity for the rolling stocks due to the limited number and length of parking tracks. Note that one rolling stock can be accommodated on a parking track that is constructed for the longer rolling stocks. Hence, the depot has different capacity constraints for the rolling stocks with different carriage compositions.Meanwhile, the storage capacity of a depot is usually reserved for two kinds of rolling stocks. One kind is the rolling stocks that consecutively depart from the depot to serve the train services before the operation period. The other kind is the rolling stocks that discretely depart from the depot during the operation period to serve the peak-hour train services during the off-to-peak transition period. Hence, constraint (4) specifies that the storage capacity ad,v reserved for the second kind of rolling stocks should be deducted from the overall depot storage capacity gd,v to acquire the reserved depot storage capacity for the first kind of rolling stocks:(4)∑i∈Idti≤vxi,d+∑i∈Iti≤v∑k∈Ki,dyd,ki≤gd,v−ad,v,∀d∈D,v∈V.


### 4.3.4. Departure Capacity of Depots

The depots and their adjacent stations of an urban rail transit line are usually connected by the exit and entrance tracks. Note that both the exit and entrance tracks can be used for the departure of rolling stocks before the operation period, but each of them can only serve one departure direction. Moreover, due to the restrictions of the signal and interlocking equipment, the departure of two adjacent rolling stocks in the opposite directions should satisfy a minimum departure headway. Meanwhile, rolling stocks can depart from depots only after the start of working time, and they must arrive at the corresponding origin stations of their assigned train services before the start of the operation period. Therefore, an available departure period of limited duration can be obtained for each depot. Given the available departure period and minimum departure headway, constraint (6) requires that each depot should satisfy a restricted departure capacity in each direction.(5)∑i∈Idui=wxi,d+∑i∈Iui=1−w∑k∈Ki,dyd,ki≤ed,w,∀d∈D,w∈W.In addition, constraint (6) also restricts the total departure capacity of each depot in both directions.(6)∑i∈Idxi,d+∑i∈I∑k∈Ki,dyd,ki≤nd,∀d∈D.


### 4.3.5. Capacity of Switch Stations

For the convenience of daily operation and scheduling, an urban rail transit line has several switch stations along the line. At a switch station, rolling stocks can switch their running directions to the opposite directions using crossing tracks that are located immediately before or after the corresponding switch station. Depending on the locations of depots as well as the signal and interlocking equipment settings, most of the switch stations can allow the rolling stocks to switch from one direction to another direction, while the rolling stocks cannot switch their running directions conversely. As a result, the switch operations of rolling stocks at the switch stations are complicated and could interrupt the normal operations at the switch stations. Therefore, two adjacent rolling stocks that need to switch their running directions at a switch station should be separated by a minimum switch headway. Meanwhile, only a limited period is available for the switch operations between the start of working time and the start of the operation period for each switch station. Therefore, constraint (7) ensures that the number of rolling stocks switching their running directions from 1−w to w at a switch station cannot exceed the capacity of the switch station in the direction w:(7)∑i∈Iui=w∑d∈Dk∈Ki,dyd,ki≤rk,w,∀k∈K,w∈W.


### 4.3.6. Domain of Decision Variables

Constraints (8) and (9) restrict the domain of decision variables xi,d and yd,ki, where both the variables xi,d and yd,ki are binary variables:(8)xi,d=0,1,∀i∈I,d∈Di,(9)yd,ki=0,1,∀i∈I,d∈D,k∈Ki,d.


## 4.3.1. Uniqueness of Deadhead Routes

To obtain practically feasible rolling stock deadhead routes in the initiation period, constraint (3) enforces that the rolling stock required by each train service must choose either one direct or one indirect route, and the rolling stock must depart from the depot which accommodates it:(3)∑d∈Dti∈Vdxi,d+∑d∈Dti∈Vd∑k∈Ki,dyd,ki=1,∀i∈I.


## 4.3.2. Feasibility of Deadhead Routes

An urban rail transit line usually consists of two main tracks: one is for the upside direction and the other for the downside direction. Except for the depot stations and switch stations, other stations do not have additional sidings other than the main tracks. Therefore, the direct and indirect deadhead routes do not exist simultaneously for any pair of depots and train services. Depending on the direction of the train services, the locations of the origin stations of the train services, and the station that is adjacent to the depot, 4 feasible deadhead routes can be obtained, as shown in Figure2:(i)
In Figure2(a), train service i is in the upside direction. If depot d is located after the origin station of train service i along the upside direction, train service i can be served by a rolling stock that departs from depot d using a direct route. Otherwise, there is no direct route between train service i and depot d, i.e., if d∉Di, we have xi,d=0.(ii)
In Figure2(b), train service i is in the upside direction. If depot d is located after the origin station of train service i, and there are also nonempty switch stations Ki,d after depot d, train service i can be performed by a rolling stock that departs from depot d using indirect routes via any switch station in Ki,d, which is depicted as the thick dashed lines in Figure 2(b). Otherwise, if depot d is located before the origin station of train service i, and nonempty switch stations Ki,d can be found after depot d, there are also indirect routes via any switch station in Ki,d between the train service i and depot d, which is denoted as the thick solid lines in Figure 2(b). However, if Ki,d=∅, we have yd,ki=0.(iii)
Train servicei is in the downside direction, as in Figure 2(c). If depot d is located after the origin station of train service i, train service i cannot be performed by the rolling stock from depot d using a direct route, i.e., if d∉Di, we have xi,d=0.(iv)
Train servicei is in the downside direction, as in Figure 2(d). Regardless of the locations of depot d and train service i, train service i cannot be performed by the rolling stock from depot d using an indirect route when no switch stations Ki,d are located before depot d, i.e., if Ki,d=∅, we have yd,ki=0.Figure 2
Illustration of feasible rolling stock deadhead routes. (a) Direct route for a upside train service line. (b) Indirect route for a upside train service line. (c) Direct route for a downside train service line. (d) Indirect route for a downside train service line.
(a)
(b)
(c)
(d)


## 4.3.3. Storage Capacity of Depots

An urban rail transit line usually operates only one type of rolling stock, however, with different numbers of carriages. In this paper, the rolling stock is distinguished by the number of carriages. Typical compositions of rolling stocks are 4 carriages, 6 carriages, and 8 carriages. A depot has a limited storage capacity for the rolling stocks due to the limited number and length of parking tracks. Note that one rolling stock can be accommodated on a parking track that is constructed for the longer rolling stocks. Hence, the depot has different capacity constraints for the rolling stocks with different carriage compositions.Meanwhile, the storage capacity of a depot is usually reserved for two kinds of rolling stocks. One kind is the rolling stocks that consecutively depart from the depot to serve the train services before the operation period. The other kind is the rolling stocks that discretely depart from the depot during the operation period to serve the peak-hour train services during the off-to-peak transition period. Hence, constraint (4) specifies that the storage capacity ad,v reserved for the second kind of rolling stocks should be deducted from the overall depot storage capacity gd,v to acquire the reserved depot storage capacity for the first kind of rolling stocks:(4)∑i∈Idti≤vxi,d+∑i∈Iti≤v∑k∈Ki,dyd,ki≤gd,v−ad,v,∀d∈D,v∈V.


## 4.3.4. Departure Capacity of Depots

The depots and their adjacent stations of an urban rail transit line are usually connected by the exit and entrance tracks. Note that both the exit and entrance tracks can be used for the departure of rolling stocks before the operation period, but each of them can only serve one departure direction. Moreover, due to the restrictions of the signal and interlocking equipment, the departure of two adjacent rolling stocks in the opposite directions should satisfy a minimum departure headway. Meanwhile, rolling stocks can depart from depots only after the start of working time, and they must arrive at the corresponding origin stations of their assigned train services before the start of the operation period. Therefore, an available departure period of limited duration can be obtained for each depot. Given the available departure period and minimum departure headway, constraint (6) requires that each depot should satisfy a restricted departure capacity in each direction.(5)∑i∈Idui=wxi,d+∑i∈Iui=1−w∑k∈Ki,dyd,ki≤ed,w,∀d∈D,w∈W.In addition, constraint (6) also restricts the total departure capacity of each depot in both directions.(6)∑i∈Idxi,d+∑i∈I∑k∈Ki,dyd,ki≤nd,∀d∈D.


## 4.3.5. Capacity of Switch Stations

For the convenience of daily operation and scheduling, an urban rail transit line has several switch stations along the line. At a switch station, rolling stocks can switch their running directions to the opposite directions using crossing tracks that are located immediately before or after the corresponding switch station. Depending on the locations of depots as well as the signal and interlocking equipment settings, most of the switch stations can allow the rolling stocks to switch from one direction to another direction, while the rolling stocks cannot switch their running directions conversely. As a result, the switch operations of rolling stocks at the switch stations are complicated and could interrupt the normal operations at the switch stations. Therefore, two adjacent rolling stocks that need to switch their running directions at a switch station should be separated by a minimum switch headway. Meanwhile, only a limited period is available for the switch operations between the start of working time and the start of the operation period for each switch station. Therefore, constraint (7) ensures that the number of rolling stocks switching their running directions from 1−w to w at a switch station cannot exceed the capacity of the switch station in the direction w:(7)∑i∈Iui=w∑d∈Dk∈Ki,dyd,ki≤rk,w,∀k∈K,w∈W.


## 4.3.6. Domain of Decision Variables

Constraints (8) and (9) restrict the domain of decision variables xi,d and yd,ki, where both the variables xi,d and yd,ki are binary variables:(8)xi,d=0,1,∀i∈I,d∈Di,(9)yd,ki=0,1,∀i∈I,d∈D,k∈Ki,d.


## 4.4. Mathematical Model Complexity Analysis

Given all candidate direct and indirect deadhead routes that can be generated in a polynomial time, the rolling stock deadhead routing problem can be formulated as a MILP model, which minimizes the total deadhead mileages in the objective function (1) while respecting the deadhead route selection as well as depot and switch station capacity constraints from (2) to (7).The problem is obviously NP-hard as it can be reduced to the multicommodity network flow problem with node capacity constraints which is a classical NP-hard problem (see, e.g., [25]). For an NP-hard problem, the existing complexity theory has already proven that it is generally difficult to find an exact optimal solution within polynomial time. However, even though the proposed model is a MILP model, it can be further transformed into a pure 0-1 linear programming model. Moreover, the model contains D×K×I variables and D×V+D×W+D+K×W constraints in the worst case, which only increase polynomially concerning the numbers of depots, switch stations, and trains on the transit line. In particular, preliminary computational tests demonstrate that state-of-the-art commercial optimization solvers can solve large-scale instances to optimality quickly on a personal computer. Hence, we directly utilize the commercial optimization solver to optimize the rolling stock deadhead routing problem in this paper.


## 5. Case Study

### 5.1. Case Description

Figure3 shows the sketch map of the Chongqing urban rail transit network in China, where line 3 is used to test the proposed method in the paper. Line 3 is one of the busiest lines in the Chongqing urban rail transit network, and it has a length of 54 km with 39 stations and an average spacing of 1421 m. In 2015, the average daily passenger demand reaches 689 thousand trips, and the annual passenger demand is over 250 million trips. The 6-carriage and 8-carriage rolling stocks are operated on line 3 with 3 circulation plans. The two endpoints of the first circulation plan are stations s1 and s26, those of the second circulation plan are stations s12 and s32, and those of the third circulation plan are stations s12 and s39. Line 3 starts and ends its operation at 6:30 am and 22:30 pm, respectively.Figure 3
Sketch map of Chongqing rail transit network.The detailed track layout of line 3 is given in Figure4. Two depots are responsible for the rolling stock maintenance works, of which depot d1 is a larger depot and depot d2 is a smaller one. The basic information of the two depots is provided in Table 4.Figure 4
Layout of the urban rail transit line 3 of Chongqing.Table 4
Basic information of the depotsd1 and d2.
Name
Station
MTC
DH_S (min)
DH_B (min)
DD (m)
d
1
s
12
52 (8 cars)
6
3
1239
d
2
s
37
21 (6 cars)
12
6
389In Table4, the columns “Station” and “MTC” indicate the adjacent stations and the maintenance capacities (i.e., the number of rolling stocks) of the two depots. According to the practical operation rules, depot d1 can accommodate both the 6-carriage and 8-carriage rolling stocks as the tracks of 8-carriage rolling stock can also be used for 6-carriage rolling stock. Furthermore, the columns “DH_S,” “DH_B,” and “DD” denote the departure headway of the same direction, the departure headway of different directions, and the departure distance of different directions, respectively. Besides, the available departure period in the initiation period is set to 60 min.Table5 lists the information of the 10 switch stations that are uniformly equipped in line 3. In Table 5, the column “Direction” denotes the switch direction of the corresponding switch station, where “0” means the upside direction and “1” means the downside direction. The column “State” represents the state of each switch station, where “1” means the switch station is available for daily operation and “0” means the switch station is temporarily reserved due to unpredictable disruptions. Note that the switch station k4 which is corresponding to the station s12 is also adjacent to the depot d1. As a result, the station s12 is only used for the departure operation rather than the switch operation of rolling stocks in the initiation period. The available switch period of all switch stations in the initiation period is also set to 60 min. The minimum switch headway is given in the column “SH,” and the switch distance is presented in the column “SD.”Table 5
Basic information of switch stations.
Name
Station
Direction
SH (min)
SD (m)
State
k
1
s
1
0
5
207
1
k
2
s
5
0
3.5
334
0
k
3
s
8
0
5
297
0
k
4
s
12
0
3.5
394
1
k
5
s
16
0
3.5
319
1
k
6
s
22
0
3.5
353
0
k
7
s
26
1
3.5
359
1
k
8
s
29
1
5
207
0
k
9
s
32
1
3.5
349
1
k
10
s
39
1
5
398
1We implement our model based on the timetable of line 3 on a weekday in 2015. After generating the rolling stock circulation plans for the given timetable, line 3 needs to operate 29 first train services at the beginning of the operation period, which demands the rolling stocks from the depotsd1 and d2. The rolling stock deadhead routes and the corresponding timetable generated by a dispatcher are shown in Figure 5. Specifically, the black solid black lines in Figure 5 indicate the deadhead routes and times before the operation period, while the solid blue lines represent the train services during the operation period. The departure of those 29 first train services at their origin stations are marked with black dots. Besides, the train services in the upside direction of the timetable are numbered with even numbers, while the train services in the downside direction are numbered with odd numbers. The detailed data of the considered train services are reported in Table 6. In Table 6, the columns TN, TOS, and TRD denote the basic information of train services, which are corresponding to the number, origin station, and running direction of the train services, respectively. Note that only the train services 16 and 20 require 8-carriage rolling stocks, while the other train services need 6-carriage rolling stocks. Meanwhile, the columns ROD, RDD, RSS, and RDM are the deadhead route information for the rolling stocks of the train services that are specified by experienced workers according to their empirical rules, which represent the origin depot, departure direction at the origin depot, switch stations for indirect routes, and deadhead mileages incurred by the deadhead route, respectively.Figure 5
Deadhead routes and the corresponding deadhead timetable generated by a dispatcher.Table 6
Data of train services during the initial operation period.
TN
TOS
TRD
ROD
RDD
RSS
RDM (m)
2
1
0
1
1
1
19686
4
1
0
1
1
1
19686
6
4
0
1
1
1
24598
8
6
0
1
1
1
28187
10
9
0
1
1
1
33512
12
11
0
1
1
1
36353
14
14
0
1
0
—
2963
16
16
0
1
0
—
5070
18
17
0
1
0
—
6142
20
19
0
1
0
—
8851
22
23
0
1
0
—
13768
24
25
0
1
0
—
15950
26
28
0
1
0
—
19383
1
2
1
1
1
—
18209
3
5
1
1
1
—
12664
5
7
1
1
1
—
9455
7
8
1
1
1
—
7906
9
11
1
1
1
—
2812
11
17
1
2
1
—
27713
13
19
1
2
1
—
25013
15
23
1
1
0
7
21101
17
26
1
1
0
7
17614
19
28
1
2
1
—
14472
21
30
1
2
0
10
19530
23
32
1
2
1
—
9722
25
32
1
1
0
9
24482
27
34
1
2
0
10
14084
29
36
1
2
0
10
10140
31
39
1
2
0
10
4322
Total:
473388


### 5.2. Computational Results

The IBM ILOG CPLEX solver is adopted to deal with the proposed optimization model, in which the embedded branch-and-cut algorithm can solve the model to optimality. All parameters in CPLEX are set to the default values, and all of the numerical experiments are performed on a PC with Intel Core i7-4700MQ 2.40 GHz CPU, 8 GB RAM, and Windows 10–64 bits operating system.An optimal solution of the test case is obtained in less than 1 s. Table7 provides the associated optimal rolling stock deadhead routes. The meanings of the columns “TN,” “ROD,” “RDD,” “RSS,” and “RDM” in Table 7 are the same as those in Table 6, and the column “DMR” denotes the deadhead mileage reduction rate compared with the empirical manual method where the positive (negative) sign represents the increase (decrease) of the deadhead mileages. In Table 7, it can be seen that the rolling stocks for 21 train services including 13 upside and 8 downside train services depart from the larger depot d1, which is located in the middle of line 3. Meanwhile, the remaining 8 downside train services are served by the rolling stocks departing from the smaller depot d2, which is located near to the end of line 3. Moreover, to minimize the total deadhead mileages, only 11 rolling stocks including 6 upside and 5 downside train services use the indirect deadhead routes and the remaining 18 rolling stocks travel through the direct deadhead routes.Table 7
Rolling stock deadhead routes obtained by the optimization method.
TN
ROD
RDD
RSS
RDM (m)
DMR (%)
2
1
1
1
19686
0
4
1
1
1
19686
0
6
1
1
1
24598
0
8
1
1
1
28187
0
10
1
1
1
33512
0
12
1
1
1
36353
0
14
1
0
—
2963
0
16
1
0
—
5070
0
18
1
0
—
6142
0
20
1
0
—
8851
0
22
1
0
—
13768
0
24
1
0
—
15950
0
26
1
0
—
19383
0
1
1
1
—
18209
0
3
1
1
—
12664
0
5
1
1
—
9455
0
7
1
1
—
7906
0
9
1
1
—
2812
0
11
2
1
—
27713
0
13
1
0
7
26018
4
15
1
0
7
21101
0
17
1
0
7
17614
0
19
2
1
—
14472
0
21
2
1
—
12062
−38.2
23
2
0
10
17190
76.8
25
2
1
—
9722
−60.3
27
2
1
—
6616
−53
29
2
1
—
2672
−73.6
31
2
0
10
4322
0
Total:
444697
−6.1By comparing the computational results in Tables6 and 7, it can be shown that the proposed optimization method does not significantly modify the rolling stock deadhead routes generated by the empirical manual method. On the other hand, only the deadhead routes of 2 train services are adjusted from the direct routes to the indirect ones, of which the deadhead mileages are slightly increased. At the same time, the deadhead routes of 4 train services are altered from the indirect routes to direct ones, through which the deadhead mileages are significantly reduced. As a result, the total deadhead mileages based on our optimization method are decreased by 28.691 km with a 6.1% reduction rate. Moreover, the annual total deadhead mileages are expected to decrease by over 10,000 km. Therefore, our proposed method is characterized by high solution quality and short computation time, and it could be implemented to improve the quality of rolling stock deadhead routing for operation initialization.In order to further compare the deadhead routes in Tables6 and 7 from the perspective of practical operations, we develop a heuristic approach in Algorithm 1 that can generate a feasible rolling stock deadhead timetable based on the optimization results of the rolling stock deadhead routing model in Section 4. More specifically, step 1 of Algorithm 1 adopts a simple priority rule-based sequential method to generate a basic deadhead timetable. After that, four strategies are further developed in step 2 of Algorithm 1 to recover the feasibility of the deadhead timetable. The detailed algorithmic steps of the heuristic approach are introduced in Algorithm 1, and the corresponding rolling stock deadhead timetable based on the deadhead routes in Table 7 is illustrated in Figure 6.Algorithm 1: Heuristic approach for generating a feasible rolling stock deadhead timetable based on the given deadhead routes.
Initialization
The index of each stationIDS; the depots d∈D; the first train services i∈I; the rolling stock deadhead routes route∈Routes; departure direction of a deadhead route wroute, route∈Routes; the set of indirect routes routeind; the set of direct routes routedir; the basic train service lines between any two adjacent stations; and the infrastructure capacities.
Step 1. Generate basic deadhead timetable
For
each depot d∈D
Select the set of first train servicesi∈Id and the corresponding deadhead routes routei∈Routesd that depart from this depot d.
Foreach deadhead route routei∈Routesd with wroute=1
If routei∈routeind∩IDSi≤IDSd
Sort train servicei according to the distance between si and sd from near to far. If there are several train services with the same departure station si, sort those train services in an ascending order by their departure times at the origin station si.
Schedule the rolling stocks according to the above sorted order with respect to the fixed train running times between any two adjacent stations, the departure headway, and switch headway.
End if routei∈routeind∩IDSi≤IDSd
If routei∈routedir∩IDSi≤IDSd
Sort train servicei according to the distance between si and sd from far to near. If there are several train services with the same departure station si, sort those train services in an ascending order by their departure times at the origin station si.
Schedule the rolling stocks according to the above sorted order with respect to the fixed train running times between any two adjacent stations, the departure headway, and switch headway.
End if routei∈routedir∩IDSi≤IDSd
If routei∈routeind∩IDSi≥IDSd
Sort train servicei according to the distance between si and sd from far to near. If there are several train services with the same departure station si, sort those train services in an ascending order by their departure times at the origin station si.
Schedule the rolling stocks according to the above sorted order with respect to the fixed train running times between any two adjacent stations, the departure headway, and switch headway.
End if routei∈routeind∩IDSi≥IDSd
End foreach deadhead route routei∈Routesd with wroute=1
Foreach deadhead route routei∈Routesd with wroute=0
Apply the same procedures as the condition withwroute=1, where routei∈routeind∩IDSi≥IDSd, routei∈routedir∩IDSi≥IDSd, and routei∈routedir∩IDSi≤IDSd.
End foreach deadhead route routei∈Routesd with wroute=0
End for
each depot d∈D
Step 2. Eliminate the conflicts in the deadhead timetable
In the case that the timetable obtained in step 1 still contains some conflicts, we propose the following four strategies to eliminate those conflicts.
Strategy (1): adjust the running speed and/or dwell times of the basic train services consisting of the infeasible routes
Strategy (2): exchange the departure orders of one infeasible route with other suitable routes from the same depot
Strategy (3): apply the adjustment methods in (1) and (2) at the same time
Strategy (4): select some infeasible routes with the minimum impact on the objective function value, and change those infeasible routes from indirect/direct routes to direct/indirect routes together with other three strategies.Figure 6
The deadhead routes and the corresponding deadhead timetable generated by a computer.We can also analyze the capacity utilization of the depots and switch stations from Table7, which is useful to identify the capacity bottlenecks of line 3 in terms of deadheading such that the total deadhead mileages may be further reduced. As reported, both the storage capacity utilization rates of the two depots are lower than 65%, which implies that the storage capacities of depots have no essential impact on the deadhead routes of rolling stocks. However, the departure capacities of depot d1 in both directions, as well as the departure capacity of depot d2 in the downside direction, are completely utilized, which means that the depot departure capacity significantly restricts the deadhead routing of rolling stocks. Furthermore, there are switch operations at only 3 switch stations and their capacity utilization rates are lower than 50%, indicating that the capacities of switch stations have little impact on the deadhead routing of the rolling stocks.


### 5.3. Measures to Decrease the Total Deadhead Mileages

We seek effective measures based on sensitivity analysis to further decrease the total rolling stock deadhead mileages of the test case. According to the computational results in Table7 and the capacity utilization rates of the depots and switch stations, two potential effective measures are identified: one is to open idle switch stations, and the other is to prolong the depot departure period.


#### 5.3.1. Opening Idle Switch Stations

We first evaluate the impact of opening closed switch stations on the total deadhead mileages. As introduced, line 3 has 10 switch stations, of which 6 switch stations are opened and the rest 4 switch stations are temporarily closed. The 4 closed switch stations are combined to generate 16 scenarios. The computational results of opening closed switch stations are illustrated in Figure7. In Figure 7, the horizontal axis represents the alternative scenarios of opening the switch stations. In particular, the left-most scenario “{−}” means that no new switch stations are opened. The subsequent scenarios are the ones to be evaluated, of which the numbers in the brackets represent the newly opened switch stations. Furthermore, the left vertical axis of Figure 7 denotes the total deadhead mileages of each scenario which is expressed by a bar in Figure 7, and the top horizontal dotted line in red color represents the total deadhead mileages of the corresponding empirical manual method. Besides, the right vertical axis of Figure 7 provides the total deadhead mileage reduction rate of each scenario compared with the empirical manual method, which is represented by the polyline in Figure 7.Figure 7
Effect of the measure to open closed switch stations.As observed, opening one extra switch station, e.g., switch stations 2 or 3, can significantly decrease the total deadhead mileages. When opening two extra switch stations, the scenarios containing the switch stations 2 or 3 outperform the other scenarios, among which the scenario containing both the switch stations 2 and 3 gives the minimum deadhead mileages. Opening switch stations 6 and 8 at the same time does not increase the reduction of total deadhead mileage. The combined effect of the location and switch direction of two switch stations and the train services of the timetable could be an explanation of this. Furthermore, when opening three extra switch stations, the scenarios containing both of the switch stations 2 and 3 are superior to other scenarios. The best scenario is obtained when both of the switch stations 2 and 3 are included, where the total deadhead mileages are reduced by 88.306 km with a reduction rate of 18.7%. Therefore, we recommend opening the switch station 3 only, where the total deadhead mileage reduction rate is 15.8% which is only 2.9% less than that of the best scenario. In conclusion, operating idle switch stations is an effective measure to reduce the total deadhead mileages.


#### 5.3.2. Prolonging the Depot Departure Period

We then evaluate the impact of prolonging the depot departure period on the total deadhead mileages. As indicated, the depot departure capacity is limited in line 3, which obviously influences the rolling stock deadhead routes and it could be improved to further reduce the total deadhead mileages. Here, the departure capacity of each depot in line 3 is increased by prolonging the departure period of the depot between its start of working time and the start of operation time. As the start of the operation time of line 3 is fixed, the departure period of each depot is extended by advancing the start of the working time of the depot. The depot departure period is extended from 60 min to 81 min with an increment of 3 min for each scenario. The computational results of prolonging the depot departure period for the 8 scenarios are shown in Figure8. In Figure 8, the horizontal axis indicates the departure period length of each scenario, and the meaning of other elements of Figure 8 is the same as those in Figure 7.Figure 8
Effect of the measure to prolong the depot departure period.It can be shown from Figure8 that the total deadhead mileages decrease moderately when the lengths of the depot departure period are prolonged from 60 min to 72 min, while the values of total deadhead mileages remain stable when the lengths of depot departure period are larger. The best deadhead routes are obtained when the depot departure period is prolonged by 12 min, where the total deadhead mileages are reduced by 36.159 km with a reduction rate of 7.6%. The results in Figure 8 can be explained by the capacity utilization rates of the depots and switch stations. Specifically, if the depot departure period is set to 72 min, the total departure capacity of depot d1 equals 25 rolling stocks which are smaller than the corresponding storage capacity of depot d1, and the total departure capacity of depot d2 is equal to 13 rolling stocks which is exactly the same as the storage capacity of depot d2. On the other hand, when the depot departure period is less than 72 min, it can be seen that the departure capacities of the two depots are critical bottlenecks. In this situation, a larger depot departure period of the depot could reduce the total deadhead mileages. However, when the depot departure period is greater than 72 min, the storage capacity of the depot d2 will become the bottleneck. As a result, prolonging the departure time period can no longer reduce the total deadhead mileages. In conclusion, prolonging the depot departure period can decrease the total deadhead mileages when the depot departure capacity is tighter than its storage capacity.


### 5.4. Further Extensions considering Operating Costs

The above two measures could increase the operating costs due to the needs of additional equipment maintenance works and human resources, which brings to the issue of achieving the balance between the operating costs and total deadhead mileages. In order to make this online real-time decision support tool more practical, the previous model can be further extended to incorporate the influence of operating costs. Thus, two objective functions in equations (10) and (11) are needed:(10)minz1=∑i∈I∑d∈Dci,d,(11)minz2=costoperating,where the costoperating is the corresponding operating costs. The operating costs costoperating in equation (12) can be presented as the sum of equipment utilization costs and human resource costs:(12)costoperating=∑k∈Kpricek⋅openk+pricetime⋅optime+protime.In equation (12), the parameters pricek and pricetime are the opening cost of a switch station k∈K and the incurred labor cost per unit of time during the initiation period, respectively. Three new decision variables are introduced here, of which the binary variable openk equals 1 if the switch station k is opened, integer variable optime indicates the time used for departing in the original departure period (the maximize number of this variable is the length of original departure period) and integer variable protime denotes how long the original depot departure period is prolonged (in min).With the newly added decision variablesopenk and protime, some of the constraints defined in Section 4 need to be reformulated, such as the constraints related to depot departure capacity and switch station capacity. In constraint (5), the right-hand side ed,w represents the maximum number of rolling stocks which can depart from depot d in the direction w. The value of ed,w is estimated based on the available depot departure period and departure headway in the same direction, which can be divided into two parts now, i.e., the rolling stocks departure without prolonging the depot departure period and the rolling stocks departure using the prolonged time protime. Therefore, the constraint (5) is reformulated as the new constraint (13):(13)∑i∈Idui=wxi,d+∑i∈Iui=1−w∑k∈Ki,dyd,ki≤optime⋅1hwd,w+protime⋅1hwd,w,∀d∈D,w∈W,where hwd,w is the departure headway of depot d in the direction w. The same is true for constraint (6), which is reformulated as the new constraint (14):(14)∑i∈Idxi,d+∑i∈I∑k∈Ki,dyd,ki≤optime⋅1hwd′+protime⋅1hwd′,∀d∈D,where hwd′ is the departure headway of depot d in the opposite direction.The switch station capacity constraint (7) is reformulated as the new constraints (15) and (16), where M is a sufficient large number. Constrain (15) indicates that only when the switch station k is opened, it can be used for the rolling stock turn-back operations. Constraint (16) denotes the revised switch station capacity based on the sum of the original deport departure period length optime and the increased depot departure period length protime divided by the switch station headway shk,w in the direction w:(15)∑i∈Iui=w∑d∈Dk∈Ki,dyd,ki≤openk⋅M,∀k∈K,w∈W,(16)∑i∈Iui=w∑d∈Dk∈Ki,dyd,ki≤protime+optimeshk,w,∀k∈K,w∈W.Note that most of the switch stations can allow the rolling stocks to switch their running directions from the direction1−w to the direction w, while the rolling stocks cannot switch their running directions from the direction w to the direction 1−w at the switch direction. However, there are also some switch stations that allow the rolling stocks to switch their running directions in both directions, i.e., both the switch from the direction 1−w to the direction w or from the direction w to the direction 1−w are possible. Thus, for those switch stations, both the total switch station capacity and the switch station capacity in each single switch direction should be satisfied.In addition, constraints (17) and (18) provide the upper bound values for the variable protime and the sum of variables openk over the set K. In particular, the parameter MaxTime represents the maximum length that the depot departure period can be prolonged. The value of MaxTime could be obtained through the comprehensive considerations of the labor costs, availability of staffs, and the operational safety conditions. Furthermore, the parameter MaxSwi in constraint (18) denotes the maximum number of switch stations that can be opened before the operation period, which is up to the urban rail transit company:(17)protime≤MaxTime,(18)∑k∈Kopenk≤MaxSwi.Besides, we need to formulate the relationship between the decision variablesoptime and protime. In short, only when the variable optime reaches its maximum value, the variable protime can be used for improving the quality of the solutions. Thus, we introduce another binary decision variable V, where V equals 0 if the value of the variable optime does not reach its maximum value, otherwise V equals 1. Constraints (19)–(22) enforce the relationship between the values of variables optime and protime:(19)V≤optimeMaxori,(20)V≥optimeMaxori−1,(21)protime≤M∗V,(22)optime≤Maxori,where the Maxori represents the upper bound value of the original departure period before the operation period.In summary, the complete extended model is listed as follows:Objective functions are as follows:(23)minZ1=∑i∈I∑d∈Dci,dminZ2=costoperatingsubject to:constraints:3-4,13–22xi,d=0,1,∀i∈I,d∈Di,yd,ki=0,1,∀i∈I,d∈D,k∈Kid,openk=0,1,∀k∈K,V=0,1,optime∈N,protime∈N.The extended model is a biobjective optimization problem. In this paper, we transform this problem into a single objective optimization problem by using the weighted-sum method [26–28]. Since the objectives Z1 and Z2 have different scales, we normalize them first. The normalized objectives Zii=1,2 are calculated by the following equation: Zi=Zi−Zimin/Zimax−Zimin. The values of Zimini=1,2 are obtained by optimizing Z1 and Z2, respectively. The values of Zimaxi=1,2 are determined by performing the optimization again with the following additional constraint: Zi′=Zi′min with i′≠i. The weights for Z1 and Z2 are denoted by the two nonnegative real numbers α1 and α2 (α1≥0, α2≥0), the sum of α1 and α2 is equal to 1. Hence, the new objective function can be formulated as(24)minZ=α1Z1+α2Z2.After seeking the advice of the operation manager at the Chongqing urban rail transit company, we set the cost of opening each switch stationpricek to 2000 CNY per day, and the labor cost per unit of time pricetime is set to 50 CNY per min. In order to find the proper value of α1 and α2, we perform a series of computation tests (50 tests) based on the settings of manual schedule. In these tests, the maximum number of switch stations allowed is set to 5 (i.e., MaxSwi=5) and the maximum value of original departure period is set to 60 min (i.e., Maxori=60 and MaxTime=0). The value of α1 ranges from 0.02 to 1 with an incremental value of 0.02 each time. Table 8 lists the detailed results of four nondominated solutions of the extended model, the manual schedule, and the optimal schedule obtained from the original model in Section 4.Table 8
Comparison of the results obtained by the empirical manual method, original model, and extended model.
Method
MaxSwi
Maxori
α
1
Switchindex
optime
Cost
RDM
Empirical manual method
5
60
—
[1, 7, 9, 10]
60
11000
473388
Original_model
5
60
—
[1, 7, 10]
60
9000
444697
Extended_model
5
60
0.02
[1, 10]
60
7000
464059
5
60
0.06
[1, 3, 10]
60
9000
417947
5
60
0.10
[1, 3, 7, 10]
60
11000
398585
5
60
0.14
[1, 2, 3, 7, 10]
60
13000
385082In Table8, the column “Switchindex” denotes the indices of the opened switch stations and the column “Cost” is the corresponding operating costs of this solution. The meanings of other columns are the same as those in Table 7. Compared with both the manual solution and original model’s solution, it can be seen that there is a Pareto solution of the extended model with the value of α1=0.06, where the extended model can achieve smaller rolling stock deadhead mileages with the same operating costs as the original model.Furthermore, two scenarios with 12 cases are tested to show the effectiveness of the proposed method. For the scenario I, the maximum length of the depot departure periodMaxori is fixed to 60 min with the value of MaxTime set to 0 min, and the value of MaxSwi is increased from 2 to 7 with an incremental value of 1 for each case, which is corresponding to the cases 1 to 6 in Table 8. For the scenario II that consists of the cases 7–12, in addition to increasing the value of MaxSwi from 2 to 7, the value of MaxTime is set to 30 min for each case with the original maximum depot departure period Maxori set to 60 min. Therefore, the length of the deport departure period in scenario II can reach 90 min. Similarly, for each case, we perform a set of experiments to obtain the proper value of α. The other input data are the same as those in Section 5.1, and CPLEX can also solve all the cases to optimality in less than 1 s. Table 9 lists the key statistics of the 12 cases.Table 9
Key statistics of different cases.
Case
MaxSwi
Maxori
MaxTime
Switchindex
optime
protime
α
1
Cost
RDM
1
2
60
—
[1, 10]
60
—
0.06
7000
464059
2
3
60
—
[1, 3, 10]
60
—
0.10
9000
417947
3
4
60
—
[1, 3, 7, 10]
60
—
0.40
11000
398585
4
5
60
—
[1, 2, 3, 7, 10]
60
—
0.14
13000
385082
5
6
60
—
[1, 2, 3, 7, 10]
60
—
0.14
13000
385082
6
7
60
—
[1, 2, 3, 7, 10]
60
—
0.14
13000
385082
7
2
60
30
[1, 10]
60
24
0.10
8200
449123
8
3
60
30
[1, 3, 10]
60
24
0.10
10200
403011
9
4
60
30
[1, 2, 3, 10]
60
24
0.30
12200
389508
10
5
60
30
[1, 2, 3, 7, 10]
60
24
0.40
14200
376600
11
6
60
30
[1, 2, 3, 7, 10]
60
24
0.40
14200
376600
12
7
60
30
[1, 2, 3, 7, 10]
60
24
0.40
14200
376600It can be seen from Table9 that the total deadhead mileages decrease when increasing the values of MaxSwi and MaxTime. Meanwhile, the operating costs are increasing. In addition, the total deadhead mileages stop decreasing when the value of MaxSwi is larger than or equal to 5 for both scenarios.Compared with the manual schedule in Table8, the schedule of cases 1, 2, 3, 7, and 8 can reduce the total deadhead mileages without increasing the operating costs. In addition, when compared with the schedule obtained from the original model, only the schedule of case 2 can reduce the total deadhead mileages without increasing the operating costs.Moreover, we can easily identify from the column “Switchindex” of Table 9 that the switch stations k1 and k10 are necessary to guarantee the feasibility of the problem, where those two switch stations are opened in every case. Similar to the conclusion in Section 5.3, Table 9 also shows that the opening of switch stations k2 and k3 can significantly reduce the total deadhead mileages, while using those two switch stations at the same time will increase the operating costs. Thus, the switch station k3 could be the first choice with the limited operating budget. Besides, it can be seen that the switch stations k9 in the manual schedule can be temporarily replaced by the switch station k2 or switch station k3, and the switch station k9 can be opened again during the operation period. The replacements of the switch stations are practical since it only requires slightly extra work at those switch stations.In short, the two measures of opening idle switch stations and prolonging the depot departure period are effective in generating better rolling stock deadhead routing plans than the empirical manual method. However, those two measures may impose more operating costs for the urban rail transit company. Therefore, when the urban rail transit company has enough budget, it could be an option for the urban transit rail company to apply both of the two measures at the same time. For instance, case 10 in Table9 with the minimum total deadhead mileages could be the best choice among all of the cases. On the other hand, if it is not allowed to prolong the deport departure period, case 5 in Table 9 could be considered the best choice. If the railway planner wants to have a high-quality schedule with lower operating cost, case 2 in Table 9 could be their ideal schedule. The computational results of the extended model for the new cases can provide more useful information about the operating costs and their corresponding impact on the rolling stock deadhead routing, which could help the urban rail transit planner make better decisions.


## 5.1. Case Description

Figure3 shows the sketch map of the Chongqing urban rail transit network in China, where line 3 is used to test the proposed method in the paper. Line 3 is one of the busiest lines in the Chongqing urban rail transit network, and it has a length of 54 km with 39 stations and an average spacing of 1421 m. In 2015, the average daily passenger demand reaches 689 thousand trips, and the annual passenger demand is over 250 million trips. The 6-carriage and 8-carriage rolling stocks are operated on line 3 with 3 circulation plans. The two endpoints of the first circulation plan are stations s1 and s26, those of the second circulation plan are stations s12 and s32, and those of the third circulation plan are stations s12 and s39. Line 3 starts and ends its operation at 6:30 am and 22:30 pm, respectively.Figure 3
Sketch map of Chongqing rail transit network.The detailed track layout of line 3 is given in Figure4. Two depots are responsible for the rolling stock maintenance works, of which depot d1 is a larger depot and depot d2 is a smaller one. The basic information of the two depots is provided in Table 4.Figure 4
Layout of the urban rail transit line 3 of Chongqing.Table 4
Basic information of the depotsd1 and d2.
Name
Station
MTC
DH_S (min)
DH_B (min)
DD (m)
d
1
s
12
52 (8 cars)
6
3
1239
d
2
s
37
21 (6 cars)
12
6
389In Table4, the columns “Station” and “MTC” indicate the adjacent stations and the maintenance capacities (i.e., the number of rolling stocks) of the two depots. According to the practical operation rules, depot d1 can accommodate both the 6-carriage and 8-carriage rolling stocks as the tracks of 8-carriage rolling stock can also be used for 6-carriage rolling stock. Furthermore, the columns “DH_S,” “DH_B,” and “DD” denote the departure headway of the same direction, the departure headway of different directions, and the departure distance of different directions, respectively. Besides, the available departure period in the initiation period is set to 60 min.Table5 lists the information of the 10 switch stations that are uniformly equipped in line 3. In Table 5, the column “Direction” denotes the switch direction of the corresponding switch station, where “0” means the upside direction and “1” means the downside direction. The column “State” represents the state of each switch station, where “1” means the switch station is available for daily operation and “0” means the switch station is temporarily reserved due to unpredictable disruptions. Note that the switch station k4 which is corresponding to the station s12 is also adjacent to the depot d1. As a result, the station s12 is only used for the departure operation rather than the switch operation of rolling stocks in the initiation period. The available switch period of all switch stations in the initiation period is also set to 60 min. The minimum switch headway is given in the column “SH,” and the switch distance is presented in the column “SD.”Table 5
Basic information of switch stations.
Name
Station
Direction
SH (min)
SD (m)
State
k
1
s
1
0
5
207
1
k
2
s
5
0
3.5
334
0
k
3
s
8
0
5
297
0
k
4
s
12
0
3.5
394
1
k
5
s
16
0
3.5
319
1
k
6
s
22
0
3.5
353
0
k
7
s
26
1
3.5
359
1
k
8
s
29
1
5
207
0
k
9
s
32
1
3.5
349
1
k
10
s
39
1
5
398
1We implement our model based on the timetable of line 3 on a weekday in 2015. After generating the rolling stock circulation plans for the given timetable, line 3 needs to operate 29 first train services at the beginning of the operation period, which demands the rolling stocks from the depotsd1 and d2. The rolling stock deadhead routes and the corresponding timetable generated by a dispatcher are shown in Figure 5. Specifically, the black solid black lines in Figure 5 indicate the deadhead routes and times before the operation period, while the solid blue lines represent the train services during the operation period. The departure of those 29 first train services at their origin stations are marked with black dots. Besides, the train services in the upside direction of the timetable are numbered with even numbers, while the train services in the downside direction are numbered with odd numbers. The detailed data of the considered train services are reported in Table 6. In Table 6, the columns TN, TOS, and TRD denote the basic information of train services, which are corresponding to the number, origin station, and running direction of the train services, respectively. Note that only the train services 16 and 20 require 8-carriage rolling stocks, while the other train services need 6-carriage rolling stocks. Meanwhile, the columns ROD, RDD, RSS, and RDM are the deadhead route information for the rolling stocks of the train services that are specified by experienced workers according to their empirical rules, which represent the origin depot, departure direction at the origin depot, switch stations for indirect routes, and deadhead mileages incurred by the deadhead route, respectively.Figure 5
Deadhead routes and the corresponding deadhead timetable generated by a dispatcher.Table 6
Data of train services during the initial operation period.
TN
TOS
TRD
ROD
RDD
RSS
RDM (m)
2
1
0
1
1
1
19686
4
1
0
1
1
1
19686
6
4
0
1
1
1
24598
8
6
0
1
1
1
28187
10
9
0
1
1
1
33512
12
11
0
1
1
1
36353
14
14
0
1
0
—
2963
16
16
0
1
0
—
5070
18
17
0
1
0
—
6142
20
19
0
1
0
—
8851
22
23
0
1
0
—
13768
24
25
0
1
0
—
15950
26
28
0
1
0
—
19383
1
2
1
1
1
—
18209
3
5
1
1
1
—
12664
5
7
1
1
1
—
9455
7
8
1
1
1
—
7906
9
11
1
1
1
—
2812
11
17
1
2
1
—
27713
13
19
1
2
1
—
25013
15
23
1
1
0
7
21101
17
26
1
1
0
7
17614
19
28
1
2
1
—
14472
21
30
1
2
0
10
19530
23
32
1
2
1
—
9722
25
32
1
1
0
9
24482
27
34
1
2
0
10
14084
29
36
1
2
0
10
10140
31
39
1
2
0
10
4322
Total:
473388


## 5.2. Computational Results

The IBM ILOG CPLEX solver is adopted to deal with the proposed optimization model, in which the embedded branch-and-cut algorithm can solve the model to optimality. All parameters in CPLEX are set to the default values, and all of the numerical experiments are performed on a PC with Intel Core i7-4700MQ 2.40 GHz CPU, 8 GB RAM, and Windows 10–64 bits operating system.An optimal solution of the test case is obtained in less than 1 s. Table7 provides the associated optimal rolling stock deadhead routes. The meanings of the columns “TN,” “ROD,” “RDD,” “RSS,” and “RDM” in Table 7 are the same as those in Table 6, and the column “DMR” denotes the deadhead mileage reduction rate compared with the empirical manual method where the positive (negative) sign represents the increase (decrease) of the deadhead mileages. In Table 7, it can be seen that the rolling stocks for 21 train services including 13 upside and 8 downside train services depart from the larger depot d1, which is located in the middle of line 3. Meanwhile, the remaining 8 downside train services are served by the rolling stocks departing from the smaller depot d2, which is located near to the end of line 3. Moreover, to minimize the total deadhead mileages, only 11 rolling stocks including 6 upside and 5 downside train services use the indirect deadhead routes and the remaining 18 rolling stocks travel through the direct deadhead routes.Table 7
Rolling stock deadhead routes obtained by the optimization method.
TN
ROD
RDD
RSS
RDM (m)
DMR (%)
2
1
1
1
19686
0
4
1
1
1
19686
0
6
1
1
1
24598
0
8
1
1
1
28187
0
10
1
1
1
33512
0
12
1
1
1
36353
0
14
1
0
—
2963
0
16
1
0
—
5070
0
18
1
0
—
6142
0
20
1
0
—
8851
0
22
1
0
—
13768
0
24
1
0
—
15950
0
26
1
0
—
19383
0
1
1
1
—
18209
0
3
1
1
—
12664
0
5
1
1
—
9455
0
7
1
1
—
7906
0
9
1
1
—
2812
0
11
2
1
—
27713
0
13
1
0
7
26018
4
15
1
0
7
21101
0
17
1
0
7
17614
0
19
2
1
—
14472
0
21
2
1
—
12062
−38.2
23
2
0
10
17190
76.8
25
2
1
—
9722
−60.3
27
2
1
—
6616
−53
29
2
1
—
2672
−73.6
31
2
0
10
4322
0
Total:
444697
−6.1By comparing the computational results in Tables6 and 7, it can be shown that the proposed optimization method does not significantly modify the rolling stock deadhead routes generated by the empirical manual method. On the other hand, only the deadhead routes of 2 train services are adjusted from the direct routes to the indirect ones, of which the deadhead mileages are slightly increased. At the same time, the deadhead routes of 4 train services are altered from the indirect routes to direct ones, through which the deadhead mileages are significantly reduced. As a result, the total deadhead mileages based on our optimization method are decreased by 28.691 km with a 6.1% reduction rate. Moreover, the annual total deadhead mileages are expected to decrease by over 10,000 km. Therefore, our proposed method is characterized by high solution quality and short computation time, and it could be implemented to improve the quality of rolling stock deadhead routing for operation initialization.In order to further compare the deadhead routes in Tables6 and 7 from the perspective of practical operations, we develop a heuristic approach in Algorithm 1 that can generate a feasible rolling stock deadhead timetable based on the optimization results of the rolling stock deadhead routing model in Section 4. More specifically, step 1 of Algorithm 1 adopts a simple priority rule-based sequential method to generate a basic deadhead timetable. After that, four strategies are further developed in step 2 of Algorithm 1 to recover the feasibility of the deadhead timetable. The detailed algorithmic steps of the heuristic approach are introduced in Algorithm 1, and the corresponding rolling stock deadhead timetable based on the deadhead routes in Table 7 is illustrated in Figure 6.Algorithm 1: Heuristic approach for generating a feasible rolling stock deadhead timetable based on the given deadhead routes.
Initialization
The index of each stationIDS; the depots d∈D; the first train services i∈I; the rolling stock deadhead routes route∈Routes; departure direction of a deadhead route wroute, route∈Routes; the set of indirect routes routeind; the set of direct routes routedir; the basic train service lines between any two adjacent stations; and the infrastructure capacities.
Step 1. Generate basic deadhead timetable
For
each depot d∈D
Select the set of first train servicesi∈Id and the corresponding deadhead routes routei∈Routesd that depart from this depot d.
Foreach deadhead route routei∈Routesd with wroute=1
If routei∈routeind∩IDSi≤IDSd
Sort train servicei according to the distance between si and sd from near to far. If there are several train services with the same departure station si, sort those train services in an ascending order by their departure times at the origin station si.
Schedule the rolling stocks according to the above sorted order with respect to the fixed train running times between any two adjacent stations, the departure headway, and switch headway.
End if routei∈routeind∩IDSi≤IDSd
If routei∈routedir∩IDSi≤IDSd
Sort train servicei according to the distance between si and sd from far to near. If there are several train services with the same departure station si, sort those train services in an ascending order by their departure times at the origin station si.
Schedule the rolling stocks according to the above sorted order with respect to the fixed train running times between any two adjacent stations, the departure headway, and switch headway.
End if routei∈routedir∩IDSi≤IDSd
If routei∈routeind∩IDSi≥IDSd
Sort train servicei according to the distance between si and sd from far to near. If there are several train services with the same departure station si, sort those train services in an ascending order by their departure times at the origin station si.
Schedule the rolling stocks according to the above sorted order with respect to the fixed train running times between any two adjacent stations, the departure headway, and switch headway.
End if routei∈routeind∩IDSi≥IDSd
End foreach deadhead route routei∈Routesd with wroute=1
Foreach deadhead route routei∈Routesd with wroute=0
Apply the same procedures as the condition withwroute=1, where routei∈routeind∩IDSi≥IDSd, routei∈routedir∩IDSi≥IDSd, and routei∈routedir∩IDSi≤IDSd.
End foreach deadhead route routei∈Routesd with wroute=0
End for
each depot d∈D
Step 2. Eliminate the conflicts in the deadhead timetable
In the case that the timetable obtained in step 1 still contains some conflicts, we propose the following four strategies to eliminate those conflicts.
Strategy (1): adjust the running speed and/or dwell times of the basic train services consisting of the infeasible routes
Strategy (2): exchange the departure orders of one infeasible route with other suitable routes from the same depot
Strategy (3): apply the adjustment methods in (1) and (2) at the same time
Strategy (4): select some infeasible routes with the minimum impact on the objective function value, and change those infeasible routes from indirect/direct routes to direct/indirect routes together with other three strategies.Figure 6
The deadhead routes and the corresponding deadhead timetable generated by a computer.We can also analyze the capacity utilization of the depots and switch stations from Table7, which is useful to identify the capacity bottlenecks of line 3 in terms of deadheading such that the total deadhead mileages may be further reduced. As reported, both the storage capacity utilization rates of the two depots are lower than 65%, which implies that the storage capacities of depots have no essential impact on the deadhead routes of rolling stocks. However, the departure capacities of depot d1 in both directions, as well as the departure capacity of depot d2 in the downside direction, are completely utilized, which means that the depot departure capacity significantly restricts the deadhead routing of rolling stocks. Furthermore, there are switch operations at only 3 switch stations and their capacity utilization rates are lower than 50%, indicating that the capacities of switch stations have little impact on the deadhead routing of the rolling stocks.


## 5.3. Measures to Decrease the Total Deadhead Mileages

We seek effective measures based on sensitivity analysis to further decrease the total rolling stock deadhead mileages of the test case. According to the computational results in Table7 and the capacity utilization rates of the depots and switch stations, two potential effective measures are identified: one is to open idle switch stations, and the other is to prolong the depot departure period.


### 5.3.1. Opening Idle Switch Stations

We first evaluate the impact of opening closed switch stations on the total deadhead mileages. As introduced, line 3 has 10 switch stations, of which 6 switch stations are opened and the rest 4 switch stations are temporarily closed. The 4 closed switch stations are combined to generate 16 scenarios. The computational results of opening closed switch stations are illustrated in Figure7. In Figure 7, the horizontal axis represents the alternative scenarios of opening the switch stations. In particular, the left-most scenario “{−}” means that no new switch stations are opened. The subsequent scenarios are the ones to be evaluated, of which the numbers in the brackets represent the newly opened switch stations. Furthermore, the left vertical axis of Figure 7 denotes the total deadhead mileages of each scenario which is expressed by a bar in Figure 7, and the top horizontal dotted line in red color represents the total deadhead mileages of the corresponding empirical manual method. Besides, the right vertical axis of Figure 7 provides the total deadhead mileage reduction rate of each scenario compared with the empirical manual method, which is represented by the polyline in Figure 7.Figure 7
Effect of the measure to open closed switch stations.As observed, opening one extra switch station, e.g., switch stations 2 or 3, can significantly decrease the total deadhead mileages. When opening two extra switch stations, the scenarios containing the switch stations 2 or 3 outperform the other scenarios, among which the scenario containing both the switch stations 2 and 3 gives the minimum deadhead mileages. Opening switch stations 6 and 8 at the same time does not increase the reduction of total deadhead mileage. The combined effect of the location and switch direction of two switch stations and the train services of the timetable could be an explanation of this. Furthermore, when opening three extra switch stations, the scenarios containing both of the switch stations 2 and 3 are superior to other scenarios. The best scenario is obtained when both of the switch stations 2 and 3 are included, where the total deadhead mileages are reduced by 88.306 km with a reduction rate of 18.7%. Therefore, we recommend opening the switch station 3 only, where the total deadhead mileage reduction rate is 15.8% which is only 2.9% less than that of the best scenario. In conclusion, operating idle switch stations is an effective measure to reduce the total deadhead mileages.


### 5.3.2. Prolonging the Depot Departure Period

We then evaluate the impact of prolonging the depot departure period on the total deadhead mileages. As indicated, the depot departure capacity is limited in line 3, which obviously influences the rolling stock deadhead routes and it could be improved to further reduce the total deadhead mileages. Here, the departure capacity of each depot in line 3 is increased by prolonging the departure period of the depot between its start of working time and the start of operation time. As the start of the operation time of line 3 is fixed, the departure period of each depot is extended by advancing the start of the working time of the depot. The depot departure period is extended from 60 min to 81 min with an increment of 3 min for each scenario. The computational results of prolonging the depot departure period for the 8 scenarios are shown in Figure8. In Figure 8, the horizontal axis indicates the departure period length of each scenario, and the meaning of other elements of Figure 8 is the same as those in Figure 7.Figure 8
Effect of the measure to prolong the depot departure period.It can be shown from Figure8 that the total deadhead mileages decrease moderately when the lengths of the depot departure period are prolonged from 60 min to 72 min, while the values of total deadhead mileages remain stable when the lengths of depot departure period are larger. The best deadhead routes are obtained when the depot departure period is prolonged by 12 min, where the total deadhead mileages are reduced by 36.159 km with a reduction rate of 7.6%. The results in Figure 8 can be explained by the capacity utilization rates of the depots and switch stations. Specifically, if the depot departure period is set to 72 min, the total departure capacity of depot d1 equals 25 rolling stocks which are smaller than the corresponding storage capacity of depot d1, and the total departure capacity of depot d2 is equal to 13 rolling stocks which is exactly the same as the storage capacity of depot d2. On the other hand, when the depot departure period is less than 72 min, it can be seen that the departure capacities of the two depots are critical bottlenecks. In this situation, a larger depot departure period of the depot could reduce the total deadhead mileages. However, when the depot departure period is greater than 72 min, the storage capacity of the depot d2 will become the bottleneck. As a result, prolonging the departure time period can no longer reduce the total deadhead mileages. In conclusion, prolonging the depot departure period can decrease the total deadhead mileages when the depot departure capacity is tighter than its storage capacity.


## 5.3.1. Opening Idle Switch Stations

We first evaluate the impact of opening closed switch stations on the total deadhead mileages. As introduced, line 3 has 10 switch stations, of which 6 switch stations are opened and the rest 4 switch stations are temporarily closed. The 4 closed switch stations are combined to generate 16 scenarios. The computational results of opening closed switch stations are illustrated in Figure7. In Figure 7, the horizontal axis represents the alternative scenarios of opening the switch stations. In particular, the left-most scenario “{−}” means that no new switch stations are opened. The subsequent scenarios are the ones to be evaluated, of which the numbers in the brackets represent the newly opened switch stations. Furthermore, the left vertical axis of Figure 7 denotes the total deadhead mileages of each scenario which is expressed by a bar in Figure 7, and the top horizontal dotted line in red color represents the total deadhead mileages of the corresponding empirical manual method. Besides, the right vertical axis of Figure 7 provides the total deadhead mileage reduction rate of each scenario compared with the empirical manual method, which is represented by the polyline in Figure 7.Figure 7
Effect of the measure to open closed switch stations.As observed, opening one extra switch station, e.g., switch stations 2 or 3, can significantly decrease the total deadhead mileages. When opening two extra switch stations, the scenarios containing the switch stations 2 or 3 outperform the other scenarios, among which the scenario containing both the switch stations 2 and 3 gives the minimum deadhead mileages. Opening switch stations 6 and 8 at the same time does not increase the reduction of total deadhead mileage. The combined effect of the location and switch direction of two switch stations and the train services of the timetable could be an explanation of this. Furthermore, when opening three extra switch stations, the scenarios containing both of the switch stations 2 and 3 are superior to other scenarios. The best scenario is obtained when both of the switch stations 2 and 3 are included, where the total deadhead mileages are reduced by 88.306 km with a reduction rate of 18.7%. Therefore, we recommend opening the switch station 3 only, where the total deadhead mileage reduction rate is 15.8% which is only 2.9% less than that of the best scenario. In conclusion, operating idle switch stations is an effective measure to reduce the total deadhead mileages.


## 5.3.2. Prolonging the Depot Departure Period

We then evaluate the impact of prolonging the depot departure period on the total deadhead mileages. As indicated, the depot departure capacity is limited in line 3, which obviously influences the rolling stock deadhead routes and it could be improved to further reduce the total deadhead mileages. Here, the departure capacity of each depot in line 3 is increased by prolonging the departure period of the depot between its start of working time and the start of operation time. As the start of the operation time of line 3 is fixed, the departure period of each depot is extended by advancing the start of the working time of the depot. The depot departure period is extended from 60 min to 81 min with an increment of 3 min for each scenario. The computational results of prolonging the depot departure period for the 8 scenarios are shown in Figure8. In Figure 8, the horizontal axis indicates the departure period length of each scenario, and the meaning of other elements of Figure 8 is the same as those in Figure 7.Figure 8
Effect of the measure to prolong the depot departure period.It can be shown from Figure8 that the total deadhead mileages decrease moderately when the lengths of the depot departure period are prolonged from 60 min to 72 min, while the values of total deadhead mileages remain stable when the lengths of depot departure period are larger. The best deadhead routes are obtained when the depot departure period is prolonged by 12 min, where the total deadhead mileages are reduced by 36.159 km with a reduction rate of 7.6%. The results in Figure 8 can be explained by the capacity utilization rates of the depots and switch stations. Specifically, if the depot departure period is set to 72 min, the total departure capacity of depot d1 equals 25 rolling stocks which are smaller than the corresponding storage capacity of depot d1, and the total departure capacity of depot d2 is equal to 13 rolling stocks which is exactly the same as the storage capacity of depot d2. On the other hand, when the depot departure period is less than 72 min, it can be seen that the departure capacities of the two depots are critical bottlenecks. In this situation, a larger depot departure period of the depot could reduce the total deadhead mileages. However, when the depot departure period is greater than 72 min, the storage capacity of the depot d2 will become the bottleneck. As a result, prolonging the departure time period can no longer reduce the total deadhead mileages. In conclusion, prolonging the depot departure period can decrease the total deadhead mileages when the depot departure capacity is tighter than its storage capacity.


## 5.4. Further Extensions considering Operating Costs

The above two measures could increase the operating costs due to the needs of additional equipment maintenance works and human resources, which brings to the issue of achieving the balance between the operating costs and total deadhead mileages. In order to make this online real-time decision support tool more practical, the previous model can be further extended to incorporate the influence of operating costs. Thus, two objective functions in equations (10) and (11) are needed:(10)minz1=∑i∈I∑d∈Dci,d,(11)minz2=costoperating,where the costoperating is the corresponding operating costs. The operating costs costoperating in equation (12) can be presented as the sum of equipment utilization costs and human resource costs:(12)costoperating=∑k∈Kpricek⋅openk+pricetime⋅optime+protime.In equation (12), the parameters pricek and pricetime are the opening cost of a switch station k∈K and the incurred labor cost per unit of time during the initiation period, respectively. Three new decision variables are introduced here, of which the binary variable openk equals 1 if the switch station k is opened, integer variable optime indicates the time used for departing in the original departure period (the maximize number of this variable is the length of original departure period) and integer variable protime denotes how long the original depot departure period is prolonged (in min).With the newly added decision variablesopenk and protime, some of the constraints defined in Section 4 need to be reformulated, such as the constraints related to depot departure capacity and switch station capacity. In constraint (5), the right-hand side ed,w represents the maximum number of rolling stocks which can depart from depot d in the direction w. The value of ed,w is estimated based on the available depot departure period and departure headway in the same direction, which can be divided into two parts now, i.e., the rolling stocks departure without prolonging the depot departure period and the rolling stocks departure using the prolonged time protime. Therefore, the constraint (5) is reformulated as the new constraint (13):(13)∑i∈Idui=wxi,d+∑i∈Iui=1−w∑k∈Ki,dyd,ki≤optime⋅1hwd,w+protime⋅1hwd,w,∀d∈D,w∈W,where hwd,w is the departure headway of depot d in the direction w. The same is true for constraint (6), which is reformulated as the new constraint (14):(14)∑i∈Idxi,d+∑i∈I∑k∈Ki,dyd,ki≤optime⋅1hwd′+protime⋅1hwd′,∀d∈D,where hwd′ is the departure headway of depot d in the opposite direction.The switch station capacity constraint (7) is reformulated as the new constraints (15) and (16), where M is a sufficient large number. Constrain (15) indicates that only when the switch station k is opened, it can be used for the rolling stock turn-back operations. Constraint (16) denotes the revised switch station capacity based on the sum of the original deport departure period length optime and the increased depot departure period length protime divided by the switch station headway shk,w in the direction w:(15)∑i∈Iui=w∑d∈Dk∈Ki,dyd,ki≤openk⋅M,∀k∈K,w∈W,(16)∑i∈Iui=w∑d∈Dk∈Ki,dyd,ki≤protime+optimeshk,w,∀k∈K,w∈W.Note that most of the switch stations can allow the rolling stocks to switch their running directions from the direction1−w to the direction w, while the rolling stocks cannot switch their running directions from the direction w to the direction 1−w at the switch direction. However, there are also some switch stations that allow the rolling stocks to switch their running directions in both directions, i.e., both the switch from the direction 1−w to the direction w or from the direction w to the direction 1−w are possible. Thus, for those switch stations, both the total switch station capacity and the switch station capacity in each single switch direction should be satisfied.In addition, constraints (17) and (18) provide the upper bound values for the variable protime and the sum of variables openk over the set K. In particular, the parameter MaxTime represents the maximum length that the depot departure period can be prolonged. The value of MaxTime could be obtained through the comprehensive considerations of the labor costs, availability of staffs, and the operational safety conditions. Furthermore, the parameter MaxSwi in constraint (18) denotes the maximum number of switch stations that can be opened before the operation period, which is up to the urban rail transit company:(17)protime≤MaxTime,(18)∑k∈Kopenk≤MaxSwi.Besides, we need to formulate the relationship between the decision variablesoptime and protime. In short, only when the variable optime reaches its maximum value, the variable protime can be used for improving the quality of the solutions. Thus, we introduce another binary decision variable V, where V equals 0 if the value of the variable optime does not reach its maximum value, otherwise V equals 1. Constraints (19)–(22) enforce the relationship between the values of variables optime and protime:(19)V≤optimeMaxori,(20)V≥optimeMaxori−1,(21)protime≤M∗V,(22)optime≤Maxori,where the Maxori represents the upper bound value of the original departure period before the operation period.In summary, the complete extended model is listed as follows:Objective functions are as follows:(23)minZ1=∑i∈I∑d∈Dci,dminZ2=costoperatingsubject to:constraints:3-4,13–22xi,d=0,1,∀i∈I,d∈Di,yd,ki=0,1,∀i∈I,d∈D,k∈Kid,openk=0,1,∀k∈K,V=0,1,optime∈N,protime∈N.The extended model is a biobjective optimization problem. In this paper, we transform this problem into a single objective optimization problem by using the weighted-sum method [26–28]. Since the objectives Z1 and Z2 have different scales, we normalize them first. The normalized objectives Zii=1,2 are calculated by the following equation: Zi=Zi−Zimin/Zimax−Zimin. The values of Zimini=1,2 are obtained by optimizing Z1 and Z2, respectively. The values of Zimaxi=1,2 are determined by performing the optimization again with the following additional constraint: Zi′=Zi′min with i′≠i. The weights for Z1 and Z2 are denoted by the two nonnegative real numbers α1 and α2 (α1≥0, α2≥0), the sum of α1 and α2 is equal to 1. Hence, the new objective function can be formulated as(24)minZ=α1Z1+α2Z2.After seeking the advice of the operation manager at the Chongqing urban rail transit company, we set the cost of opening each switch stationpricek to 2000 CNY per day, and the labor cost per unit of time pricetime is set to 50 CNY per min. In order to find the proper value of α1 and α2, we perform a series of computation tests (50 tests) based on the settings of manual schedule. In these tests, the maximum number of switch stations allowed is set to 5 (i.e., MaxSwi=5) and the maximum value of original departure period is set to 60 min (i.e., Maxori=60 and MaxTime=0). The value of α1 ranges from 0.02 to 1 with an incremental value of 0.02 each time. Table 8 lists the detailed results of four nondominated solutions of the extended model, the manual schedule, and the optimal schedule obtained from the original model in Section 4.Table 8
Comparison of the results obtained by the empirical manual method, original model, and extended model.
Method
MaxSwi
Maxori
α
1
Switchindex
optime
Cost
RDM
Empirical manual method
5
60
—
[1, 7, 9, 10]
60
11000
473388
Original_model
5
60
—
[1, 7, 10]
60
9000
444697
Extended_model
5
60
0.02
[1, 10]
60
7000
464059
5
60
0.06
[1, 3, 10]
60
9000
417947
5
60
0.10
[1, 3, 7, 10]
60
11000
398585
5
60
0.14
[1, 2, 3, 7, 10]
60
13000
385082In Table8, the column “Switchindex” denotes the indices of the opened switch stations and the column “Cost” is the corresponding operating costs of this solution. The meanings of other columns are the same as those in Table 7. Compared with both the manual solution and original model’s solution, it can be seen that there is a Pareto solution of the extended model with the value of α1=0.06, where the extended model can achieve smaller rolling stock deadhead mileages with the same operating costs as the original model.Furthermore, two scenarios with 12 cases are tested to show the effectiveness of the proposed method. For the scenario I, the maximum length of the depot departure periodMaxori is fixed to 60 min with the value of MaxTime set to 0 min, and the value of MaxSwi is increased from 2 to 7 with an incremental value of 1 for each case, which is corresponding to the cases 1 to 6 in Table 8. For the scenario II that consists of the cases 7–12, in addition to increasing the value of MaxSwi from 2 to 7, the value of MaxTime is set to 30 min for each case with the original maximum depot departure period Maxori set to 60 min. Therefore, the length of the deport departure period in scenario II can reach 90 min. Similarly, for each case, we perform a set of experiments to obtain the proper value of α. The other input data are the same as those in Section 5.1, and CPLEX can also solve all the cases to optimality in less than 1 s. Table 9 lists the key statistics of the 12 cases.Table 9
Key statistics of different cases.
Case
MaxSwi
Maxori
MaxTime
Switchindex
optime
protime
α
1
Cost
RDM
1
2
60
—
[1, 10]
60
—
0.06
7000
464059
2
3
60
—
[1, 3, 10]
60
—
0.10
9000
417947
3
4
60
—
[1, 3, 7, 10]
60
—
0.40
11000
398585
4
5
60
—
[1, 2, 3, 7, 10]
60
—
0.14
13000
385082
5
6
60
—
[1, 2, 3, 7, 10]
60
—
0.14
13000
385082
6
7
60
—
[1, 2, 3, 7, 10]
60
—
0.14
13000
385082
7
2
60
30
[1, 10]
60
24
0.10
8200
449123
8
3
60
30
[1, 3, 10]
60
24
0.10
10200
403011
9
4
60
30
[1, 2, 3, 10]
60
24
0.30
12200
389508
10
5
60
30
[1, 2, 3, 7, 10]
60
24
0.40
14200
376600
11
6
60
30
[1, 2, 3, 7, 10]
60
24
0.40
14200
376600
12
7
60
30
[1, 2, 3, 7, 10]
60
24
0.40
14200
376600It can be seen from Table9 that the total deadhead mileages decrease when increasing the values of MaxSwi and MaxTime. Meanwhile, the operating costs are increasing. In addition, the total deadhead mileages stop decreasing when the value of MaxSwi is larger than or equal to 5 for both scenarios.Compared with the manual schedule in Table8, the schedule of cases 1, 2, 3, 7, and 8 can reduce the total deadhead mileages without increasing the operating costs. In addition, when compared with the schedule obtained from the original model, only the schedule of case 2 can reduce the total deadhead mileages without increasing the operating costs.Moreover, we can easily identify from the column “Switchindex” of Table 9 that the switch stations k1 and k10 are necessary to guarantee the feasibility of the problem, where those two switch stations are opened in every case. Similar to the conclusion in Section 5.3, Table 9 also shows that the opening of switch stations k2 and k3 can significantly reduce the total deadhead mileages, while using those two switch stations at the same time will increase the operating costs. Thus, the switch station k3 could be the first choice with the limited operating budget. Besides, it can be seen that the switch stations k9 in the manual schedule can be temporarily replaced by the switch station k2 or switch station k3, and the switch station k9 can be opened again during the operation period. The replacements of the switch stations are practical since it only requires slightly extra work at those switch stations.In short, the two measures of opening idle switch stations and prolonging the depot departure period are effective in generating better rolling stock deadhead routing plans than the empirical manual method. However, those two measures may impose more operating costs for the urban rail transit company. Therefore, when the urban rail transit company has enough budget, it could be an option for the urban transit rail company to apply both of the two measures at the same time. For instance, case 10 in Table9 with the minimum total deadhead mileages could be the best choice among all of the cases. On the other hand, if it is not allowed to prolong the deport departure period, case 5 in Table 9 could be considered the best choice. If the railway planner wants to have a high-quality schedule with lower operating cost, case 2 in Table 9 could be their ideal schedule. The computational results of the extended model for the new cases can provide more useful information about the operating costs and their corresponding impact on the rolling stock deadhead routing, which could help the urban rail transit planner make better decisions.


## 6. Conclusion

The rolling stock deadhead routing problem before the operation period is closely related to rolling stock circulation plans of an urban rail transit line. However, this problem has not been widely recognized in the literature. Furthermore, the deadhead routes in practice are still manually scheduled by experienced dispatchers with empirical rules. In this paper, we develop a mixed integer linear program (MILP), which minimizes the total deadhead mileages, to solve the problem with multiple circulation plans, depots, and rolling stock types. Our approach can be complied as a real-time decision support toll in the current train timetabling system of an urban rail transit line. The model is polynomially bounded with respect to the numbers of depots, switch stations, and train services so that the large-scale cases can be efficiently solved using the state-of-the-art commercial optimization solvers on a personal computer. A heuristic approach is developed based on the optimization results of the proposed rolling stock deadhead routing model, which can easily generate a feasible rolling stock deadhead timetable.Real-world instances based on the urban rail transit line 3 of Chongqing in China are designed to verify the effectiveness of the proposed method. In particular, computational results demonstrate that our model can obtain a better solution by slightly modifying the deadhead routes compared with the empirical manual method. Furthermore, it is indicated that the deadhead movement of rolling stocks is largely restricted by the depot capacity rather than the switch station capacity. Moreover, in order to further reduce the total deadhead mileages, sensitivity analysis is conducted to seek effective measures. The results of the sensitivity analysis show that opening idle switch stations is very effective to improve the utilization efficiency of rolling stocks considering the given viable technical and economic conditions. However, prolonging the depot departure period only takes effects when the departure capacity of depots is smaller than the storage capacity. Besides, an extended model considering the impact of operating costs is also proposed, where more useful information is obtained by numerically testing different cases and the extended model could help the planners make a better decision in case of a special situation.The future work of this paper can be extended in the following three interesting directions. First, implementation of the model on more real-world cases with different characteristics is necessary to test the scalability and applicability of the model. Second, the extension of the model to further consider the train timetable, including the deadheading timetable before the operation period and the whole operation day’s timetable, can provide more system-wide benefits in practice [29]. Third, some new mathematical formulations and solution methods can be further developed by modeling the problem as a similar vehicle routing problem, which can accurately consider the dynamic boarding and alighting of passengers and the rolling stock seat capacity [30].



---

*Source: 3809734-2020-01-22.xml*