A line planning approach based on harmony search for high-speed rail: From the perspective of service accessibility

1Introduction

Over the past 12 years, China has built the largest high-speed rail network in the world. By the end of 2019, HSR lines operated 35,000 km across the country. In an attempt to optimize the network capacity in order to meet passenger demand, the line planning problem (LLP) is crucial to mitigate the operational issues faced by the rail company. The line plan specifies the routes between origin and destination station, stops and service capacity [12]. The LLP determines the stops, frequencies of train service, as well as train makeup, for services based on passenger demand. Additional information regarding the capacity of each section and station should be utilized efficiently. The LLP operated under the HSR network in China is complicated and difficult to manage in comparison to other countries, such as Germany and Japan, due to its larger size of the network and higher volume of transport demand. The basic objective function of LLP is to minimize the total traveling cost of passenger, maximize the benefits of rail enterprise, and maximize the total passenger that can be transported. While, some shortages are generated from traditional approaches, for example, trains with frequent stations, are organized in this manner to service the demand of intermediate nodes, the total travel time between origins and destinations (ODs) inevitably extends. Due to differences of GDP, population and transport demand among cities along the rail line, service frequencies vary considerably. For example, the average service frequency of small nodes between Beijing and Shanghai HSR is about 6.9 (about two-thirds of the nodes along the line), which means that accessibility of those nodes can be improved. The average travel speed between large-size nodes (such as Beijing, Jinan, Nanjing and Shanghai) is approximately 248 km/h, even though the maximum speed reaches 350 km/h.

In this paper, the service accessibility is presented to evaluate the line plan of rail network, try to get a better line plan for high speed railway by means of balancing the relationship between two conflicting problems, which are improve the travel time among large nodes, and increase service frequencies of middle and small nodes. The paper is organized as follows. Section 2 reviews related line planning literature. Section 3 and Section 4 present a model and algorithm for line planning problem and consider service accessibility. Section 5 is devoted to the evaluation of the numerical experiments. The final section presents major conclusions and gives an outline of future research tasks.

2Literature review

The LPP can be categorized by two typical objective functions of related line planning models: cost-oriented and customer-oriented. Cost-oriented models function to optimize line plan by minimizing operation cost of rail companies and are primarily concerned with the number of trains. Customer-oriented models determine line plan with the objective of optimizing passenger benefits. The model focuses on determining the number of passengers that can be transported and travel cost (such as ticket price and cost of travel time).

Claessens et al. [5] presented integer programming models with cost-oriented objective. Goossen et al. [8, 9] improved upon the model proposed by Claessens, and introduced a branch-and-cut algorithm to solve the LPP. Goerigk et al. [7] further designed a heuristic approach for this problem. Bussieck et al. [1] presented the LPP model to maximize the number of direct travelers. While Scholl [17] remarked that Bussieck’s model may lead to more transfers for travelers and further developed a new model by considering the number of transfers. Guan et al. [10] proposed a new model by minimizing the cost, total passenger and travel time simultaneously, with additional focus on the number of transfers. The researchers follow a similar policy of optimizing train frequencies with pre-given stops. Another policy to solve the LPP, provides an approach that simultaneously optimizes train frequencies and stops. Chang et al. [3] formulated a multi-objective model that minimizes the operation cost, travel time and presents a fuzzy mathematical approach to form a policy that would assist in solving LLP for Taiwan HSR system. Kaspi and Raviv [15] proposed an approach that integrates the line planning, cyclic timetabling, and routing as a new model. Fu et al. [12] presented a hierarchical line planning approach for China HSR network. Su et al. [21] formulated a bilevel optimization model and considered the train operational cost and passenger travel cost in the upper level and passenger assignment in the lower level. Some research focused on algorithm for LPP, such as Column Generation algorithm [19], Simulated Annealing [11].

There are few researches on the comprehensive optimization of LPP of intercity high-speed railway in network state rather than single line state. Due to the rapid development of urban scale and high-speed railway, the research on the latest development situation of railway network is still insufficient. With the large number of stations and large passenger flow OD, the train operation paths are very large. Therefore, this paper adapts to the actual needs and carries out more in-depth research on the LPP of high-speed railway under the network state.

Accessibility has been a central issue in transport geography and has been broadly used in various fields during the past decades [2, 13, 14]. But there is no research on LPP in HSR based on accessibility. The accessibility can be measured by different indicators that typically measure travel time and quality/quantity. For example, weighted average travel time, daily accessibility, potential accessibility etc, Most of the studies focus on the accessibility of physical transport network. The total travel time of trains is used to calculate such indicators. While this travel time is calculated by minimum on-train time, waiting time for trains (determined by services frequency) at station is unaccounted for. The application of proposed approaches is difficult while measuring the accessibility of service network that presented by line planning of HSR.

3Proposed line planning approach

There are several ways to describe network accessibility, for example, accessibility based on transportation cost, travel time and number of services offered [4, 16, 20]. While, almost all of the research focuses on the accessibility of physical network, in this paper, the SA-HSRLP model based on the service accessibility of high-speed railway line plan is established. This paper takes into consideration the number of services provided and travel time to the destination of a node, in the service network during the plan horizon. The number of services is determined by train frequencies of LPP. Travel time is summation of waiting time at origin station and total travel time to destination. The timespan of planning horizon divided by the train frequencies is the average waiting time and total travel time equal to the travel time between station plus stop time at intermediate stations. From the perspective of HSR network accessibility, different line plans with different train frequency and stops will lead to differentiated service accessibility.

The related notations involved in the SA-HSRLP model are defined as follows:

(1) Multi objective function

Objective function 1: maximization of service accessibility

The high-speed rail network can be set as G = (S, E). The service network of line plan is described as G^f =  (N, A). Assume that the stops of line plan are given, we can know the potential train services for each OD. Equation (1) was put forward by Wang et al. [20], which was used to measure the service accessibility of node i. Then the service accessibility F₁ of can be formulated as objective function (2) by accumulating all the service accessibility of nodes in one region. The value of Tij* is determined by the travel speed of trains (direct service or not, and the number of stops), service frequency (the number of service decides the waiting time at stations).

The economic and population level of the destination node j is the geometric average of GDP and population GjPj , which describes the number of passenger opportunities that can be obtained and reflects the attraction of the place. The approaches to calculate Tij* and ϖ are as follows.

a. the shortest direct travel time between i and j.

Assume that there is only one transfer between any two nodes and if there is more than one node that can be used to transfer during travel time, the one with the shortest transfer time is chosen. Then t_ij by expression (3) is gotten.

Where, nijr is the number of direct services of type r between i and j, can be calculated by Equation (4). So, if there have direct service between i and j, the travel time is composed by waiting time as station, as well as travel time and stop times at intermediate nodes.

b. the shortest travel time with transfer between i and j:

In order to meet the requirements of fast commuting and ensure the convenience and comfort of passengers, it is assumed that all passengers have at most one transfer during the journey. Considering that there can be multiple transfer points between, the transfer point with the smallest transfer time is taken as the transfer point.

For any transfer node k, the number of direct services to the destination i is:

After a transfer at station k, the shortest travel time from the start node i to the destination node j is:

That is, if transfer at node k between node i and j, then node k should have direct service to node j, so nkjr>0 . The travel time of transfer at node k is Tijk=tik+tkj+tk . When nkjr=0 , the transfer node k has no direct service to the destination node j, that is to say, if the transfer between node i and j cannot be made at node k, so Tijk=M .

c. the shortest travel time between i and j:

The shortest travel time is the smaller value of direct travel time and travel time with transfer.

d. convert the shortest travel time to a Boolean value ϖ:

Objective function 2: minimizing train operation cost:

We model the LLP with policy of optimizing train frequencies with pre-given stops. The makeup of trains is assumed to be fixed, and passengers always choose the service with shortest travel time with no more than one transfer for the whole trip if there are no direct services. The model of LPP by considering service accessibility is formulated as follows.

(2) constraints of station capacity:

Carrying capacity:

The actual number of trains passing through the section shall be less than the carrying capacity of the line.

Station capacity of departure:

The number of departing trains at a station should be less than the departure capacity of the station.

Station capacity of receiving:

The number of receiving trains at a station should be less than the receiving capacity of the station.

(3) constraints of passenger flow distribution:

Flow conservation:

In the service network of high-speed railway operation, except for the starting node and the end node, the outflow flow and inflow flow of the intermediate node are equal.

Transportation capacity:

The number of passengers that are assigned to each arc should not exceed the service capacity of this arc and the service capacity equals to the sum of the number of seats of all trains that pass through each arc.

(4) constraint of integer:

4Harmony search algorithm

The proposed model is nonlinear, and line planning is a system optimization problem and is extremely complex, especially with the continuous expansion of the current HSR network scale. Some exact solutions are inspirational [24], while there are difficult to apply to this model. Intelligent optimization algorithm is needed to solve the problem. Therefore, according to the characteristics of line planning problem, it is of great practical significance to study and select the appropriate optimization algorithm, so as to quickly obtain satisfactory train operation scheme. Compared with ILOG, Gurobi and other optimization software, although heuristic algorithm cannot guarantee the optimality of the solution, and even cannot explain its approximation to the optimal solution in most cases, it can find the feasible solution in the acceptable cost and time range. This is consistent with the requirements of train operation plan preparation: to obtain a feasible plan within an acceptable time.

According to the characteristics of the model, this paper uses harmony search algorithm (HS) to solve the model. Compared with traditional heuristic algorithms such as genetic algorithm (GA), ant colony algorithm and simulated annealing algorithm, harmony search algorithm has the characteristics of easy understanding, simple steps, novel solution construction, easy programming and calculation, and less adjustment parameters.

Compared with the traditional GA, the initial solution generation of HS algorithm is random, and both of them have the evaluation mechanism of fitness function. HS algorithm has crossover and mutation operations similar to GA, so it has most of the advantages of GA. At the same time, because the HS algorithm produces a new solution clearly, only one new solution is generated in each iteration, so the complexity is low. In view of the advantages of HS algorithm, this paper intends to use HS algorithm to solve the line planning problem.

The model proposed in the previous section is a multi-objective nonlinear integer programming model. To tackle it, we first transform this model into a single-objective one and then design an algorithm based on Harmony Search [6, 18] to resolve it.

The solution can be presented as (16, where f_r is a positive integer, which means that the frequency of pre-given service is r. We generate initial solution by getting a number randomly in the interval [0, Ce] for each r. If the size of Harmony Memory (HM) set to be HMS, then get the HM as shown as (17).

During the iteration, new solutions can be generated as follows. First, get a random number from [0,1], note as rand, compare rand with HMCR (probability to choose a solution from HM). If rand <  HMCR, then select a solution from HM randomly. Disturb this selected solution with probability of PAR, and disturbance strategies include, reduction of one time of service of any r. If its frequency is more than 1, or add one time of service of any r if its frequency is no more than Ce – 1. If rand≥HMCR, generate a new solution as the way to get the initial solution.

For multi-objective optimization problems, Nyoman [22] introduced the scalarization method to convert the problem to a single-objective one. As Liu [23] did, the multi-objective function is converted as (18). F1max and F2max means the optimal value of the model with only one of those two objective function. So, the value of F1F1max and F2F2max both larger than 1. Set δ₁ and δ₂ are the weight of those two functions of (8) and (9). We valued those two parameters as 0.5, which means both of the operation cost and service accessibility are of equal importance. Then the solutions of each iteration can be evaluated by expression (18). If the new solution is better than (the value of objective is smaller than) the worst solution in HM, replace it by the new solution and update the HM. Otherwise, keep the set of HM unchanged.

For each solution that in HM or new generated, we need to assign passenger flow to those services. We first search the K-shortest path for each OD based on the total travel time. We assume the passenger chooses the direct trains with priority and select the service with shortest travel time among those direct trains. If there are no direct trains, passengers can choose the transfer service with the shortest travel time. We can assign the passenger flow to the shortest path (service) based on all-or-nothing policy. Finally, the penalty function is used to deal with the infeasible solution if the passenger flow cannot be assigned to the service network.

The procedure of this algorithm then can be presented as follows;

Step 1: parameter initialization.

Step 2: generation of the initial HM and calculation of the values of objective function of solution in HM.

Step 3: generation of a new solution.

Step 4: compare the value of the new solution and that’s the solution in HM, and then update the HM.

Step 5: end for pre-given number of iteration steps, or back to Step 3.

The complete algorithm flow is shown in Fig. 1.

Fig. 1

Algorithm flow.

5Numerical experiments

We now present the numerical experiment of the above line planning approach that consider service accessibility. The HSR network and pre-given train services are shown as under Fig. 2. The section mileage, GDP and population of each node, the passenger demands are present in Tables 1 to 3.

Fig. 2

HSR network and pre-given line plan.

This algorithm is written in Matlab and run on an Intel i3 with 4 G Ram. After several time tests, we set the parameters of this algorithm as: HMS = 35, HMCR = 0.9, PAR = 0.1, the maximum iterations are 2000. After near 800 iterations in 180 seconds, the final solution as shown in Fig. 3, 13 services are selected from pre-given 21 potential choices, and the total number of trains are 23. The iterative convergence is shown in Fig. 4.

Fig. 3

Final solution of this multi-objective function model.

Fig. 4

Iterative convergence of algorithm.

Results analysis of the numerical experiments.

(1) Number of trains under different objective function.

The waiting time at the origin station can be reduced by adding more trains for service. While, from the perspective of operator, more trains under operation means larger cost. The experiment tested and compared the solution of modes with multi-objective function (M), with the single objective function of minimizing operation cost (SC) and the best service accessibility (SA). The results are shown in Table 4. The number of trains in the three scenarios are 23, 19 and 28 respectively. In order to minimize operation cost, the rail company can organize trains that have more stops, which will compromise the level of service of HSR. So we add the cost of each stop in the objective function, in order to adjust the number of trains with poor level of service, such as the train that stop at all of the intermediate stations.

Under scenario SA, train services of 9, 17 and 21 have been planed 4, 3 and 6 train during the plan horizon. For the scenario of SC, the number are 1, 2 and 1, respectively. So, we know that, more trains with more stops can improve the service accessibility of nodes and network. While, the transport demand of large nodes in the network will spend more time on trains. Under scenario M, more trains that service large nodes and have small number of stop at intermediate nodes have been organized. For example, we planned train service r = 1 and r = 10, which are direct trains just service large node. And trains service r = 5 and r = 15 that origin and terminate at large nodes and stops at a small number of the other node are planned simultaneously. The travel time for the passenger from large nodes and service opportunity for passenger from intermediate and small nodes can be well balanced.

(2) Service frequencies of nodes under different objective function.

The result is shown in Fig. 5. Compare to the scenario SC, the service frequencies of nodes A, C, D, E, F, G, H, K, L and M are increased in scenario M. Some of the medium-size node, such as C, E and F, the service frequencies increased 2 trains, 2 trains and 3 trains per hour.

Fig. 5

Service frequencies of nodes.

(3) Service accessibility of nodes and network.

The accessibility of network of scenario M, SC and SA are 9.35, 10.81 and 7.34 respectively. The service accessibility of nodes is shown in Table 5. We know that service accessibility of nodes under scenario M is better than that of scenario SC, as none of the nodes service accessibility of scenario SC is better than scenario M, 71.4% of those nodes are medium and small nodes.

6Conclusions

This paper introduces service accessibility into tradition line planning problem of HSR. The service accessibility is determined by the number of services, trip time to the destination of a node and the service network during the planned horizon. From the perspective of line plan, service accessibility depends on the trains frequencies and stops. The study proposed a multi-objective nonlinear model for HSR line planning problem which aims to balance the travel time between large-size nodes and the service accessibility of medium and small size nodes in HSR network. A heuristic based on Harmony Search is designed after transformation of the model into a single-objective function one. The results of numerical experiment show that proposed approach can improve service accessibility of the whole network and most of the medium and small size nodes, as compared to the model with single objective function of minimizing the operation cost.

In practice, there may be more than one transfer when the transportation of large HSR network as China is considered. The study intends to further enhance its model by contemplating a transport system through more than one transfer when no direct trains are available. In addition, further case studies with real world data will be utilized to test the model and algorithm and will be discussed further.