# Study on the Train Operation Optimization of Passenger Dedicated Lines Based on Satisfaction

Authors: Zhipeng Huang; Huimin Niu
Journal: Discrete Dynamics in Nature and Society
 (2012)

---

## Abstract

The passenger transport demands at a given junction station fluctuate obviously in different time periods, which makes the rail departments unable to establish an even train operation schedule. This paper considers an optimization problem for train operations at the junction station in passenger dedicated lines. A satisfaction function of passengers is constructed by means of analyzing the satisfaction characteristics and correlative influencing factors. Through discussing the passengers’ travel choice behavior, we formulate an optimization model based on maximum passenger satisfaction for the junction and then design a heuristic algorithm. Finally, a numerical example is provided to demonstrate the application of the method proposed in this paper.


---

## Body

## 1. Introduction

In passenger dedicated lines, passenger trains feature high-speed, high-density, and small train-unit, and the characteristics of passenger transport demands are similar to those of city bus passenger demands. Therefore, train operations in passenger dedicated lines need to be designed differently from the cases in other lines. In particular, train operations at junction stations must be schemed based on the changing of passenger demands. Many scholars had studied the train plan problem in passenger dedicated lines. Crisalli presented a system of within-day dynamic railway service choice and assignment models, which were used as a large decision support system for the operational planning of rail services [1]. Salido and Barber presented a set of heuristics for a constraint-based train scheduling tool to formulate train scheduling as constraint optimization problems [2]. Freling et al. introduced the problem of shunting passenger train units in a railway station. Shunting occurs whenever train units are temporarily not necessary to operate a given timetable [3]. Some other scholars noticed that passenger flows were much uneven in different time-periods in everyday, so they studied the dynamic feature of passenger flows. Niu presented a matching problem between skip-stop operations and time-dependent demands in city headways, and formulated a nonlinear programming model which minimized the overall waiting time and in-vehicle crowding costs [4]. Jha et al. studied the alternative travel choices which were evaluated by a disutility function of perceived travel time and perceived schedule delay, and formulated a Bayesian updating model to optimize an alternative scheme [5]. He et al. presented a fuzzy dispatching model to assist the coordination among multiobjective decisions in railway dispatching plan [6]. Nie et al. considered the passenger choice behavior in rail, and proposed a calculation method of network impedance which could reduce the influence of different travel distance in passengers choice behavior [7]. Chang et al. developed a multiobjective programming model for the optimal allocation of passenger train service on an intercity high-speed rail line without branches. Minimizing the operator's total operating cost and the passenger's total travel time loss is the two planning objectives of the model [8]. Shi et al. established a multiobjective optimum model of passenger train plans for dedicated passenger traffic lines by balancing benefits of both railway transportation corporations and passengers, and proposed a method to solve the optimization problem [9]. Ghoseiri et al. developed a multiobjective optimization model for the passenger train-scheduling problem on a railroad network which included single and multiple tracks [10]. In this study, lowering the fuel consumption cost was the measure of satisfaction of the railway company, and shortening the total passenger-time was being regarded as the passenger satisfaction criterion.In previous studies, operation plans of passenger trains were mainly studied on optimizing transport organization in rail lines, including the train stop-schedule, service frequency, fleet size, and so forth. However, research on optimizing transport organization at a junction station is less concerned by other scholars. In general, the optimization objective of train operations for rail departments is to utilize trains efficiently and to lower travel cost for passengers. Therefore, the optimized train operations should be balanced between rail departments' operating cost and the travel cost of passengers. However, passenger demands are uneven in different time-periods, and train-set quantity is limited at junction stations; the train-set quantity probably cannot meet passenger demands at peak time-period. Passengers will be unsatisfied when their travel cost is increased by longer waiting time or raised ticket price. Thus, it is important to reasonably arrange the train’s quantity and degrees in different time-periods. In this paper, we will focus on the matching of passenger train quantity with passenger demands at junction stations in different time-periods in passenger dedicated lines.This paper is organized as follows: Passenger demands and travel choices at peak time-period are discussed in Section2. An optimized model is built in Section 3, whose objective is to get maximum total passengers’ satisfaction at the junction stations. In Section 4, a heuristic algorithm is designed to meet the changing of passenger demands and satisfy the constraint of train-set quantity. A numerical example is provided to illustrate the application of the model and algorithm in Section 5. The last section highlights the conclusion, and suggests future research directions.


## 2. Problem Statement

### 2.1. Passenger Demands and Travel Choices

As mentioned above, the passenger demands in passenger dedicated lines are heavily different at different time-periods, thus train operations show irregularly in every time-period at junction stations. Previous studies have discussed the departing interval of trains at junction stations based on the condition that passenger transport demands and capacities are equal during the peak time-periods. In fact, the hypothesis is unreasonable when passenger transport demands are larger than capacities during the peak time-periods. Therefore, the railway departments can not arrange enough trains to meet the passenger demands in the peak time-periods.Passengers mainly consider the degree and departing time of trains when they choose railway to travel. However, passenger demands are larger than transport ability during the peak time-periods. In this case, this paper considers that passengers probably choose the following suboptimal travel schemes for themselves: avoiding the peak time-periods and taking a train of the same degree to travel in another time-period; choosing a train of another degree to travel when its quantity is large enough in the same time-period.


### 2.2. Optimization Methods

The optimization objective for train operations at junction stations is to get maximum passenger satisfaction. Passenger satisfaction for train operations, presented in this paper, is an important indicator to evaluate the train operations. Here, the service time at junction stations is divided intom time-periods, according to which passenger demands and train-set quantity at junction stations are obtained, respectively. The time-periods in which passenger demands are larger than transport abilities are defined as peak time-periods. Finally, train operations in peak time-periods are organized according to the following two schemes.


#### 2.2.1. Transferring Passenger Demands

The process that passengers choose the suboptimal schemes to travel is shown in Figure1. The parameters u and u' represent some time-periods in the service time at the junctions, respectively; a and c indicate the aboard process that passengers take r and r' degree trains, respectively; b and d indicate the travelling process that passengers take r and r' degree trains, respectively; e represents the fare loss of passengers who intend to take r' degree train but are transferred to r degree train; f represents travelling time loss of the passenger who intends to take r degree train but is transferred to r' degree train; g indicates the waiting time cost of passengers who have to travel in time-period u'.Figure 1
The process that passengers choose suboptimal schemes to travel.


#### 2.2.2. Adjusting Operation Section of Train-Set

Passenger demands generate at the junction stations, from which passenger trains are dispatched to different terminal stationsj1, j2, and j3 in passenger dedicated lines as shown in Figure 2.Figure 2
Through train plan from original station to different terminal stations.As mentioned above, the transport capacity is limited at a junction station because the train-set quantity is affected by its operation mode. Stationary operation mode of train-set is used in most of the passenger dedicated lines presently; train-sets are operated on fixed railway sections as shown in Figure3. s represents a train-set; tf represents the departure interval of the same kind of train-sets at stations. In general, the value of tf is larger than that of tz, which represents the train service time at stations as shown in Figure 3(a). However, the value of tf must be minimized to just meet train servicing time at stations; the value of tf is equal to that of tz in peak time-period as shown in Figure 3(b). Thus, the measure ensures that the train-set operation will be optimized and the transport capacity will be raised.The operation mode of train-sets on fixed railway section.
(a)
Normal time-period.
(b)
Peak time-period.Train-sets are not utilized completely in normal periods according to the above analysis. The paper introduces a method to adjust some train-sets from one rail section to another. For example,u is the peak time-period for rail section 1 but not for rail section 2. Moreover, there are superfluous train-sets in rail section 2, then we can adjust some from section 2 to section 1 in time-period u.


## 2.1. Passenger Demands and Travel Choices

As mentioned above, the passenger demands in passenger dedicated lines are heavily different at different time-periods, thus train operations show irregularly in every time-period at junction stations. Previous studies have discussed the departing interval of trains at junction stations based on the condition that passenger transport demands and capacities are equal during the peak time-periods. In fact, the hypothesis is unreasonable when passenger transport demands are larger than capacities during the peak time-periods. Therefore, the railway departments can not arrange enough trains to meet the passenger demands in the peak time-periods.Passengers mainly consider the degree and departing time of trains when they choose railway to travel. However, passenger demands are larger than transport ability during the peak time-periods. In this case, this paper considers that passengers probably choose the following suboptimal travel schemes for themselves: avoiding the peak time-periods and taking a train of the same degree to travel in another time-period; choosing a train of another degree to travel when its quantity is large enough in the same time-period.


## 2.2. Optimization Methods

The optimization objective for train operations at junction stations is to get maximum passenger satisfaction. Passenger satisfaction for train operations, presented in this paper, is an important indicator to evaluate the train operations. Here, the service time at junction stations is divided intom time-periods, according to which passenger demands and train-set quantity at junction stations are obtained, respectively. The time-periods in which passenger demands are larger than transport abilities are defined as peak time-periods. Finally, train operations in peak time-periods are organized according to the following two schemes.


### 2.2.1. Transferring Passenger Demands

The process that passengers choose the suboptimal schemes to travel is shown in Figure1. The parameters u and u' represent some time-periods in the service time at the junctions, respectively; a and c indicate the aboard process that passengers take r and r' degree trains, respectively; b and d indicate the travelling process that passengers take r and r' degree trains, respectively; e represents the fare loss of passengers who intend to take r' degree train but are transferred to r degree train; f represents travelling time loss of the passenger who intends to take r degree train but is transferred to r' degree train; g indicates the waiting time cost of passengers who have to travel in time-period u'.Figure 1
The process that passengers choose suboptimal schemes to travel.


### 2.2.2. Adjusting Operation Section of Train-Set

Passenger demands generate at the junction stations, from which passenger trains are dispatched to different terminal stationsj1, j2, and j3 in passenger dedicated lines as shown in Figure 2.Figure 2
Through train plan from original station to different terminal stations.As mentioned above, the transport capacity is limited at a junction station because the train-set quantity is affected by its operation mode. Stationary operation mode of train-set is used in most of the passenger dedicated lines presently; train-sets are operated on fixed railway sections as shown in Figure3. s represents a train-set; tf represents the departure interval of the same kind of train-sets at stations. In general, the value of tf is larger than that of tz, which represents the train service time at stations as shown in Figure 3(a). However, the value of tf must be minimized to just meet train servicing time at stations; the value of tf is equal to that of tz in peak time-period as shown in Figure 3(b). Thus, the measure ensures that the train-set operation will be optimized and the transport capacity will be raised.The operation mode of train-sets on fixed railway section.
(a)
Normal time-period.
(b)
Peak time-period.Train-sets are not utilized completely in normal periods according to the above analysis. The paper introduces a method to adjust some train-sets from one rail section to another. For example,u is the peak time-period for rail section 1 but not for rail section 2. Moreover, there are superfluous train-sets in rail section 2, then we can adjust some from section 2 to section 1 in time-period u.


## 2.2.1. Transferring Passenger Demands

The process that passengers choose the suboptimal schemes to travel is shown in Figure1. The parameters u and u' represent some time-periods in the service time at the junctions, respectively; a and c indicate the aboard process that passengers take r and r' degree trains, respectively; b and d indicate the travelling process that passengers take r and r' degree trains, respectively; e represents the fare loss of passengers who intend to take r' degree train but are transferred to r degree train; f represents travelling time loss of the passenger who intends to take r degree train but is transferred to r' degree train; g indicates the waiting time cost of passengers who have to travel in time-period u'.Figure 1
The process that passengers choose suboptimal schemes to travel.


## 2.2.2. Adjusting Operation Section of Train-Set

Passenger demands generate at the junction stations, from which passenger trains are dispatched to different terminal stationsj1, j2, and j3 in passenger dedicated lines as shown in Figure 2.Figure 2
Through train plan from original station to different terminal stations.As mentioned above, the transport capacity is limited at a junction station because the train-set quantity is affected by its operation mode. Stationary operation mode of train-set is used in most of the passenger dedicated lines presently; train-sets are operated on fixed railway sections as shown in Figure3. s represents a train-set; tf represents the departure interval of the same kind of train-sets at stations. In general, the value of tf is larger than that of tz, which represents the train service time at stations as shown in Figure 3(a). However, the value of tf must be minimized to just meet train servicing time at stations; the value of tf is equal to that of tz in peak time-period as shown in Figure 3(b). Thus, the measure ensures that the train-set operation will be optimized and the transport capacity will be raised.The operation mode of train-sets on fixed railway section.
(a)
Normal time-period.
(b)
Peak time-period.Train-sets are not utilized completely in normal periods according to the above analysis. The paper introduces a method to adjust some train-sets from one rail section to another. For example,u is the peak time-period for rail section 1 but not for rail section 2. Moreover, there are superfluous train-sets in rail section 2, then we can adjust some from section 2 to section 1 in time-period u.


## 3. The Train Operation Model

### 3.1. Definitions and Notations

The following notations are used to describe the proposed model.U is the set of time-periods, U={1,2,…,m};u,u'∈U,u≠u'.R is the set of train degrees, R={1,2};r,r′∈R,r≠r'.J is the set of terminal stations, J={j1,j2,j3},j∈J.m
j
u
,
r is the demands of passengers who prepare to get rth degree trains to jth terminal station in uth time-period.e
j
u
,
r is the train-set quantity of rth degree trains which are dispatched to jth terminal station in uth time-period.k
r is the maximum number of seats in rth degree trains.δ
j
u
,
u
′ is the passenger satisfaction when passenger’s departure time is changed from uth to u'th time-period.δ
j
r
,
r
′ is the passenger satisfaction when passenger train is changed from rth to r'th degree.ξ
j
u
,
r is the weighted average satisfaction of total passengers who prepare to get to jth terminal station by rth degree trains in uth time-period.Three intermediate variables are defined as follows.x
j
u
,
r is the passenger demands which can be contented in mju,r.y
j
u
'
,
r is the passenger demands which are adjusted to travel in u'th time-period.z
j
u
,
r
' is the passenger demands which are adjusted to travel by  r'th degree trains.The decision variable is defined as follows.n
j
u
,
r is the train operation quantity when rail department organizes rth degree trains to jth terminal station in uth time-period.


### 3.2. Passenger Satisfaction Function

#### 3.2.1. Passenger’s Sensitivity for Changing Their Travel Plan

For every passenger who prepares to travel byrth degree train in uth time-period, their satisfactions are different. In this paper, the satisfaction value is set to 1 when the passenger’s travel plan is contented; otherwise, the value is smaller than 1. Passenger satisfactions are on account of passenger’s sensitivity for the changing of their departure time or train degree. The passenger’s sensitivity for departure time is a tolerable degree for waiting time when passengers have to change their departure time to travel. The passenger’s sensitivity for train degree is a tolerable degree for ticket price rise when passengers have to change the train degree to travel.The functionfj(u,u') is defined to illustrate the passenger’s sensitivity when their departure time is delayed. It is related with the waiting time and travel time as shown in formula (3.1). The formula reflects a ratio relation between the waiting time at junction stations and the travel time in lines. In this formula, numerator represents the passenger’s waiting time at junction stations, and denominator shows the travel time on lines. The passenger’s departure time is put off to the next time-period when |u-u'|=1. Otherwise, |u-u'|>1. Consider
(3.1)fj(u,u')=|u-u'|·tptj,
where tp is the average waiting time of every time-period. tj represents the travel time from junction station to the jth terminal station.The functiongj(r,r') is defined to illustrate the passenger’s sensitivity when their train degree is changed. It is related with the rangeability of ticket price, as shown in (3.2). The value of pjr is larger than that of pjr' when the value of r is less than that of r'. The passenger’s satisfaction does not decrease with the reducing of ticket price in this case but will decrease with the changing of their travel plan. Here, λ is introduced to present the descending of passenger satisfaction:
(3.2)gj(r,r')={λr<r′,pjr'-pjrpjr·λr>r′,
where, λ is the parameter when the train degree is changed, 0≤λ≤1. pjr represents the ticket price of rth degree train from the junction station to jth terminal station.


#### 3.2.2. Passenger Satisfaction for Changing Travel Plan

The value ofδju,u' is correlative with the function fj(u,u'). The larger the value of fj(u,u'), the smaller the value of δju,u'. The passenger satisfaction function for changing train departure time can be defined as (3.3). In the same way, δjr,r' has similar character, and the passenger satisfaction function for changing train degree is defined as (3.4):
(3.3)δju,u'=exp[-fj(u,u′)],(3.4)δjr,r'=exp[-gj(r,r′)].


#### 3.2.3. Passenger Satisfaction Function

In this paper, passenger satisfaction is defined as formula (3.5) representing the weighted average satisfaction of total passengers who prepare to get to the jth terminal station by the rth degree train in the uth time-period:
(3.5)ξju,r=xju,r·1+∑u'∈U,u'≠uyju',r·δju,u'+zju,r'·δjr,r'mju,r.


### 3.3. The Division Method of Time-Period

According to the above analysis, passenger satisfaction will decrease when passenger’s waiting time is enlarged at junction station, as passenger’s waiting time will increase with the prolonging of the time-period. Thus, time-periods are divided according to the minimum passenger satisfactionτ. The time-period division is unreasonable when the value of δju,u' is less than τ. This paper computes the value of tp when the parameter δju,u' is equal to τ, and uses the value of tp as the dividing standard of time-period, as shown in formula (3.6). The number of time-periods is calculated by (3.7):
(3.6)tp=-tj|u-u′|lnτ,(3.7)m=ltp,
where m is the number of time-periods, and l denotes the length of service time in passenger dedicated lines.


### 3.4. Modeling

#### 3.4.1. Objective Function

Here,ξju,r represents the weighted average satisfaction of total passengers who prepare to get to jth terminal station by rth degree train in uth time-period, and the range of value ξju,r is from 0 to 1. In (3.8), the objective is to get maximum total passenger satisfaction:
(3.8)maxQ=∑j∈J∑u∈U∑r∈Rξju,r,
where, ∑r∈Rξju,r represents the satisfaction of passengers who get to jth terminal station at uth time-period. ∑u∈U∑r∈Rξju,r is the satisfaction of all passengers who get to jth station.


#### 3.4.2. Constraints

The constraint of even passenger flow is shown in (3.9). The value of mju,r can be divided into xju,r, yju',r, and zju,r' when the passenger demands cannot be contented completely in peak-periods. ∑u'∈U,u'≠uyju',r indicates the demand of passengers who prepare to travel in uth time-period and probably to be assigned to other time-periods. Consider
(3.9)xju,r+∑u'∈U,u'≠uyju',r+zju,r'=mju,r.The constraint of the train operation quantity balance is shown in (3.10). In this formula, ε={xju,r,∑u'∈Uyju',r,zju,r'}, “mod” is the symbol of modular division. The formula “xju,rmodkr+βε·1” indicates that the train quantity should meet the passenger demands xju,r. Similarly, the formula “∑u′∈Uyju′,rmodkr+βε·1” and “zju,r'modkr+βε·1” represent the train quantity meeting the demands ∑u'∈U,u'≠uyju',rand zju,r', respectively:
(3.10)nju,r=xju,rmodkr+∑u'∈Uyju',rmodkr+zju,r'modkr+∑εβε·1,(3.11)βε={1εmodkr≠0,0εmodkr=0.The constraint of the train-set quantity is shown in (3.12), which represents that train quantity nju,r is restricted by train-set quantity eju,r:
(3.12)nju,r≤eju,r.The constraint of minimum passenger satisfaction is shown in, in which δju,u' and δjr,r' should be larger than the empirical value of the passenger’s toleration for changing travel plan. Consider
(3.13)δju,u'≥τ,δjr,r′≥τ.The nonnegative and integer constraint is shown in:(3.14)nju,r≥0,xju,r≥0,yju',r≥0,zju,r'≥0
and are integer.


## 3.1. Definitions and Notations

The following notations are used to describe the proposed model.U is the set of time-periods, U={1,2,…,m};u,u'∈U,u≠u'.R is the set of train degrees, R={1,2};r,r′∈R,r≠r'.J is the set of terminal stations, J={j1,j2,j3},j∈J.m
j
u
,
r is the demands of passengers who prepare to get rth degree trains to jth terminal station in uth time-period.e
j
u
,
r is the train-set quantity of rth degree trains which are dispatched to jth terminal station in uth time-period.k
r is the maximum number of seats in rth degree trains.δ
j
u
,
u
′ is the passenger satisfaction when passenger’s departure time is changed from uth to u'th time-period.δ
j
r
,
r
′ is the passenger satisfaction when passenger train is changed from rth to r'th degree.ξ
j
u
,
r is the weighted average satisfaction of total passengers who prepare to get to jth terminal station by rth degree trains in uth time-period.Three intermediate variables are defined as follows.x
j
u
,
r is the passenger demands which can be contented in mju,r.y
j
u
'
,
r is the passenger demands which are adjusted to travel in u'th time-period.z
j
u
,
r
' is the passenger demands which are adjusted to travel by  r'th degree trains.The decision variable is defined as follows.n
j
u
,
r is the train operation quantity when rail department organizes rth degree trains to jth terminal station in uth time-period.


## 3.2. Passenger Satisfaction Function

### 3.2.1. Passenger’s Sensitivity for Changing Their Travel Plan

For every passenger who prepares to travel byrth degree train in uth time-period, their satisfactions are different. In this paper, the satisfaction value is set to 1 when the passenger’s travel plan is contented; otherwise, the value is smaller than 1. Passenger satisfactions are on account of passenger’s sensitivity for the changing of their departure time or train degree. The passenger’s sensitivity for departure time is a tolerable degree for waiting time when passengers have to change their departure time to travel. The passenger’s sensitivity for train degree is a tolerable degree for ticket price rise when passengers have to change the train degree to travel.The functionfj(u,u') is defined to illustrate the passenger’s sensitivity when their departure time is delayed. It is related with the waiting time and travel time as shown in formula (3.1). The formula reflects a ratio relation between the waiting time at junction stations and the travel time in lines. In this formula, numerator represents the passenger’s waiting time at junction stations, and denominator shows the travel time on lines. The passenger’s departure time is put off to the next time-period when |u-u'|=1. Otherwise, |u-u'|>1. Consider
(3.1)fj(u,u')=|u-u'|·tptj,
where tp is the average waiting time of every time-period. tj represents the travel time from junction station to the jth terminal station.The functiongj(r,r') is defined to illustrate the passenger’s sensitivity when their train degree is changed. It is related with the rangeability of ticket price, as shown in (3.2). The value of pjr is larger than that of pjr' when the value of r is less than that of r'. The passenger’s satisfaction does not decrease with the reducing of ticket price in this case but will decrease with the changing of their travel plan. Here, λ is introduced to present the descending of passenger satisfaction:
(3.2)gj(r,r')={λr<r′,pjr'-pjrpjr·λr>r′,
where, λ is the parameter when the train degree is changed, 0≤λ≤1. pjr represents the ticket price of rth degree train from the junction station to jth terminal station.


### 3.2.2. Passenger Satisfaction for Changing Travel Plan

The value ofδju,u' is correlative with the function fj(u,u'). The larger the value of fj(u,u'), the smaller the value of δju,u'. The passenger satisfaction function for changing train departure time can be defined as (3.3). In the same way, δjr,r' has similar character, and the passenger satisfaction function for changing train degree is defined as (3.4):
(3.3)δju,u'=exp[-fj(u,u′)],(3.4)δjr,r'=exp[-gj(r,r′)].


### 3.2.3. Passenger Satisfaction Function

In this paper, passenger satisfaction is defined as formula (3.5) representing the weighted average satisfaction of total passengers who prepare to get to the jth terminal station by the rth degree train in the uth time-period:
(3.5)ξju,r=xju,r·1+∑u'∈U,u'≠uyju',r·δju,u'+zju,r'·δjr,r'mju,r.


## 3.2.1. Passenger’s Sensitivity for Changing Their Travel Plan

For every passenger who prepares to travel byrth degree train in uth time-period, their satisfactions are different. In this paper, the satisfaction value is set to 1 when the passenger’s travel plan is contented; otherwise, the value is smaller than 1. Passenger satisfactions are on account of passenger’s sensitivity for the changing of their departure time or train degree. The passenger’s sensitivity for departure time is a tolerable degree for waiting time when passengers have to change their departure time to travel. The passenger’s sensitivity for train degree is a tolerable degree for ticket price rise when passengers have to change the train degree to travel.The functionfj(u,u') is defined to illustrate the passenger’s sensitivity when their departure time is delayed. It is related with the waiting time and travel time as shown in formula (3.1). The formula reflects a ratio relation between the waiting time at junction stations and the travel time in lines. In this formula, numerator represents the passenger’s waiting time at junction stations, and denominator shows the travel time on lines. The passenger’s departure time is put off to the next time-period when |u-u'|=1. Otherwise, |u-u'|>1. Consider
(3.1)fj(u,u')=|u-u'|·tptj,
where tp is the average waiting time of every time-period. tj represents the travel time from junction station to the jth terminal station.The functiongj(r,r') is defined to illustrate the passenger’s sensitivity when their train degree is changed. It is related with the rangeability of ticket price, as shown in (3.2). The value of pjr is larger than that of pjr' when the value of r is less than that of r'. The passenger’s satisfaction does not decrease with the reducing of ticket price in this case but will decrease with the changing of their travel plan. Here, λ is introduced to present the descending of passenger satisfaction:
(3.2)gj(r,r')={λr<r′,pjr'-pjrpjr·λr>r′,
where, λ is the parameter when the train degree is changed, 0≤λ≤1. pjr represents the ticket price of rth degree train from the junction station to jth terminal station.


## 3.2.2. Passenger Satisfaction for Changing Travel Plan

The value ofδju,u' is correlative with the function fj(u,u'). The larger the value of fj(u,u'), the smaller the value of δju,u'. The passenger satisfaction function for changing train departure time can be defined as (3.3). In the same way, δjr,r' has similar character, and the passenger satisfaction function for changing train degree is defined as (3.4):
(3.3)δju,u'=exp[-fj(u,u′)],(3.4)δjr,r'=exp[-gj(r,r′)].


## 3.2.3. Passenger Satisfaction Function

In this paper, passenger satisfaction is defined as formula (3.5) representing the weighted average satisfaction of total passengers who prepare to get to the jth terminal station by the rth degree train in the uth time-period:
(3.5)ξju,r=xju,r·1+∑u'∈U,u'≠uyju',r·δju,u'+zju,r'·δjr,r'mju,r.


## 3.3. The Division Method of Time-Period

According to the above analysis, passenger satisfaction will decrease when passenger’s waiting time is enlarged at junction station, as passenger’s waiting time will increase with the prolonging of the time-period. Thus, time-periods are divided according to the minimum passenger satisfactionτ. The time-period division is unreasonable when the value of δju,u' is less than τ. This paper computes the value of tp when the parameter δju,u' is equal to τ, and uses the value of tp as the dividing standard of time-period, as shown in formula (3.6). The number of time-periods is calculated by (3.7):
(3.6)tp=-tj|u-u′|lnτ,(3.7)m=ltp,
where m is the number of time-periods, and l denotes the length of service time in passenger dedicated lines.


## 3.4. Modeling

### 3.4.1. Objective Function

Here,ξju,r represents the weighted average satisfaction of total passengers who prepare to get to jth terminal station by rth degree train in uth time-period, and the range of value ξju,r is from 0 to 1. In (3.8), the objective is to get maximum total passenger satisfaction:
(3.8)maxQ=∑j∈J∑u∈U∑r∈Rξju,r,
where, ∑r∈Rξju,r represents the satisfaction of passengers who get to jth terminal station at uth time-period. ∑u∈U∑r∈Rξju,r is the satisfaction of all passengers who get to jth station.


### 3.4.2. Constraints

The constraint of even passenger flow is shown in (3.9). The value of mju,r can be divided into xju,r, yju',r, and zju,r' when the passenger demands cannot be contented completely in peak-periods. ∑u'∈U,u'≠uyju',r indicates the demand of passengers who prepare to travel in uth time-period and probably to be assigned to other time-periods. Consider
(3.9)xju,r+∑u'∈U,u'≠uyju',r+zju,r'=mju,r.The constraint of the train operation quantity balance is shown in (3.10). In this formula, ε={xju,r,∑u'∈Uyju',r,zju,r'}, “mod” is the symbol of modular division. The formula “xju,rmodkr+βε·1” indicates that the train quantity should meet the passenger demands xju,r. Similarly, the formula “∑u′∈Uyju′,rmodkr+βε·1” and “zju,r'modkr+βε·1” represent the train quantity meeting the demands ∑u'∈U,u'≠uyju',rand zju,r', respectively:
(3.10)nju,r=xju,rmodkr+∑u'∈Uyju',rmodkr+zju,r'modkr+∑εβε·1,(3.11)βε={1εmodkr≠0,0εmodkr=0.The constraint of the train-set quantity is shown in (3.12), which represents that train quantity nju,r is restricted by train-set quantity eju,r:
(3.12)nju,r≤eju,r.The constraint of minimum passenger satisfaction is shown in, in which δju,u' and δjr,r' should be larger than the empirical value of the passenger’s toleration for changing travel plan. Consider
(3.13)δju,u'≥τ,δjr,r′≥τ.The nonnegative and integer constraint is shown in:(3.14)nju,r≥0,xju,r≥0,yju',r≥0,zju,r'≥0
and are integer.


## 3.4.1. Objective Function

Here,ξju,r represents the weighted average satisfaction of total passengers who prepare to get to jth terminal station by rth degree train in uth time-period, and the range of value ξju,r is from 0 to 1. In (3.8), the objective is to get maximum total passenger satisfaction:
(3.8)maxQ=∑j∈J∑u∈U∑r∈Rξju,r,
where, ∑r∈Rξju,r represents the satisfaction of passengers who get to jth terminal station at uth time-period. ∑u∈U∑r∈Rξju,r is the satisfaction of all passengers who get to jth station.


## 3.4.2. Constraints

The constraint of even passenger flow is shown in (3.9). The value of mju,r can be divided into xju,r, yju',r, and zju,r' when the passenger demands cannot be contented completely in peak-periods. ∑u'∈U,u'≠uyju',r indicates the demand of passengers who prepare to travel in uth time-period and probably to be assigned to other time-periods. Consider
(3.9)xju,r+∑u'∈U,u'≠uyju',r+zju,r'=mju,r.The constraint of the train operation quantity balance is shown in (3.10). In this formula, ε={xju,r,∑u'∈Uyju',r,zju,r'}, “mod” is the symbol of modular division. The formula “xju,rmodkr+βε·1” indicates that the train quantity should meet the passenger demands xju,r. Similarly, the formula “∑u′∈Uyju′,rmodkr+βε·1” and “zju,r'modkr+βε·1” represent the train quantity meeting the demands ∑u'∈U,u'≠uyju',rand zju,r', respectively:
(3.10)nju,r=xju,rmodkr+∑u'∈Uyju',rmodkr+zju,r'modkr+∑εβε·1,(3.11)βε={1εmodkr≠0,0εmodkr=0.The constraint of the train-set quantity is shown in (3.12), which represents that train quantity nju,r is restricted by train-set quantity eju,r:
(3.12)nju,r≤eju,r.The constraint of minimum passenger satisfaction is shown in, in which δju,u' and δjr,r' should be larger than the empirical value of the passenger’s toleration for changing travel plan. Consider
(3.13)δju,u'≥τ,δjr,r′≥τ.The nonnegative and integer constraint is shown in:(3.14)nju,r≥0,xju,r≥0,yju',r≥0,zju,r'≥0
and are integer.


## 4. Algorithm Design

This paper designs a heuristic algorithm of train operation based on maximum passenger satisfaction. The algorithm process is shown as follows.Step 1 (initialization).
Firstly, the smaller value between train-set and train demand quantity is assigned to the train operation quantity, namelynju,r=min{eiju,r,aiju,r}. Secondly, the value of demands mju,r is assigned to intermediate variable xju,r, and 0 is assigned to intermediate variable yju',r and zju,r', respectively. Thirdly, define the counter b and feasible scheme p. Finally, the value of b and Q are set to 0.Step 2 (examining the balance constraint of train-set capacity and demand).
If the train demand quantityaju,ris less than train operation quantity nju,rin some time-periods, namely mju,rmodkr+βε·1<nju,r, go to Step 3. Otherwise, go to Step 4.Step 3 (passenger satisfaction examination).
Firstly, take the value ofq meetingq=min{δju,u',δjr,r'}. Secondly, passenger satisfaction is calculated when the value of q is larger than that of τ, and output this scheme p.  Otherwise, all passenger demands transformed from other time-periods are adjusted to prior time-period u-1, and equal passenger demands generated at time-period u-1 are adjusted to uth time-period. Then go to Step 4. Secondly, the counter p is refreshed with the equation of p=p+1.Step 4 (adjusting scheme).
The value ofbju,r is assigned to the value of aju,r-nju,r when the value of aju,r is larger than nju,r. Then, the value of bju,r is assigned equally to yju',r and zju,r', according to formula yju',r=zju,r'=0.5krbju,r. Finally, the value of train-set quantity nju,r is refreshed by formula nju,r=(xju,r+yju-1,r+zju,r')modkr+βε·1, and go to Step 2.


## 5. Numerical Example

In some passenger dedicated lines, passenger trains are only operated from the junction station to the terminal stationsj1, j2, and j3. The travel time from the junction station to terminal stations j1, j2, and j3 is 2, 3, and 5 hours, respectively, namely t1=2, t2=3, and t3=5. There are two degree trains, r=1, r'=2. The trains’ ticket prices are shown in Table 1. The service time of every day is 14 hours from 6:00 to 20:00. The length of the time-period tp and the number of time-periods m are computed according to (3.6) and (3.7). The calculation results: the value of tp is 3.3 hours, and the number of time-period m is 4. The service time can be divided into four time-periods, from which the passenger demands collected are shown in Table 2.Table 1
The train ticket price.
r
,
j
1, 1
1, 2
1, 3
2, 1
2, 2
2, 3
P
j
r
80
120
135
50
80
100Table 2
Passenger demands (unit: person times).
u
,
r
1,1
1,2
2,1
2,2
3,1
3,2
4,1
4,2
m
j
1
u
,
r
1110
3600
5500
12200
11100
6100
2780
1220
m
j
2
u
,
r
8300
9100
13000
9150
10000
3650
2750
2440
m
j
3
u
,
r
5500
4880
11100
9150
5500
7300
1660
1800The passenger demands can be transformed to train demands according to (3.10), and the constraint of train-set is given in the numerical example as shown in Table 3, where the notation eju,r and aju,r represent maximum train-set quantity and train demands. Then the datum, in which eju,ris less than aju,r, is adjusted to other time-periods or other degree trains according to the above heuristic algorithm.Table 3
The value ofeju,rand aju,r  (unit: train).
u
,
r
1,1
1,2
2,1
2,2
3,1
3,2
4,1
4,2
e
j
1
u
,
r,  aj1u,r
10,2
8,6
5,10
10,20
15,20
15,10
7,5
5,2
e
j
2
u
,
r,  aj2u,r
14,15
13,15
20,25
25,15
20,18
10,6
5,5
2,4
e
j
3
u
,
r,  aj3u,r
12,10
10,8
15,20
20,15
7,10
10,12
8,3
8,3This paper optimizes the passenger operation at the junction station according to the above model and algorithm in Table4. The adjustment result of passenger demands is shown in Table 5, and that of the passenger satisfaction is in Table 6.Table 4
Train operation quantity in every time-periodnju,r  (unit: train).
u
,
r
1,1
1,2
2,1
2,2
3,1
3,2
4,1
4,2
j
1
2
6
5
10
20
15
7
6
j
2
13
11
20
23
20
6
5
2
j
3
10
8
15
20
7
10
6
5Table 5
Adjustment the scheme of passenger trains.
Terminal station
Adjustment program [(u, r)→(u′, r) or (u, r′): the adjusted train quantity]
j
1
(2,1) → (3,1): 4, (2,2) → (3,2): 6, (3,1) → (4,1): 5
j
2
(1,1) → (1,2): 2, (2,1) → (3,1): 3, (1,1) → (3,1): 1, (4,2) → (4,1): 1
j
3
(2,1) → (3,1): 5, (3,1) → (4,1): 2, (3,2) → (4,2): 2Table 6
Passenger satisfactions.
u
,
r
1,1
1,2
2,1
2,2
3,1
3,2
4,1
4,2
j
1
1
1
0.53
0.7
0.85
0.93
1
1
j
2
0.87
0.73
0.8
0.93
0.89
0.8
1
0.5
j
3
1
1
0.75
1
0.7
0.83
1
1


## 6. Conclusion

In this paper, an optimization model based on maximum passenger satisfaction for the junction station has been given. A heuristic algorithm is proposed to solve it. According to the scheme results, all passenger satisfaction is calculated. Average satisfaction of passengers who prepare to get toj1th, j2th, and j3th terminal stations are 0.87, 0.81, and 0.91, respectively. Minimum satisfaction of passengers who prepare to get to j1th, j2th, and j3th terminal station are 0.42, 0.45, and 0.4, respectively. The result shows that the method proposed in this paper can effectively solve the problem, and is suitable for formulating passenger train operation in passenger dedicated lines. Furthermore, it is an important topic for further research to consider the train operation based on collaborative optimization among several junction stations in passenger dedicated lines.



---

*Source: 451201-2012-10-11.xml*