# Train Service Plan Design under the Condition of Multimodal Rail Transit Systems Integration and Interconnection

Authors: Li Lin; Xuelei Meng; Xiaoqing Cheng; Yangyang Ma; Shichao Xu
Journal: Journal of Advanced Transportation
 (2023)

---

## Abstract

Multimodal rail transit systems integration and interconnection can solve frequent transfer problems and better adapt to disequilibrium passenger flow and space. It is an inevitable choice in the development of various rail transit systems. Firstly, this paper proposes a novel train service plan design model in the scenario of multimodal rail transit systems integration and interconnection. Our model takes into account the costs of both passengers and enterprises, and passengers travel time is converted into cost using passengers’ nonworking time value coefficient. The model contains some conventional constraints such as passenger flow, station capacity, and line carrying capacity. It also considers whether the transportation capacity of different lines is matched, that is, the constraint of capacity matching degree. Secondly, an improved harmonic search algorithm (IHSA) is designed to solve the problem, and a numerical experiment is used to prove the performance of the proposed method. Our research result shows that the model and algorithm proposed in this paper is effective, which can help overcome the drawbacks of the existing independent operation mode of different rail transit systems. This study is also applicable to the scenario of other kinds of rail transit systems integration and interconnection.


---

## Body

## 1. Introduction

In many countries, rail transit has become the preferred mode of transportation for people to travel, owing to its rapidity, punctuality, safety, and environmentally friendly quality. At the same time, besides the punctuality and safety of travel, people also began to pursue the convenience, comfort, and efficiency. It is difficult for a single rail transit system to meet all kinds of passengers travel needs due to the diversity of travel demands. For example, the metro usually operates in the core area of the city, providing service for passengers intra-city travel. Suburban railway mainly serves the suburbs, while intercity railway mainly serves adjacent cities or urban agglomerations. Different rail transit systems have different kinds of vehicles, different operating speed standards, and different service distances. Various rail transit systems provide travel services for passengers with different travel needs. However, frequent transfer, long waiting time, and inability to realize point-to-point transportation are common problems in the independent operation mode of each rail transit system. Consequently, the conventional independent operation mode of different rail transit systems can no longer meet the swelling travel demand. The integration of multiple lines within a single rail transit system, such as metro and metro lines, cannot meet the travel demand neither. All the lines and trains as well as stations belong to the same rail transit system in that case. Moreover, the operation scope of the metro is limited. It is impossible to finish long-distance travel only by taking the metro, and passengers would transfer from the metro to other types of rail transit trains, such as intercity trains. The problems frequent transfer, long waiting time, and inability to realize point-to-point transportation are still unsolved. The integration and interconnection of metro and other rail transit systems like intercity railways might solve the above problems.Therefore, the integration and interconnection of various rail transit systems are what we can expect in the future. Integration means that different rail transit systems can be regarded as a whole, and through train service is available between them. All kinds of equipment and facilities as well as the remaining carrying capacity of trains, lines, and stations can be shared among different systems. However, different lines, trains, and stations may be belonging to different rail transit systems. The operating process involves the sharing of traffic resources and distributing of operating incomes. The unification of technical standards and operation management methods should be considered in the early stage of planning and construction, which is the prerequisite for realizing the integration of different rail transit systems. The above problems do not need to be considered in the integration of multiple lines belonging to the same rail transit system. Interconnection means the operation lines are connected physically, which makes trains can cross from one line to another that belonging to different railway operators, that is, cross-line operation. The integration and interconnection of various rail transit systems can not only reduce transfer frequency and save travel time, but also make the best use of transportation resource. As an emerging transportation organization mode, multimodal rail transit systems integration and interconnection will inevitably have many unprecedented problems.The current research on the integration and interconnection of multimodal rail transit systems mainly focuses on the perspective of qualitative analysis. For example, some scholars pay attention to the development strategies and the concept of integrated planning [1, 2], and others study it with realistic cases. Zhang [3] took Xi’an rail transit as an example and raised the idea of multitransit-network integration by both adjusting some subway lines to be urban express lines and using the transport capacity of existing trunk railway lines to operate urban trains. Guo [4] studied the interconnection scheme of the intercity rail network between Shenzhen and Daya Bay and then proposed an optimization strategy for the intercity railway interconnection layout. Zhou et al. [5] analyzed the problems of realizing multimodal rail transit systems integration and interconnection at this stage, and explored the realization method of integrated transportation organization from a macroperspective by taking Chengdu plain urban agglomeration as an example.Above studies have proved the feasibility and necessity of multimodal rail transit systems integration and interconnection from the aspects of development ideas and overall planning. Little attention has been paid to introduce multimodal rail transit systems integration and interconnection into the train service plan design, which is of great significance in the perspective of long-term development. At the operation organization level, the most important problem to be solved is train service plan design. Train service plan is the most crucial phases in the design of public transportation systems and particular in railway systems. The design of the train service plan is the core work of transportation organization and the basis of train diagram preparation. Therefore, it is vital to study the train service plan design problem. The purpose of designing a train service plan is to determine stop patterns, optimal routes (origin-destination paths), and train service frequencies [6–8].A small number of scholars also studied the train service plan design problem under the interconnection operation mode of multiple lines within a single-modal urban rail system, such as railway rapid transit network [9], high-frequency railway system [10], and strongly heterogeneous railway lines with direct connections [11]. Canca et al. [12] considered maximizing the net profit over a planning horizon as the objective and used an adaptive large neighborhood search metaheuristic algorithm to solve the integrated network design and train service plan design problem. Zhou et al. [13] analyzed the line configuration and train frequency setting in an urban rail transit network to optimize the train service plan, and the problem is formulated as a mixed-integer nonlinear programming model with linear constraints. Szeto and Jiang [14] constructed a bi-level rail transit network design model where the transit routes and train service frequency settings are determined simultaneously. Ding et al. [15] proposed a mathematical model to determine the short turning pattern, and an empirical case of Shanghai Metro was incorporated to demonstrate the effectiveness of the proposed model. Yang et al. [16] proposed a new model to achieve both passenger travel time and operation cost savings and optimized the frequencies, stopping patterns, and operation zones of cross-line express trains and local trains simultaneously. Li et al. [17] focuses on the train service design problem incorporating multiple service routes and multiple train compositions, the problem lies on determining the turn-back stations, train composition, and frequency of each service route operated on the line. Xu et al. [18] calculated the travel time reliability based on the passenger flow to study train service plan. Luo et al. [19] aimed at express and local trains for regional rail transit lines and established an integer programming model with the objective of minimizing the travel time of passengers. Wang et al. [20] paid more attention to extra-long distance transportation and established a mathematical model to optimize train service frequency and stop patterns. Baoji-Lanzhou high-speed railway network was used as a real-world example to make further discussion.To summarize, the research on the integration and interconnection of multimodal rail transit systems mainly focuses on the evolving scheme and planning ideas, and research methods are mainly based on qualitative analysis [3–5]. For the perspective of designing a train service plan, most of the researches focus on trunk railway system [9–11] or other single-modal urban rail transit system [14–20]. Existing studies on train service plan design have been performed on only one kind of rail transit system with less consideration of cross-line operation from the original line to the line, belonging to other kind of rail transit system. Few scholars study train service plan design under the condition of multimodal rail transit systems integration and interconnection. The integration and interconnection of multimodal rail transit systems are an inevitable choice in the development of transportation companies. Relevant research on multimodal rail transit systems is lacking. Scientifically and reasonably designing train service plan under the condition of multimodal rail transit systems integration and interconnection can provide better services for passengers, enhance operational efficiency and allocate transportation resources more reasonably for companies, and form an integrated transportation network with strong transportation organization capability for the city. Therefore, this paper designs a train service plan under the condition of multimodal rail transit systems integration and interconnection. The difference between the most related published papers and this paper is compared in Table 1.Table 1
The comparison between this paper and previous works.
PaperIn the scenario of multimodal rail transit systems integration and interconnection?With cross-line operation?With passenger flow constraint?With capacity matching degree constraint?Solution methodChang et al. [6]NoNoYesNoFuzzy mathematical programmingBussieck et al. [7]NoNoNoNoA heuristic variable fixing procedureBorndörfer et al. [8]NoNoNoNoColumn generation approachCanca et al. [9]NoNoYesNoAdaptive large neighborhood search algorithmBurggraeve et al. [10]NoNoYesNoHeuristic algorithmYan and Goverde [11]NoNoYesNoAn iterative methodCanca et al. [12]NoNoYesNoAdaptive large neighborhood search metaheuristicZhou et al. [13]NoNoYesNoAn outer approximation methodSzeto and Jiang [14]NoNoYesNoA hybrid artificial bee colony algorithmDing et al. [15]NoNoYesNoUnspecifiedYang et al. [16]NoYesNoNoGenetic algorithmThis paperYesYesYesYesImproved harmonic search algorithmTrain service plan design problem has numerous parameters, huge solution dimensions, and complicated constraints. According to the existing studies, this type of problem is always NP-hard, even with a small-scale calculation example, it is hard to be solved by existing software [21–23]. Therefore, algorithm designing is another critical issue of the train service plan design problem. Many existing researches have used heuristic algorithms to solve train service plan design problem [10], such as genetic algorithm [16, 19] and simulated annealing algorithm [24]. We tried to use an emerging algorithm, which was called the harmonic search algorithm. The harmonic search algorithm has the advantages of strong robustness and high reliability, showing good performance in solving nonlinear programming problems [25, 26]. This is also confirmed in the subsequent case study.The detailed contributions of this paper are as follows:(1)
A novel train service plan design model in the scenario of multimodal rail transit systems integration and interconnection is built. The model is based on a relatively new research scenario, where trains can cross-line operation. Besides, it considers whether the transportation capacity of different lines is matched, that is, the constraint of capacity matching degree. This constraint is ignored by the existing train service plan design models.(2)
The improved harmonic search algorithm (IHSA) is used to solve the train service plan design problem, which has never been applied to solve the train service plan design before. Apply the proposed approach to the case study, and calculation results are analyzed that inspire the realization of multimodal rail transit systems integration and interconnection.The remainder of the paper is organized as follows. Section1 constructs a mathematical model for train service plan design. In Section 2, the improved harmonic search algorithm (IHSA) is designed for solving the constructed model. In Section 3, a computation case is presented, based on the data of an interconnected suburban rail line and intercity line to show the effectiveness of the model. Section 4 draws conclusions and proposes some issues for future research.


## 2. Model for Train Service Plan Design

This section starts by discussing the necessity and importance of multimodal rail transit systems integration and interconnection. Then, the problem scenario and model assumptions are described in detail. Finally, the problem is defined mathematically with a nonlinear model.


### 2.1. Problem Description

With the expansion of rail transit network as well as fast-growing passenger flow, the shortcomings of the conventional independent operation mode of different rail transit systems are becoming more and more obvious. Mismatching service supply, low resource utilization, and worse resource sharing are common problems in many rail transit systems. In addition, the transfer process in this operation mode may be difficult and taking a lot of time, which greatly increases the total travel time of passengers and reduces the attraction of rail transit travel.Therefore, it is necessary to realize different rail transit systems integration and interconnection, and the most common method to make it true is cross-line operation. It means trains can share the track with other trains that belonging to different railway companies. The traffic resources can be shared among different rail transit systems under the cross-line operation mode, and passengers can take the same train to travel freely among different lines without transfer. It can reduce the number of transfers and save walking time of transfer pedestrians and their second waiting time. As a result, cross-line operation can save transfer time, improve travel efficiency, and optimize passengers travel process. At the same time, it can also promote the image of the operating enterprise and increase operating income.Suppose that there are three types of rail transit lines, as shown in Figure1. L0 is an urban rail transit line, which is connected to the downtown area and providing service for passengers intra-city travel. L1 is the suburban rail line, which providing services for passengers to travel in the suburbs, and linking up with urban rail transit lines through the transfer station. L2 is the cross-line between L1 and L3, providing through service for passengers. L2 is not an independent line, but marked by the authors to distinguish it from other lines. L3 is the intercity line which provides service for passengers who need to travel between cities, and connecting with suburban rail line through the transfer station.Figure 1
Sketch map of train running lines.S=Si|i=1,⋯,a,⋯,b,⋯,c,⋯,N is the set of stations. S1 is the departure station of L1 line and also the transfer station from L0 line to L1 line. Sa is the departure station of L2 line and also the transfer station from L1 line to L2 line. Sb is the cross-track-station of L2 line, terminal station of L1 line, departure station of L3 line, and the transfer hub of the three lines. If we split L2 from station Sb into two lines, we can get part of the suburban line L1 and the intercity line L3. There are different types of trains running on the different lines. Passengers transfer from a line to another that means transferring from a kind of train to another. Sc is the terminal station of L2 line and also a transfer station from L2 line to L3 line. SN is the terminal station of L3 line, N is the total number of stations.The four lines jointly provide services to passengers in this area. Passengers in the downtown area can choose to take urban rail transit trains (trains running onL0 line) to station S1 and transfer to L1 line, and then go to other cities via L2 line and L3 line. This paper proposed a solution to satisfy the passengers' travel demand between station S1 and station SN while train service plan of urban rail transit line L0 is already known.As shown in Figure2, the line can be divided into sections I, II, III and IV according to the passengers travel path, and the subsequent description of passenger flows distribution and passengers travel time is based on this division.Figure 2
Division of operation lines.According to the passenger flows distribution in Figure3, passenger flows in the upward direction can be divided into 10 categories, namely, Class-11 passenger flows, Class-12 passenger flows, Class-13 passenger flows, Class-14 passenger flows, Class-22 passenger flows, Class-23 passenger flows, Class-24 passenger flows, Class-33 passenger flows, Class-34 passenger flows, Class-44 passenger flows. Both the beginning and the end of the travel path for Class-11 passenger flows are in section I. The beginning of the travel path for Class-12 passenger flows is in section I, and the end of it is in section II. Other types of passenger flows will be deduced by analogy, so we will not repeat them one by one.Figure 3
Schematic diagram of passenger flows distribution.


### 2.2. Assumptions of the Model

The model is based on the following assumptions:(1)
Requirements for cross-line operation have been fully considered in the initial stage of construction. Operating enterprises have made long-term plans in terms of line construction and vehicle selection. Running cross-line trains between the two different lines is feasible. Moreover, each intermediate station is available for running turn-back trains, and the turn-back time of trains at each station is the same. Therefore,Sa can be any station between S1 and Sb, Sc can be any station between Sb and SN.(2)
We only design a train service plan in the upward direction. Moreover, the marshaling mode of various trains is fixed, and the stop scheme adopts the all-stop mode.(3)
Passengers arrive at the station evenly and obey the principle of first-come-first-serve. Passengers will take the first train that arrives at the station. In addition, there are no stranded passengers.(4)
Part of the passenger flows chooses nontransfer (through) mode, and the other part has no preference for travel mode choice. Excluding the transfer with urban rail transit, passengers can only transfer once at most. Both transfer and nontransfer passenger flows have the same time value.


### 2.3. Decision Variables and Parameters of the Model

The decision variables and parameters of the train service plan design model are listed in Table2.Table 2
The notations used in the model.
NotationsDescriptionRoleS=Si|i=1,⋯,NA set of stationsSetL=Lu|u=0,1,2,3A set of linesSetV=Vu|u=0,1,2,3A set of train typesSetV0The set of urban rail transit trains which running onL0 line (the service frequency is already known)SetV1The set of suburban rail trains which running onL1 lineSetV2The set of cross-line trains which running onL2 lineSetV3The set of intercity trains which running onL3 lineSetaLocation of the departure stationSaDecision variablecLocation of the terminal stationScDecision variablefVuService frequency ofVu type trainsDecision variableWrunCost of train runningIntermediate variableWcrossCross-line operation costIntermediate variableqeπVuThe number of passengers takingVu type trains in section eπIntermediate variableTTotal travel time of all passengersIntermediate variableTxyTravel time from sectionx to section y, x,y∈ {I, II, III, IV} and x≤yIntermediate variableWThe overall objective function after transformationObjectiveW′Total operating cost of enterprisesObjectiveW″Cost converted from passengers’ travel timeObjectiveeπSection between stationSπ and station Sπ+1, π=1,2,⋯,N−1SymbolcostrunVuOperating cost of eachVu type vehicle running per kilometerParametercostcrossV2Additional cost arising from per stop of cross-line trainsParametermVuMarshalling number ofVu type trainsParameterCapVuCapacity ofVu type trainsParameterξVuCapacity utilization ofVu type trainsParameterdijMileage between stationSi and station SjParametercosttimePassengers’ nonworking time value coefficient (it can convert time into money)ParameterqijThe number of passengers from stationSi to station SjParameterαProportion of passengers who choose to transfer at the transfer node (excluding transfer with urban rail)ParameterttransferTransfer time of each passenger in a single transferParameterMVuNumber ofVu type trains’ available vehicles in the unit timeParameterfmaxL1Maximal carrying capacity ofL1 lineParameterfmaxL3Maximal carrying capacity ofL3 lineParameterfminL1,depMinimal departure frequency ofV1 trainsParameterfminL3,depMinimal departure frequency ofV3 trainsParameterfSiThrough capacity of stationSiParameterλProportion of passengers who choose urban rail transit as the travel mode to go to stationS1ParameterδThe number of urban rail transit lines connected to stationS1Parametert0Departure interval of urban rail transit trainsParameterρProportion of transport capacity provided by urban rail transit trains to passengers who transfer to theL1 lineParameter


### 2.4. Optimization Objectives

#### 2.4.1. Enterprise-Oriented Objective

From the perspective of the enterprises, the operating cost is an important indicator that can be evaluated quantitatively. The operating cost of enterprises includes the cost of train running and the extra cost caused by cross-line trains. For the enterprises, the lower operating cost, the better.(1)minW′=Wrun+Wcross,Wrun=costrunV1⋅fV1⋅mV1⋅d1b+costrunV2⋅fV2⋅mV2⋅dac+costrunV3⋅fV3⋅mV3⋅dbN,Wcross=fV2⋅costcrossV2⋅c−a+1.


#### 2.4.2. Passenger-Oriented Objective

For passengers, travel time is the most closely related quantitative indicator to train service plan. In order to facilitate the subsequent merging of the two objective functions, passengers’ nonworking time value coefficient is used here to convert passengers travel time into the cost. Cost converted from passengers travel time can be expressed by total travel time and passengers’ nonworking time value coefficient.(2)minW″=costtime⋅T.As shown in Figure3, there are 10 types of passenger flows in the upward directions: 11, 12, 13, 14, 22, 23, 24, 33, 34, and 44. Therefore, the total travel time can also be expressed as the sum of all kinds of passengers travel time.(3)T=∑x=14∑y=x4Txy.The total travel time of passengers includes waiting time, travel time on the train, and the transferring time from one train to another. There is hardly any correlation between one-way travel time and train service plan, so we only consider waiting time and transfer time. The previous researchers believe that the average passenger waiting time is approximately half of the departure interval if the departure interval is very short [24, 27, 28]. Therefore, the travel time of various sections can be expressed as equations (6)–(15).Taking the most complex formula (9) as an example to explain T23. Similarly, the travel time expression Txy of other types of passenger flows can be obtained. α represents the proportion of transfer passengers, and the proportion of nontransfer passengers is 1−α, so the total number of nontransfer passengers is ∑i=ab−1∑j=b+1c1−α⋅qij. From section II to section III, passenger flows without transfers can only take V2 trains. Therefore, according to the above principles in [24, 27, 28], the waiting time of this kind of passenger flow is 1/2fV2.The proportion of transfer passengers isα, so the total number of transfer passengers is ∑i=ab−1∑j=b+1cα⋅qij. When transfer passengers get on trains from section II, they can choose to take V1 trains or V2 trains, and the proportion of transfer passengers choosing V1 trains is fV1/fV1+fV2, and the proportion of transfer passengers choosing V2 trains is fV2/fV1+fV2. After arriving at station Sb, transfer passengers who choose V1 trains can transfer to the destination station of section III by V2 or V3 trains, so the total waiting time of this type of passengers can be expressed as 1/2fV1+ttransfer/60+1/2fV2+fV3. And after transfer, passengers who take V2 trains arriving at station Sb, if they transfer, can only choose V3 trains to section III, so the total waiting time of this kind of passengers can be expressed as 1/2fV2+ttransfer/60+1/2fV3. To sum up, the expression of T23 can be obtained.(4)T11=∑i=1a−1∑j=i+1aqij⋅12fV1,(5)T12=∑i=1a−1∑j=a+1bqij⋅α⋅12fV1+ttransfer60+12fV2+1−α⋅12fV1,(6)T13=∑i=1a−1∑j=b+1cqij⋅fV2fV2+fV3⋅12fV1+ttransfer60+12fV2+fV3fV2+fV3⋅12fV1+ttransfer60+12fV3,(7)T14=∑i=1a−1∑j=c+1Nqij⋅12fV1+ttransfer60+12fV3,(8)T22=∑i=ab−1∑j=i+1bqij⋅12fV1+fV2,(9)T23=∑i=ab−1∑j=b+1cqij⋅1−α⋅12fV2+α⋅fV2fV1+fV2⋅12fV2+ttransfer60+12fV3+α⋅fV1fV1+fV2⋅12fV1+ttransfer60+12fV2+fV3,(10)T24=∑i=ab−1∑j=c+1Nqij⋅fV1fV1+fV2⋅12fV1+ttransfer60+12fV3+fV2fV1+fV2⋅12fV2+ttransfer60+12fV3,(11)T33=∑i=bc−1∑j=i+1cqij⋅12fV2+fV3,(12)T34=∑i=bc−1∑j=c+1Nqij⋅α⋅12fV2+ttransfer60+12fV3+1−α⋅12fV3,(13)T44=∑i=cN−1∑j=i+1Nqij⋅12fV3.


### 2.5. Constraints of Train Service Plan Design Model

There are numerous constraints to assure that passengers must be transported to their destinations and the capacity cannot be exceeded. The detail of the constraints is listed as follows.


#### 2.5.1. Constraint of Passenger Flow

Transporting all the passengers to their destination is the primary condition. Passengers must be transported withV1, V2, and V3 trains. Use qeπV1 as an example to explain the constraint. V1 trains depart from station S1 and return from station Sb. V1 trains pass through sect ions I and II, so only passengers in these two sections need to be considered when calculate qeπV1.We can see that from Figure1, in section I, passengers can only take V1 trains. eπ can be any section in section I, passengers taking V1 trains in section eπ can be divided into four types according to Figure 4, that is, 11, 12, 13 and 14. All the departure stations of passengers should be located at section S1,Sπ, terminal station be located at section Sπ+1,SN. In Figure 4, eπ is any section within section I, and the green dotted line in the figure indicates the travel path of passengers. The total number of passengers to be transported in section eπ is ∑1≤i≤π∑π<j≤Nqij.Figure 4
Travel path of passengers takingV1 trains in section eπ,eπ∈I.Similarly, as shown in Figure5, for any eπ belongs to section II, passengers taking V1 trains in section eπ can be divided into six types, namely, 12, 13, 14, 22, 23, and 24. Moreover, all the departure stations of passengers should be located at section S1,Sπ and terminal station be located at section Sπ+1,SN.Figure 5
Travel path of passengers takingV1 trains in section eπ,eπ∈II.If type 12 passenger flows takingV1 trains in section II, it means that these passengers have no transfer behavior at station Sa, so there are ∑1≤i<a∑π<j≤b1−α⋅qij passengers in total.As shown in Figure6, type 13 passenger flows can choose to take V1 trains to station Sa and then transfer to V2 trains, or they can choose to take V1 trains to station Sb and then transfer to V2 or V3 trains. The proportion of the first case (the green dotted line at the top of Figure 6) is 1/2⋅fV2/fV2+fV3, the proportion of the second case (the green dotted line in the middle of Figure 6) is 1/2⋅fV2/fV2+fV3, and the proportion of the third case (the green dotted line at the bottom of Figure 6) is fV3/fV2+fV3. In the second and third cases, passengers will take V1 trains in section II. Therefore, this part of passenger flows can be expressed as ∑1≤i<a∑b<j≤cfV3/fV2+fV3+1/2⋅fV2/fV2+fV3⋅qij.Figure 6
Travel scheme of type 13 passenger flows.For type 14 passenger flows, since passengers can only transfer once at most under the assumption, take classV1 trains to station Sb, and then transfer to V3 trains to the destination station in section IV. Therefore, the total passengers of this kind are ∑1≤i<a∑c<j≤Nqij.Type 22 passenger flows can only takeV1 or V2 trains in section II. Therefore, when eπ belongs to section II, the number of type 22 passenger flows taking V1 trains in section eπ can be expressed as ∑a≤i≤π∑π<j≤bfV1/fV1+fV2⋅qij.Among type 23 passenger flows, the proportion of nontransfer passengers is1−α. This part of passengers arriving at the destination by V2 trains, and the proportion of passengers who opt to transfer is α. There are three possible transfer modes. The travel scheme of type 23 passenger flows is shown in Figure 7. Therefore, any eπ belongs to section II, the number of type 23 passengers taking V1 trains in section eπ is ∑a≤i≤π∑b<j≤cα⋅fV1/fV1+fV2⋅qij.Figure 7
Travel scheme of type 23 passenger flows.There are three possible travel schemes for type 24 passenger flows, as shown in Figure8. For any eπ belongs to section II, the number of type 24 passengers taking V1 trains in section eπ can be expressed as ∑a≤i≤π∑c<j≤NfV1/fV1+fV2⋅qij.Figure 8
Travel scheme of type 24 passenger flows.In summary, the expression ofqeπV1 is shown in equation (14). The qeπV1 should not exceed the capacity limit of V1 trains, that is, qeπV1≤fV1⋅CapV1⋅ξV1,eπ∈Ι,ΙΙ. Similarly, train capacity constraints of V2 and V3 trains are as follows:(14)qeπV1=∑1≤i≤π∑π<j≤Nqijeπ∈Ι∑1≤i<a∑π<j≤b1−α⋅qij+∑1≤i<a∑b<j≤cfV3fV2+fV3+12⋅fV2fV2+fV3⋅qij+∑1≤i<a∑c<j≤Nqij+∑a≤i≤π∑π<j≤bfV1fV1+fV2⋅qij+∑a≤i≤π∑b<j≤cα⋅fV1fV1+fV2⋅qij+∑a≤i≤π∑c<j≤NfV1fV1+fV2⋅qijeπ∈ΙΙ,(15)qeπV1≤fV1⋅CapV1⋅ξV1,eπ∈Ι,ΙΙ,qeπV2=∑1≤i<a∑π<j≤bα⋅qij+∑1≤i<a∑b<j≤c12⋅fV2fV2+fV3⋅qij+∑a≤i≤π∑π<j≤bfV2fV1+fV2⋅qij+∑a≤i≤π∑b<j≤cα⋅fV2fV1+fV2⋅qij+1−α⋅qij+∑a≤i≤π∑c<j≤NfV2fV1+fV2⋅qijeπ∈ΙΙ∑1≤i<a∑π<j≤cfV2fV2+fV3⋅qij+∑a≤i<b∑π<j≤c1−α⋅qij+α⋅fV1fV1+fV2⋅fV2fV2+fV3⋅qij+∑a≤i<b∑c<j≤N12⋅fV2fV1+fV2⋅qij+∑b≤i≤π∑π<j≤cfV2fV2+fV3⋅qij+∑b≤i≤π∑c<j≤Nα⋅qijeπ∈ΙΙΙ,qeπV2≤fV2⋅CapV2⋅ξV2,eπ∈Ι,ΙΙΙ,qeπV3=∑1≤i<a∑π<j≤cfV3fV2+fV3⋅qij+∑1≤i<a∑c<j≤Nqij+∑a≤i<b∑π<j≤cα⋅qij⋅fV2fV1+fV2+fV1fV1+fV2⋅fV3fV2+fV3+∑a≤i<b∑c<j≤NfV1fV1+fV2+12⋅fV2fV1+fV2⋅qij+∑b≤i≤π∑π<j≤cfV3fV2+fV3⋅qij+∑b≤i≤π∑c<j≤N1−α⋅qijeπ∈ΙΙΙ∑1≤i≤π∑π<j≤Nqijeπ∈ΙV,qeπV3≤fV3⋅CapV3⋅ξV3,eπ∈ΙΙΙ,ΙV.


#### 2.5.2. Constraint of Vehicles Number

The number of vehicles used during the study period (one hour) cannot exceed the total available vehicles.(16)fV1⋅mV1≤MV1,fV2⋅mV2≤MV2,fV3⋅mV3≤MV3.


#### 2.5.3. Constraint of Line Carrying Capacity

The carrying capacity of each line cannot be exceeded according to the train service plan.(17)fV1+fV2≤fmaxL1,fV2+fV3≤fmaxL3.


#### 2.5.4. Constraint of Departure Frequency

In order to ensure the service quality, the departure frequency of original trains (trains running on their own lines) shall not be lower than the minimal departure frequency.(18)fV1≥fminL1,dep,fV3≥fminL3,dep.


#### 2.5.5. Constraint of the Station Capacity

The carrying capacity of each station cannot be exceeded.(19)fV1≤fSi,i∈1,⋯,a−1,fV1+fV2≤fSi,i∈a,⋯,b−1,fV2+fV3≤fSi,i∈b,⋯,c−1,fV3≤fSi,i∈c,⋯,N.


#### 2.5.6. Constraint of Capacity Matching Degree

Take the upward direction as an example; if the capacity of the suburban line and urban rail transit line is highly matched, the transportation capacity provided by urban rail transit should meet the travel needs of suburban passenger flows.(20)fV1⋅CapV1⋅ξV1⋅λ≤δ⋅60t0⋅CapV0⋅ξV0⋅ρ.


#### 2.5.7. Constraint of Origination and Destination Setting

The origination and destination of cross-lineL2 should be set at the intermediate stations with turn-back capability in L1 line and L3 line.(21)2≤a≤b−1,b+1≤c≤N−1.


#### 2.5.8. Constraint of Variable Assignment

The value of train service frequency belongs to natural number setN.(22)fVu∈N∀u∈1,2,3.


### 2.6. Transformation of Objective Functions

Considering the complexity and difficulty of solving a multiobjective model, we combine the two objectives and describe it with a single formula. The linear weighted sum method is used to transform the multiobjective optimization model into a single-objective one.Φ is the weight coefficient between 0,1. In order to unify the magnitude of two objective functions, the minimum values of objective function one (W∗′) and objective function two (W∗″) are calculated in advance. Then, the ratio of W′ and W∗″ is used as the conversion coefficient. W is the general objective function after transformation.(23)minW=Φ⋅W′+1−Φ⋅W∗′W∗″⋅W″.


## 2.1. Problem Description

With the expansion of rail transit network as well as fast-growing passenger flow, the shortcomings of the conventional independent operation mode of different rail transit systems are becoming more and more obvious. Mismatching service supply, low resource utilization, and worse resource sharing are common problems in many rail transit systems. In addition, the transfer process in this operation mode may be difficult and taking a lot of time, which greatly increases the total travel time of passengers and reduces the attraction of rail transit travel.Therefore, it is necessary to realize different rail transit systems integration and interconnection, and the most common method to make it true is cross-line operation. It means trains can share the track with other trains that belonging to different railway companies. The traffic resources can be shared among different rail transit systems under the cross-line operation mode, and passengers can take the same train to travel freely among different lines without transfer. It can reduce the number of transfers and save walking time of transfer pedestrians and their second waiting time. As a result, cross-line operation can save transfer time, improve travel efficiency, and optimize passengers travel process. At the same time, it can also promote the image of the operating enterprise and increase operating income.Suppose that there are three types of rail transit lines, as shown in Figure1. L0 is an urban rail transit line, which is connected to the downtown area and providing service for passengers intra-city travel. L1 is the suburban rail line, which providing services for passengers to travel in the suburbs, and linking up with urban rail transit lines through the transfer station. L2 is the cross-line between L1 and L3, providing through service for passengers. L2 is not an independent line, but marked by the authors to distinguish it from other lines. L3 is the intercity line which provides service for passengers who need to travel between cities, and connecting with suburban rail line through the transfer station.Figure 1
Sketch map of train running lines.S=Si|i=1,⋯,a,⋯,b,⋯,c,⋯,N is the set of stations. S1 is the departure station of L1 line and also the transfer station from L0 line to L1 line. Sa is the departure station of L2 line and also the transfer station from L1 line to L2 line. Sb is the cross-track-station of L2 line, terminal station of L1 line, departure station of L3 line, and the transfer hub of the three lines. If we split L2 from station Sb into two lines, we can get part of the suburban line L1 and the intercity line L3. There are different types of trains running on the different lines. Passengers transfer from a line to another that means transferring from a kind of train to another. Sc is the terminal station of L2 line and also a transfer station from L2 line to L3 line. SN is the terminal station of L3 line, N is the total number of stations.The four lines jointly provide services to passengers in this area. Passengers in the downtown area can choose to take urban rail transit trains (trains running onL0 line) to station S1 and transfer to L1 line, and then go to other cities via L2 line and L3 line. This paper proposed a solution to satisfy the passengers' travel demand between station S1 and station SN while train service plan of urban rail transit line L0 is already known.As shown in Figure2, the line can be divided into sections I, II, III and IV according to the passengers travel path, and the subsequent description of passenger flows distribution and passengers travel time is based on this division.Figure 2
Division of operation lines.According to the passenger flows distribution in Figure3, passenger flows in the upward direction can be divided into 10 categories, namely, Class-11 passenger flows, Class-12 passenger flows, Class-13 passenger flows, Class-14 passenger flows, Class-22 passenger flows, Class-23 passenger flows, Class-24 passenger flows, Class-33 passenger flows, Class-34 passenger flows, Class-44 passenger flows. Both the beginning and the end of the travel path for Class-11 passenger flows are in section I. The beginning of the travel path for Class-12 passenger flows is in section I, and the end of it is in section II. Other types of passenger flows will be deduced by analogy, so we will not repeat them one by one.Figure 3
Schematic diagram of passenger flows distribution.


## 2.2. Assumptions of the Model

The model is based on the following assumptions:(1)
Requirements for cross-line operation have been fully considered in the initial stage of construction. Operating enterprises have made long-term plans in terms of line construction and vehicle selection. Running cross-line trains between the two different lines is feasible. Moreover, each intermediate station is available for running turn-back trains, and the turn-back time of trains at each station is the same. Therefore,Sa can be any station between S1 and Sb, Sc can be any station between Sb and SN.(2)
We only design a train service plan in the upward direction. Moreover, the marshaling mode of various trains is fixed, and the stop scheme adopts the all-stop mode.(3)
Passengers arrive at the station evenly and obey the principle of first-come-first-serve. Passengers will take the first train that arrives at the station. In addition, there are no stranded passengers.(4)
Part of the passenger flows chooses nontransfer (through) mode, and the other part has no preference for travel mode choice. Excluding the transfer with urban rail transit, passengers can only transfer once at most. Both transfer and nontransfer passenger flows have the same time value.


## 2.3. Decision Variables and Parameters of the Model

The decision variables and parameters of the train service plan design model are listed in Table2.Table 2
The notations used in the model.
NotationsDescriptionRoleS=Si|i=1,⋯,NA set of stationsSetL=Lu|u=0,1,2,3A set of linesSetV=Vu|u=0,1,2,3A set of train typesSetV0The set of urban rail transit trains which running onL0 line (the service frequency is already known)SetV1The set of suburban rail trains which running onL1 lineSetV2The set of cross-line trains which running onL2 lineSetV3The set of intercity trains which running onL3 lineSetaLocation of the departure stationSaDecision variablecLocation of the terminal stationScDecision variablefVuService frequency ofVu type trainsDecision variableWrunCost of train runningIntermediate variableWcrossCross-line operation costIntermediate variableqeπVuThe number of passengers takingVu type trains in section eπIntermediate variableTTotal travel time of all passengersIntermediate variableTxyTravel time from sectionx to section y, x,y∈ {I, II, III, IV} and x≤yIntermediate variableWThe overall objective function after transformationObjectiveW′Total operating cost of enterprisesObjectiveW″Cost converted from passengers’ travel timeObjectiveeπSection between stationSπ and station Sπ+1, π=1,2,⋯,N−1SymbolcostrunVuOperating cost of eachVu type vehicle running per kilometerParametercostcrossV2Additional cost arising from per stop of cross-line trainsParametermVuMarshalling number ofVu type trainsParameterCapVuCapacity ofVu type trainsParameterξVuCapacity utilization ofVu type trainsParameterdijMileage between stationSi and station SjParametercosttimePassengers’ nonworking time value coefficient (it can convert time into money)ParameterqijThe number of passengers from stationSi to station SjParameterαProportion of passengers who choose to transfer at the transfer node (excluding transfer with urban rail)ParameterttransferTransfer time of each passenger in a single transferParameterMVuNumber ofVu type trains’ available vehicles in the unit timeParameterfmaxL1Maximal carrying capacity ofL1 lineParameterfmaxL3Maximal carrying capacity ofL3 lineParameterfminL1,depMinimal departure frequency ofV1 trainsParameterfminL3,depMinimal departure frequency ofV3 trainsParameterfSiThrough capacity of stationSiParameterλProportion of passengers who choose urban rail transit as the travel mode to go to stationS1ParameterδThe number of urban rail transit lines connected to stationS1Parametert0Departure interval of urban rail transit trainsParameterρProportion of transport capacity provided by urban rail transit trains to passengers who transfer to theL1 lineParameter


## 2.4. Optimization Objectives

### 2.4.1. Enterprise-Oriented Objective

From the perspective of the enterprises, the operating cost is an important indicator that can be evaluated quantitatively. The operating cost of enterprises includes the cost of train running and the extra cost caused by cross-line trains. For the enterprises, the lower operating cost, the better.(1)minW′=Wrun+Wcross,Wrun=costrunV1⋅fV1⋅mV1⋅d1b+costrunV2⋅fV2⋅mV2⋅dac+costrunV3⋅fV3⋅mV3⋅dbN,Wcross=fV2⋅costcrossV2⋅c−a+1.


### 2.4.2. Passenger-Oriented Objective

For passengers, travel time is the most closely related quantitative indicator to train service plan. In order to facilitate the subsequent merging of the two objective functions, passengers’ nonworking time value coefficient is used here to convert passengers travel time into the cost. Cost converted from passengers travel time can be expressed by total travel time and passengers’ nonworking time value coefficient.(2)minW″=costtime⋅T.As shown in Figure3, there are 10 types of passenger flows in the upward directions: 11, 12, 13, 14, 22, 23, 24, 33, 34, and 44. Therefore, the total travel time can also be expressed as the sum of all kinds of passengers travel time.(3)T=∑x=14∑y=x4Txy.The total travel time of passengers includes waiting time, travel time on the train, and the transferring time from one train to another. There is hardly any correlation between one-way travel time and train service plan, so we only consider waiting time and transfer time. The previous researchers believe that the average passenger waiting time is approximately half of the departure interval if the departure interval is very short [24, 27, 28]. Therefore, the travel time of various sections can be expressed as equations (6)–(15).Taking the most complex formula (9) as an example to explain T23. Similarly, the travel time expression Txy of other types of passenger flows can be obtained. α represents the proportion of transfer passengers, and the proportion of nontransfer passengers is 1−α, so the total number of nontransfer passengers is ∑i=ab−1∑j=b+1c1−α⋅qij. From section II to section III, passenger flows without transfers can only take V2 trains. Therefore, according to the above principles in [24, 27, 28], the waiting time of this kind of passenger flow is 1/2fV2.The proportion of transfer passengers isα, so the total number of transfer passengers is ∑i=ab−1∑j=b+1cα⋅qij. When transfer passengers get on trains from section II, they can choose to take V1 trains or V2 trains, and the proportion of transfer passengers choosing V1 trains is fV1/fV1+fV2, and the proportion of transfer passengers choosing V2 trains is fV2/fV1+fV2. After arriving at station Sb, transfer passengers who choose V1 trains can transfer to the destination station of section III by V2 or V3 trains, so the total waiting time of this type of passengers can be expressed as 1/2fV1+ttransfer/60+1/2fV2+fV3. And after transfer, passengers who take V2 trains arriving at station Sb, if they transfer, can only choose V3 trains to section III, so the total waiting time of this kind of passengers can be expressed as 1/2fV2+ttransfer/60+1/2fV3. To sum up, the expression of T23 can be obtained.(4)T11=∑i=1a−1∑j=i+1aqij⋅12fV1,(5)T12=∑i=1a−1∑j=a+1bqij⋅α⋅12fV1+ttransfer60+12fV2+1−α⋅12fV1,(6)T13=∑i=1a−1∑j=b+1cqij⋅fV2fV2+fV3⋅12fV1+ttransfer60+12fV2+fV3fV2+fV3⋅12fV1+ttransfer60+12fV3,(7)T14=∑i=1a−1∑j=c+1Nqij⋅12fV1+ttransfer60+12fV3,(8)T22=∑i=ab−1∑j=i+1bqij⋅12fV1+fV2,(9)T23=∑i=ab−1∑j=b+1cqij⋅1−α⋅12fV2+α⋅fV2fV1+fV2⋅12fV2+ttransfer60+12fV3+α⋅fV1fV1+fV2⋅12fV1+ttransfer60+12fV2+fV3,(10)T24=∑i=ab−1∑j=c+1Nqij⋅fV1fV1+fV2⋅12fV1+ttransfer60+12fV3+fV2fV1+fV2⋅12fV2+ttransfer60+12fV3,(11)T33=∑i=bc−1∑j=i+1cqij⋅12fV2+fV3,(12)T34=∑i=bc−1∑j=c+1Nqij⋅α⋅12fV2+ttransfer60+12fV3+1−α⋅12fV3,(13)T44=∑i=cN−1∑j=i+1Nqij⋅12fV3.


## 2.4.1. Enterprise-Oriented Objective

From the perspective of the enterprises, the operating cost is an important indicator that can be evaluated quantitatively. The operating cost of enterprises includes the cost of train running and the extra cost caused by cross-line trains. For the enterprises, the lower operating cost, the better.(1)minW′=Wrun+Wcross,Wrun=costrunV1⋅fV1⋅mV1⋅d1b+costrunV2⋅fV2⋅mV2⋅dac+costrunV3⋅fV3⋅mV3⋅dbN,Wcross=fV2⋅costcrossV2⋅c−a+1.


## 2.4.2. Passenger-Oriented Objective

For passengers, travel time is the most closely related quantitative indicator to train service plan. In order to facilitate the subsequent merging of the two objective functions, passengers’ nonworking time value coefficient is used here to convert passengers travel time into the cost. Cost converted from passengers travel time can be expressed by total travel time and passengers’ nonworking time value coefficient.(2)minW″=costtime⋅T.As shown in Figure3, there are 10 types of passenger flows in the upward directions: 11, 12, 13, 14, 22, 23, 24, 33, 34, and 44. Therefore, the total travel time can also be expressed as the sum of all kinds of passengers travel time.(3)T=∑x=14∑y=x4Txy.The total travel time of passengers includes waiting time, travel time on the train, and the transferring time from one train to another. There is hardly any correlation between one-way travel time and train service plan, so we only consider waiting time and transfer time. The previous researchers believe that the average passenger waiting time is approximately half of the departure interval if the departure interval is very short [24, 27, 28]. Therefore, the travel time of various sections can be expressed as equations (6)–(15).Taking the most complex formula (9) as an example to explain T23. Similarly, the travel time expression Txy of other types of passenger flows can be obtained. α represents the proportion of transfer passengers, and the proportion of nontransfer passengers is 1−α, so the total number of nontransfer passengers is ∑i=ab−1∑j=b+1c1−α⋅qij. From section II to section III, passenger flows without transfers can only take V2 trains. Therefore, according to the above principles in [24, 27, 28], the waiting time of this kind of passenger flow is 1/2fV2.The proportion of transfer passengers isα, so the total number of transfer passengers is ∑i=ab−1∑j=b+1cα⋅qij. When transfer passengers get on trains from section II, they can choose to take V1 trains or V2 trains, and the proportion of transfer passengers choosing V1 trains is fV1/fV1+fV2, and the proportion of transfer passengers choosing V2 trains is fV2/fV1+fV2. After arriving at station Sb, transfer passengers who choose V1 trains can transfer to the destination station of section III by V2 or V3 trains, so the total waiting time of this type of passengers can be expressed as 1/2fV1+ttransfer/60+1/2fV2+fV3. And after transfer, passengers who take V2 trains arriving at station Sb, if they transfer, can only choose V3 trains to section III, so the total waiting time of this kind of passengers can be expressed as 1/2fV2+ttransfer/60+1/2fV3. To sum up, the expression of T23 can be obtained.(4)T11=∑i=1a−1∑j=i+1aqij⋅12fV1,(5)T12=∑i=1a−1∑j=a+1bqij⋅α⋅12fV1+ttransfer60+12fV2+1−α⋅12fV1,(6)T13=∑i=1a−1∑j=b+1cqij⋅fV2fV2+fV3⋅12fV1+ttransfer60+12fV2+fV3fV2+fV3⋅12fV1+ttransfer60+12fV3,(7)T14=∑i=1a−1∑j=c+1Nqij⋅12fV1+ttransfer60+12fV3,(8)T22=∑i=ab−1∑j=i+1bqij⋅12fV1+fV2,(9)T23=∑i=ab−1∑j=b+1cqij⋅1−α⋅12fV2+α⋅fV2fV1+fV2⋅12fV2+ttransfer60+12fV3+α⋅fV1fV1+fV2⋅12fV1+ttransfer60+12fV2+fV3,(10)T24=∑i=ab−1∑j=c+1Nqij⋅fV1fV1+fV2⋅12fV1+ttransfer60+12fV3+fV2fV1+fV2⋅12fV2+ttransfer60+12fV3,(11)T33=∑i=bc−1∑j=i+1cqij⋅12fV2+fV3,(12)T34=∑i=bc−1∑j=c+1Nqij⋅α⋅12fV2+ttransfer60+12fV3+1−α⋅12fV3,(13)T44=∑i=cN−1∑j=i+1Nqij⋅12fV3.


## 2.5. Constraints of Train Service Plan Design Model

There are numerous constraints to assure that passengers must be transported to their destinations and the capacity cannot be exceeded. The detail of the constraints is listed as follows.


### 2.5.1. Constraint of Passenger Flow

Transporting all the passengers to their destination is the primary condition. Passengers must be transported withV1, V2, and V3 trains. Use qeπV1 as an example to explain the constraint. V1 trains depart from station S1 and return from station Sb. V1 trains pass through sect ions I and II, so only passengers in these two sections need to be considered when calculate qeπV1.We can see that from Figure1, in section I, passengers can only take V1 trains. eπ can be any section in section I, passengers taking V1 trains in section eπ can be divided into four types according to Figure 4, that is, 11, 12, 13 and 14. All the departure stations of passengers should be located at section S1,Sπ, terminal station be located at section Sπ+1,SN. In Figure 4, eπ is any section within section I, and the green dotted line in the figure indicates the travel path of passengers. The total number of passengers to be transported in section eπ is ∑1≤i≤π∑π<j≤Nqij.Figure 4
Travel path of passengers takingV1 trains in section eπ,eπ∈I.Similarly, as shown in Figure5, for any eπ belongs to section II, passengers taking V1 trains in section eπ can be divided into six types, namely, 12, 13, 14, 22, 23, and 24. Moreover, all the departure stations of passengers should be located at section S1,Sπ and terminal station be located at section Sπ+1,SN.Figure 5
Travel path of passengers takingV1 trains in section eπ,eπ∈II.If type 12 passenger flows takingV1 trains in section II, it means that these passengers have no transfer behavior at station Sa, so there are ∑1≤i<a∑π<j≤b1−α⋅qij passengers in total.As shown in Figure6, type 13 passenger flows can choose to take V1 trains to station Sa and then transfer to V2 trains, or they can choose to take V1 trains to station Sb and then transfer to V2 or V3 trains. The proportion of the first case (the green dotted line at the top of Figure 6) is 1/2⋅fV2/fV2+fV3, the proportion of the second case (the green dotted line in the middle of Figure 6) is 1/2⋅fV2/fV2+fV3, and the proportion of the third case (the green dotted line at the bottom of Figure 6) is fV3/fV2+fV3. In the second and third cases, passengers will take V1 trains in section II. Therefore, this part of passenger flows can be expressed as ∑1≤i<a∑b<j≤cfV3/fV2+fV3+1/2⋅fV2/fV2+fV3⋅qij.Figure 6
Travel scheme of type 13 passenger flows.For type 14 passenger flows, since passengers can only transfer once at most under the assumption, take classV1 trains to station Sb, and then transfer to V3 trains to the destination station in section IV. Therefore, the total passengers of this kind are ∑1≤i<a∑c<j≤Nqij.Type 22 passenger flows can only takeV1 or V2 trains in section II. Therefore, when eπ belongs to section II, the number of type 22 passenger flows taking V1 trains in section eπ can be expressed as ∑a≤i≤π∑π<j≤bfV1/fV1+fV2⋅qij.Among type 23 passenger flows, the proportion of nontransfer passengers is1−α. This part of passengers arriving at the destination by V2 trains, and the proportion of passengers who opt to transfer is α. There are three possible transfer modes. The travel scheme of type 23 passenger flows is shown in Figure 7. Therefore, any eπ belongs to section II, the number of type 23 passengers taking V1 trains in section eπ is ∑a≤i≤π∑b<j≤cα⋅fV1/fV1+fV2⋅qij.Figure 7
Travel scheme of type 23 passenger flows.There are three possible travel schemes for type 24 passenger flows, as shown in Figure8. For any eπ belongs to section II, the number of type 24 passengers taking V1 trains in section eπ can be expressed as ∑a≤i≤π∑c<j≤NfV1/fV1+fV2⋅qij.Figure 8
Travel scheme of type 24 passenger flows.In summary, the expression ofqeπV1 is shown in equation (14). The qeπV1 should not exceed the capacity limit of V1 trains, that is, qeπV1≤fV1⋅CapV1⋅ξV1,eπ∈Ι,ΙΙ. Similarly, train capacity constraints of V2 and V3 trains are as follows:(14)qeπV1=∑1≤i≤π∑π<j≤Nqijeπ∈Ι∑1≤i<a∑π<j≤b1−α⋅qij+∑1≤i<a∑b<j≤cfV3fV2+fV3+12⋅fV2fV2+fV3⋅qij+∑1≤i<a∑c<j≤Nqij+∑a≤i≤π∑π<j≤bfV1fV1+fV2⋅qij+∑a≤i≤π∑b<j≤cα⋅fV1fV1+fV2⋅qij+∑a≤i≤π∑c<j≤NfV1fV1+fV2⋅qijeπ∈ΙΙ,(15)qeπV1≤fV1⋅CapV1⋅ξV1,eπ∈Ι,ΙΙ,qeπV2=∑1≤i<a∑π<j≤bα⋅qij+∑1≤i<a∑b<j≤c12⋅fV2fV2+fV3⋅qij+∑a≤i≤π∑π<j≤bfV2fV1+fV2⋅qij+∑a≤i≤π∑b<j≤cα⋅fV2fV1+fV2⋅qij+1−α⋅qij+∑a≤i≤π∑c<j≤NfV2fV1+fV2⋅qijeπ∈ΙΙ∑1≤i<a∑π<j≤cfV2fV2+fV3⋅qij+∑a≤i<b∑π<j≤c1−α⋅qij+α⋅fV1fV1+fV2⋅fV2fV2+fV3⋅qij+∑a≤i<b∑c<j≤N12⋅fV2fV1+fV2⋅qij+∑b≤i≤π∑π<j≤cfV2fV2+fV3⋅qij+∑b≤i≤π∑c<j≤Nα⋅qijeπ∈ΙΙΙ,qeπV2≤fV2⋅CapV2⋅ξV2,eπ∈Ι,ΙΙΙ,qeπV3=∑1≤i<a∑π<j≤cfV3fV2+fV3⋅qij+∑1≤i<a∑c<j≤Nqij+∑a≤i<b∑π<j≤cα⋅qij⋅fV2fV1+fV2+fV1fV1+fV2⋅fV3fV2+fV3+∑a≤i<b∑c<j≤NfV1fV1+fV2+12⋅fV2fV1+fV2⋅qij+∑b≤i≤π∑π<j≤cfV3fV2+fV3⋅qij+∑b≤i≤π∑c<j≤N1−α⋅qijeπ∈ΙΙΙ∑1≤i≤π∑π<j≤Nqijeπ∈ΙV,qeπV3≤fV3⋅CapV3⋅ξV3,eπ∈ΙΙΙ,ΙV.


### 2.5.2. Constraint of Vehicles Number

The number of vehicles used during the study period (one hour) cannot exceed the total available vehicles.(16)fV1⋅mV1≤MV1,fV2⋅mV2≤MV2,fV3⋅mV3≤MV3.


### 2.5.3. Constraint of Line Carrying Capacity

The carrying capacity of each line cannot be exceeded according to the train service plan.(17)fV1+fV2≤fmaxL1,fV2+fV3≤fmaxL3.


### 2.5.4. Constraint of Departure Frequency

In order to ensure the service quality, the departure frequency of original trains (trains running on their own lines) shall not be lower than the minimal departure frequency.(18)fV1≥fminL1,dep,fV3≥fminL3,dep.


### 2.5.5. Constraint of the Station Capacity

The carrying capacity of each station cannot be exceeded.(19)fV1≤fSi,i∈1,⋯,a−1,fV1+fV2≤fSi,i∈a,⋯,b−1,fV2+fV3≤fSi,i∈b,⋯,c−1,fV3≤fSi,i∈c,⋯,N.


### 2.5.6. Constraint of Capacity Matching Degree

Take the upward direction as an example; if the capacity of the suburban line and urban rail transit line is highly matched, the transportation capacity provided by urban rail transit should meet the travel needs of suburban passenger flows.(20)fV1⋅CapV1⋅ξV1⋅λ≤δ⋅60t0⋅CapV0⋅ξV0⋅ρ.


### 2.5.7. Constraint of Origination and Destination Setting

The origination and destination of cross-lineL2 should be set at the intermediate stations with turn-back capability in L1 line and L3 line.(21)2≤a≤b−1,b+1≤c≤N−1.


### 2.5.8. Constraint of Variable Assignment

The value of train service frequency belongs to natural number setN.(22)fVu∈N∀u∈1,2,3.


## 2.5.1. Constraint of Passenger Flow

Transporting all the passengers to their destination is the primary condition. Passengers must be transported withV1, V2, and V3 trains. Use qeπV1 as an example to explain the constraint. V1 trains depart from station S1 and return from station Sb. V1 trains pass through sect ions I and II, so only passengers in these two sections need to be considered when calculate qeπV1.We can see that from Figure1, in section I, passengers can only take V1 trains. eπ can be any section in section I, passengers taking V1 trains in section eπ can be divided into four types according to Figure 4, that is, 11, 12, 13 and 14. All the departure stations of passengers should be located at section S1,Sπ, terminal station be located at section Sπ+1,SN. In Figure 4, eπ is any section within section I, and the green dotted line in the figure indicates the travel path of passengers. The total number of passengers to be transported in section eπ is ∑1≤i≤π∑π<j≤Nqij.Figure 4
Travel path of passengers takingV1 trains in section eπ,eπ∈I.Similarly, as shown in Figure5, for any eπ belongs to section II, passengers taking V1 trains in section eπ can be divided into six types, namely, 12, 13, 14, 22, 23, and 24. Moreover, all the departure stations of passengers should be located at section S1,Sπ and terminal station be located at section Sπ+1,SN.Figure 5
Travel path of passengers takingV1 trains in section eπ,eπ∈II.If type 12 passenger flows takingV1 trains in section II, it means that these passengers have no transfer behavior at station Sa, so there are ∑1≤i<a∑π<j≤b1−α⋅qij passengers in total.As shown in Figure6, type 13 passenger flows can choose to take V1 trains to station Sa and then transfer to V2 trains, or they can choose to take V1 trains to station Sb and then transfer to V2 or V3 trains. The proportion of the first case (the green dotted line at the top of Figure 6) is 1/2⋅fV2/fV2+fV3, the proportion of the second case (the green dotted line in the middle of Figure 6) is 1/2⋅fV2/fV2+fV3, and the proportion of the third case (the green dotted line at the bottom of Figure 6) is fV3/fV2+fV3. In the second and third cases, passengers will take V1 trains in section II. Therefore, this part of passenger flows can be expressed as ∑1≤i<a∑b<j≤cfV3/fV2+fV3+1/2⋅fV2/fV2+fV3⋅qij.Figure 6
Travel scheme of type 13 passenger flows.For type 14 passenger flows, since passengers can only transfer once at most under the assumption, take classV1 trains to station Sb, and then transfer to V3 trains to the destination station in section IV. Therefore, the total passengers of this kind are ∑1≤i<a∑c<j≤Nqij.Type 22 passenger flows can only takeV1 or V2 trains in section II. Therefore, when eπ belongs to section II, the number of type 22 passenger flows taking V1 trains in section eπ can be expressed as ∑a≤i≤π∑π<j≤bfV1/fV1+fV2⋅qij.Among type 23 passenger flows, the proportion of nontransfer passengers is1−α. This part of passengers arriving at the destination by V2 trains, and the proportion of passengers who opt to transfer is α. There are three possible transfer modes. The travel scheme of type 23 passenger flows is shown in Figure 7. Therefore, any eπ belongs to section II, the number of type 23 passengers taking V1 trains in section eπ is ∑a≤i≤π∑b<j≤cα⋅fV1/fV1+fV2⋅qij.Figure 7
Travel scheme of type 23 passenger flows.There are three possible travel schemes for type 24 passenger flows, as shown in Figure8. For any eπ belongs to section II, the number of type 24 passengers taking V1 trains in section eπ can be expressed as ∑a≤i≤π∑c<j≤NfV1/fV1+fV2⋅qij.Figure 8
Travel scheme of type 24 passenger flows.In summary, the expression ofqeπV1 is shown in equation (14). The qeπV1 should not exceed the capacity limit of V1 trains, that is, qeπV1≤fV1⋅CapV1⋅ξV1,eπ∈Ι,ΙΙ. Similarly, train capacity constraints of V2 and V3 trains are as follows:(14)qeπV1=∑1≤i≤π∑π<j≤Nqijeπ∈Ι∑1≤i<a∑π<j≤b1−α⋅qij+∑1≤i<a∑b<j≤cfV3fV2+fV3+12⋅fV2fV2+fV3⋅qij+∑1≤i<a∑c<j≤Nqij+∑a≤i≤π∑π<j≤bfV1fV1+fV2⋅qij+∑a≤i≤π∑b<j≤cα⋅fV1fV1+fV2⋅qij+∑a≤i≤π∑c<j≤NfV1fV1+fV2⋅qijeπ∈ΙΙ,(15)qeπV1≤fV1⋅CapV1⋅ξV1,eπ∈Ι,ΙΙ,qeπV2=∑1≤i<a∑π<j≤bα⋅qij+∑1≤i<a∑b<j≤c12⋅fV2fV2+fV3⋅qij+∑a≤i≤π∑π<j≤bfV2fV1+fV2⋅qij+∑a≤i≤π∑b<j≤cα⋅fV2fV1+fV2⋅qij+1−α⋅qij+∑a≤i≤π∑c<j≤NfV2fV1+fV2⋅qijeπ∈ΙΙ∑1≤i<a∑π<j≤cfV2fV2+fV3⋅qij+∑a≤i<b∑π<j≤c1−α⋅qij+α⋅fV1fV1+fV2⋅fV2fV2+fV3⋅qij+∑a≤i<b∑c<j≤N12⋅fV2fV1+fV2⋅qij+∑b≤i≤π∑π<j≤cfV2fV2+fV3⋅qij+∑b≤i≤π∑c<j≤Nα⋅qijeπ∈ΙΙΙ,qeπV2≤fV2⋅CapV2⋅ξV2,eπ∈Ι,ΙΙΙ,qeπV3=∑1≤i<a∑π<j≤cfV3fV2+fV3⋅qij+∑1≤i<a∑c<j≤Nqij+∑a≤i<b∑π<j≤cα⋅qij⋅fV2fV1+fV2+fV1fV1+fV2⋅fV3fV2+fV3+∑a≤i<b∑c<j≤NfV1fV1+fV2+12⋅fV2fV1+fV2⋅qij+∑b≤i≤π∑π<j≤cfV3fV2+fV3⋅qij+∑b≤i≤π∑c<j≤N1−α⋅qijeπ∈ΙΙΙ∑1≤i≤π∑π<j≤Nqijeπ∈ΙV,qeπV3≤fV3⋅CapV3⋅ξV3,eπ∈ΙΙΙ,ΙV.


## 2.5.2. Constraint of Vehicles Number

The number of vehicles used during the study period (one hour) cannot exceed the total available vehicles.(16)fV1⋅mV1≤MV1,fV2⋅mV2≤MV2,fV3⋅mV3≤MV3.


## 2.5.3. Constraint of Line Carrying Capacity

The carrying capacity of each line cannot be exceeded according to the train service plan.(17)fV1+fV2≤fmaxL1,fV2+fV3≤fmaxL3.


## 2.5.4. Constraint of Departure Frequency

In order to ensure the service quality, the departure frequency of original trains (trains running on their own lines) shall not be lower than the minimal departure frequency.(18)fV1≥fminL1,dep,fV3≥fminL3,dep.


## 2.5.5. Constraint of the Station Capacity

The carrying capacity of each station cannot be exceeded.(19)fV1≤fSi,i∈1,⋯,a−1,fV1+fV2≤fSi,i∈a,⋯,b−1,fV2+fV3≤fSi,i∈b,⋯,c−1,fV3≤fSi,i∈c,⋯,N.


## 2.5.6. Constraint of Capacity Matching Degree

Take the upward direction as an example; if the capacity of the suburban line and urban rail transit line is highly matched, the transportation capacity provided by urban rail transit should meet the travel needs of suburban passenger flows.(20)fV1⋅CapV1⋅ξV1⋅λ≤δ⋅60t0⋅CapV0⋅ξV0⋅ρ.


## 2.5.7. Constraint of Origination and Destination Setting

The origination and destination of cross-lineL2 should be set at the intermediate stations with turn-back capability in L1 line and L3 line.(21)2≤a≤b−1,b+1≤c≤N−1.


## 2.5.8. Constraint of Variable Assignment

The value of train service frequency belongs to natural number setN.(22)fVu∈N∀u∈1,2,3.


## 2.6. Transformation of Objective Functions

Considering the complexity and difficulty of solving a multiobjective model, we combine the two objectives and describe it with a single formula. The linear weighted sum method is used to transform the multiobjective optimization model into a single-objective one.Φ is the weight coefficient between 0,1. In order to unify the magnitude of two objective functions, the minimum values of objective function one (W∗′) and objective function two (W∗″) are calculated in advance. Then, the ratio of W′ and W∗″ is used as the conversion coefficient. W is the general objective function after transformation.(23)minW=Φ⋅W′+1−Φ⋅W∗′W∗″⋅W″.


## 3. Algorithm Design for Solving Train Service Plan

The train service plan design problem is proved to be NP-hard even for a single rail line or a small-scale rail network [21–23]. Since the above model is nonlinear, it is difficult to find the solution with existing software and hard to get a satisfactory feasible solution. In order to obtain a better solution in a short time, we intend to use the heuristic algorithm to find the solution.Harmonic search algorithm (HSA) is a new heuristic algorithm, which has a completely different search mechanism compared to the classic population-based algorithms. It was proposed by Geem et al. [25], inspired by the music creation process. In the process, the players, relying on their own memories, repeatedly adjust the tone of the instruments, ultimately reaching a wonderful harmony state. The algorithm has the advantages of being easy to understand, few parameters, and strong global search ability and has been successfully applied in combinatorial optimization problems. Therefore, HSA is selected to solve the train service plan design problem in this paper. The fitness function used in the algorithm is shown as follows:(24)minGf=Wf+σ⋅Pf2,where Wf is the optimization objective, σ is a penalty factor, which should take a large number in the process of calculation, for example: 1000. Pf is a penalty term for violating the constraints.


### 3.1. Basic Principles of Classical Harmony Search Algorithm

In classical harmony search algorithm (CHSA), decision variables are similar to the role of all kinds of instruments in a piece of music. The harmony can be regarded as the solution vector of the problem to be solved. A piece of music needs harmony to reach the aesthetic standard. Analogously, a set of solutions is required to satisfy the requirement of the objective function. The evaluation of harmony depends on the function value of the objective function. Rehearsal for the music is equivalent to the iteration process in CHSA.The algorithm works as follows. The algorithm first generates harmony memory size (HMS) solutions and put them into harmony memory (HM), which can be analogous to the initial memory of musicians, as the initial solution. After that, parameters rand1 and rand2 are randomly generated between 0 and 1, and the harmony memory considering rate (PHMCR) and pitch adjusting rate (PPAR) is introduced. If rand1<PHMCR, then we can search for a new optimal solution in the existing harmony memory (HM). Otherwise, search for a new solution outside the harmony memory (HM). At the same time, rand2 and PPAR are compared, if rand2<PPAR, the new harmony taken from HM is pitch adjusted by using the bandwidth (BandW) with PPAR. If the new harmony is better than the worst harmony in HM, then include the new harmony in HM and exclude the worst harmony from HM. Otherwise, no replacement operation will be performed. Repeat the above steps until the iteration reaches the maximum rehearsal number (Imax) or other stopping criteria.


### 3.2. Construction of Initial Solution

The initial solution is constructed according to the train service plan design model. We generateHMS kinds of train service frequency randomly, which satisfy all the constraints and take the intermediate station with largest change in passenger flows on L1 line and L3 line as the origination and destination of the cross-line; then we calculate out the corresponding objective function value and put all of them into HM.HM can be expressed as the following formula, where Hii=1,2,⋯,HMS represents a group of harmony.(25)HM=H1W1H2W2⋮⋮HHMSWHMS=a1c1fV11fV21fV31W1a2c2fV12fV22fV32W2⋮⋮⋮⋮⋮⋮aHMScHMSfV1HMSfV2HMSfV3HMSWHMS.


### 3.3. Harmony Adjustment Strategies and Algorithm Improvement

The neighborhood search strategy and parameters in the classical harmony search algorithm (CHSA) are fixed, but a large number of irregular adjustments can easily lead to situations where the solving process is not efficient and even difficult to converge [26]. Hence, we design the improved harmonic search algorithm (IHSA) to solve the problem. The improvements are designed according to the characteristic of our train service plans design model, such as variable rounding and in-advance termination strategy. Improvement strategies are as follows.When a group of harmony inHM is selected with the probability PHMCR for adjustment, the method of pitch adjusting in CHSA is adopted, for example, the element Hji in i-th row and j-th column is randomly selected for adjustment, and the new harmony vector Hjnew generated after adjustment is: Hjnew=⌈Hji±rand0,1×BandW⌉, where ⌈⌉ represents rounding up function.When we select a group of harmony outsideHM for adjustment, the adjustment strategy is designed as follows: new harmony should learn from the current optimal harmony so as to effectively find a better solution. For example, the adjustment strategy of the i-th row and j-th column components Hji is: Hjnew=⌈Hji+1−PHMCR×Hjbest−Hji⌉, where Hjbest is the current optimal harmony, Hjnew is the new harmony after adjustment.To avoid a large number of undirected searching, we preset the number of rehearsals:Ipause1 and Ipause2, Ipause1<Ipause2<Imax. When the number of rehearsals has not reached Ipause1, the service frequency of various trains and the origination and destination of cross-line should be adjusted according to the above harmony adjustment strategy. When the cumulative number of rehearsals reaches Ipause1, a and c shall not be adjusted any more, but only the service frequency will be adjusted. When the cumulative number of rehearsals reaches Ipause2, fV2 is no longer adjusted, only fV1 and fV3 will be adjusted. In order to improve the efficiency of the algorithm, when comparing the new harmony with the harmonies in HM, the best harmony would be replaced rather than the worst one.


### 3.4. Solution Procedures of IHSA

Solution steps of the improved harmonic search algorithm (IHSA) are as follows, and the algorithm flow chart is shown in Figure9.Step 1: Initialize parameters of the proposed train service plan design model and IHSA.Step 2: ConstructHM according to the method described in Section 2.2, and select the current optimal solution.Step 3: Using the rand function to generate two random numbers rand1 and rand2 on the interval [0, 1]. If rand1<PHMCR, select a group of harmony in HM to be adjusted. If rand1≥PHMCR, the new harmony is designed according to the harmony adjustment strategy outside HM. For the random number rand2, if rand2<PPAR, the harmony is adjusted according to the harmony adjustment strategy in HM, otherwise no adjustment is made.Step 4: Calculate objective function valueWnew. If Wnew<Wbest=minW1,W2,⋯,WHMS, then replace Hbest in HM with Hnew, and update the global optimal solution. Otherwise, no adjustment is made.Step 5: Repeat Step 1–Step 4, when the number of iterations reachesIpause1, a and c shall not be adjusted any more. When the number of iterations reaches Ipause2, fV2 shall not be adjusted any more. When the number of iterations reaches Imax, end the cycle and output the optimal solution.Figure 9
Flow chart of IHSA.


## 3.1. Basic Principles of Classical Harmony Search Algorithm

In classical harmony search algorithm (CHSA), decision variables are similar to the role of all kinds of instruments in a piece of music. The harmony can be regarded as the solution vector of the problem to be solved. A piece of music needs harmony to reach the aesthetic standard. Analogously, a set of solutions is required to satisfy the requirement of the objective function. The evaluation of harmony depends on the function value of the objective function. Rehearsal for the music is equivalent to the iteration process in CHSA.The algorithm works as follows. The algorithm first generates harmony memory size (HMS) solutions and put them into harmony memory (HM), which can be analogous to the initial memory of musicians, as the initial solution. After that, parameters rand1 and rand2 are randomly generated between 0 and 1, and the harmony memory considering rate (PHMCR) and pitch adjusting rate (PPAR) is introduced. If rand1<PHMCR, then we can search for a new optimal solution in the existing harmony memory (HM). Otherwise, search for a new solution outside the harmony memory (HM). At the same time, rand2 and PPAR are compared, if rand2<PPAR, the new harmony taken from HM is pitch adjusted by using the bandwidth (BandW) with PPAR. If the new harmony is better than the worst harmony in HM, then include the new harmony in HM and exclude the worst harmony from HM. Otherwise, no replacement operation will be performed. Repeat the above steps until the iteration reaches the maximum rehearsal number (Imax) or other stopping criteria.


## 3.2. Construction of Initial Solution

The initial solution is constructed according to the train service plan design model. We generateHMS kinds of train service frequency randomly, which satisfy all the constraints and take the intermediate station with largest change in passenger flows on L1 line and L3 line as the origination and destination of the cross-line; then we calculate out the corresponding objective function value and put all of them into HM.HM can be expressed as the following formula, where Hii=1,2,⋯,HMS represents a group of harmony.(25)HM=H1W1H2W2⋮⋮HHMSWHMS=a1c1fV11fV21fV31W1a2c2fV12fV22fV32W2⋮⋮⋮⋮⋮⋮aHMScHMSfV1HMSfV2HMSfV3HMSWHMS.


## 3.3. Harmony Adjustment Strategies and Algorithm Improvement

The neighborhood search strategy and parameters in the classical harmony search algorithm (CHSA) are fixed, but a large number of irregular adjustments can easily lead to situations where the solving process is not efficient and even difficult to converge [26]. Hence, we design the improved harmonic search algorithm (IHSA) to solve the problem. The improvements are designed according to the characteristic of our train service plans design model, such as variable rounding and in-advance termination strategy. Improvement strategies are as follows.When a group of harmony inHM is selected with the probability PHMCR for adjustment, the method of pitch adjusting in CHSA is adopted, for example, the element Hji in i-th row and j-th column is randomly selected for adjustment, and the new harmony vector Hjnew generated after adjustment is: Hjnew=⌈Hji±rand0,1×BandW⌉, where ⌈⌉ represents rounding up function.When we select a group of harmony outsideHM for adjustment, the adjustment strategy is designed as follows: new harmony should learn from the current optimal harmony so as to effectively find a better solution. For example, the adjustment strategy of the i-th row and j-th column components Hji is: Hjnew=⌈Hji+1−PHMCR×Hjbest−Hji⌉, where Hjbest is the current optimal harmony, Hjnew is the new harmony after adjustment.To avoid a large number of undirected searching, we preset the number of rehearsals:Ipause1 and Ipause2, Ipause1<Ipause2<Imax. When the number of rehearsals has not reached Ipause1, the service frequency of various trains and the origination and destination of cross-line should be adjusted according to the above harmony adjustment strategy. When the cumulative number of rehearsals reaches Ipause1, a and c shall not be adjusted any more, but only the service frequency will be adjusted. When the cumulative number of rehearsals reaches Ipause2, fV2 is no longer adjusted, only fV1 and fV3 will be adjusted. In order to improve the efficiency of the algorithm, when comparing the new harmony with the harmonies in HM, the best harmony would be replaced rather than the worst one.


## 3.4. Solution Procedures of IHSA

Solution steps of the improved harmonic search algorithm (IHSA) are as follows, and the algorithm flow chart is shown in Figure9.Step 1: Initialize parameters of the proposed train service plan design model and IHSA.Step 2: ConstructHM according to the method described in Section 2.2, and select the current optimal solution.Step 3: Using the rand function to generate two random numbers rand1 and rand2 on the interval [0, 1]. If rand1<PHMCR, select a group of harmony in HM to be adjusted. If rand1≥PHMCR, the new harmony is designed according to the harmony adjustment strategy outside HM. For the random number rand2, if rand2<PPAR, the harmony is adjusted according to the harmony adjustment strategy in HM, otherwise no adjustment is made.Step 4: Calculate objective function valueWnew. If Wnew<Wbest=minW1,W2,⋯,WHMS, then replace Hbest in HM with Hnew, and update the global optimal solution. Otherwise, no adjustment is made.Step 5: Repeat Step 1–Step 4, when the number of iterations reachesIpause1, a and c shall not be adjusted any more. When the number of iterations reaches Ipause2, fV2 shall not be adjusted any more. When the number of iterations reaches Imax, end the cycle and output the optimal solution.Figure 9
Flow chart of IHSA.


## 4. Computing Case and Results Analysis

In this section, the effectiveness and feasibility of the proposed model and algorithm will be proved by several experiments. The proposed method is implemented in C# and runs on an Intel (R) Core (TM) i7 -7500U CPU at 2.90 GHz and 16.0 GB computer. And the data is mainly from a real case of the intercity line under construction in a metropolitan area of China.


### 4.1. Basic Data Settings of the Case

There are interconnected suburban rail lineL1, cross-line L2, and intercity line L3 as shown in Figure 10, in which the average distance between each station in L1 is 5 km, and the total length d1b is 55 km. The average distance between each station in L3 is 10 km, and the total length dbN is 140 km. dac=512−a+10c−12, the length of L2 is related to the setting of origination Sa and destination Sc.Figure 10
Line schematic in the computing case.Some of the parameters are empirical data, and others are mainly based on the actual situation, travel experience, or referring to the data in master’s and doctoral thesis [29, 30]. For more information about the values of the model-related parameters, see Table 3.Table 3
Parameter values of the model.
ParameterValueMeasurement unitcostrunV145Yuan (vehicle·km)costrunV260Yuan (vehicle·km)costrunV375Yuan (vehicle·km)costcrossV211Yuan (train·station)mV1, mV2, mV38VehicleCapV01860PersonCapV1, CapV2, CapV3668,610,557PersonξV090%—ξV1, ξV2, ξV375%—costtime25Yuan (h)α25%—MV1, MV2, MV3120,150,160Vehiclettransfer15minfmaxL1, fmaxL330Train (h)fminL1,dep4Train (h)fminL3,dep6Train (h)fSi30Train (h)λ60%—δ2—t04minρ40%—Passenger ODs (origination and destination) are shown in the Table4. For the parameters mentioned in the algorithm: HMS=100, PHMCR=0.3, PPAR=0.5, BandW=2, Imax=500, Ipause1=100, Ipause2=300. Referring to the idea of weight assignment in [31], the objective functions are given multiple groups of weight to analyze the influence of weight setting on results.


### 4.2. The Influence of the Objective Functions Weight Setting on Results

In order to analyze the influence of objective functions weight setting on the results in detail, all possible weight values of two objective functions are enumerated (0.1 is the smallest unit). We can get the calculation results as shown in Table5.Table 4
The passenger OD matrix (upward direction) during the study period.
OD12345678910111213141516171819202122232425261—01143912103464394154511319212416191881312152——63618155243911951611912081191042432281541301642402251211271063———3911152420601167527327627418013285125176147971372151912174————031406253421291815131317218561058165—————62172636757254516253832643828124034406——————191145726456333527394648414841454438457———————722579710814014415114415197121131152151122104961178————————225525214815815318811314613510416688135126791029—————————94374474542969210510512584104851061089210——————————35118267197159116139135136215104947296869611———————————49271179275122240235160137205103971057711012————————————71051572028519215518919419911539558713—————————————5701610989669343128541814——————————————625412012552581451015———————————————1021068741531215516————————————————804530703910634817—————————————————67340417155418——————————————————2411191231341019———————————————————45266301820————————————————————311311221—————————————————————02400422——————————————————————2712223———————————————————————071724————————————————————————3525—————————————————————————526——————————————————————————Table 5
Influence analyses of weight setting on computing results.
ΦacfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanΔWyuan0.1623121812245876466698.142088572.4000.2723121811233136669176.912165098.0276525.620.3622121810220416673005.282229985.39141412.990.462212189212016675271.622234438.98145866.580.572212189207676876684.572215381.24126808.840.6721131611206724079750.012219581.83131009.430.7721121611204744081323.642182128.1793555.770.8721121611204744081323.642137232.1248659.720.9721121611204744081323.642092336.063763.66ΔW represents the difference between current objective value and the optimal objective value.Table5 shows that W″ gradually increases and W′ gradually decreases while Φ increases. When Φ increases to 0.7, the optimal solution and the values of the two objective functions are no longer changed. Due to the constraints, the value of each decision variable cannot be changed unlimitedly. It is worth mentioning that the operating cost of enterprises is not strictly positively correlated with the sum of three types of trains. W′ mainly depends on the sum of fVu⋅costrunVu⋅dij, as well as the number of stations, which V2 type trains pass. W″ mainly depends on the number of passenger flows and service frequency of various trains in each section. When the value of Φ changes from 0.5 to 0.6, although the train service frequency of V1 and V3 increases, train service frequency of V2 decreases from 18 trains/h to 16 trains/h. Passenger flows in the cross-line section is the largest, so the train service plan of V2 has a great influence on the value of W″. At the same time, the length of cross-line section reduces from 125 km to 115 km. As a result, W′ decreases from 2076768 yuan to 2067240 yuan, and W″ increases by 3065.44 yuan.The trend of the two objective function values changing withΦ is shown in Figure 11. When designing a train service plan, decision-makers can decide the best scheme according to different decision preferences.Figure 11
Graph of objective function values varying with weight coefficients.


### 4.3. The Influence of Cross-Line’s Origination and Destination Setting on Results

The weight of objective functions is set as a fixed value to analyze the influence of the cross-line’s origination and destination setting on results. In order to equalize the interests of both enterprises and passengers, takeΦ=0.5 as an example to analyze. From Table 6, we can see that the optimal solution and the objective value are quite different due to the different origination and destination of the cross line. For example, compared with the optimal solution, the service frequency of V1 decreases when a is five and c is 22. However, W′ increases by 47196 yuan because that both the length of cross-line section and the number of stations which V2 trains pass have increased. In addition, W″ increased by 344.61 yuan due to the decline of train service frequency.Table 6
Influence analyses of cross-line’s origination and destination setting on computing results.
acfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanΔWyuan72212189207676876684.572215381.240623121812245876466698.142253102.0037720.7652210189212396477029.182244268.5128887.27421111711220596679532.552323692.52108311.28ΔW represents the difference between current objective value and the optimal objective value.Therefore, a reasonable setting of the cross-line’s origination and destination can effectively save passengers waiting time, reduce the cost of enterprises, and help improve the service level.From the above analysis, it can be obtained that the optimal cross-line routing scheme diagram (whenΦ takes 0.5) is shown in Figure 12.Figure 12
Diagram of the optimal routing schemes.


### 4.4. Comparative Analyses of Different Operation Modes

In order to reflect the advantages of the model established in this paper, train service plans in the independent operation mode of the suburban rail line and intercity line is used for comparative analysis. We set the weight of objective functions as fixed values to analyze the influence of the operation mode on the results. In order to equalize the interests of both enterprises and passengers, takeΦ=0.5 for analysis.It can be seen from Table7 that the total train service frequency in the cross-line operation mode of urban railway and intercity railway is fV1+fV2+fV3=12+18+9=39train/h. In other words, 39 trains are operated per hour, and the number of vehicles used during one hour is 312. The minimum operating cost of enterprises is 2076768 yuan, the minimum cost converted from passengers travel time is 76684.57 yuan, and the total objective function value is 2215381.24 yuan. In the independent operation mode of the suburban railways and intercity railways, the total train service frequency is fV1+fV3=30+27=57train/h. There are 57 trains operated per hour, and the number of vehicles used during one hour is 456. The minimum operating cost of the enterprise is 2862000 yuan, the minimum cost converted from passengers travel time is 148558.33 yuan, and the total objective function value is 2942622.49 yuan.Table 7
Solution results of different models.
acfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanΔWyuan72212189207676876684.572215381.240——30—272862000148558.332942622.49727241.25ΔW represents the difference between current objective value and the optimal objective value.Compared with the independent operation mode of different rail transit systems, the number of trains running per hour is reduced by 18, the number of vehicles used is reduced by 144, and the operating cost of the enterprise is reduced by 785232 yuan in the cross-line operation mode. Since passengers do not need to transfer at the stationSb, the cost converted from travel time is reduced by 71873.76 yuan. Through calculation, W is reduced by 727241.25 yuan using cross-line operation mode.When cross-line operation mode is adopted, there will be through trains running from the suburban lineL1 to the intercity line L3, sharing transportation resources between the two lines and reducing the waste of transportation capacity. Moreover, the running section of the V2-type through trains covers the section with the largest passenger flow, which relieves the transportation pressure, reduces the transfer time of passengers, and improves transportation efficiency. Cross-line operation can solve the problems of unbalanced spatial distribution of passenger flow and insufficient sharing of transportation capacity from the operation organization level.


### 4.5. Comparative Analyses of Algorithms

The classical harmony search algorithm (CHSA) is used as the comparison algorithm, and it is implemented by C# programming on the same computer. Similarly, takingΦ=0.5 as an example, and three sets of parameters are used to compare the performance of two algorithms. The sets of parameters are given according to the scale of the case in this paper combined with the example experiments, and also referring to existing researches [25, 32].The first set of parameters:HMS=100, PHMCR=0.3, PPAR=0.5, BandW=2, Imax=500, Ipause1=100, Ipause2=300.The second set of parameters:HMS=70, PHMCR=0.5, PPAR=0.3, BandW=3, Imax=500, Ipause1=200, Ipause2=400.The third set of parameters:HMS=50, PHMCR=0.9, PPAR=0.5, BandW=1, Imax=500, Ipause1=150, Ipause2=200.It can be seen from Tables8–10 that no matter which set of parameters is used, the problem-solving efficiency and computing quality of IHSA are always higher than those of CHSA. IHSA always get a low total cost by fewer iterations. Taking the value of the first set of parameters as an example, MATLAB is used to draw the algorithm iterative process diagram, as shown in Figure 13. We can learn from Figure 13 that the IHSA designed in this paper has better performance, so the algorithm improvement strategy is effective.Table 8
Comparative analysis of IHSA and CHSA (the first set of parameters).
AlgorithmIteration timesacfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanIHSA25072212189207676876684.572215381.24CHSA39062211189210036676821.302229278.85Table 9
Comparative analysis of IHSA and CHSA (the second set of parameters).
AlgorithmIteration timesacfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanIHSA27542212189220696272742.232219969.06CHSA410722131711220439273951.252237240.73Table 10
Comparative analysis of IHSA and CHSA (the third set of parameters).
AlgorithmIteration timesacfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanIHSA230723121811233136667176.912196751.40CHSA375622111810218436673560.062221223.52Figure 13
Iterative process diagram.However, the above analysis is based on solving the train service plan design model constructed in this paper. The performance of the algorithm is affected by the setting of parameters and whether the algorithm is suitable for problems to be solved. With this study, it cannot demonstrate that the improved harmony search algorithm always shows good performance in any scenario.


## 4.1. Basic Data Settings of the Case

There are interconnected suburban rail lineL1, cross-line L2, and intercity line L3 as shown in Figure 10, in which the average distance between each station in L1 is 5 km, and the total length d1b is 55 km. The average distance between each station in L3 is 10 km, and the total length dbN is 140 km. dac=512−a+10c−12, the length of L2 is related to the setting of origination Sa and destination Sc.Figure 10
Line schematic in the computing case.Some of the parameters are empirical data, and others are mainly based on the actual situation, travel experience, or referring to the data in master’s and doctoral thesis [29, 30]. For more information about the values of the model-related parameters, see Table 3.Table 3
Parameter values of the model.
ParameterValueMeasurement unitcostrunV145Yuan (vehicle·km)costrunV260Yuan (vehicle·km)costrunV375Yuan (vehicle·km)costcrossV211Yuan (train·station)mV1, mV2, mV38VehicleCapV01860PersonCapV1, CapV2, CapV3668,610,557PersonξV090%—ξV1, ξV2, ξV375%—costtime25Yuan (h)α25%—MV1, MV2, MV3120,150,160Vehiclettransfer15minfmaxL1, fmaxL330Train (h)fminL1,dep4Train (h)fminL3,dep6Train (h)fSi30Train (h)λ60%—δ2—t04minρ40%—Passenger ODs (origination and destination) are shown in the Table4. For the parameters mentioned in the algorithm: HMS=100, PHMCR=0.3, PPAR=0.5, BandW=2, Imax=500, Ipause1=100, Ipause2=300. Referring to the idea of weight assignment in [31], the objective functions are given multiple groups of weight to analyze the influence of weight setting on results.


## 4.2. The Influence of the Objective Functions Weight Setting on Results

In order to analyze the influence of objective functions weight setting on the results in detail, all possible weight values of two objective functions are enumerated (0.1 is the smallest unit). We can get the calculation results as shown in Table5.Table 4
The passenger OD matrix (upward direction) during the study period.
OD12345678910111213141516171819202122232425261—01143912103464394154511319212416191881312152——63618155243911951611912081191042432281541301642402251211271063———3911152420601167527327627418013285125176147971372151912174————031406253421291815131317218561058165—————62172636757254516253832643828124034406——————191145726456333527394648414841454438457———————722579710814014415114415197121131152151122104961178————————225525214815815318811314613510416688135126791029—————————94374474542969210510512584104851061089210——————————35118267197159116139135136215104947296869611———————————49271179275122240235160137205103971057711012————————————71051572028519215518919419911539558713—————————————5701610989669343128541814——————————————625412012552581451015———————————————1021068741531215516————————————————804530703910634817—————————————————67340417155418——————————————————2411191231341019———————————————————45266301820————————————————————311311221—————————————————————02400422——————————————————————2712223———————————————————————071724————————————————————————3525—————————————————————————526——————————————————————————Table 5
Influence analyses of weight setting on computing results.
ΦacfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanΔWyuan0.1623121812245876466698.142088572.4000.2723121811233136669176.912165098.0276525.620.3622121810220416673005.282229985.39141412.990.462212189212016675271.622234438.98145866.580.572212189207676876684.572215381.24126808.840.6721131611206724079750.012219581.83131009.430.7721121611204744081323.642182128.1793555.770.8721121611204744081323.642137232.1248659.720.9721121611204744081323.642092336.063763.66ΔW represents the difference between current objective value and the optimal objective value.Table5 shows that W″ gradually increases and W′ gradually decreases while Φ increases. When Φ increases to 0.7, the optimal solution and the values of the two objective functions are no longer changed. Due to the constraints, the value of each decision variable cannot be changed unlimitedly. It is worth mentioning that the operating cost of enterprises is not strictly positively correlated with the sum of three types of trains. W′ mainly depends on the sum of fVu⋅costrunVu⋅dij, as well as the number of stations, which V2 type trains pass. W″ mainly depends on the number of passenger flows and service frequency of various trains in each section. When the value of Φ changes from 0.5 to 0.6, although the train service frequency of V1 and V3 increases, train service frequency of V2 decreases from 18 trains/h to 16 trains/h. Passenger flows in the cross-line section is the largest, so the train service plan of V2 has a great influence on the value of W″. At the same time, the length of cross-line section reduces from 125 km to 115 km. As a result, W′ decreases from 2076768 yuan to 2067240 yuan, and W″ increases by 3065.44 yuan.The trend of the two objective function values changing withΦ is shown in Figure 11. When designing a train service plan, decision-makers can decide the best scheme according to different decision preferences.Figure 11
Graph of objective function values varying with weight coefficients.


## 4.3. The Influence of Cross-Line’s Origination and Destination Setting on Results

The weight of objective functions is set as a fixed value to analyze the influence of the cross-line’s origination and destination setting on results. In order to equalize the interests of both enterprises and passengers, takeΦ=0.5 as an example to analyze. From Table 6, we can see that the optimal solution and the objective value are quite different due to the different origination and destination of the cross line. For example, compared with the optimal solution, the service frequency of V1 decreases when a is five and c is 22. However, W′ increases by 47196 yuan because that both the length of cross-line section and the number of stations which V2 trains pass have increased. In addition, W″ increased by 344.61 yuan due to the decline of train service frequency.Table 6
Influence analyses of cross-line’s origination and destination setting on computing results.
acfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanΔWyuan72212189207676876684.572215381.240623121812245876466698.142253102.0037720.7652210189212396477029.182244268.5128887.27421111711220596679532.552323692.52108311.28ΔW represents the difference between current objective value and the optimal objective value.Therefore, a reasonable setting of the cross-line’s origination and destination can effectively save passengers waiting time, reduce the cost of enterprises, and help improve the service level.From the above analysis, it can be obtained that the optimal cross-line routing scheme diagram (whenΦ takes 0.5) is shown in Figure 12.Figure 12
Diagram of the optimal routing schemes.


## 4.4. Comparative Analyses of Different Operation Modes

In order to reflect the advantages of the model established in this paper, train service plans in the independent operation mode of the suburban rail line and intercity line is used for comparative analysis. We set the weight of objective functions as fixed values to analyze the influence of the operation mode on the results. In order to equalize the interests of both enterprises and passengers, takeΦ=0.5 for analysis.It can be seen from Table7 that the total train service frequency in the cross-line operation mode of urban railway and intercity railway is fV1+fV2+fV3=12+18+9=39train/h. In other words, 39 trains are operated per hour, and the number of vehicles used during one hour is 312. The minimum operating cost of enterprises is 2076768 yuan, the minimum cost converted from passengers travel time is 76684.57 yuan, and the total objective function value is 2215381.24 yuan. In the independent operation mode of the suburban railways and intercity railways, the total train service frequency is fV1+fV3=30+27=57train/h. There are 57 trains operated per hour, and the number of vehicles used during one hour is 456. The minimum operating cost of the enterprise is 2862000 yuan, the minimum cost converted from passengers travel time is 148558.33 yuan, and the total objective function value is 2942622.49 yuan.Table 7
Solution results of different models.
acfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanΔWyuan72212189207676876684.572215381.240——30—272862000148558.332942622.49727241.25ΔW represents the difference between current objective value and the optimal objective value.Compared with the independent operation mode of different rail transit systems, the number of trains running per hour is reduced by 18, the number of vehicles used is reduced by 144, and the operating cost of the enterprise is reduced by 785232 yuan in the cross-line operation mode. Since passengers do not need to transfer at the stationSb, the cost converted from travel time is reduced by 71873.76 yuan. Through calculation, W is reduced by 727241.25 yuan using cross-line operation mode.When cross-line operation mode is adopted, there will be through trains running from the suburban lineL1 to the intercity line L3, sharing transportation resources between the two lines and reducing the waste of transportation capacity. Moreover, the running section of the V2-type through trains covers the section with the largest passenger flow, which relieves the transportation pressure, reduces the transfer time of passengers, and improves transportation efficiency. Cross-line operation can solve the problems of unbalanced spatial distribution of passenger flow and insufficient sharing of transportation capacity from the operation organization level.


## 4.5. Comparative Analyses of Algorithms

The classical harmony search algorithm (CHSA) is used as the comparison algorithm, and it is implemented by C# programming on the same computer. Similarly, takingΦ=0.5 as an example, and three sets of parameters are used to compare the performance of two algorithms. The sets of parameters are given according to the scale of the case in this paper combined with the example experiments, and also referring to existing researches [25, 32].The first set of parameters:HMS=100, PHMCR=0.3, PPAR=0.5, BandW=2, Imax=500, Ipause1=100, Ipause2=300.The second set of parameters:HMS=70, PHMCR=0.5, PPAR=0.3, BandW=3, Imax=500, Ipause1=200, Ipause2=400.The third set of parameters:HMS=50, PHMCR=0.9, PPAR=0.5, BandW=1, Imax=500, Ipause1=150, Ipause2=200.It can be seen from Tables8–10 that no matter which set of parameters is used, the problem-solving efficiency and computing quality of IHSA are always higher than those of CHSA. IHSA always get a low total cost by fewer iterations. Taking the value of the first set of parameters as an example, MATLAB is used to draw the algorithm iterative process diagram, as shown in Figure 13. We can learn from Figure 13 that the IHSA designed in this paper has better performance, so the algorithm improvement strategy is effective.Table 8
Comparative analysis of IHSA and CHSA (the first set of parameters).
AlgorithmIteration timesacfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanIHSA25072212189207676876684.572215381.24CHSA39062211189210036676821.302229278.85Table 9
Comparative analysis of IHSA and CHSA (the second set of parameters).
AlgorithmIteration timesacfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanIHSA27542212189220696272742.232219969.06CHSA410722131711220439273951.252237240.73Table 10
Comparative analysis of IHSA and CHSA (the third set of parameters).
AlgorithmIteration timesacfV1train/hfV2train/hfV3train/hW′yuanW″yuanWyuanIHSA230723121811233136667176.912196751.40CHSA375622111810218436673560.062221223.52Figure 13
Iterative process diagram.However, the above analysis is based on solving the train service plan design model constructed in this paper. The performance of the algorithm is affected by the setting of parameters and whether the algorithm is suitable for problems to be solved. With this study, it cannot demonstrate that the improved harmony search algorithm always shows good performance in any scenario.


## 5. Conclusion

According to the guiding opinions on developing modern metropolitan areas, all regions should coordinate the layout of rail transit network and realize the integration and interconnection of multimodal rail transit systems. Therefore, design a train service plan based on the integration and interconnection of multimodal rail transit systems is an urgent problem to be solved at this stage. We consider the costs of both operating enterprises and passengers to construct the model and use an improved harmony search algorithm (IHSA) to find the solution.The proposed model and algorithm can provide useful help for the relevant operating enterprises. The problems such as insufficient sharing of transport capacity, long transfer time, and limit improvement of transportation efficiency in the existing independent operation mode of different rail transit systems can be partly solved by the proposed method. However, we only consider train service plan design under the condition of unidirectional and static passenger flows in this paper. The multidirection train service plan with dynamic passenger flows can certainly be looked forward in the future research.



---

*Source: 8275191-2023-02-14.xml*