Importance-based technique with genetic algorithm for generating the initial rail transit network: A case study of Hefei

Abstract

Recently, a growing body of research has emerged that focuses on rail transit network planning from the qualitative judgment, but few has made quantitative analysis on rail network generation. Therefore, this article proposes a theory of generating the initial rail transit network based on the importance in indicator system, where the analysis on a rail path was quantitatively conducted from three dimensions of plane, hub, and path. In this article, the morphology of initial rail transit network is primarily identified by the measurement of importance indicator for each traffic zone. Second, to maximize the coverage of passenger hubs, the virtual paths in the initial network are determined by the random search method and the genetic algorithm. Then, with the adjustment of the virtual paths based on the shortest path model, this article has empirically generated the entity paths for the rail transit system in Hefei as case study.

Introduction

Generally, a plan for the rail transit network in a city is formed through several stages, which mainly include the network size calculation, the morphology determination, the rail paths building, and then the initial network formation. Afterward, a revision and optimization, based on passenger flow test results, will be repeatedly implemented on the initial network until the ultimate rail transit network plan is formed. Throughout the whole process, the initial network is key to the determination of the geographical position and path direction of urban rails in all periods and scopes.

Existing studies on city rail transit network planning could be mainly grouped into two streams. One is theoretically focused on the generation and optimization of city rail transit network employing analytic network approach. This stream went through three individual stages. Studies in the first stage from 1970s to 1980s are single-goaled and achieved by the optimization of one path on another. For example, DiCesare ¹ proposed a single-path model to minimize construction fee. Church and Clifford ² proposed a simple network grid model to balance the path network configuration, by which a path rendering the lowest fees between the origin and destination (O-D) is generated. As the model fails to serve the majority of population in a region, it cannot be implemented. In the second stage from 1990s to the early 21st century, multiple goals were proposed for network design on certain premises. For example, based on Church’s studies, Current et al. ³ established the dual goal-based generation model to design a rail network serving the maximized passenger flow with the shortest line length. Utilizing the Tabu Search Heuristic algorithm, Dufourd et al. ⁴ developed a dual goal-based rail transit optimization model for rail network design. Afterward, Liu ⁵ proposed a virtual network model for urban rail transit. Based on current research, Bruno et al. ⁶ tried the K-shortest-paths algorithm to analyze options for rail transit networks with fixed demands and found that the resulted network was better performed in the optimization of minimizing construction and traveling cost. Wang et al. ⁷ used network graph theory in the investigation of the network size, morphology, and initial network layout. In the third stage from early 21st century till now, numerous planning methods for rail transit network layout come out, such as bi-level planning and designing models, joint studies on passenger flow forecast and network optimization, network planning based on elastic demands, and new path expansion method. Based on the four-phase model framework, Laporte et al. ⁸ defined a new model using the maximum coverage of the public demand and the path as an objective function and it could be used for a kernel rail transit network design and the ultimate urban rail transit network formation, Marín and García-Ródenasbs ⁹ established a bi-level path network optimization model.

The other stream is practically involved with methodologies applied in the generation and optimization of rail transit network including demand test, where both quantitative and qualitative analyses are employed. For instance, Beijing Urban Construction Institute advocated the plane-, hub-, and path-based factor analysis. ¹⁰ China Academy of Urban Planning and Design proposed a method for weaving transit network, which takes the planning for the goal and principle, the functional hierarchy for the orientation, and the traffic hub for the outline. ¹¹ Escudero and Munoz ¹² proposed a two-phase planning method that incorporates loop rail paths in network expansion. The first phase uses the integer planning and design model to arrange rail transit stations. The second phase connects specified stations under certain constraints. ¹² Considering that most Chinese cities follow the multi-center axis development, Peng ¹³ proposed the station-based networking method. Kong ¹⁴ also proposed a technique for generating the initial rail transit network, which is separated into three steps: generating the initial network—designing alternative plans—determining the final plan. At the same time, the assessment system for rail transit network is also improving. Guo and Lu ¹⁵ examined the relationship among city space structure, land usage, and rail transit network layout and assessed the network layout of typical cities. Wang et al. ¹⁶ raised three qualitative indicators that are the fitness between rail transit network center and city center of gravity, the consistency of shape division dimensions between the city and rail transit network, and the similarity of the direction between population and rail transit network.

As mentioned above, numerous theories and methodologies on the rail transit network planning have been brought out, but still some gaps exist there. Current theoretical studies aimed at optimizing the whole rail network and building their corresponding network models lack the due practicability. Most mature methods on rail network planning still stay in a qualitative level, especially the determination of network morphology and passenger hubs. The process for line network generation lacks data for quantitative study. Therefore, the objective of this article is to generate a rail transit network using the reference drawn by the importance theory and employing the quantitative analysis from plane, hub, and path factors.

Determining the initial rail network morphology based on the plane factor

Constructing the adjacent matrix and border matrix

Adjacent matrix reflects the adjacency between zones, which is the basis for path searches. Suppose the adjacent matrix is represented by A, and the value of its element $a_{\mathrm{ij}}$ is as follows

$$a_{\mathrm{ij}}=\{\begin{array}{c}1\mathrm{Zone}i\mathrm{is}\mathrm{adjacent}\mathrm{to}\mathrm{zone}j\hfill \\ \multicolumn{1}{c}{0\mathrm{Zone}i\mathrm{is}\mathrm{not}\mathrm{adjacent}\mathrm{to}\mathrm{zone}j}\end{array}$$

(1)

The adjacent matrix of a zone is as follows

$$A=\left[\begin{array}{cccc}{a}_{11}\hfill & a_{12}\hfill & \cdots \hfill & a_{1n}\hfill \\ \multicolumn{1}{c}{a_{21}}& a_{22}\hfill & \cdots \hfill & a_{2n}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{a_{n1}}& a_{n2}\hfill & \cdots \hfill & a_{\mathrm{nn}}\hfill \end{array}\right]$$

(2)

In practice, additional attention should be given to the city morphology and its future development that these eccentric or concentric zones should be considered to be adjacent. According adjustments should be made on the adjacent matrix and build a revised adjacent matrix $A\prime$ .

Border matrix is a set of zones that are possible to be destinations of a path and usually refer to zones in the bordering area (bordering zones for short). Suppose the border matrix is represented by B, and the value of its element $b_j$ is as follows

$$b_j=\{\begin{array}{c}1b_j\mathrm{is}a\mathrm{bordering}\mathrm{zone}\hfill \\ \multicolumn{1}{c}{0b_j\mathrm{is}\mathrm{not}a\mathrm{bordering}\mathrm{zone}}\end{array}$$

(3)

The border matrix between zones is as follows

$$B=\left[\begin{array}{cccccc}{b}_1\hfill & b_2\hfill & \cdots \hfill & b_j\hfill & \cdots \hfill & b_n\hfill \end{array}\right]$$

(4)

Since the O-D of a rail transit may not always fall in the bordering zones of a city but sometimes fall in zones inside the city, adjustments should also be made to meet the actual situation and build a revised border matrix $B\prime$ .

Importance of traffic zones

The importance of a traffic zone is related not only to its population and number of jobs, but also to its geographical position in a city. Therefore, the calculation of a traffic zone importance involves two parts: position importance and transportation importance.

Position importance of a traffic zone

Assume that both origin and destination of a generated trip locate in the geographical center of the zones. As to traffic zones in the periphery with larger size, the main passenger hubs are selected as their centers. Suppose a research area is divided into n traffic zones and according to distances between the zones centers, we build a space matrix for it

$$S=\left[\begin{array}{cccccc}{s}_{11}\hfill & s_{12}\hfill & \cdots \hfill & s_{1j}\hfill & \cdots \hfill & s_{1n}\hfill \\ \multicolumn{1}{c}{s_{21}}& s_{22}\hfill & \cdots \hfill & s_{2j}\hfill & \cdots \hfill & s_{2n}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{s_{i1}}& s_{i2}\hfill & \cdots \hfill & s_{\mathrm{ij}}\hfill & \cdots \hfill & s_{\mathrm{in}}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{s_{n1}}& s_{n2}\hfill & \cdots \hfill & s_{\mathrm{nj}}\hfill & \cdots \hfill & s_{\mathrm{nn}}\hfill \end{array}\right]$$

(5)

$$S_i=\sum _{j=1}^n{s}_{\mathrm{ij}}$$

(6)

where $s_{\mathrm{ij}}$ represents the spatial distance between traffic zone centers of i and j; $S_i$ refers to the sum of distances that i to all the other zones. Smaller value of $S_i$ indicates that zone i is more advanced and more important in geographical position. The geographical importance of traffic zone i can be denoted by D_i

$$D_i=\frac{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$S_i$}\right.}{{{\displaystyle \sum }}_{i=1}^n\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$S_i$}\right.}$$

(7)

Transportation importance of a traffic zone

From the transportation perspective, the importance of a traffic zone typically depends on the trips generated in this zone (production and attraction). Therefore, the generated trip amount is the key determinant of the transportation importance. The transportation importance of a traffic zone $T_i$ is

$$T_i=\frac{\raisebox{1ex}{$G_i$}\!\left/ \!\raisebox{-1ex}{$A_i$}\right.}{{{\displaystyle \sum }}_{i=1}^n\raisebox{1ex}{$G_i$}\!\left/ \!\raisebox{-1ex}{$A_i$}\right.}$$

(8)

where $G_i$ is the generated trip number and $A_i$ is the size of traffic zone i.

Overall importance of a traffic zone

The overall importance of i is weighted by position importance and transportation importance

$$E_i=\alpha ·D_i+\beta ·T_i$$

(9)

In equation (9), $\alpha$ and $\beta$ are defined by the coefficient of variation method. Compared with the traditional judgment matrix approach and expert grading method, the coefficient of variation method is more objective that can reduce the subjectivity and randomness in weight calculation and avoid the equalization problem. Additionally, the raw data of various indicators can be used to guarantee that weights comply with the reality.

Path initialization to searches

Based on adjacent and border matrixes and importance indicators, the direction weight in path searches could be defined by

$$F_{\mathrm{ij}}=\frac{E_j}{S_{\mathrm{ij}}}·q_{\mathrm{ij}}$$

(10)

where $F_{\mathrm{ij}}$ is the direction weight for search that starts from i to j, $E_j$ is the importance indicator of j, $S_{\mathrm{ij}}$ is the distance between the centers of i and j, and $q_{\mathrm{ij}}$ represents the passenger hubs between the two zones.

As to the rail path search, the steps could be summarized as follows:

• Step 1: Determine the origin, calculate the importance indicator of traffic zones, and rank these zones according to the importance. Select centers that are of higher importance and meanwhile distributed to different zones as the origin. The number of origins depends on the actual situation, mostly, 4 to 6.

• Step 2: Path search starts from the origin to its adjacent zones with higher importance. The search could have four options in direction. During the search, if the weight difference between two directions is within 20%, search both directions. The search must comply with the smooth requirement that the turn angle should be between 90° and 180°.

• Step 3: Once the centers between adjacent zones are connected, the searching would come to the next direction with the smaller weight to avoid repeated paths.

• Step 4: If the searched point is a center of a border matrix, the search ends. The collection set of zones throughout the path is $Z_k=\{z_k^1,z_k^2,\dots ,z_k^t\}$ , where k is the line number, and $z_k^1,z_k^2,\dots ,z_k^t$ are the zone numbers that k passes through.

• Step 5: Conduct preliminary analyses of generated path morphologies. If some zones with obvious high importance are not searched or the rail network size is apparently small, repeat steps 1, 2, 3, and 4 until the general paths on the rail transit network show up.

Generating the virtual rail transit network based on the hub factor

Determining the importance of a hub

Identifying passenger hubs

A passenger hub is the place where the passenger flow produces and attracts, and it usually refers to a regional center (I) or transportation hub (II). Typically, a regional center system consists of an administrative center, a business center, a large-sized company, residence, and a resort center. On the other hand, a transportation hub is usually presented in the form of a bus station, passenger station, rail station, or an airport. Usually, (I) typed passenger hubs are classified according to the land use and development strength surrounding the hub and its detailed classification is shown in Table 1.

Table 1.

Classification of (I) typed passenger hubs.

Type	Covered area	Flow feature
Traffic hub	Large-sized bus station or airport	Passenger flow for transferring in hubs
Residence hub	Large-sized residence	Passenger flow for commuting or elastic trips
Industrial hub	Industrial parks and feature industry area	Trips for commuting or on business
Administrative hub	Large offices	Trips for commuting or on business
Business center	Shopping malls	Customer flow for shopping
Culture center hub	Culture centers	Passenger flow for study or recreation
Medical center hub	Large-sized hospitals	Doctor visit passengers
Sports center hub	Large-sized stadium	Passenger flow for fitness or sports
Holiday resort hubs	Famous holiday resorts	Tourist flow

According to the transportation functions and service scope, (II) typed passenger hubs are divided into regional, community, and urban passenger hubs, as shown in Table 2.

Table 2.

Classification of (II) typed passenger hubs.

Type	Covered area	Flow feature
Regional hub	Inter-city transportation center	Inter-city passenger flow
Community hub	Functional community center	Inter-community passenger flow
Urban hub	Secondary functional area	Internal conversion passengers

Constructing the indicator system

Based on the factor analysis of city passenger hubs, a hierarchical analysis method that incorporates geographical condition, production and attraction of passenger flows, and accessibility of hubs is applied to build the passenger hub indicator system, as shown in Figure 1.

Figure 1.

The indicator system of passenger hubs.

Determining and standardizing indicators

Both qualitative and quantitative indicators are included in this section. Quantitative indicators can be mainly obtained through corresponding surveys or statistics, while qualitative indicators can be identified by experts grading method and processed by the following expression

$$I_{\mathrm{ij}}=\frac{1}{Z}\sum _{z=1}^Z{u}_{\mathrm{ijz}}$$

(11)

where $I_{\mathrm{ij}}$ is the value of the jth indicator in the ith hub, Z refers to the number of experts, and $u_{\mathrm{ijz}}$ is the score rated by the zth expert for the jth indicator in the ith hub.

Since the units, dimensions, and magnitude of indicators are different, we cannot measure the importance of passenger hubs directly. So, there is a need to standardize these indicators.

Assume that $I_{maxj}$ represents the largest value of the jth indicator among the m passenger hubs, and $I_{minj}$ represents the smallest value of the indicator

$$\begin{array}{c}{I}_{\mathrm{maxj}}=max\{I_{1j},I_{2j},\dots ,I_{\mathrm{mj}}\}\hfill \\ I_{\mathrm{minj}}=min\{I_{1j},I_{2j},\dots ,I_{\mathrm{mj}}\}\hfill \end{array}$$

(12)

The standardization process is as follows

$$I_{\mathrm{ij}}^{*}=\frac{I_{\mathrm{ij}}-I_{minj}}{I_{maxj}-I_{minj}}$$

(13)

After standardization, the range of indicator $I_{\mathrm{ij}}^{*}$ is scaled into [0, 1], but no change occurs in its variation. Finally, we come to the standardization matrix $X=(x_{\mathrm{ij}}{)}_{m\times n}=(I_{\mathrm{ij}}{)}_{m\times n}$ .

Determining the weights of indicators

Weight indicates the importance, value, and proportion of an indicator in the whole indicator system. In general, the weights determined at the goal layer are largely the results of qualitative experience, leading to high subjectivity. This thesis uses entropy method to determine indicators’ weights.^17,18 Entropy, a measure of the disorder in a system, is commonly employed to draw the effective information or weights behind the given data. Therefore, its application for the weight calculation in the goal layer is reasonable and objective.

The decision matrix driven from data standardization is used for the weight calculation of the jth indicator in the ith passenger hub

$$q_{\mathrm{ij}}=\frac{x_{\mathrm{ij}}}{\sum _{i=1}^m{x}_{\mathrm{ij}}}i=1,2,\dots ,m;j=1,2,\dots ,n$$

(14)

Through the calculation based on the above expression, we can get the matrix $Q=\{q_{\mathrm{ij}}{\}}_{m\times n}$ ,where $Q_i=\{q_{i1},q_{i2},\dots ,q_{\mathrm{in}}\}$ are the standard assessment vectors.

Then, the entropy of the jth indicator is

$$H_j=-\frac{1}{\ln m}\sum _{i=1}^m{q}_{\mathrm{ij}}\times \ln q_{\mathrm{ij}}j=1,2,\dots ,n$$

(15)

If $q_{\mathrm{ij}}=0,q_{\mathrm{ij}}\times \ln q_{\mathrm{ij}}=0$ . The weight of an indicator is as follows

$$a_j=\frac{1-H_j}{n-\sum _{j=1}^n{H}_j}j=1,2,\dots ,n$$

(16)

$$A=(a_1,a_2,\dots ,a_n)$$

$$0\le a_j\le 1,\sum _j^n{a}_j=1$$

where $a_j$ indicates the weight of the jth indicator and A indicates the normalized weight vectors.

Calculating the importance

After the weights of indicators are determined, the importance indicator E_i of passenger hub i in a city can be calculated

$$\begin{array}{l}{E}_i=A·Q_i={\displaystyle \sum _{j=1}^n{a}_j}\frac{x_{ij}}{{\displaystyle \sum _{i=1}^m{x}_{ij}}}\\ ={\displaystyle \sum _{j=1}^n{a}_j}{q}_{ij}i=1,2,\mathrm{\dots },m\end{array}$$

(17)

where $E_i$ denotes importance indicator of passenger hub i, $m$ is the number of passenger hubs, $n$ is the number of selected indicators, and $q_{\mathrm{ij}}$ is the normalized value of jth indicator of the hub i.

Determining the path origin and destination

To connect rails with inter-city transportation effectively without any transfers, we need to select certain pairs of O-D in the border matrix according to the importance of passenger hubs. Sometimes, O-D in non-border matrixes (mainly refers to fringe regions with frequent traveling activities) should be considered with the vehicle land use as constraints. Afterward, we need to match origins with destinations, based on the search results in the plane-based initial rail transit network, trip distribution, the maximum rail length constraint, and the possibility of building a rail in between.

Determining the path search area

The path search area is determined by the origin and destination, as well as the distance in between. After the O-D is determined, it comes to the analysis of reasonable distance between the O-D. As mentioned above, the diameter of a central town is 30–40 km. Given that origins and destinations are generally not located in the city border, the straight line distance between them is around 35 km. Suppose the nonlinear coefficient of rail transit is 1.35 (the average nonlinear coefficient of rail transit in Beijing is 1.15 while that of Shanghai is 1.33), then the maximum O-D distance is 47 km. On this basis, the search area can be determined.

Determining the matching set of effective passenger hubs between O-D

Building a directed graph between O-D and passenger hubs

Take any point in the city plane for the origin and build a rectangular plane coordinates, as shown in Figure 2. Select the $(S_i,E_i)$ matching set. Build a directed graph that starts from $S_i$ and ends at $E_i$ . To ensure the positivity of a rail path, the two ends must meet the following expression: $|x_i^n-x_i^s|<|x_i^{n+\lambda }-x_i^s|$ , $\lambda =1,2,\dots$ .

Figure 2.

The directed graph of O-D and hubs.

Algorithm for determining the matching set of effective passenger hubs

In the directed graph, the collection set of points in the kth path between $S_i$ and $E_i$ constitutes the matching set of effective passenger hubs: $D_i^k=(d_i^{k1},d_i^{k2},\dots ,d_i^{\mathrm{kt}})$ . Relationships between elements in the set are directional, among which $d_i^{k1}$ corresponds to $(x_i^1,y_i^1)$ , $d_i^{\mathrm{kt}}$ corresponds to $(x_i^t,y_i^t)$ , and $d_i^{\mathrm{kh}}\in P,h\in \{2,3,\dots ,t-1\}$ .

According to previous analysis, we need to calculate the multiple paths between O-D. This article uses the double-sweep algorithm ¹⁹ combined with the genetic algorithm (GA) to search the matching set of effective passenger hubs with meeting the requirements on smoothness (the turn angle is more than 90°) and maximum line length of the search area.

The genetic algorithm was developed by Holland ²⁰ for solving complicated optimization and search problems. With the growing studies on heuristics, the application of GA in complex adaptive systems has been given more and more attention.

The genetic algorithm is inspired by the mechanism of natural evolution including inheritance, mutation, selection, and crossover. In the algorithm, a candidate solution to an optimization problem is denoted by the notion of “chromosome,” which is encoded in certain manner. Usually, the coding system is binary represented, but other encodings (e.g. floating coding) are also possible. The process of genetic algorithm for the optimal solution is analogous to that of natural evolution which obeys the principle of “survival of the fittest.” In the genetic algorithm, the evolution is an iteration process where a population of chromosomes in each iteration is called a generation. The initial generation is produced at random. In a generation, the quality of each chromosome is evaluated with a fitness function which is usually an adaptation of the objective function of the model. Chromosomes with higher fitness are more likely to be picked out from the current generation to produce a new generation by means of duplication, mutation, and crossover. Then the new generation can be used in the next iteration. Dominated by the principle of “survival of the fittest,” the iteration process will converge and the global optimal can be obtained. In practice, the algorithm stops when either the threshold of iterations or a satisfactory fitness level is reached for the population.

The iteration number, the population size, the crossover rate, and the mutation rate are several parameters that have great impacts of the performance of GA. Large iterations or population number hold more potential to obtain global optimal solution but will also increase searching time. High mutation rate can confirm the diversity of solutions to avoid trapping in local optimal but at the cost of huge time consumption.

The detailed steps are shown as follows:

• Step 1. Select an encoding system; set population size = N; set maximum iterations = T; current iteration = t; obtain an initial generation Pop(t), t = 1;

• Step 2.

  Do while t < = T

   For i = 1 to N

     f_i = fitness(Pop_i(t))

  /*calculating the fitness of each chromosome of Generation t*/

   End for

   If (a satisfactory fitness level obtained) then

    End do

    print solution

   Else

    For i = 1 to N

      $p_i=\raisebox{1ex}{$f_i$}\!\left/ \!\raisebox{-1ex}{${{\displaystyle \sum }}_{i=1}^N{f}_i$}\right.$

  /*calculating the selection odds of each chromosome of Generation t*/

    End for

   End if

   Do crossover: CrossPop(t + 1)/*obtaining Cross Pop (t + 1) by means of “crossover”*/

   Do mutation: MutPop(t + 1)/* mutating part of chromosomes from CrossPop(t + 1) */

   t = t + 1

   Pop(t) = MutPop(t + 1)

  End do

Thus, the search process of genetic search can be seen in Figure 3.

Figure 3.

Flowchart of the genetic search.

The obtained matching set of effective passenger hubs is $B{D}_i=\{D_i^1,D_i^2,\dots ,D_i^k\}$ .

Determining the matching set of optimal passenger hubs

Next, we need to calculate the overall importance $E^j$ of each path in the obtained matching set $B{D}_i=\{D_i^1,D_i^2,\dots ,D_i^m\}$

$$E^j=\sum _{i=1}^n{E}_{i}j\in (1,2,\dots ,m)$$

(18)

$$E^k=max\{E^1,E^2,\dots ,E^m\}$$

(19)

where $E_i$ is importance indicator of passenger hub i, $n$ is number of passenger hubs in the matching set $D_i^j$ , and $E^j$ is overall importance of matching set $D_i^j$ .

Among all paths, select the path of the highest overall importance $E^k$ , which means the kth path is the matching set of optimal passenger hubs.

Adjusting entity paths at the path layer

The passenger hub matching set $B{D}_i=\{D_i^1,D_i^2,\dots ,D_i^m\}$ uses the anchor to determine passenger hubs and the general path direction. On the final path, passenger hubs are fixed. Therefore, all path plans are the combination of adjacent stations. To select an optimal path, we need to take two steps: first, distribute O-D distribution results in the future rail transit network via shortest-distance approach and obtain the value of passenger flow on the path; second, select and set up the entity paths among the virtual paths based on the distribution results.

Since passenger hubs are relatively close and usually locate at the network nodes, the searched virtual rail paths highly match the actual transportation network, as shown in Figure 4. To keep a high consistency between actual rail paths and passenger flow corridors, the study selects the optimal rail paths and sets up the rail path layout accordingly.

Figure 4.

Graph of rail path layout.

Case study of Hefei

Determining the morphology of the initial rail transit network

To elaborately show the morphology of the initial network, this article combined modeling zones according to their structure. First, build the distance matrix between zones according to the rail transit network plan, which is used to calculate the position importance of zones. Second, forecast the generated traveling needs of a zone and divide the value by the zone size, by which the transportation importance of the zone could be calculated. Third, combine the position importance and the transportation importance and get the overall importance of a zone, as shown in Figure 5.

Figure 5.

Importance distribution and initial network morphology map.

What to follow is to build the adjacent matrix and border matrix and to calculate the direction weights of searching adjacent zones based on the importance indicator, distance matrix, and forecasted O-D distribution results. As suggested above, traffic zones that have higher importance and locate in different zones should be chosen as the origin. In this case study, traffic zones 1, 37, and 63 were selected as origins and then we searched their revised adjacent zones. The search network covering 59 zones was produced and shown in Figure 5, by which all possible rail paths in the central city are listed in Table 3.

Table 3.

Possible paths in the initial rail network.

Name	Path
A	9-17-19-20-23-24-50-1-40-39-37-36-35-32-31-44
B	9-17-19-20-23-24-48-58-39-37-36-35-32-31-44
C	9-17-19-20-23-24-29-60-61-59-39-37-36-35-32-31-44
D	44-45-46-47-48-50-60-63-65-66-67-69
E	44-45-46-47-48-58-40-59-61-63-65-66-67-69
F	42-6-37-38-2-3-76-75-73-72
G	42-6-58-1-50-29-28-27-26-15
H	82-81-78-2-59-61-60-29-24-5-7-43
I	82-81-78-3-62-63-4-29-24-5-7-43
J	72-73-75-64-65-4-28-23-20-19-17-9
K	51-52-53-54-56-57-58-39-2-3-76-75-73-72
L	51-52-53-54-56-57-58-1-61-63-65-66-67-69
M	51-52-53-54-56-57-58-1-60-63-65-66-67-69

Generating the entity rail path

To form a rail transit network, two steps are involved: (1) build the network structure and morphology and (2) set up and optimize each rail path one by one. As an example, this paper selected line A to follow the steps based on the importance indicator.

Determining passenger hubs, path origin, and path destination

The path search area is the main traffic corridor at the east-west direction in the major town of Hefei. This study selected Changing Avenue and Dazhong Road as the origin and destination considering the urbanization trend of Hefei, the match with the rail transit network, connection modes between rail paths, and land use constraints in the neighboring area. Within the covering area of the main corridor, 50 passenger hubs were selected as alternative options.

Determining the optimal passenger hubs

Based on the optimization of passenger hubs, a directed graph including origin, destination, and hubs was built and then using the double-sweep algorithm, we obtained a set of alternative paths between the O-D. According to the calculated importance for each passenger hub, and each alternative path a final set including 28 optimal passenger hubs is obtained: {Changing Avenue of Nan gang Town,…, Large East Gate,…, Dazhong Road of Long gang Town}.

In the next procedure, a path distribution was made with the consideration of the real road situation, an implementation was conducted for virtual path in the hub layer, and the optimal path for line A was determined as shown in Figure 6.

Figure 6.

Passenger hubs matching and path optimization of line A.

Generating the initial network based on path-by-path searches

Following the path optimization of line A, other optimal paths could be searched. Moreover, key elements that are transfer stations and connection between multiple paths should be considered in the initial path search and analyzed in the formation of initial network plan for the major town of Hefei. The resulted initial network is presented in Figure 7.

Figure 7.

The initial network search diagram of Hefei.

Conclusion

As the initial network is the basic form of the final network plan especially in the respects of network size and morphology, it is key to the determination of ultimate rail transit network. Moreover, the important role of the initial network in modeling test on passenger flow and path optimization confirms its significance in city rail transit planning. To ensure the reliability of the initial rail transit network generated in the network planning, this article proposed an importance-based technique. It conducts the analysis from the plane, hub, and path perspectives and makes the network optimization path-by-path.

The case study of Hefei has proved its proficient advantages in three aspects. First, its analysis on the initial network is considered to be more supportive for its quantitative feature in the calculation on the overall importance and search direction weight. Second, all procedures in initial virtual network generation using the importance calculation in the indicator system, and the random search method reflect the station-anchoring theory and its aim at maximizing network coverage. Third, the application of the importance theory in the generation of the initial rail transit network makes it possible that the rail path setup and optimization are conducted quantitatively. In summary, this article contributes to both theories and practices in the rail transit research area.