# Integrated Optimization of Service-Oriented Train Plan and Schedule on Intercity Rail Network with Varying Demand

Authors: Wenliang Zhou; Junli Tian; Lianbo Deng; Jin Qin
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

For a better service level of a train operating plan, we propose an integrated optimization method of train planning and train scheduling, which generally are optimized, respectively. Based on the cost analysis of both passengers travelling and enterprises operation, and the constraint analysis of trains operation, we construct a multiobjective function and build an integrated optimization model with the aim of reducing both passenger travel costs and enterprise operating costs. Then, a solving algorithm is established based on the simulated annealing algorithm. Finally, using as an example the Changzhutan intercity rail network, as an example we analyze the optimized results and the influence of the model parameters on the results.


---

## Body

## 1. Introduction

A passenger train operating plan (TOP) is not only the basis of train organization and station operation for enterprise, but also the foundation of train choice for passengers travelling by rail transit (e.g., an urban railway system, intercity railway system, and high-speed railway system). A high-quality TOP directly contributes to improving the level of passenger service and boosts enterprise operation efficiency. The TOP generally should arrange origin and destination stations, run routes, intermediate stations, vehicle numbers, and schedule for trains. More broadly, it also determines the crew scheduling and usage plan of the locomotive or electric multiple units (EMUs). However, the latter part of the TOP is not considered in this paper. Due to the complexity and difficulty of solving the TOP of a large-scale rail network, the TOP problem is usually divided into two subproblems: the train planning problem and train scheduling problem, which are solved one by one. Firstly, the train plan is optimized to arrange the origin and destination station, run route, intermediate stations, vehicle number, and frequency of trains with the aim of improving both the passenger travel benefit and enterprise operation profit. And then the train scheduling problem is solved in order to schedule each train’s departure and arrival time at each station based on the former optimized train plan.Most research on the train planning problem so far concentrates on designing an optimization model and its algorithm, aiming at getting a better service-level and high-benefit train plan with constraints of line and station capacity and rail resources (e.g., maximum departure number per day and available vehicles, etc.). Anthony [1] gave a basic frame for solving the passenger train planning problem as early as 1965. Chang et al. [2] proposed a multiobjective model and its algorithm of a train plan with the aim of reducing both enterprise operating costs and passenger travel cost. Yaghini et al. [3] took into account the passenger direct ratio besides travel costs in optimizing train plan. Wang et al. [4] provided an optimization method for a periodic train plan. Recently, some studies [5–7] combined the passenger train choice problem into the train plan problem and accordingly proposed the bilevel programming method of a train plan based on the leader-following relation between formulating a train plan and passenger train choice. For more examples of train plan optimization, see Schmidt and Schöbel [8], Goossens et al. [9], and Schöbel and Scholl [10].The train scheduling problem is to generally find an optimal or satisfying train timetable with a given optimization objective, subject to a lot of operational and safety constraints (e.g., arrival and departure headway requirements). A branch-and-bound algorithm, Lagrangian relaxation algorithm, and simulation method are widespread used to solve this problem. Higgins et al. [11] developed a branch-and-bound solution framework and some heuristic techniques to find feasible train timetables, and Zhou and Zhong [12] further incorporated some effective rules into the branch-and-bound algorithm for improving its solving efficiency. Brännlund et al. [13] proposed a Lagrangian relaxation approach to find a profit-maximizing train timetable. Dorfman and Medanic [14] proposed an effective simulation approach called TAS to solve the large-scale and real-world train scheduling problem, and Li et al. [15] and Xu et al. [16] further improved TAS by introducing some modified rules and efficient strategies inserted into it. For more studies of train scheduling, refer to Jong et al. [17], Sahana et al. [18], Yalçinkaya and Mirac Bayhan [19], and Zhou et al. [20].Obviously, optimizing a train plan and train schedule successively has some drawbacks in enhancing the passenger service level and satisfying varying travel demands of intercity rail. First, with the lack of time information, when optimizing a train plan, it is impossible to describe in detail passenger transfer time, wait time, and in-vehicle time determined exactly by a train timetable. Thus, improving passenger travel time is beyond the train plan problem to some extent. And the optimization of a train timetable generally aims to minimize the total travel time of trains, but not of passengers, because it has no passenger volume information about the train. Moreover, this two-stage method cannot make trains’ time distribution fit passenger demand distribution better in one day. To overcome the drawbacks thoroughly, combining the train plan and train schedule as a whole, that is, TOP, an integrated optimization of them is an effective alternative. Compared with the two-stage approach, the integrated optimization method has the following differences.(1)
It is to optimize train plan and train schedule simultaneously based on a rail network and its passengers demand distributions, while the two-stage method is firstly to determine a train plan which is taken as one input when scheduling trains latter. Thus, the integrated method has the decision variables and constraints of both train planning and train scheduling.(2)
Although reducing passengers travel costs and enterprise operating costs is taken as the objective in both two methods, their calculation is based on a train schedule in the integrated method while that is only based on a train plan in the two-stage method.It should be noted that the efficiency of this integrated optimization is not a knotty obstacle for an intercity rail network with a relatively small scale owing to the improvement of computer speed and the development of modern optimization algorithm.The main contributions of this paper are as follows.(1)
An integrated optimization model of train planning and scheduling is built to minimize both passenger travel costs and enterprise operating costs. It can more exactly and fully describe passenger travel costs.(2)
A solving algorithm based on simulated annealing algorithms (SA) is designed to solve the proposed optimization model.The remainder of this paper is organized as follows. In Section2, we describe the problem of TOP optimization and analyze passenger travel costs and enterprise operating costs. In Section 3, we discuss the constraints and multiobjective function and present the integrated optimization model of TOP. In Section 4, we design a solving algorithm based on SA. Moreover, the case of the Changzhutan intercity rail network is used to illustrate the application of the proposed model and algorithm and also to analyze the impact of their parameters on passenger travel costs and enterprise operating costs in Section 5. Finally, the conclusion and further study are given in Section 6.


## 2. Problem Description

An intercity rail network(S,E) is represented by a set of stations S={1,2,…,K} and a set of double-track sections E=ek,k′∣k,k′∈S in which ek,k′ and ek′,k show, respectively, the down and up direction sections connecting station k and k′. The mileage of ek,k′ is denoted by lk,k′ or by le.Intercity rail passenger flow has the obvious characteristic of fluctuating with the time of day, and it has peak hours and low hours of travel. So, it is called varying demand in this paper. The varying demand from originr to destination s in one day is denoted by a function of timet denoted by qrst.For simplification, the following assumptions are made based on the actual condition of intercity railway in this paper.(A1)
The research range is limited to an independent intercity rail network and passenger total demand of one day among stations is not affected by travel costs determined by the TOP.(A2)
The intercity rail network provides only one speed type (e.g., 200 km/h) of train servicing passengers, and all vehicles have the same capacity for passengers.(A3)
The network capacity is enough to satisfy passengers travelling by the mileage-shortest route; thus, all passengers can travel with those routes.(A4)
Passengers get on the train according to their arriving order.The TOP can be expressed as a set of trainsΩ, and each train is made up by route, vehicle number, and schedule. The route of train i is denoted by Si, which is composed of a set of stations or a set of sections, the vehicle number of train i is expressed by bi, and the sequences of departure time and arrival time arranged by ascending order are denoted by Xi,Yi, respectively. Meanwhile, the arrival time and departure time of train i at station k are denoted by yik,xik, respectively.


### 2.1. Analysis of Passenger Travel Costs

Passenger travel costs mainly consist of wait time at the origin station, transfer time including necessary walking time and wait time during the process from getting off the train to getting on board of another train at the transfer station, in-vehicle time, and fare spending. Considering the additional inconvenience produced by transfer, an additional cost is imposed on transfer passengers besides transfer time. This additional cost contributes to avoiding transfer for passengers when they have other nontransfer paths for travelling. Under the assumption (A3), passenger fare spending calculated by travel mileage multiplying price rate per mileage is a constant and is not considered in this paper.Wait time at the origin station depends on passengers’ arriving time and boarding time. When passengers arrive at stationr at time t and wait there until boarding train i at time xir, their wait time c1(r,i) can be calculated by(1)c1r,i=xir-t.When passengers transfer in stationk with train i and transfer out with train j, their transfer time c2i,j,k can be determined as follows according to departure time xjk of train j and arrival time yik of train i:(2)c2i,j,k=xjk-yik.Moreover, their additional cost of transfer c3i,j,k can be given as ρ multiple of their transfer time; namely,(3)c3i,j,k=ρc2i,j,k.In-vehicle time comprises train operation time and dwell time of each intermediate station. When passengers travel with traini from station k to station k′, their in-vehicle time c4i,k,k′ spent on this train is(4)c4i,k,k′=yik′-xik.Passenger travel cost is the total of wait time, transfer time and transfer additional cost, and in-vehicle time. For passengers travelling by pathp from station r to station s, their travel cost Cr,s,p is(5)Cr,s,p=c1r,ip0+∑(i,j,k)∈pc2i,j,k+c3i,j,k+∑(i,k,k′)∈pc4i,k,k′,where p is the travel path of passengers, ip0 is the first train for passengers of path p travelling, and i,j,k∈p shows passengers of path p needing to transfer from train i to train j at station k. And i,k,k′∈p means that passengers of path p have to travel by train i when going from station k to station k′.


### 2.2. Analysis of Enterprise Operating Costs

With the action of assumptions (A1) and (A3), an intercity rail enterprise has a fixed ticket income, the product of passenger flow, and its corresponding fare. Thus, the operating costs are considered only in this paper. Operating cost is the sum of the following three components: that is, train organization costFO, rail line cost FL, and rail vehicle cost FV. It is represented as(6)F=FO+FL+FV.Train organization cost is the fee spent mainly on the train crew and the organizing operation at the train’s origin station. It is the product of train numberN and the organization cost ω per train; namely,(7)FO=Nω.Rail line cost is generated for line maintenance and is directly related to the total travel mileage of a train. It can be expressed as(8)FL=ψ∑i∈Ωli,where ψ is the maintenance cost per kilometer line and li is the travel mileage of train i.Vehicle cost is used for vehicle maintenance. It can be calculated as(9)FV=∑i∈Ωχ0+χlibi,where χ0 is the fixed cost for each vehicle maintenance and χ is the average maintenance cost of vehicle per mileage.


## 2.1. Analysis of Passenger Travel Costs

Passenger travel costs mainly consist of wait time at the origin station, transfer time including necessary walking time and wait time during the process from getting off the train to getting on board of another train at the transfer station, in-vehicle time, and fare spending. Considering the additional inconvenience produced by transfer, an additional cost is imposed on transfer passengers besides transfer time. This additional cost contributes to avoiding transfer for passengers when they have other nontransfer paths for travelling. Under the assumption (A3), passenger fare spending calculated by travel mileage multiplying price rate per mileage is a constant and is not considered in this paper.Wait time at the origin station depends on passengers’ arriving time and boarding time. When passengers arrive at stationr at time t and wait there until boarding train i at time xir, their wait time c1(r,i) can be calculated by(1)c1r,i=xir-t.When passengers transfer in stationk with train i and transfer out with train j, their transfer time c2i,j,k can be determined as follows according to departure time xjk of train j and arrival time yik of train i:(2)c2i,j,k=xjk-yik.Moreover, their additional cost of transfer c3i,j,k can be given as ρ multiple of their transfer time; namely,(3)c3i,j,k=ρc2i,j,k.In-vehicle time comprises train operation time and dwell time of each intermediate station. When passengers travel with traini from station k to station k′, their in-vehicle time c4i,k,k′ spent on this train is(4)c4i,k,k′=yik′-xik.Passenger travel cost is the total of wait time, transfer time and transfer additional cost, and in-vehicle time. For passengers travelling by pathp from station r to station s, their travel cost Cr,s,p is(5)Cr,s,p=c1r,ip0+∑(i,j,k)∈pc2i,j,k+c3i,j,k+∑(i,k,k′)∈pc4i,k,k′,where p is the travel path of passengers, ip0 is the first train for passengers of path p travelling, and i,j,k∈p shows passengers of path p needing to transfer from train i to train j at station k. And i,k,k′∈p means that passengers of path p have to travel by train i when going from station k to station k′.


## 2.2. Analysis of Enterprise Operating Costs

With the action of assumptions (A1) and (A3), an intercity rail enterprise has a fixed ticket income, the product of passenger flow, and its corresponding fare. Thus, the operating costs are considered only in this paper. Operating cost is the sum of the following three components: that is, train organization costFO, rail line cost FL, and rail vehicle cost FV. It is represented as(6)F=FO+FL+FV.Train organization cost is the fee spent mainly on the train crew and the organizing operation at the train’s origin station. It is the product of train numberN and the organization cost ω per train; namely,(7)FO=Nω.Rail line cost is generated for line maintenance and is directly related to the total travel mileage of a train. It can be expressed as(8)FL=ψ∑i∈Ωli,where ψ is the maintenance cost per kilometer line and li is the travel mileage of train i.Vehicle cost is used for vehicle maintenance. It can be calculated as(9)FV=∑i∈Ωχ0+χlibi,where χ0 is the fixed cost for each vehicle maintenance and χ is the average maintenance cost of vehicle per mileage.


## 3. Optimization Model

### 3.1. Analysis of Constraints

Train origin and destination must be a technical station that has the areas and facilities for a train’s technical operation and servicing work. The set of technical stations on an intercity rail network is denoted bySt, and then the origin station oi and destination station di of train i must be included in set St; namely,(10)oi,di∈St∀i.The vehicle number of a train should be set for an upper bound limited by the length of station track. The train vehicle number of upper bound for all travel routes is expressed asb¯. That is,(11)bi≤b¯∀i.Meanwhile, the vehicle number of a train should not be less than the number that makes this train operate without profit when it reaches its passenger capacity. When train i reaches its passenger capacity, its operating cost Fi and ticket income Ri can be given, respectively, by(12)Fi=ω+ψli+χ0+χlibi,Ri=ϕlibiφ,where ϕ is the fare rate per passenger per kilometer and φ is the passenger capacity of vehicle.To make traini profitable, its ticket income Ri should be more than the operating cost Fi; that is,(13)Ri>Fi.Based on that, the vehicle number of train i should satisfy another constraint as(14)bi≥ω+ψliϕliφ-χ0-χli∀i,where  is the symbol of rounding up.The train schedule should meet the constraint of operating time period from timets to time te. That is,(15)ts≤xik≤te∀i,k∈Gi,ts≤yik≤te∀i,k∈Gi.Two same-direction trains departing from or arriving at the same station should satisfy the minimum safety time interval; namely,(16)xjk-xik≥τf∀i≠j;k∈Gi∩Gj,yjk-yik≥τd∀i≠j;k∈Gi∩Gj,where τf,τd are separately the minimum safety time interval between departure operations and between arrival operations.In addition, a train’s departure and arrival time in section should meet the constraint of minimum total run time. The technical speed of the train is denoted byv, and train additional times for starting and stopping in section e are expressed by τe′,τe′′, respectively. That is,(17)yjk′-xik≥δikτe′+lev+δik′τe′′∀i,ek,k′∈Gi,where δik is the symbol of describing whether train i should stop at station k or not. If train i stops at station k, then δik=1; otherwise, δik=0.Meanwhile, a train’s arrival and departure time at the station should satisfy the constraint of minimum dwell time related to the volume of passengers getting on and getting off train. That is,(18)xjk-yik≥Γik∀i,k∈Gi,where Γik is the minimum dwell time of train i at station k for ensuring that passengers get on and off safely. It can be given by(19)Γikqik=0,qik=0,1,0<qik≤q-,1+qik-q-ξ,qik>q-,where qik is the volume of passengers getting on and getting off train i at station k, q- is the maximum number of passengers for getting on and off the train in one minute, and ξ is the parameter affecting the increase of train dwell time.


### 3.2. Objective Function and Optimization Model

The cost minimization of intercity rail transit system, that is, minimizing both enterprise operating costs and passenger travel costs, is mostly used as the optimization objective of the train plan in many studies [2, 5–7]. In this paper, it is also adopted as the optimization objective of the TOP, but passenger travel costs including not only in-vehicle time, but also wait time and transfer time, are more full-scale and are calculated more exactly.The objective function is expressed as the weighted sum of an enterprise’s operating costs and passengers’ travel costs. That is,(20)min⁡Z=αF+1-αC=αF+1-αλ∑r∑s∑p∈Prsqr,s,pCr,s,p=αNω+ψ∑i∈Ωli+∑i∈Ωχ0+χlibi+1-αλ·∑r∑s∑p∈Prsqr,s,pssssssssssssss·c1r,ip0∑i,k,k′∈pc4i,k,k′ssssssssssssssssssss+∑(i,j,k)∈pc2i,j,k+c3i,j,ksssssssssssssssssss+∑(i,k,k′)∈pc4i,k,k′,where α is the weight parameter balancing the enterprise’s operating costs and passengers’ travel costs, λ is the average time value of passengers, and qr,s,p is the volume of passengers of path p from origin r to destination s.Based on the above analysis, with the decision variables of train setΩ, the optimization model (M1) of the TOP consists of the objective function (20) and all constraints (10), (11), and (14) through (18). It should be noted that model (M1) has to determine not only each train’s route, vehicle number, and schedule, but also train number.


## 3.1. Analysis of Constraints

Train origin and destination must be a technical station that has the areas and facilities for a train’s technical operation and servicing work. The set of technical stations on an intercity rail network is denoted bySt, and then the origin station oi and destination station di of train i must be included in set St; namely,(10)oi,di∈St∀i.The vehicle number of a train should be set for an upper bound limited by the length of station track. The train vehicle number of upper bound for all travel routes is expressed asb¯. That is,(11)bi≤b¯∀i.Meanwhile, the vehicle number of a train should not be less than the number that makes this train operate without profit when it reaches its passenger capacity. When train i reaches its passenger capacity, its operating cost Fi and ticket income Ri can be given, respectively, by(12)Fi=ω+ψli+χ0+χlibi,Ri=ϕlibiφ,where ϕ is the fare rate per passenger per kilometer and φ is the passenger capacity of vehicle.To make traini profitable, its ticket income Ri should be more than the operating cost Fi; that is,(13)Ri>Fi.Based on that, the vehicle number of train i should satisfy another constraint as(14)bi≥ω+ψliϕliφ-χ0-χli∀i,where  is the symbol of rounding up.The train schedule should meet the constraint of operating time period from timets to time te. That is,(15)ts≤xik≤te∀i,k∈Gi,ts≤yik≤te∀i,k∈Gi.Two same-direction trains departing from or arriving at the same station should satisfy the minimum safety time interval; namely,(16)xjk-xik≥τf∀i≠j;k∈Gi∩Gj,yjk-yik≥τd∀i≠j;k∈Gi∩Gj,where τf,τd are separately the minimum safety time interval between departure operations and between arrival operations.In addition, a train’s departure and arrival time in section should meet the constraint of minimum total run time. The technical speed of the train is denoted byv, and train additional times for starting and stopping in section e are expressed by τe′,τe′′, respectively. That is,(17)yjk′-xik≥δikτe′+lev+δik′τe′′∀i,ek,k′∈Gi,where δik is the symbol of describing whether train i should stop at station k or not. If train i stops at station k, then δik=1; otherwise, δik=0.Meanwhile, a train’s arrival and departure time at the station should satisfy the constraint of minimum dwell time related to the volume of passengers getting on and getting off train. That is,(18)xjk-yik≥Γik∀i,k∈Gi,where Γik is the minimum dwell time of train i at station k for ensuring that passengers get on and off safely. It can be given by(19)Γikqik=0,qik=0,1,0<qik≤q-,1+qik-q-ξ,qik>q-,where qik is the volume of passengers getting on and getting off train i at station k, q- is the maximum number of passengers for getting on and off the train in one minute, and ξ is the parameter affecting the increase of train dwell time.


## 3.2. Objective Function and Optimization Model

The cost minimization of intercity rail transit system, that is, minimizing both enterprise operating costs and passenger travel costs, is mostly used as the optimization objective of the train plan in many studies [2, 5–7]. In this paper, it is also adopted as the optimization objective of the TOP, but passenger travel costs including not only in-vehicle time, but also wait time and transfer time, are more full-scale and are calculated more exactly.The objective function is expressed as the weighted sum of an enterprise’s operating costs and passengers’ travel costs. That is,(20)min⁡Z=αF+1-αC=αF+1-αλ∑r∑s∑p∈Prsqr,s,pCr,s,p=αNω+ψ∑i∈Ωli+∑i∈Ωχ0+χlibi+1-αλ·∑r∑s∑p∈Prsqr,s,pssssssssssssss·c1r,ip0∑i,k,k′∈pc4i,k,k′ssssssssssssssssssss+∑(i,j,k)∈pc2i,j,k+c3i,j,ksssssssssssssssssss+∑(i,k,k′)∈pc4i,k,k′,where α is the weight parameter balancing the enterprise’s operating costs and passengers’ travel costs, λ is the average time value of passengers, and qr,s,p is the volume of passengers of path p from origin r to destination s.Based on the above analysis, with the decision variables of train setΩ, the optimization model (M1) of the TOP consists of the objective function (20) and all constraints (10), (11), and (14) through (18). It should be noted that model (M1) has to determine not only each train’s route, vehicle number, and schedule, but also train number.


## 4. Optimization Algorithm Based on SA

### 4.1. Algorithm for Passenger Train Choice and Calculation of Passenger Travel Costs

All passengers have to obey the rule of time-space priority when choosing a train. In other words, passengers arriving at a station earlier have the priority of boarding the train, but they also have to yield to those on the train as to the limit of train capacity. For that, passengers are distributed to trains according to the ascending order of train departure and arrival time treated as the decision-making time.At the decision-making time of a train departing, which passengers waiting in the station will choose this train and how many of them can get on it should be determined. Passengers waiting in the station can be divided into two parts, original departing and transferring passengers. The sets of original departing passengers and transferring passengers at stationk are denoted by Gk and Hk, respectively. For original departing passengers g∈Gk, their earliest arriving time is tg and destination is sg. And for transferring passengers h∈Hk, their transferring in time is th, destination is sh, and their number is qh.When traini departs from station k, passengers whose cost-shortest path from station k to their destination contains train i need to get on it, but the number of those who can get on board successfully depends on the empty seat number ui of train i. Based first-arriving-first-boarding principle, the number of passengers getting on the train is given as(21)q-g=∫tgt∗qksgtdttg≤t∗0tg>t∗g∈G-k∈Gk,q-h=qhth≤t∗0th>t∗h∈H-k∈Hk,where G-k,H-k are the sets of original departing passengers and transferring passengers needing to get on train i at station k and t∗ is the time boundary deciding what time passengers arriving can get on board of the train. It means that passengers arriving before t∗ can get on the train, but those arriving after this time cannot get on board, because there are no empty seats left. When the passenger total number of G-k,H-k is less than ui, then t∗=xik. Otherwise, the value of t∗ can be calculated by solving the following equality: (22)∑h∈H-k∣th≤t∗qh+∑g∈G-k∣tg≤t∗∫tgt∗qksgtdt=ui.The wait time, transfer time, and additional cost for transfer at stationk of passengers getting on train i can be calculated by(23)c1k,i=∑g∈G-kc1gk,i=∑g∈G-kmax⁡∫tgt∗qksgtxik-tdt,0,c2k,i=∑h∈H-kc2h=∑h∈H-kxik-thq-h,c3k,i=ρc2k,i.At the decision-making time of traini arriving station k, passengers having arrived at their destination or whose cost-shortest path from station k to their destination does not include train i again have to get off. The set of passengers arriving at station k with train i is denoted by Bi, with the subset of those getting off the train being denoted by B-i. For passengers b∈Bi, their destination is sb, and their number is qb. The in-vehicle time of passengers b∈Bi from the rear station k′ to station k can be calculated by(24)c4bi,k′,k=yik-xik′,b∈B-i,xik-xik′,b∈Bi-B-i.And the total of their in-vehicle time is given as(25)c4i,k′,k=∑b∈Biqbc4bi,k′,k.Based on the above analysis, Algorithm1 for passenger train choice and calculation of passenger travel costs is described as follows.Algorithm 1.
Consider the following.
Step 1 (initialization). Set Bi=∅ and ui=biφ of each train and Hk=∅ of each station. Find all original departing passengers Gk of each station and let C=0 as the total travel costs of passengers.
Step 2 (find the earliest decision-making time t). If t corresponds to departure time xik, then go to Step 2.1; otherwise, if t corresponds to arrival time yik, then go to Step 2.2.Step 2.1. Determine boarding passengers G-k, H-k and their number q-g (g∈G-k), q-h (h∈H-k). Then, calculate their wait time c1(k,i), transfer time c2(k,i), and transfer additional cost c3k,i. Set C=C+c1k,i+c2k,i+c3k,i and update empty seats number ui, transferring passengers Hk, original departing passengers Gk, and train passengers Bi. Go to Step 3.Step 2.2. Determine getting-off passengers B-i and calculate their in-vehicle time c4i,k′,k. Then, set C=C+c4i,k′,k and update empty seats number ui, transferring passengers Hk and train passengers Bi.Step 3 (judge whether there are other decision-making times or not). If yes, then return to Step 2. Otherwise, C is the passengers’ total travel costs, and terminate this algorithm.


### 4.2. The General Algorithm for Optimizing TOP

#### 4.2.1. Generation of an Initial Solution of TOP

Trains of the initial solution are created one by one based on the varying demand on the network. A new train is organized with departing timet when the product of its boarding passengers’ number Q- and their average wait time R including wait time and transfer wait time at a technical station satisfies(26)QR=Mand its vehicle number is determined by(27)b=Qφl,where M is the control parameter for organizing one new train and l is the average usage rate of train capacity.From formula (26), we know that a train should be organized either when there are enough passengers waiting for boarding, or when some passengers have waited for too long.The newly created train is assumed to stop at all the passed stations during the process of generating the initial solution. When it arrives at the next technical station, if the sum of passengers waiting to get on and those on the train is more thanς percent of its capacity, it moves forward along the direction with the largest value of ς. Otherwise, it stops here as its destination.


#### 4.2.2. Generation of a Neighbor Solution of TOP

A new solution is generated by changing the train’s route, stop stations, vehicle number, and starting time of the current solution with the probability method. As for the train route, it is adjusted by adding some new sections to its front and end or removing partial sections depending on train’s operating costs and passenger volume of them. Two Boolean variablesϱ and ϖ both created by Bernoulli distribution are, respectively, used to indicate whether partial sections should be added to the train route and removed from it. If ϱ=1, the corresponding sections are added to the train route, and when ϖ=1, the corresponding sections are removed from it. As for the train sections μbetween two technical stations, the probability of ϱ=1 is given by(28)ϰ=1-e-WμCu/FμT,where Wμ, Cu, and Fμ are the passenger-kilometer, passengers’ average travel costs, and operating cost in train section μ respectively, and T is the current temperature.For new sectionsμ, the probability of ϖ=1 is given by(29)ϰ=1-e-Qu/θuT,where Qu is the number of passengers transferring from or transferring to the current train and θu is their average transfer cost.The alteration of train stop stations is also based on a Bernoulli distribution. For stationk of train i, the probability of a train’s stop is given by(30)ϰik=e-QikCikT,where Qik is the number of passengers getting on and off the train and Cik is the average travel cost of passengers getting on the train at station k.The modification of both the train vehicle number and starting time is given as follows:(31)d∗=d+ηB-dζ≥0d+ηd-Aζ<0,(32)ζ=T1+1T2ξ-1-1sgnξ-0.5,where d∗,d∈A,B are the value of current solution and neighboring solution, respectively, and ξ is generated by the next probability density function, which makes the vehicle number and starting time of one train with low benefit or efficiency have a high adjustment chance. Consider(33)y=γ-1x-0.5+1,x∈0,1,where γ is determined by the indexes of train i. For train vehicle number and starting time, it is given, respectively, by(34)γ=1-WiCi/FiavgWC/F,γ=Ci/Qiavg(C/Q),where Wi is the passenger kilometer, Fi is the average operating cost per vehicle, Ci is the total wait time and transfer cost, and Qi is the number of passengers on the train.In formulas (28), (29), (30), and (32), the calculation of their probabilities is mainly based on train’s service level, passenger volume, operating costs, and the current temperature as a parameter of SA, and the higher the current temperature is, the larger their probabilities are.With the above generation method of an initial solution and a neighborhood solution, the general Algorithm2 based on SA for optimizing TOP is described as follows.Algorithm 2.
Consider the following.
Step 1 (initialization). Generate the initial feasible solution Ω under the initial temperature T0 and then calculate the objective value Z(Ω) based on simulating passenger train choice and calculating passenger travel costs with Algorithm 1. Set β=0 as the current running times of the outer cycle. Let n=0 be the current running times of the inner cycle and let T=T0 be the current temperature. Set Tmin⁡ as the minimum temperature of the outer cycle and Υ as the number of iterations at each temperature.
Step 2 (construction of neighborhood). Generate a new solution Ω′ and calculate its objective value corresponding to ZΩ′ based on simulating passenger train choice and calculating passenger travel costs with Algorithm 1.
Step 3 (metropolis sampling). When ZΩ>Z(Ω′), then set Ω=Ω′; otherwise, if exp⁡ΔZ/T>rand (rand is a random number in (0,1) and ΔZ is the difference between them, the current and optimal solution), then let Ω=Ω′. Then, set n=n+1.
Step 4 (test of the termination criterion of the inner cycle). If n=Υ, terminate the inner cycle and let β=β+1; otherwise, return to Step 2.
Step 5 (cooling schedule). Calculate the temperature T(β).
Step 6 (test of the termination criterion of the outer cycle). When T(k)≤Tmin⁡, terminate this algorithm and output the optimal solution; otherwise, return to Step 2.


## 4.1. Algorithm for Passenger Train Choice and Calculation of Passenger Travel Costs

All passengers have to obey the rule of time-space priority when choosing a train. In other words, passengers arriving at a station earlier have the priority of boarding the train, but they also have to yield to those on the train as to the limit of train capacity. For that, passengers are distributed to trains according to the ascending order of train departure and arrival time treated as the decision-making time.At the decision-making time of a train departing, which passengers waiting in the station will choose this train and how many of them can get on it should be determined. Passengers waiting in the station can be divided into two parts, original departing and transferring passengers. The sets of original departing passengers and transferring passengers at stationk are denoted by Gk and Hk, respectively. For original departing passengers g∈Gk, their earliest arriving time is tg and destination is sg. And for transferring passengers h∈Hk, their transferring in time is th, destination is sh, and their number is qh.When traini departs from station k, passengers whose cost-shortest path from station k to their destination contains train i need to get on it, but the number of those who can get on board successfully depends on the empty seat number ui of train i. Based first-arriving-first-boarding principle, the number of passengers getting on the train is given as(21)q-g=∫tgt∗qksgtdttg≤t∗0tg>t∗g∈G-k∈Gk,q-h=qhth≤t∗0th>t∗h∈H-k∈Hk,where G-k,H-k are the sets of original departing passengers and transferring passengers needing to get on train i at station k and t∗ is the time boundary deciding what time passengers arriving can get on board of the train. It means that passengers arriving before t∗ can get on the train, but those arriving after this time cannot get on board, because there are no empty seats left. When the passenger total number of G-k,H-k is less than ui, then t∗=xik. Otherwise, the value of t∗ can be calculated by solving the following equality: (22)∑h∈H-k∣th≤t∗qh+∑g∈G-k∣tg≤t∗∫tgt∗qksgtdt=ui.The wait time, transfer time, and additional cost for transfer at stationk of passengers getting on train i can be calculated by(23)c1k,i=∑g∈G-kc1gk,i=∑g∈G-kmax⁡∫tgt∗qksgtxik-tdt,0,c2k,i=∑h∈H-kc2h=∑h∈H-kxik-thq-h,c3k,i=ρc2k,i.At the decision-making time of traini arriving station k, passengers having arrived at their destination or whose cost-shortest path from station k to their destination does not include train i again have to get off. The set of passengers arriving at station k with train i is denoted by Bi, with the subset of those getting off the train being denoted by B-i. For passengers b∈Bi, their destination is sb, and their number is qb. The in-vehicle time of passengers b∈Bi from the rear station k′ to station k can be calculated by(24)c4bi,k′,k=yik-xik′,b∈B-i,xik-xik′,b∈Bi-B-i.And the total of their in-vehicle time is given as(25)c4i,k′,k=∑b∈Biqbc4bi,k′,k.Based on the above analysis, Algorithm1 for passenger train choice and calculation of passenger travel costs is described as follows.Algorithm 1.
Consider the following.
Step 1 (initialization). Set Bi=∅ and ui=biφ of each train and Hk=∅ of each station. Find all original departing passengers Gk of each station and let C=0 as the total travel costs of passengers.
Step 2 (find the earliest decision-making time t). If t corresponds to departure time xik, then go to Step 2.1; otherwise, if t corresponds to arrival time yik, then go to Step 2.2.Step 2.1. Determine boarding passengers G-k, H-k and their number q-g (g∈G-k), q-h (h∈H-k). Then, calculate their wait time c1(k,i), transfer time c2(k,i), and transfer additional cost c3k,i. Set C=C+c1k,i+c2k,i+c3k,i and update empty seats number ui, transferring passengers Hk, original departing passengers Gk, and train passengers Bi. Go to Step 3.Step 2.2. Determine getting-off passengers B-i and calculate their in-vehicle time c4i,k′,k. Then, set C=C+c4i,k′,k and update empty seats number ui, transferring passengers Hk and train passengers Bi.Step 3 (judge whether there are other decision-making times or not). If yes, then return to Step 2. Otherwise, C is the passengers’ total travel costs, and terminate this algorithm.


## 4.2. The General Algorithm for Optimizing TOP

### 4.2.1. Generation of an Initial Solution of TOP

Trains of the initial solution are created one by one based on the varying demand on the network. A new train is organized with departing timet when the product of its boarding passengers’ number Q- and their average wait time R including wait time and transfer wait time at a technical station satisfies(26)QR=Mand its vehicle number is determined by(27)b=Qφl,where M is the control parameter for organizing one new train and l is the average usage rate of train capacity.From formula (26), we know that a train should be organized either when there are enough passengers waiting for boarding, or when some passengers have waited for too long.The newly created train is assumed to stop at all the passed stations during the process of generating the initial solution. When it arrives at the next technical station, if the sum of passengers waiting to get on and those on the train is more thanς percent of its capacity, it moves forward along the direction with the largest value of ς. Otherwise, it stops here as its destination.


### 4.2.2. Generation of a Neighbor Solution of TOP

A new solution is generated by changing the train’s route, stop stations, vehicle number, and starting time of the current solution with the probability method. As for the train route, it is adjusted by adding some new sections to its front and end or removing partial sections depending on train’s operating costs and passenger volume of them. Two Boolean variablesϱ and ϖ both created by Bernoulli distribution are, respectively, used to indicate whether partial sections should be added to the train route and removed from it. If ϱ=1, the corresponding sections are added to the train route, and when ϖ=1, the corresponding sections are removed from it. As for the train sections μbetween two technical stations, the probability of ϱ=1 is given by(28)ϰ=1-e-WμCu/FμT,where Wμ, Cu, and Fμ are the passenger-kilometer, passengers’ average travel costs, and operating cost in train section μ respectively, and T is the current temperature.For new sectionsμ, the probability of ϖ=1 is given by(29)ϰ=1-e-Qu/θuT,where Qu is the number of passengers transferring from or transferring to the current train and θu is their average transfer cost.The alteration of train stop stations is also based on a Bernoulli distribution. For stationk of train i, the probability of a train’s stop is given by(30)ϰik=e-QikCikT,where Qik is the number of passengers getting on and off the train and Cik is the average travel cost of passengers getting on the train at station k.The modification of both the train vehicle number and starting time is given as follows:(31)d∗=d+ηB-dζ≥0d+ηd-Aζ<0,(32)ζ=T1+1T2ξ-1-1sgnξ-0.5,where d∗,d∈A,B are the value of current solution and neighboring solution, respectively, and ξ is generated by the next probability density function, which makes the vehicle number and starting time of one train with low benefit or efficiency have a high adjustment chance. Consider(33)y=γ-1x-0.5+1,x∈0,1,where γ is determined by the indexes of train i. For train vehicle number and starting time, it is given, respectively, by(34)γ=1-WiCi/FiavgWC/F,γ=Ci/Qiavg(C/Q),where Wi is the passenger kilometer, Fi is the average operating cost per vehicle, Ci is the total wait time and transfer cost, and Qi is the number of passengers on the train.In formulas (28), (29), (30), and (32), the calculation of their probabilities is mainly based on train’s service level, passenger volume, operating costs, and the current temperature as a parameter of SA, and the higher the current temperature is, the larger their probabilities are.With the above generation method of an initial solution and a neighborhood solution, the general Algorithm2 based on SA for optimizing TOP is described as follows.Algorithm 2.
Consider the following.
Step 1 (initialization). Generate the initial feasible solution Ω under the initial temperature T0 and then calculate the objective value Z(Ω) based on simulating passenger train choice and calculating passenger travel costs with Algorithm 1. Set β=0 as the current running times of the outer cycle. Let n=0 be the current running times of the inner cycle and let T=T0 be the current temperature. Set Tmin⁡ as the minimum temperature of the outer cycle and Υ as the number of iterations at each temperature.
Step 2 (construction of neighborhood). Generate a new solution Ω′ and calculate its objective value corresponding to ZΩ′ based on simulating passenger train choice and calculating passenger travel costs with Algorithm 1.
Step 3 (metropolis sampling). When ZΩ>Z(Ω′), then set Ω=Ω′; otherwise, if exp⁡ΔZ/T>rand (rand is a random number in (0,1) and ΔZ is the difference between them, the current and optimal solution), then let Ω=Ω′. Then, set n=n+1.
Step 4 (test of the termination criterion of the inner cycle). If n=Υ, terminate the inner cycle and let β=β+1; otherwise, return to Step 2.
Step 5 (cooling schedule). Calculate the temperature T(β).
Step 6 (test of the termination criterion of the outer cycle). When T(k)≤Tmin⁡, terminate this algorithm and output the optimal solution; otherwise, return to Step 2.


## 4.2.1. Generation of an Initial Solution of TOP

Trains of the initial solution are created one by one based on the varying demand on the network. A new train is organized with departing timet when the product of its boarding passengers’ number Q- and their average wait time R including wait time and transfer wait time at a technical station satisfies(26)QR=Mand its vehicle number is determined by(27)b=Qφl,where M is the control parameter for organizing one new train and l is the average usage rate of train capacity.From formula (26), we know that a train should be organized either when there are enough passengers waiting for boarding, or when some passengers have waited for too long.The newly created train is assumed to stop at all the passed stations during the process of generating the initial solution. When it arrives at the next technical station, if the sum of passengers waiting to get on and those on the train is more thanς percent of its capacity, it moves forward along the direction with the largest value of ς. Otherwise, it stops here as its destination.


## 4.2.2. Generation of a Neighbor Solution of TOP

A new solution is generated by changing the train’s route, stop stations, vehicle number, and starting time of the current solution with the probability method. As for the train route, it is adjusted by adding some new sections to its front and end or removing partial sections depending on train’s operating costs and passenger volume of them. Two Boolean variablesϱ and ϖ both created by Bernoulli distribution are, respectively, used to indicate whether partial sections should be added to the train route and removed from it. If ϱ=1, the corresponding sections are added to the train route, and when ϖ=1, the corresponding sections are removed from it. As for the train sections μbetween two technical stations, the probability of ϱ=1 is given by(28)ϰ=1-e-WμCu/FμT,where Wμ, Cu, and Fμ are the passenger-kilometer, passengers’ average travel costs, and operating cost in train section μ respectively, and T is the current temperature.For new sectionsμ, the probability of ϖ=1 is given by(29)ϰ=1-e-Qu/θuT,where Qu is the number of passengers transferring from or transferring to the current train and θu is their average transfer cost.The alteration of train stop stations is also based on a Bernoulli distribution. For stationk of train i, the probability of a train’s stop is given by(30)ϰik=e-QikCikT,where Qik is the number of passengers getting on and off the train and Cik is the average travel cost of passengers getting on the train at station k.The modification of both the train vehicle number and starting time is given as follows:(31)d∗=d+ηB-dζ≥0d+ηd-Aζ<0,(32)ζ=T1+1T2ξ-1-1sgnξ-0.5,where d∗,d∈A,B are the value of current solution and neighboring solution, respectively, and ξ is generated by the next probability density function, which makes the vehicle number and starting time of one train with low benefit or efficiency have a high adjustment chance. Consider(33)y=γ-1x-0.5+1,x∈0,1,where γ is determined by the indexes of train i. For train vehicle number and starting time, it is given, respectively, by(34)γ=1-WiCi/FiavgWC/F,γ=Ci/Qiavg(C/Q),where Wi is the passenger kilometer, Fi is the average operating cost per vehicle, Ci is the total wait time and transfer cost, and Qi is the number of passengers on the train.In formulas (28), (29), (30), and (32), the calculation of their probabilities is mainly based on train’s service level, passenger volume, operating costs, and the current temperature as a parameter of SA, and the higher the current temperature is, the larger their probabilities are.With the above generation method of an initial solution and a neighborhood solution, the general Algorithm2 based on SA for optimizing TOP is described as follows.Algorithm 2.
Consider the following.
Step 1 (initialization). Generate the initial feasible solution Ω under the initial temperature T0 and then calculate the objective value Z(Ω) based on simulating passenger train choice and calculating passenger travel costs with Algorithm 1. Set β=0 as the current running times of the outer cycle. Let n=0 be the current running times of the inner cycle and let T=T0 be the current temperature. Set Tmin⁡ as the minimum temperature of the outer cycle and Υ as the number of iterations at each temperature.
Step 2 (construction of neighborhood). Generate a new solution Ω′ and calculate its objective value corresponding to ZΩ′ based on simulating passenger train choice and calculating passenger travel costs with Algorithm 1.
Step 3 (metropolis sampling). When ZΩ>Z(Ω′), then set Ω=Ω′; otherwise, if exp⁡ΔZ/T>rand (rand is a random number in (0,1) and ΔZ is the difference between them, the current and optimal solution), then let Ω=Ω′. Then, set n=n+1.
Step 4 (test of the termination criterion of the inner cycle). If n=Υ, terminate the inner cycle and let β=β+1; otherwise, return to Step 2.
Step 5 (cooling schedule). Calculate the temperature T(β).
Step 6 (test of the termination criterion of the outer cycle). When T(k)≤Tmin⁡, terminate this algorithm and output the optimal solution; otherwise, return to Step 2.


## 5. Numerical Studies in Changzhutan Intercity Rail Network

The Changzhutan intercity rail network in the cluster including the cities of Changsha, Zhuzhou, and Xiangtan of China is planned to be completed in 2016. It consists of 21 stations and has the total length of 96 km. The above algorithm is developed with computer language C# on the platform of Microsoft Visual Studio.net and runs on the computer with the system of Microsoft Windows XP (Home Edition), RAM configuration of Pentium(R) Dual-Core CPU E5800, 3.19 GHz, 2.96 GB. The values of parameters in model (M1) and its solving algorithm are given in Tables1 and 2, respectively.Table 1
Parameter values of model (M1).
Symbol
Value
Unit
Symbol
Value
Unit
ρ
2.0
—
χ
0
4200
¥/vehicle
ω
25000
¥/train
χ
6.5
¥/vehicle·km
ψ
31.5
¥/train·km
b
¯
10
Vehicle
ϕ
2.5
¥/passenger·km
φ
80
Passenger/vehicle
t
s
6:30
—
t
e
22:00
—
τ
f
6
Min
τ
d
8
Min
v
200
Km/h
τ
e
′
1
Min
τ
e
′
′
1
Min
q
-
200
Passenger
ξ
150
Passenger/min
λ
80
¥/hTable 2
Parameter values of algorithm.
Symbol
Value
Unit
Symbol
Value
Unit
M
15500
Passenger·min
l
0.5
—
ς
0.4
—
T
0
1000
—
T
min
⁡
1
—
Υ
50
—Firstly, some observations on the convergence process of the algorithm with the value ofα being 0.2, 0.5, and 0.8, respectively, are made. The change relations between the best objective values with the total computing times of algorithm running are shown in Figure 1. As seen from it, the objective values decline sharply with the computing time in the first 10 minutes or so for both three instances and then drop slowly until about 17 minutes. After that, they became stable, which indicates that the algorithm has converged to a better solution.Figure 1
Convergence of the solution with different values of weight paraα.Table3 shows the optimization results with the value of α being 0.4, 0.6, and 0.8, respectively. From these results, passenger average wait time and each operating cost vary sharply with a different value of α, but the differences of average transfer cost, proportion of transfer passengers, and passenger in-vehicle speed are smaller. This is because the number of operating trains rising with the increase of α mainly determines the enterprise operating cost, and the higher the trains’ departure frequency is, the shorter the wait time varying passengers have. But trains can have a high travel speed, and their arrival and departure time can connect well, no matter how many trains there are.Table 3
Optimization results with different value ofα.
The value of weight paraα
0.4
0.6
0.8
Average wait time per passenger (min)
13.6
14.1
22.2
Average transfer time per passenger (min)
19.6
20.2
21.5
Average transfer additional cost per passenger (min)
39.2
40.4
43.0
The proportion of transfer passenger (%)
11.3
12.5
12.2
Passenger in-vehicle speed (km/h)
172.4
171.6
172.8
Train organization cost (¥)
3550000
3175000
2725000
Rail line cost (¥)
237069
231030
206010
Rail vehicle cost (¥)
458272
435136
334520For different values ofα, the percentage distributions of passenger wait time are shown in Figure 2. As we can see, regardless of α=0.4, α=0.6, or α=0.8, their passenger percentage distributions are similar to a normal distribution. But their wait time with the maximum percentage increases from 10.2 min to 11.8 min and then to 18.3 min with the increase of α. The wait time of 75% of the passengers is mainly concentrated in 0 to 16 min both when α=0.4 and α=0.6, and that of 80% of the passengers is located in 0 to 20 min while α=0.8. The maximum wait time of these three cases is 30 min, which is the ultimate value passengers can bear.Figure 2
Distribution of passenger wait time.The percentage distributions of passenger transfer time with a different value ofα are shown in Figure 3. As passenger average walking time for each transfer is assumed to be 10 min, passenger minimum transfer times when α=0.4, α=0.6, and α=0.8 are all 10 min. As seen in Figure 3, the transfer time with the maximum percentage of about 18% does not vary with the different value of α, and it is 16 min or so, corresponding to a passenger transfer wait time of 6 min, in all three cases. Moreover, the transfer time of 90% of the transfer passengers is mainly concentrated in 10 to 24 min. Through a comprehensive comparison of the transfer time and the transfer passenger number of three cases, it can be found that the average transfer time and total number of transfer passenger with α=0.4 are slightly less than these with α=0.8, but their differences are very small, which indicates that the factor α has a little effect on passenger service level of transfer.Figure 3
Distribution of passenger transfer time.For determining the influence of weight parameterα, the objective values composed of enterprise operating cost and passenger travel cost are calculated with different values of α, and the change in these two partial costs for various α is shown in Figure 4. As we can see, operating cost decreases rapidly when α increases from 0.1 to 0.3, and later it has a relative slow-down speed as α continues to increase. However, travel time increases smoothly with α increasing from 0.1 to 0.9. A balance with the minimum of their total can be made between these two parts when α=0.7 is taken as a reasonable value.Figure 4
Relationship between objective function values and weight parameterα.


## 6. Conclusion and Further Study

In this paper, for the integrated optimization of train planning and train scheduling, based on analyzing passenger travel costs and enterprise operating costs, we present their integrated optimization model aiming to minimize both passenger and enterprise costs with the constraints of trains operating and build a solution algorithm based on SA algorithm. From the analysis of the optimization results for the Changzhutan intercity rail network, the proposed model and algorithm can effectively obtain a satisfactory TOP, and a solution with the total minimum of operating costs and travel costs can be reached when the value of weight parameterα is about 0.7.As passenger demand of intercity rail largely depends on their service level under the competitive environment between railway and highway, one further research area is to optimize TOP considering this effect. Another one is to study it involving the allocation of vehicles to train, which can determine more exactly the train operating costs.



---

*Source: 419042-2015-04-12.xml*