An Improved Ant Colony Algorithm for Urban Bus Network Optimization Based on Existing Bus Routes

Abstract

Adding new lines on the basis of the existing public transport network is an important way to improve public transport operation networks and the quality of urban public transport service. Aiming at the problem that existing routes are rarely considered in the previous research on public transportation network planning, a public transportation network optimization method based on an ant colony optimization (ACO) algorithm coupled with the existing routes is proposed. First, the actual road network and existing bus lines were abstracted with a graph data structure, and the integration with origin–destination passenger flow data was completed. Second, according to the ACO algorithm, combined with the existing line structure constraints and ant transfer rules at adjacent nodes, new bus-line planning was realized. Finally, according to the change of direct passenger flow in the entire network, the optimal bus-line network optimization scheme was determined. In the process of node transfer calculation, the algorithm adopts the Softmax strategy to realize path diversity and increase the path search range, while avoiding premature convergence and falling into local optimization. Moreover, the elite ant strategy increases the pheromone release on the current optimal path and accelerates the convergence of the algorithm. Based on existing road network and bus lines, the algorithm carries out new line planning, which increases the rationality and practical feasibility of the new bus-line structure.

1. Introduction

A public transportation system is an important form of connection between various functional areas of a city. Its network layout and planning should track and reflect the occurrence and distribution law of passenger flow in the current stage of urban development in a timely manner. Based on a passenger-flow survey, the line network is optimized to make the distribution of line network capacity most in line with actual passenger flow, so as to facilitate residents’ travel and consider the operation benefits of public transport enterprises [1,2]. With the continuous changes of the external environment, such as urban expansion, the transformation of urban functional areas, and the increase of subway lines, the adjustment and optimization of public transport networks have become the routine endeavors of public transport management and operation institutions. In the case of imperfect informatization and digitization, field research is still the main method of bus-line network adjustment.

Public transportation network optimization is a complex line planning and multi-objective optimization problem, and there are many more mature methods available in this area [3,4,5,6]. Schöbel has summarized the planning models for various routes of the bus, rail, and subway. The ant colony algorithm (ACO) was found to exhibit unique advantages in solving multi-objective path-planning problems [7]. The ant colony algorithm (ACO) was first proposed by Dorigo et al. [8,9,10,11] and is a swarm intelligence algorithm that is constructed by simulating the foraging behavior of an ant colony to find an optimal path. It has also been widely used in the field of vehicle path selection and bus route planning in later research [12,13]. Poorzahedy et al. [14] took the minimization of total passenger travel time as the evaluation factor, used an ant colony algorithm to study the example of bus line network design, and verified the effectiveness of the ant colony algorithm in solving similar problems by comparing its performance with a genetic algorithm. Martynova et al. [15] took the maximization of the number of direct travelers per unit length as the evaluation index and used an ant colony algorithm to optimize the public transport network of Tomsk, Russia, and the results showed that an optimized transfer network has significantly reduced transfers and travel time. Hu et al. [16] proposed an ant colony optimization (ACO)-based approach to adjust existing bus lines in the transportation network. The end result showed that the method can achieve satisfactory bus lines with a low transfer rate and high direct rate. Giovanni et al. [17]. conducted a study on bus feeder planning by using an agent-based model that was based on (ACO) for the path finding of the least-cost route, finally covering the gap between public transport coverage and ridership in weak-demand areas.

Based on the above research, it can be seen that there are various optimization objectives for bus-line network optimization, such as maximum direct passenger flow [15], minimum operation cost [17], maximum bus network efficiency [16], and optimal individual accessibility [18]. An ant colony algorithm, genetic algorithm, and other optimization algorithms can be used to realize line network optimization [19]. Because the main objective of optimization is different, the strategy adopted in model construction will be different. In actual bus line planning, various factors must be considered, such as bus stops and subway connections, which need to limit the starting or end points of buses, as they restrict the universality of these algorithms. In addition, few studies have considered the impact of existing bus lines on the new planned lines, and canceling the existing lines to re-deploy the line network usually cannot meet the actual application needs. In view of this, a public-transportation network optimization method based on an ant colony algorithm that considers the existing public transportation network and aims to maximize direct passenger flow is proposed in this paper. The method in this paper does not make changes to the existing network, but only adds new bus lines to the existing network according to the needs of urban development.

2. Data

2.1. Study Area

The main built-up area of the high-tech zone in Zhengzhou City, Henan Province, China, was taken as the research area. The area is relatively independent among the districts in the main urban area of the city, with two main roads, as well as a subway line connected with the main urban area. Recently, due to the expansion of built-up areas and the suburbanization of industrial parks, a large number of new built-up areas lacking public transport coverage have brought inconvenience to the residents’ life and commuting. In addition, because of the influence of historical factors, such as road construction and passenger flow pursuit, the public transit re-routing coefficient of some sections is high, and the passenger flow competition is obvious. Thus, the operation efficiency of the line requires improvement.

At the time of data acquisition, there were 23 public transport routes in the study area (the up and down routes are considered only once herein). After removing the characteristic lines, such as the night shift and customization, 20 effective public transport lines remained, with a total length of 153.7 km. The length of the roads available for public transportation in the research area was 644.9 km, and the proportion of the line network was 11.9%.

On the whole, optimization of the public transport network in the study area takes two directions, namely improving efficiency and broadening. Along with the goal of increasing the coverage of public transport lines, improving the operation efficiency of the entire public transport network is also considered, and it is evaluated here mainly through direct passenger flow.

2.2. Data Acquisition

The data used in this study include the road network data in the research area, existing public transport route data, and OD travel data. The road network data are an abstraction of the actual roads that are available for public transportation in the study area. The actual accessible transit roads are the basis of public transport route planning. In this study, to simplify the problem, the real road network data were abstracted as the line-structured data in a Geographic Information System, mainly focusing on the connection relationship of every road section. The public transport route data are the existing lines in the study area. The OD data use mobile phone signaling data in the region, which are mainly used to study the population travel patterns. Here, the OD data only consider the migration in the study region without cross-regional travel. The main spatial distribution of the data in the research area is shown in Figure 1.

2.3. Data Fusion

The obtained original road, public transport line, and OD data cannot be directly applied to the subsequent analysis. According to the data structure required by the ant colony optimization (ACO) algorithm, the original data can be effectively fused. The overall modeling flow of the method in this paper is shown in Figure 2.

According to Figure 2, the model nodalizes the existing real bus routes based on the completed road nodalization representation. In the network optimization based on ACO, three main decision variables, namely passenger flow, route repetition coefficient, and non-linear coefficient, are added for constraint, where the data fusion process consists of the following 3 main steps before the line network optimization based on ACO.

• Road node expression:

The purpose of road node expression is to express road data as graph data structure based on road nodes. The specific approach involves the extraction and numbering of key nodes of the roads at the intersection, important road turning points, and end points not connected to other roads (see Figure 3) and then using these nodes to represent the road. In this way, the node expression of the roads is completed. In the specific application process, the adjacency matrix or adjacency table in the graph concept can be used to store the data. In this study, the adjacency matrix is used for expression. The study area abstracts N road nodes in total; then we have the following:

$$N=\{nod{e}_i|i\in \left[1,N\right]\}$$

(1)

• Node expression of public transport routes:

The actual public traffic lines can be regarded as a connection of multiple adjacent sections divided by nodes. To unify the public transport lines and roads, the public traffic lines are also turned into lines represented by nodes (see Figure 4). If there are M public transport routes in the study area, then we have the following:

$$\{\begin{array}{l}M=\{pat{h}_i | i \in \left[1,M\right]\} \\ pat{h}_m=\left\{list\langle nod{e}_i\rangle \right| i \in \left[1,N\right]\}\end{array}$$

(2)

• Spatial unification of OD data with road nodes and line nodes:

The purpose of this step is to aggregate the original OD data according to the road node data. The specific approach is to merge the beginning and end points of each piece of original OD data into the nearest road node (see Figure 5) and then aggregate them according to the node number of the beginning and end points. Finally, the OD data based on the road node number are obtained. It is actually the passenger traffic data based on mobile phones signaling data between the original OD nodes closest to the road nodes. Using $o{d}_{ij}$ to represent the direct passenger flow between nodes i and j, the passenger flow matrix OD can be expressed as follows:

$$OD=\{o{d}_{ij} | i,j\in \left[1,N\right]\}$$

(3)

3. Algorithm

3.1. Algorithm Procedure

The basic idea of the ACO algorithm [20,21] is that the ants walk on the initialized road network and select the intersection according to the set transfer rules, while they will release pheromones, which will volatilize according to the set conditions. After several iterations, the pheromone concentration on the optimal path will become higher and higher, and the ants will keep walking along the optimal path, and the algorithm will converge to obtain the final path-finding result. The ACO algorithm works efficiently in graph and network space [9,22]. Moreover, this algorithm has the advantages of parallelism, robustness, positive feedback, and good combinatorial ability [23]. Applying the ACO algorithm to the optimization problem of the actual public transport routes can effectively improve the operation ability of a public traffic system [24].

The classical ACO algorithm is used to find a feasible solution in a large number of feasible paths through the action mode of the entire ant colony [25]. Regional network optimization must plan multiple routes at the same time to optimize or improve the efficiency of the entire network. Here, we must improve the classical ACO algorithm to achieve the purpose of multi-path planning. In our method, the number of ant populations is set to the number of new bus routes to be added in the plan. Under the constraint of the evaluation factors of the entire public transport network, the path search, iteration, and optimization are completed through the entire ant population iteration. For path selection by ants, a Softmax strategy is used in this paper that is a widely used method in solving selection problems between multiple actions with different benefits based on machine learning [26]. The purpose of the Softmax strategy used in ant path selection is to increase the probability of choosing a high-yield action, while also giving the ants a certain chance to choose a lower-yield option to increase the exploratory nature of the algorithm and avoid falling into a local optimum and converging prematurely. The overall algorithm procedure is shown in Figure 6.

In the initialization process, it is assumed that the initial pheromones of all road sections are equal, and then the pheromones of the road sections between road nodes i and j are ${\tau }_{ij}=Ci,j\in N$, while C is the initialization constant. In the optimization process, the road segment pheromone, ${\tau }_{ij}$, will change with the incremental change of the pheromone left by the ant colony. In the entire line network optimization process, the transition probability calculation, pheromone update strategy, and the measurement method of the entire network performance in the ants’ path search process are the most important calculation procedures, which are introduced separately in the following subsections.

3.2. Transition Probability Calculation of Path Selection

In the abstract road network, in addition to the end of the road, any road node is connected to no less than two sections. When the ants arrive at an arbitrary node, there will be at least one node to choose as the next moving target. When the number of selectable nodes is greater than 1, how to finally select a node mainly depends on the transition probability of each node. The calculation of transition probability is related to the ultimate path obtained by the current ant search.

When combining the features of public transport route planning and the actual design command of the route, it is necessary to improve the transfer probability calculation method of the classical ACO algorithm. When calculating, in addition to the road pheromone residue that must be considered, three influencing parameters are added, namely passenger flow, route length, and non-linear coefficient. Among these, the residue of pheromone on the path is the embodiment of ant colony intelligence and the core of the ACO algorithm. The non-linear coefficient is the ratio of the actual traffic distance to the spatial linear distance between the start and end points of the road, which is an important indicator of the convenience of the route [27].

Ant k (k = 1, 2, …, m) decides the next node to visit based on the pheromone concentration on the connection path of each node. Let ${\tau }_{ij}\left(t\right)$ be the pheromone concentration of road segment $l_{ij}$ at moment t. The initial pheromone concentration of all road segments, ${\tau }_{ij}\left(0\right)=0$; $P_{ij}^k$, denotes the transfer probability of ant k moving from node i to node j at moment t. Then we obtain the following:

$$P_{ij}^k=\{\begin{array}{c} \frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha } {\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }}{{{\displaystyle \sum }}_{h\in J_k\left(i\right)}{\left[{\tau }_{ih}\left(t\right)\right]}^{\alpha } {\left[{\eta }_{ih}\left(t\right)\right]}^{\beta }} , j\in J_k\left(i\right)\\ 0 , j\notin J_k\left(i\right) \end{array}$$

(4)

where ${\eta }_{ij}\left(t\right)$ is a heuristic function that represents the expected degree of ant transfer from node i to j. $J_k\left(i\right)$ is the set of the next node that ant k can choose at node i, excluding the nodes that have been passed. The factors α and β are used to indicate the importance of the pheromone and heuristic function, respectively. In the original ant colony algorithm, the heuristic function is expressed as follows: ${\eta }_{ij}\left(t\right)=\frac{1}{d_{ij}}$, which uses the spatial distance between nodes as the heuristic factor to find the shortest path.

In this study, bus-route planning is not pursuing the shortest path as the priority goal, but needs to consider a variety of factors, such as inter-node passenger flow, route length, and route non-linear coefficient as heuristic factors. Here, the meaning of these heuristic factors and their mathematical representation in this paper need to be explained.

(1)

Since $o{d}_{ij}^{*}$ is the passenger flow heuristic factor, the purpose is to make the ants tend toward choosing the route with higher passenger flow. In order to maintain the consistency of order of magnitude in the calculation of each influence factor, $o{d}_{ij}^{*}$ is the result after the extreme difference normalization calculation of OD traffic.

$$o{d}_{ij}^{*}=\frac{o{d}_{ij}-mi{n}_{OD}}{ma{x}_{OD}-mi{n}_{OD}}$$

(5)

(2)

$F_{oj}$ is the non-linear coefficient heuristic factor of the bus route that denotes the non-linear coefficient from the starting point o of the route planning to node j, and it is calculated as follows:

$$F_{oj}=\{\begin{array}{c}\frac{{{\displaystyle \sum }}_{i=o}^{j-1}{d}_{i,i+1}}{d_{o,j}} , d_{o,j}>0\\ 1 , d_{o,j}=0 \end{array}$$

(6)

According to Formula (6), except for the case of overlapping starting and ending points (circular lines), the calculation result of the non-linear coefficient of the line will not be theoretically less than 1. According to the standard [27], its value should not be greater than 1.4. In order to make the ants more inclined to choose the route with a smaller non-linear coefficient, the inverse of $F_{oj}$ is taken as the non-linear coefficient heuristic factor in the calculation.

(3)

$R_{ij}$ is the existing route weight heuristic factor, which makes the ants more inclined to choose the nodes in the current road network through which no bus routes pass, and it is calculated as follows:

Let A be the set of nodes of the existing bus-line network, and let B be the set of nodes from the starting point of the currently planned line to node j. Then we obtain the following:

$$R_{ij}=\{\begin{array}{c}\frac{1}{N_{A\cap B}} , N_{A\cap B}>0\\ 1 , N_{A\cap B}=0\end{array}$$

(7)

where $N_{A\cap B}$ is the number of intersections of A and B.

Based on the above definition of heuristic factors, the heuristic function of the original ant colony algorithm can be modified as follows:

Let the following stand:

$${\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }=o{d}_{ij}^{*}{}^{\gamma }·{(\frac{1}{F_{oj}})}^{\omega }·R_{ij}{}^{\delta }$$

(8)

Then we obtain the following:

$$P_{ij}^k=\{\begin{array}{c} \frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[o{d}_{ij}^{*}\right]}^{\gamma }{\left[\frac{1}{F_{oj}}\right]}^{\omega }{\left[R_{ij}\right]}^{\delta }}{{{\displaystyle \sum }}_{h\in J_k\left(i\right)}{\left[{\tau }_{ih}\left(t\right)\right]}^{\alpha }{[o{d}_{ij}^{*}]}^{\gamma }\left[\frac{1}{F_{oj}}{]}^{\omega }\right[R_{ij}{]}^{\delta } } , j\in J_k\left(i\right)\\ 0 , j\notin J_k\left(i\right) \end{array}$$

(9)

where α, γ, δ, and ω are used to regulate the importance of the corresponding factors.

3.3. Pheromone Update Strategy

Pheromone updating is the core factor of swarm intelligence, and it must be executed after the ant colony completes the path search. A good updating strategy can effectively balance group wisdom and individual advantages. Pheromone updating includes the two processes of pheromone release and volatilization. Release means that the ant colony releases pheromones along the path, while volatilization is a pheromone characteristic simulating nature. The pheromone intensity of each line decreases due to volatilization over time. In order to accelerate the convergence of the algorithm, the pheromone is updated by using an elite ant strategy to increase the probability of the optimal route being selected. The elite ant strategy is also essentially an improvement of the original ant colony algorithm, which is designed to give an additional pheromone increment to the optimal path after each completed iteration [28]. The pheromone update strategy is as follows:

$${\tau }_{ij}{}_{new}=\left(1-\rho \right){\tau }_{ij}{}_{old}+{\displaystyle \sum }_{k=1}^m\Delta {\tau }_{ij}^k+e\Delta {\tau }_{ij}^{best} \rho \in \left(0,1\right)$$

(10)

where ${\tau }_{ij}{}_{old}$ is the original pheromone residue on the road section with the node number i,j at both ends; $\rho$ is the pheromone evaporation coefficient, and it indicates the volatile intensity of the pheromone; $\Delta {\tau }_{ij}^k$ denotes the concentration of pheromone released by the k-th ant at node i,j section; $\sum _{k=1}^m\Delta {\tau }_{ij}^k$ denotes the sum of pheromone concentrations released by all ants at the i,j section; $\Delta {\tau }_{ij}^{best}$ is the additional pheromone added to the optimal route; and e is the weight assigned to this increment.

$$\Delta {\tau }_{ij}^{best}=\{\begin{array}{c}\frac{1}{L^{best}} \left(i,j\right) \in T^{best}\\ 0 \left(i,j\right) \notin T^{best}\end{array}$$

(11)

where $L^{best}$ is the length of the optimal route, and $T^{best}$ is the set of nodes of the optimal route. Ant pheromone release using the Ant Quantuty System model is presented as follows:

$$\Delta {\tau }_{ij}^k=\frac{Q}{d_{ij}}$$

(12)

Q is the pheromone quantity left by the current ants, which can actually be determined by referring to the passenger flow on the ants’ current path; and $d_{ij}$ is the distance between nodes i and j.

3.4. Current Network Performance Evaluation

How to evaluate the performance of the current entire public transportation network is fundamental to network optimization. According to the actual situation, direct passenger flow, line overlap coefficient, and line coverage are all indicators used to evaluate network performance. Since the line overlap coefficient and line coverage factor have been considered in the transfer probability calculation, the direct passenger flow, $\eta$, of the entire network is mainly considered as the evaluation factor in the assessment of network performance. The calculation method of network direct passenger flow is as follows:

$$\eta =\sum _{m=1}^M\sum o{d}_{ij}i,j\in pat{h}_{m\in M}$$

(13)

where M is the number of public transport routes, $o{d}_{ij}$ the direct passenger flow between nodes i and j, and $pat{h}_{m\in M}$ is the line in the current public traffic network.

4. Results

4.1. Convergence Analysis

Because of the randomness of the ant’s probability selection at any node, the results of each iteration may be different. The final planning scheme must be determined after the network performance evaluation value reaches a stable interval; therefore, the convergence of the algorithm must be analyzed. In the experiment, the algorithm convergence evaluation was carried out with the change of the total direct passenger flow of five planned lines, and 1000 iterations were performed to obtain the trend of direct passenger-flow change (see Figure 7).

Over the 1000 iterations, the change in direct passenger traffic goes through several stages, with a short oscillation period before 20 iterations, stabilizing at around 580 persons/time between 20 and 90 iterations and experiencing three significant increases in each of the subsequent iterations, with an increasing amplitude of the curve. However, on the whole, with increasing iterations, the total number of direct passenger flow shows a trend of increasing in stages. Finally, after 350 iterations, the average growth rate and amplitude of the curve stabilize, indicating that the algorithm has entered a convergence state.

In the curves of Figure 6, the fluctuation of the change of direct passenger flow between the number of iterations is mainly affected by the randomness of the algorithm. To avoid falling into a local optimum, the Softmax strategy is adopted so that the algorithm still has some exploration ability after reaching the optimal solution.

4.2. Spatial Distribution of Line Network After Planning

Combined with the location of bus parking and the spatial distribution of OD nodes, five bus-line-planning starting points were determined. The line length and non-linear coefficient limits are 15 km and 2.0, respectively. Based on the convergence analysis, 1000 iterations were set, and the optimized bus-line network was obtained (see Figure 8).

In terms of spatial distribution, the new planning routes are mainly distributed in areas not covered by the original line network, i.e., mainly in newly built-up urban areas, effectively supplementing the gaps in the original line network. We performed an analysis of the reasons, on the one hand, because the starting point of the route planning is mostly chosen in the suburbs and, on the other hand, because the algorithm adds a route repetition heuristic factor, so that the newly planned routes do not pass through the road sections where there are already bus routes as much as possible. Such a planning result avoids adjustments to existing routes and is in line with the actual decision-making needs.

An overlay analysis of the planned network with the population distribution [29] in the study area (see Figure 9) also reveals that, while the new planned routes avoid passing through low-density areas, they are not all concentrated in high-density areas, as these high-density areas already have more established bus networks.

In addition, there are several newly built areas in which roads have just been constructed, and the construction of residential and related supporting facilities has not been completed, with low occupancy rate and low population density (area A in Figure 8). The algorithm avoids passing through such areas when performing route planning, partly because the OD traffic heuristic factor is considered in the path transfer probability calculation and partly because the overall network performance evaluation also uses the total amount of OD traffic as the basis for route selection. This result helps protect the operational efficiency of the bus company.

Overall, the overlap between the new planned routes and original bus routes in the region is low, maintaining a relatively low level of duplication ratio. The planning results show that the new routes have concave–convex directions in individual sections (area B in Figure 8). The reason for this phenomenon is that these sections are characterized by high passenger flow and high bus duplication, and the algorithm must avoid the latter, while aiming to achieve the former in the process of planning bus routes.

4.3. Comparison

After optimization of the line network is completed, it is necessary to compare the optimized line network with the original one to quantify and analyze the effect of optimization. The main evaluation indicators and quantitative statistical results are shown in

Table 1. Comparison of indicators before and after bus network optimization.

Evaluation Items	Before Optimization	After Optimization	Changes
Number of bus lines	20	25	25%↑
Total length of bus lines (km)	153.7	222.3	44.63%↑
Length of roads which bus passes (km)	77.0	115.8	50.39%↑
Proportion of bus lines to road network (%)	11.9	17.9	5%↑
Proportion of overlapping lengths (%)	1.996	1.920	3.81%↓
Number of direct passenger traffic	589	713	21.05%↑
Number of bus stops	376	450	19.68%↑
5 min service area (km²)	30.10	36.48	21.20%↑

.

The analysis results show that the algorithm can obtain more reasonable bus lines without changing the structure of the existing line network. On the one hand, the number of bus lines, total length, proportion of bus lines to the road network, 5 min service area, and direct passenger traffic have increased, indicating that the newly added and planned bus routes are effective in filling the bus service gaps and increasing the spatial service scope and service capacity of the route network, which can also be proved by combining these results with the analysis of the spatial distribution of the bus route network. On the other hand, compared with the preplanned bus network, the proportion of duplicate routes in the new bus network decreases, and the number of direct passengers increases, indicating that the consideration of the complex line coefficient and the network performance evaluation based on direct passenger traffic in the calculation of transfer probability have had an effect.

The total length of roads in the study area is 252.02 km, and the area is 69.32 km². According to the standard [27], the bus-network density should reach 3–4 km/km² in the urban center and 2–2.5 km/km² in the urban fringe. Based on the current area of the study area, the line network density was 2.22 km/km² before optimization and reached 3.20 km/km² after optimization. Considering that there is a large area of new development zone in the study area, the current population density in these areas is still relatively low, and they belong to the urban fringe areas, the planned line network density is fully able to reach the demand standard.

The distribution of bus stops along the new planned routes was also analyzed. Although the siting of bus stops was not the goal of this study, examining the availability of existing stops for the new planned routes will help analyze the implement ability of the scheme. According to the current planning scheme, to put the planned route into operation, considering the two-way traffic on the line, then about 74 new stops are needed and 78 existing stops can be utilized. The existing stations that can be utilized for the new line are able to reach 51.32%, and these available existing stations represent 20.75% of the total number of existing stations in the study area. With the constraint of minimizing the duplication of new lines with existing lines, this level of station reuse can be achieved to ensure the effective integration of the new planned lines with the existing network and meet the interchange needs of passengers, indicating that such a planning scheme is implementable.

5. Discussion and Conclusions

5.1. Discussion

The method in this study is an improvement of the classical ACO algorithm, allowing a user to customize the planning starting point of new bus routes based on the existing line network according to the characteristics and practical needs of the study area. The result of the planning is the optimization of the existing bus-line network that does not affect the already existing bus lines in operation and is more in line with practical application scenarios.

The Softmax strategy is used for the calculation of transfer probability of path selection, which increases the exploratory nature of the ants, while significantly increasing the randomness of the results, which can be clearly observed in the convergence curve of the overall bus line network evaluation results. However, the strategy of elite ants helps the algorithm achieve faster convergence, and, eventually, the line network evaluation results stabilized after 350 iterations.

By analyzing the spatial distribution of the optimized bus network and the main quantitative evaluation indexes, it can be found that the algorithm has achieved the expected planning effect, while filling the gaps in the original line network, and it can effectively avoid areas with low passenger flow. Moreover, the overall capacity and capacity of the network were improved, and the total length of the line, proportion of the line network, direct passenger flow, and other major indicators have increased, while the proportion of the entire line network was reduced, indicating that the overall structure of the bus network was optimized.

The line network evaluation uses the sum of the direct passenger traffic of the entire network, and the main consideration is to optimize the overall capacity of the line network while considering the operational efficiency of the bus company. However, the evaluation of the bus-line network performance is multifaceted and includes many aspects, such as bus-line structure, passenger arrival time, bus operation performance, and bus-service level. The process of optimizing the line network here does not take all dimensions of bus-line network evaluation indicators into account. In this study, the evaluation is mainly carried out from the aspects of route structure, bus-line overlap coefficient, and bus-passenger flow under ideal conditions. Subsequent studies need to verify and optimize the algorithm with the actual operation of the scheme. In addition, the impact of the placement of the new line stations and the choice of the starting point of the line on the overall scheme are also issues that need to be specifically studied and explored in depth, and these will be considered in future studies.

5.2. Conclusions

In this study, an ant-colony-algorithm-based optimization method for a regional bus-line network was proposed based on the consideration of existing bus route structures. While increasing the path search range and achieving path diversity, the convergence of the algorithm is accelerated by an elite ant strategy. The method can automatically plan a reasonable bus route by providing the starting point on the basis of securing direct passenger flow, length of the line, line non-linear coefficient, local non-linear coefficient, bus-line overlap coefficient, and other factors to ensure the reasonableness of the line and line direction. Moreover, this approach also avoids the phenomenon of a high degree of overlap of bus lines in some busy sections. Finally, experiments of line network planning were conducted to verify the feasibility of the method and the reasonableness of the results based on the comparison of the main indicators before and after line network optimization.

For new urban areas that are developing at a fast pace, the existing bus network often fails to cover the newly developed areas and has difficulty in meeting the demand of new bus users. The approach in this study achieves capacity enhancement of the existing network while balancing operating costs and efficiency. It can provide a reference solution for route optimization in areas with uneven spatial coverage of bus lines. The algorithm also has a relatively large application space for single-point path planning, i.e., metro articulation.

Practice shows that the algorithm can achieve good results in county-level bus-line optimization. It can be used as a reference for bus-line network optimization and also as an alternative method to increase feeder lines and optimize suburban coverage in metropolitan areas.