Application of an Improved A* Algorithm for the Path Analysis of Urban Multi-Type Transportation Systems

Abstract

The modern urban transportation service network could be split into unrestricted and restricted networks depending on whether travelers face limitations in route selection. Along with the continuous expansion of the city, it is difficult for travelers to find a more reasonable travel solution when confronted with such a complex transportation service network, which combines both unrestricted and restricted networks, especially for the park-and-ride (P&R) travel mode. This paper addresses the issue of route analysis in modern urban transportation service systems to provide travelers with reasonable travel solutions based on multiple types of transportation services. An improved A* algorithm is proposed to address the optimal path analysis for restricted networks to provide reasonable travel solutions for public transportation trips. Furthermore, by establishing the topological relationship between restricted and unrestricted networks, this paper presented an improved A* algorithm based on hybrid networks that solves the optimal path analysis problem for P&R trips, bringing convenience to many urban travelers.

1. Introduction

Multiple transportation lines mix and coexist in a modern urban transportation system [1]. Urban roads, overpasses, and underpasses constitute the city’s road traffic network, while urban rail transit, bus lines, tourist lines, and airport express lines constitute the urban public transport network. The urban transport service network is made up of these overlapping and crisscrossing traffic service lines. For instance, the public transportation network in Shanghai, China, already included more than 1000 public transportation lines by 2022, encompassing subway, light rail, bus, and airport express lines, among others [2]. Travelers are typically bound to the specified line and can’t request route adjustments from bus drivers to accommodate their requirements. Meanwhile, other means of transportation, such as walking, bicycles, taxis, and private cars, provide additional travel options. Based on whether travelers’ route choice is restricted, the urban traffic service network is split into unrestricted and restricted networks, with both networks amalgamating into a hybrid network in most instances. Such a hybrid network represents the essence of the modern urban traffic service system.

Moreover, many global metropolises have gradually developed and evolved into satellite town mode due to ongoing urban expansion [3,4]. The park-and-ride (P&R) traffic mode, in which travelers drive to a transfer parking lot in urban suburbs and then use public transportation to reach their destination in the city center, has provided people with a new way of life and travel to solve the traffic challenges between satellite towns and central urban areas [5,6,7,8,9]. The P&R traffic mode supports integrating the road transportation system into the urban public transportation system and promoting higher use of urban public transportation systems. Taking Shanghai as an example, by the end of 2022, there were 20 P&R transfer parking lots close to the satellite urban rail transit stations. The P&R traffic mode formally complies with the idea of low-carbon transportation, which may significantly lessen traffic congestion and reduce carbon emissions [9]. It is often challenging for travelers to develop a practical travel plan given the intricate transportation service network and wide range of travel alternatives [10,11]. The growing travel demand for P&R parking and transfer mode in particular compels travelers to develop a reasonable travel plan in the hybrid network comprising both road traffic and the public transportation network, introducing considerable difficulty for travelers. The P&R traffic mode has been an important part of the hybrid urban traffic service network. Therefore, based on various forms of traffic services, this paper solves the problem of path analysis in the modern urban traffic service system and provides suitable transportation plans for travelers.

A large number of specialists and researchers have carried out extensive studies on path analysis algorithms, with the Dijkstra algorithm [12,13,14,15,16,17] and the A* algorithm [18,19,20,21,22,23,24] standing out as the most representative. The majority of these studies have primarily focused on a single transportation network. For example, Khaing et al. [25] applied Dijkstra’s algorithm to analyze the shortest bus paths in Yangon City based on bus transit network data. Daci and Tola [26] solved the problem of shortest path analysis for Tirana’s urban tram network using the Dijkstra’s algorithm, while Ray et al. [27] focused on cab shortest path analysis. Herlawati et al. [28] implemented the shortest path travel scheme for tourists in the urban Bekasi road network using the A* algorithm within the Android system. Yudha et al. [29] tackled the path analysis of tourist attractions in Java using the A* algorithm, considering factors such as the shortest distance and traffic flow as the primary evaluation criteria. Ariyanto et al. [30] improved the A* algorithm by incorporating time, distance, and altitude to construct a heuristic function, solving the optimal and fastest cycling routes in the bicycle network in the city of Batu, Indonesia. Li et al. [31] applied the A* algorithm to solve the optimal path analysis problem for the public transportation network in Incheon, South Korea, using the distance to Manhattan as a heuristic function. Wang et al. [32] designed a dynamic planning algorithm based on the urban transit commuting path planning method, which firstly calculates the shortest path between residential and office nodes using the shortest path algorithm, and then calculates the optimal transit travel plan on the shortest path using the dynamic planning algorithm. While the mentioned literature optimizes and improves path analysis algorithms in a single network of urban transportation, most of the above algorithms are evaluated in terms of distance, without comprehensively considering factors like time, transfers, and walking. Limited research has been conducted on hybrid network-based path analysis algorithms. Some have proposed hierarchical hub location models, treating hub locations as transfer stations, and conducting optimal path analysis by searching the paths from ordinary station to transfer station and vice versa [33,34,35]. However, these algorithms often use the number of transfers as the primary evaluation criterion, and neglect factors like the distance, time, and cost. Additionally, they struggle to solve the problem of this path analysis of hybrid networks, when travelers need to arrive at the next transfer station by walking, biking, or cab. Zhou et al. [36] used the A* algorithm, constructing heuristic functions based on straight-line distances, travel speeds, and fares, to solve the problem of travel between urban and intercity transportation networks. While effective for transferring between various restricted networks, such as subways, high-speed railways, and airplanes, this algorithm does not involve unrestricted networks, such as road networks. In addition to the typical constrained networks, such as urban transportation networks, there are also maritime berths and aviation networks that fall into the category of restricted networks, and there is corresponding research on their path planning [37,38].

To solve the urban multi-modal transportation mixed travel path planning problem, this paper firstly constructs a hybrid network designed for path planning analysis. This is achieved by establishing the topological relationship between restricted and unrestricted networks. Subsequently, an innovative multivariate heuristic function is proposed. By incorporating a multivariate constraint onto the distance heuristic function, this improvement aims to optimize and refine the traditional A* algorithm. The number of interchanges, travel time, and travel cost, which are the key concerns of travelers, are also added to the heuristic function as constraint functions to realize the different needs of travelers within both restricted and unrestricted networks, achieved through a controlled prioritization of individual evaluation criteria. The contributions in this paper focus on the following three aspects:

1.

Design a multivariate heuristic function to solve the limitation of a single evaluation standard in the traditional A* algorithm. This improvement fully considers the traveler’s experience and feelings. The application of the algorithm aims to furnish travelers with an optimal and highly comfortable travel plan.

2.

Propose an improved A* algorithm tailored to restricted networks, specially designed to offer travelers the optimal travel plan for the combination of subway, bus, ferry, tourist line, airport express, and other modes of transport interchange in the urban public transportation network.

3.

Put forth an improved A* algorithm designed for hybrid networks to solve the problem that the traditional A* algorithm is only suitable for path analysis of a single transportation network, which realizes an optimal travel plan for travelers to provide a combination of public transportation and P&R transfer.

The path analysis algorithm proposed in this paper has been applied in the Shanghai public information query system. This system incorporates diverse data, including various levels of Shanghai road networks, 8303 bus stops, 1394 bus lines, 18 rail lines, and 20 P&R stations. According to the improved A* algorithm proposed in this paper, travelers can input the arbitrary starting and ending points, and quickly output the optimal travel plan based on the aforementioned data from Shanghai’s public road transportation network.

2. Methods

2.1. Improved A* Algorithm for the Path Analysis of Restricted Networks

The A* algorithm has been widely used in the path analysis of unrestricted networks as a heuristic search approach with great efficiency and flexibility. In this study, the number of transfers is employed as the heuristic function H(N) of the A* algorithm, with the transfer matrix used to calculate the minimum number of transfers between any two sites within the restricted network. Additionally, an improved A* algorithm suitable for the path analysis of restricted networks is also proposed.

2.1.1. Traditional A* Algorithm

The A* algorithm must calculate the evaluation function F(N) each time a sub-node is generated to estimate the optimal path cost of the constraints of the starting node through the nodes to reach the destination node. When nodes are expanded, the nodes with the smallest F(N) value are always selected as the expansion object from the pool of nodes to be expanded. This approach ensures that the search progresses in the most promising direction. The following formula is the expression for F(N):

F(N) = G(N) + H(N).

(1)

Here, G(N) represents the estimated value of the actual cost G’(N) of the optimal path from starting node O to any node N (G(N) ≥ G’(N)). The heuristic function H(N) is the estimated value of the actual cost H’(N) for the optimal path from node N to target node D (H’(N) ≥ H(N)) [5]. The selection of heuristic function H(N) is rather important. It lacks a stable mathematical model and mainly depends on the prior knowledge of the characteristics of the problem to be solved, as well as strategy tricks for it is resolution.

Generally, H(N) is commonly used as the distance formula between two points to estimate the cost of traveling from point N to ending point D in the future. G(N) represents the previous cost from starting point O to point N, e.g., the sum of the distances traveled on each path. In road networks, the distance heuristic function can provide relatively reliable and effective path planning for travelers. During their travel, people are more concerned about the number of transfers, travel time, travel costs, and walking distance in public transportation networks. However, the traditional heuristic function cannot meet these specific needs. In this paper, we optimize the heuristic function and improve the traditional A* algorithm to solve the above problems.

2.1.2. Multivariate Heuristic Function Optimization

Considering the factors of interest to the traveler, the heuristic functions for both public transport networks and road networks are optimized as follows:

$$H\left(N\right)=\left\{\begin{array}{c}{D\left(n,d\right)}_{}\\ {Q\left(n,d\right)}_{}\\ {T\left(n,d\right)}_{}\\ {C\left(n,d\right)}_{}\end{array}\right.$$

(2)

where n represents the ID sequence number of any point N, and d denotes the ID sequence number of the ending point D. The optimized heuristic function in the above equation is called the multivariate heuristic function. Here, D represents the distance from point N to point D, Q denotes the number of required transfers from point N to point D, T represents the time required from point N to point D, and C denotes the cost required from point N to point D. The different needs of travelers in restricted and unrestricted networks are realized within the heuristic function by prioritizing the control of each evaluation criterion. In a restricted network, the travel time and travel cost (fare) of public transportation between any two stations are easily accessible, and Section 2.1.3 will focus on how the number of transfers between any two points is calculated to obtain them. The aforementioned travel time, travel costs, and transfer matrices between any two stations can be pre-generated in batches during initialization, which can greatly optimize the execution efficiency of the algorithm. Here, the walking distance is not included in the heuristic function, mainly considering that the walking distance needs to be calculated according to different starting and ending locations in the road network, which will affect the execution efficiency of the algorithm. In this study, walking distance is used as a sorting condition to prioritize the searched travel plans.

2.1.3. Transfer Matrix

Before introducing the transfer matrix, let’s look at the adjacency matrix and its weight matrix.

Figure 1 illustrates a restricted network composed of two lines, R₁ and R₂, with nodes 1–6 representing sites, and the edges in the network connecting between these sites. Each line has a predetermined direction, and there may be one or more public sites between them.

The adjacency matrix, commonly used in network analysis, expresses the connectivity between nodes within a network. Similarly, for a restricted network, the adjacency matrix may be used to express the connectivity between sites. The element M_ij = k in the matrix indicates that there are k service lines that link the sites i and j, and the diagonal element M_ii is 0. Figure 2 depicts the adjacency matrix for sites 1 to 4 in Figure 1. M₂₄ = 2, indicating there are two lines, R₁ and R₂, connecting site 2 to site 4, establishing a connection between these sites. The weight matrix $M_{ij}^n=k$ derived from the adjacency matrix T indicates that there are k plans from site i to site j through n − 1 transfers. For instance, $M_{24}^2=4$ means that there is one transfer from site 2 to site 4, and there are four plans, namely R₁ (2→3) to R₁ (3→4); R₁ (2→3) to R₂ (3→4); R₂ (2→3) to R₁ (3→4); R₂ (2→3) to R₂ (3→4). While it is difficult in practice to transfer to the same automobile, this circumstance exists in theory.

As mentioned earlier, the adjacency matrix and its weight matrix can be used to determine if any two points at varying numbers of transfers are connected (at least one transfer plan) or detached. Thus, obtaining the minimum number of transfers from site i to site j, i.e., the minimum number of transfers required while there is at least one transfer plan from i to j, is simple. The transfer matrix element Q_ij = n implies that the minimum number of transfers from i to j is n − 1. The calculation steps for the transfer matrix are as follows:

• Establish an adjacency matrix among sites and clear all elements of transfer matrix Q.
• Calculate the weight matrix $M^n$ of the adjacency matrix, where n starts from 1 and accumulates sequentially.
• Compare $Q_{\mathit{ij}}$ and $M_{ij}$ in order; if $Q_{\mathit{ij}}=0$ and $M_{ij}^n\ne 0$, then $Q_{\mathit{ij}}=n$.
• Repeat Steps 2 and 3 until all elements in Q, except for the diagonal, are non-zero, and the loop ends.

The transfer matrix for sites 1–4 is shown in Figure 3. The diagonal elements and the elements that cannot be accessed, regardless of the number of transfers between two points, are both set to 0 in this case.

2.1.4. Implementation Steps of the Improved A* Algorithm for the Path Analysis of Restricted Networks

In this algorithm, for a restricted network, the multivariate heuristic function H(N) is used to estimate the cost of traveling from any point N to reach the ending point D. In a restricted network, the shortest distance is no longer the most concerning travel criterion, as travel time and distance are correlated; generally, the longer the time, the larger the distance. Consequently, the distance priority in the multivariate heuristic function is lowest, and the distance is negligible, which means that the number of transfers, travel time, and travel cost become the key travel criteria in the restricted network. Therefore, G(N) denotes the price, including the number of transfers, the travel time, and the travel costs, paid from starting node O to any point N. During the data pre-processing stage, the number of transfers, time, and cost between any two points in the restricted network can be pre-stored in an array list, which makes it easy to obtain the estimated cost H(N) for reaching the ending point D from any point N. Thus, the price F(N), including the transfer number, travel time, and travel costs, paid from the starting node O to the ending point D through any point N, can be efficiently calculated in real time during the execution of the algorithm. The main steps of the improved A* algorithm of path analysis for restricted networks (Figure 4) are outlined as follows:

• Load data for restricted networks, and calculate the G(N), H(N), and F(N) values of the starting node O, which are respectively represented by g, h, and f. According to the previous analysis, $g_{0 }=\left\{\begin{array}{c}0\\ 0\\ 0\end{array}\right.$, $h_0={\left\{\begin{array}{c}{Q}_{od}\\ T_{od}\\ C_{od}\end{array}\right.}_{}$, ${ f}_0=g_0+h_0$, where ${ Q}_{\mathit{od}}$, $T_{od}$, and $C_{od}$ are the paid cost from O to D. Furthermore, the O node is added into the array ExNodes.
• If the array ExNodes is not empty, select node M with the minimum f value from ExNodes, and expand node M. The minimum value of f is calculated according to the following rules. First, if the values of Q_od are not equal, comparing the values of Q_od, the minimum value of f is that the smallest Q_od belongs to f. If values of Q_od are equal, comparing the values of T_od, the minimum value of f is that the smallest T_od belongs to f. If the values of T_od are equal too, comparing the values of C_od, the minimum value of f is that the smallest C_od belongs to f.
• The expansion steps of node M are as follows.

  (1)

  Search for nodes adjacent to M, and calculate their corresponding g, h, and f values. The method how to search for nodes adjacent to M is to search for nodes adjacent to M via the line topology connection. For any expanded nodes E of M, if E and M are on the same line, then $Q_{\mathit{oe}}={ Q}_{\mathit{om}}$; otherwise, $Q_{\mathit{oe}}={ Q}_{\mathit{om}}+1$. Moreover, $h_e=\left\{\begin{array}{c}{Q}_{ed}\\ T_{ed}\\ C_{ed}\end{array}\right.$.

  (2)

  Evaluate whether node E coincides with the nodes in the current array ExNodes. If node E coincides with node P in ExNodes, $Q_{\mathit{oe}} <{ Q}_{\mathit{op}}$, node P in Exnodes is replaced with node E. If $Q_{\mathit{oe}}>{ Q}_{\mathit{op}}$, node E is deleted. If $Q_{\mathit{oe}}={ Q}_{\mathit{op}}$, comparing the values of T, if $T_{\mathit{oe}} <{ T}_{\mathit{op}}$, node P in Exnodes is replaced with node E. If $T_{\mathit{oe}}>{ T}_{\mathit{op}}$, node E is deleted. If $T_{\mathit{oe}}={ T}_{\mathit{op} }too$, comparing the values of C, if $C_{\mathit{oe}} <{ C}_{\mathit{op}}$, node P in Exnodes is replaced with node E. If $C_{\mathit{oe}}>{ C}_{\mathit{op}}$, node E is deleted.

  (3)

  If there is no coincidence node between E and that in ExNodes, the status of node E is recorded and added into ExNodes.

• After the expansion of node M, the best path from O to M is recorded.
• Judge whether node M is the ending point D. If M is not the ending point, continue to select the node M with the minimum value f from ExNodes to expand, and repeat steps 2–4 until it reaches the ending point D.
• If M is the ending point D, output the travel plan from O to D, and the algorithm ends.

The A* algorithm’s performance is affected by two main factors: determining how to sort the sequence of nodes to be expanded and checking the coincidence problem for each generated sub-node. The former uses a heap to store the nodes to be expanded, while the latter stores all the generated sub-nodes with varying states in a search tree to improve search performance.

2.2. Improved A* Algorithm for Path Analysis of Hybrid Networks

2.2.1. Hybrid Networks Topology Relationship

In practice, people’s travel is frequently not confined to one mode of transportation; for example, travelers may desire to reach the next transfer site by walking, cycling, taking a taxi, or using a private car. Alternatively, they might take a bus and then transfer to a taxi to reach their destination. An unrestricted urban road centerline network includes modes such as walking, cycling, private cars, and taxis. The topological relationship between restricted and unrestricted networks must first be analyzed to solve the path analysis problem.

In real life, there are two kinds of restricted networks. One is the restricted network represented by rail transportation as shown in Figure 5a(R₁). Since rail transit vehicles do not run on the road, there is no direct topological relationship between the restricted network and the road centerline network. A topological relationship exists only between the rail transit stations and the unrestricted network, as depicted in Figure 5b, indicating the road section where the rail transit station is located. Another type of restricted network, represented by bus lines as shown in Figure 5a(R₂), has a strong topological relationship with the road centerline network, given that the bus operates on the road, as illustrated in Figure 5c. Bus stops are usually positioned along the road centerline, and bus lines are composed of entire or partial borders of many road centerlines. For example, bus line R₂ (5→2) is formed by road centerlines E_5,7, E_7,8, E_8,9, E_9,10, and E_10,2. The relationship between the two restriction networks and the road centerline is depicted in Figure 5d. Regardless of the mode of transportation adopted, the travelers will travel along the urban road network.

2.2.2. Implementation Steps of the Improved A* Algorithm for Path Analysis of Hybrid Network

The relationships between nodes and lines, as well as the road centerline, are established for the restricted network. On this basis, the improved A* algorithm for path analysis of the restricted network, as described in Section 2.1.4, is expanded to develop path analysis algorithm based on a hybrid network. The main steps of the improved A* algorithm for hybrid network path analysis are outlined below, as shown in Figure 6.

• Steps 1–3 are identical to those outlined in the algorithm for path analysis of the restricted network in Section 2.1.4.
• Following the expansion of node M, assess whether M corresponds to a P&R parking and transfer station. If not, the following algorithm is the same as that in Section 2.1.4. Otherwise, load data from the unrestricted network.
• Determine which node of the starting node and ending node of the travel route may be the driving node. It is the starting node or destination of the traveler’s driving. According to the P&R transfer characteristics, the driving node is generally located in the suburbs of the city. Thus, if neither the starting node nor the ending node is in the suburbs, or if both are, select a city center point, and judge which node is farther away from the city center point, designating it as the driving node.
• Calculate and record the best path from O to M in the unrestricted network if the starting node O is the driving node. In this step, the number of transfers in the multivariate heuristic function does not work for unrestricted networks and the number of transfers is negligible. H(N) is chosen as the distance, time, and cost consumption between two nodes to estimate the cost from N to ending point D in the future. G(N) represents the cost already paid from O to N, e.g., the total consumption of traversing each path. The next algorithm steps are identical to the algorithm 4–6 steps in Section 2.1.4.
• Calculate and record the optimal path from M to D in the unrestricted network, which is the road network, if the ending node D is the driving node.
• Output the travel plan from O to D and conclude the algorithm.

In summary, the switching between restricted and unrestricted networks in hybrid network is accomplished via the P&R transfer point and the topological relationship between unrestricted and restricted networks. Meanwhile, the multivariate heuristic function realizes the different needs of travelers in restricted and unrestricted networks by prioritizing the control of each evaluation criterion. The A* algorithm is used to search for the respective optimal path and, finally, a complete optimal path based on hybrid networks is obtained.

3. Algorithm Implementation and Case Study

3.1. Algorithm Implementation

The path analysis algorithm proposed in this paper has been applied in the Shanghai Public Information Query System, which contains the data of the Shanghai road network of all grades, 8303 bus and rail stations, 1394 bus lines, 16 rail lines, and 20 P&R stations. Employing the improved A* algorithm proposed in this paper, the following tasks were accomplished in the implementation of the algorithm to realize the input of arbitrary starting point and ending point and quickly output the optimal transfer plan for the aforementioned public road traffic network data in Shanghai.

3.1.1. Data Pre-Processing

There are many different types of bus lines in the city, including special bus lines, airport express lines, tourist lines, and general lines, with many stops overlapping across these lines. In addition, rail stations and bus stations often coincide to facilitate interchanges. In this paper, the bus and rail transit data are pre-processed before the implementation of the algorithm, and the adjacent stations are merged to facilitate the subsequent implementation of the algorithm. Considering the characteristics of bus stops and rail stops in Shanghai, the rules of stop merging are as follows:

• Merge bus stops within 100 m intervals.
• Merge rail stations within 300 m intervals.
• Merge bus and rail stations within 500 m intervals.
• For the merged stations, store the ID of the merged station and the corresponding line ID.

3.1.2. Generation of Transfer Matrix

Following the data pre-processing, the transfer matrix is initially generated by batch processing, adhering to the transfer matrix generation algorithm for all stations, which includes bus stations and rail stations. The transfer matrix is implemented as a pre-generated file to be called during the implementation of the algorithm. Figure 7 illustrates the local schematic diagram of the transfer matrix.

3.1.3. Data Structure of the Expanded Node

In real life, the stations within the traffic network (Figure 1) serve as bus or rail transit stations for restricted networks and road intersections for unrestricted networks. In this algorithm, it is referred to as an expansion node—ExNode. The data structure of an expanded node is shown in

Table 1. The data structure of the expanded node.

Field Type	Field Name	Field Meaning
Integer	NodeID	The ID of an expanded node
Bool	bSameLine	Whether the node and the expanded node are in the same line? If yes, the value is true; otherwise, the value is false.
Bool	bStartPoint	Is it the starting point? If yes, the value is true; otherwise, the value is false.
Bool	bDestination	Is it the destination? If yes, the value is true; otherwise, the value is false.
Bool	bPR	Is it the P&R? If yes, the value is true; otherwise, the value is false.
Short	g	The value of G(N) from the starting node O to the expanded node N.
Short	h	The value of H(N) from the expanded node N to the ending node D.
ExNode	pLastNode	The last node of the expanded node.

. For restricted networks, the route pertains to the bus line or rail transit line, whereas, for unrestricted networks, the route corresponds to the road center. In addition, the expanded node also stores the judgment value of the node property to identify whether the node is the starting point, the ending point, or the P&R transfer point. Furthermore, the values of G(N) and H(N) are also stored in the expanded node as the key judgment elements when searching for the optimal path. Finally, the last connection node pointer of the node is also stored in the expanded node, which is used to establish the pointer linked list of the expanded node.

3.2. Algorithm Applications

The following arithmetic example randomly selected 10 coordinate points in Shanghai, as shown in

Table 2. Starting and ending points of algorithm instances.

Point No.	Name	Coordinate X	Coordinate Y
1	The intersection of Boxue Road and Fengnian Road	−16,337.7225	13,934.2415
2	Fashion Valley Creative Par	−28,572.1326	−22,363.2356
3	The intersection of Zhenhua Road and Fuping Road	−5873.8770	3594.2072
4	The intersection of Wuning Road and Zhongshan North Road	−5242.9461	988.5317
5	Shanghai Railway Station	−1496.1732	1535.3135
6	Intersection of Laiyang Road and Dongbo Road	10,788.9938	5577.3211
7	People’s Square	326.9187	79.0569
8	No. 2 High School of East China Normal University	11,500.3261	−3554.2670
9	Yongjingyuan of Xinjiangwan City	5180.1871	11,049.6381
10	The intersection of Qingyu Road and Xinyu Road	−10,740.1864	1314.6496

, the selection principles of 10 coordinate points are as follows:

• Located in the central city and suburban areas of Shanghai, respectively.
• Covering all administrative areas of Shanghai as much as possible.

In this paper, 10 coordinate points are arbitrarily selected within the administrative boundaries of Shanghai. These points include road intersections, schools, residential campuses, business parks, transportation hubs, landmarks, etc., and make sure that the 10 points can cover the suburbs, central towns, downtown areas, Pudong area, and Puxi area of Shanghai. These 10 points are then designated as both the starting and ending points for one another. The algorithm proposed in this paper is employed to search for the optimal travel plan. If there is a P&R transfer station in the search path, the travel plan gives priority to the P&R transfer combination plan, which is also in line with the current trend towards low-carbon travel. The case study is shown in Appendix A.

3.3. Details of Algorithm Instances

The P&R travel concept has introduced people to a new way of living and traveling. It encourages people to use urban public transportation systems more and to integrate private car transportation into urban public transportation systems, which substantially simplifies travel for city residents living in the suburbs and corresponds to the low-carbon travel philosophy. The application and development space for P&R traffic modes is extensive [39,40,41]. For example, by the end of 2022, the number of P&R parking lots in Shanghai has grown to 20. A typical hybrid network transfer algorithm that mixes restricted and unrestricted networks is the optimal path-search algorithm for P&R travel. Private cars operate within an unrestricted network, whereas public transportation operates within a restricted network. The two requirements must be combined by constructing a topological relationship. Two representative examples of P&R travel in

Table 3. Plan Comparison for path analysis of Case 1.

Plan	Transfer Number	Walk Distance (m)	Cost (CNY)	Time (min)
Plan 1	1	700	14	48
Plan 2	1	2400	6	90
Plan 3	1	2000	7	90

are selected for detailed elaboration.

3.3.1. Case 1

The travel begins at the intersection of Boxue Road and Fengnian Road in Jiading District and ends at the intersection of Zhongshan North Road and Wuning Road in Putuo District. Jiading District is located in the Shanghai suburbs. Near Fengnian Road and Boxue Road, there are many residential communities. Many new Shanghainese buy homes and settle down here. Putuo, located in the heart of Shanghai, between Zhongshan North Road and Wuning Road, is home to various firms and businesses. This is a typical instance of a working and living travel algorithm. The transfer algorithm presented in this study generates three better transfer plans.

Figure 8 presents the route map of Plan 1.

(1)

Drive to the P&R parking lot of Nanxiang Station.

(2)

Take Metro Line 11 and get off at Caoyang Road Station.

(3)

Walk 700 m to the Destination.

Figure 9 presents the route map of Plan 2.

(1)

Walk 1200 m to Fengrao Road Kemao Road Station.

(2)

Take Bus Jiading No. 58 and get off at Zhennan Road Zhongren Station.

(3)

Walk 500 m to Nanxiang Station.

(4)

Transfer to Metro Line 11 and get off at Caoyang Road Station.

(5)

Walk 700 m to the Destination.

Figure 10 presents the route map of Plan 3.

(1)

Walk 1100 m to Chengliu Middle Road Fengrao Road Station.

(2)

Take Bus Jiading No. 101 and get off at Malu Station.

(3)

Walk 500 m to rail transit Malu Station.

(4)

Transfer to Metro Line 11 and get off at Caoyang Road Station.

(5)

Walk 700 m to the Destination.

3.3.2. Case 2

The journey starts at the Fashion Valley Creative Park in Songjiang District in the suburbs and ends at People’s Square in the center of Shanghai. This is a typical example of a trip from the outskirts of the city to the city center, and the algorithm proposed in this paper is followed to obtain two more reasonable itineraries.

Figure 11 presents the route map of Plan 1.

(1)

Drive to the P&R parking lot of Songjiang University Town Station.

(2)

Take Metro Line 9 and get off at Lujiabang Road Station.

(3)

Transfer to Metro Line 8 and get off at People’s Square Station.

(4)

Walk 100 m to the Destination.

Figure 12 presents the route map of Plan 2.

(1)

Walk 1400 m to Dixian Road Road Station.

(2)

Take Songjiang No. 16 and get off at Songjiang Xincheng Station.

(3)

Transfer to Metro Line 9 and get off at Lujiabang Station.

(4)

Transfer to Metro Line 8 and get off at People’s Square Station.

(5)

Walk 100 m to the Destination.

Both of the mentioned cases were implemented in hybrid networks. The starting points of the two cases are located in Jiading and Songjiang districts, respectively. In recent years, with the development of satellite cities and the adoption of low-carbon tourism concepts, Shanghai has gradually built several P&R transfer parking facilities in the suburbs near the light rail, and the two cases coincidentally seek P&R transfer solutions. With the gradual development of urban public transport networks, more and more travelers tend to choose P&R transfer systems. The algorithm proposed in this study can provide travelers with more and better options and guide them to low-carbon tourism, which is suitable for the needs of urban development and the promotion of the low-carbon tourism concept.

In Case 1, the transfer numbers of the three plans are all one, as demonstrated in Table 3. The P&R transfer parking mode is used in Plan 1. It takes 18 min to self-drive, covering 11 km to the Nanxiang P&R parking lot, then transfer to the rail transit line 11, and then walk 700 m to the destination from Caoyang Road station. The complete journey takes 48 min and costs 14 CNY, comprising a P&R parking fee of 10 CNY and a rail transit fee of 4 CNY. Plan 2 and Plan 3 both adopt bus-to-rail transportation systems. Plan 2 has a total walking distance of 2.4 km, whereas Plan 3 has a total walking distance of 2 km. Both plans take 90 min to complete the journey. For individuals residing in the suburbs and working in the city on weekdays, Plan 1 offers a daily reduction of 3 km in travel distance, an 84-min time savings, and an additional cost of 7 CNY. Considering most people’s living patterns and consumption conceptions, travelers prefer to use less time and less walking distance to reach their destination, and most people can overlook the cost if it is less than 10 CNY per day. Therefore, Plan 1 is the best option after careful evaluation. Of course, each traveler may tailor his or her itinerary to meet his or her requirements. In Case 2, the number of transfers for both plans is two. As shown in

Table 4. Plan Comparison for path analysis of Case 2.

Plan	Transfer Number	Walk Distance (m)	Cost (CNY)	Time (min)
Plan 1	2	100	12	80
Plan 2	2	1500	7	120

, Plan 1 takes 15 min to drive 9 km from the starting point to the P&R transfer station in Songjiang University Town, and then transfers to lines 9 and 8 to reach the end point. Compared to Plan 2, Plan 1 is more expensive but takes 40 min less time and 1.4 km less walking. Under the current low-carbon travel concept, Plan 1 is undoubtedly the best choice for most people living in the suburbs when they want to go into the city center to play, do business, or have a party. There are also several options for travelers to choose from to suit their individual needs.

4. Discussion and Conclusions

4.1. Algorithm Discussion

The A* algorithm commonly employs the distance function as its heuristic function, with popular choices including Manhattan distance and Euclidean distance [42,43,44]. The distance heuristic function is widely used in road network path search, providing relatively reliable and effective shortest path planning for travelers. However, the shortest path is far from satisfying the needs of travelers for public transportation networks, and the optimal path searched according to the traditional A* algorithm is ineffective in most cases. For example, the algorithm is likely to allow travelers to constantly change the type of ride or ride to meet the requirements of the shortest distance, and the number of transfers may reach dozens of times. It is not in line with the objective reality of the situation, in which the traveler is more concerned about the number of transfers, travel time, travel costs, and walking distance. At present, with the continuous development of the city, people’s travel options are greater and greater, and travelers often complete their trips in a mixed network composed of road networks and public transportation networks. The distance heuristic function of the traditional A* algorithm can no longer solve the modern urban travel path planning problem.

In this study, the heuristic function of the traditional A* algorithm is optimized and improved, and a multivariate heuristic function is proposed by adding a multivariate constraint function into the original distance function. Factors concerning travelers such as the number of transfers, travel time, and travel cost, which are correlated, are also integrated into the heuristic function as a constraint function. By prioritizing the control of each evaluation criterion, the different demands of travelers in restricted and unrestricted networks are realized.

4.1.1. Path Planning for Restricted Network

The traditional heuristic function can effectively solve the shortest path planning problem but falls short when dealing with path planning in a restricted networks where the focus of the traveler is shifted from the shortest path to the least number of transfers, the shortest time, and the lowest cost. The multivariate heuristic function solves the above problem by taking the traveler’s concern as a constraint function.

4.1.2. Path Planning for Hybrid Networks

The traditional heuristic function is designed for single network path planning, overlooking the complexity of real-life travel networks that often involve both driving and public transportation. The traditional heuristic function cannot solve the path planning problem of hybrid networks where various modes of transportation coexist. In this paper, a hybrid network that can be used for path planning analysis is constructed firstly by establishing the topological relationship between restricted and unrestricted networks, then, based on the multivariate heuristic function, the different needs of travelers in the hybrid network are realized by prioritizing the control of each evaluation criterion of constraint functions in the heuristic function.

4.1.3. Algorithmic Efficiency Enhancements

The complexity of the algorithm proposed in this paper increases greatly due to the added constraints in the multivariate heuristic function and the expanded evaluation criteria from one element to multivariate. As the algorithm’s complexity increases, the search time is reduced. The algorithm designed in this paper has done the following work:

• Batch-calculate in advance the transfer number, travel time, and travel cost between any two points in the hybrid network and design a reasonable storage structure by sacrificing a certain amount of storage space in exchange for time.
• This paper uses C++ to implement the algorithm, greatly improving the retrieval efficiency of the algorithm by incorporating techniques such as chain lists, lookup trees, and stacks. As shown in

  Table A1. Algorithm instances applied to the Shanghai Public Information Query System.

  Instances	Starting Point	Ending Point	Travel Plan	Number of Transfers	Walk Distance (m)	Cost (CNY)	Time (min)	Algorithm Calculation Time (s)
  1	1	2	Drive from the starting point to Nanxiang P&R Parking Lot, transfer to Metro Line 11 from Nanxiang Station to Xujiahui Station, and transfer to Metro Line 9 from Xujiahui Station to Songjiang XinchengSstation, and transfer to Songjiang No. 16 to the destination.	3	2000	15	160	2.96
  			Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, transfer to Metro Line 11 from Nanxiang Station to Xujiahui Station, and transfer to Metro Line 9 from Xujiahui Station to Songjiang Xincheng Station, and transfer to Songjiang No. 16 to the destination.	3	3500	11	190	3.02
  2	1	3	Drive from the starting point to Nanxiang P&R Parking Lot, transfer to Metro Line 11 from Nanxiang Station to Shanghai West Railway Station, and then transfer to a shared bike to the destination.	2	300	14	46	2.23
  			Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, transfer to Metro Line 11 from Nanxiang Station to Shanghai West Railway Station, and transfer to a shared bike to the destination.	2	2000	6	85	2.12
  			Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, transfer to Metro Line 11 from Nanxiang Station to Shanghai West Railway Station, and transfer to Changzheng No. 1 bus from Shanghai West Railway Station to Fuping Road Station.	2	2000	8	105	2.56
  3	1	4	Drive from the starting point to the Nanxiang P&R parking lot, and transfer to Metro Line 11 from Nanxiang Station to Caoyang Road Station.	1	700	14	48	0.54
  			Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, and transfer to Metro Line 11 from Nanxiang Station to Caoyang Road Station.	1	2400	6	90	0.63
  			Take the Jiading No. 101 bus from Fengrao East Road Station to Malu Station, and transfer to Metro Line 11 from Malu Station to Caoyang Road Station.	1	2000	7	90	0.58
  4	1	5	Drive from the starting point to Nanxiang P&R Parking Lot, transfer to Metro Line 11 from Nanxiang Station to Caoyang Road Station, and transfer to Metro Line 3 from Caoyang Road Station to Shanghai Railway Station.	2	300	14	52	1.12
  			Take the Jiatai Line from Chengliuzhong Road Station to Taihe Road Station, and transfer to Metro Line 1 from Gongfu Xincun Station to Shanghai Railway Station.	1	1500	4	93	0.87
  			Take Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, transfer to Metro Line 11 from Nanxiang Station to Caoyang Road Station, and transfer to Metro Line 3 from Caoyang Road Station to Shanghai Railway Station.	2	2000	6	98	1.69
  5	1	6	Drive from the starting point to Nanxiang P&R Parking Lot, transfer to Metro Line 11 from Nanxiang Station to Caoyang Road Station, transfer to Metro Line 4 from Caoyang Road Station to Dalian Road Station, and transfer to Metro Line 12 from Dalian Road Station to Donglu Road Station.	3	1200	16	98	2.87
  			Take the Jiatai Line from Chengliuzhong Road Station to Taihe Road Station, transfer to Metro Line 1 from Gongfu Xincun Station to Hanzhong Road Station, and transfer to Metro Line 12 from Hanzhong Road Station to Donglu Road Station.	2	2600	7	140	1.73
  			Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, transfer to Metro Line 11 from Nanxiang Station to Caoyang Road Station, transfer to Metro Line 4 from Caoyang Road Station to Dalian Road Station, and transfer to Metro Line 12 from Dalian Road Station to Donglu Road Station.	3	3000	8	138	2.92
  6	1	7	Drive from the starting point to Nanxiang P&R parking lot, transfer to Metro Line 11 from Nanxiang Station to Zhenru Station, and transfer to Metro Line 14 from Zhenru Station to Big World Station.	2	800	15	70	1.68
  			Take Jiatai Line from Chengliuzhong Road Station to Taihe Road Station, and transfer to Metro Line 1 from Gongfu Xincun Station to People’s Square Station.	1	2000	6	108	0.72
  			Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, transfer to Metro Line 11 from Nanxiang Station to Zhenru Station, and transfer to Metro Line 14 from Zhenru Station to Big World Station.	2	2500	7	108	1.85
  7	1	8	Drive from the starting point to Nanxiang P&R Parking Lot, transfer to Metro Line 11 from Nanxiang Station to Jiangsu Road Station, and transfer to Metro Line 2 from Jiangsu Road Station to Zhangjiang Hi-Tech Park Station.	2	700	16	90	1.71
  			Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, transfer to Metro Line 11 from Nanxiang Station to Jiangsu Road Station, and transfer to Metro Line 2 from Jiangsu Road Station to Zhangjiang Hi-Tech Park Station.	2	2500	8	130	1.92
  8	1	9	Take the Jiatai Line from Chengliu Middle Road Station to Taihe Road Station, transfer to Bus 719 from Taihe Road Station to Changzheng Xincun Station, and transfer to Bus 90 from Changzheng Xincun Station to Zhayin Road Station.	2	2100	7	138	1.83
  			Take the Jiatai Line from Chengliu Middle Road Station to Taihe Road Station, transfer to Metro Line 1 from Gongfu Xincun Station to Tonghe Xincun Station, and transfer to Bus 726 from Changjiang West Road Station to Zhayin Road Station.	2	2300	5	140	1.82
  9	1	10	Drive from the starting point to Nanxiang P&R Parking Lot, transfer to Metro Line 11 from Nanxiang Station to Longde Road Station, and transfer to Metro Line 13 from Longde Road Station to Fengzhuang Station.	2	700	15	70	1.62
  			Take Jiading No. 101 bus from Chengliu Middle Road to Bao’an Highway Station, and transfer to Jiading No. 65 bus from Huyi Highway Station to Xinyu Road Station.	1	2600	4	118	0.76
  			Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, transfer to Metro Line 11 from Nanxiang Station to Longde Road Station, and transfer to Metro Line 13 from Longde Road Station to Fengzhuang Station.	2	2000	7	111	1.52
  10	2	3	Drive from the starting point to Songjiang University Town P&R Parking Lot, transfer to Metro Line 9 from Songjiang University Town Station to Guilin Road Station, transfer to Metro Line 15 from Guilin Road Station to Shanghai West Railway Station.	2	1500	12	100	1.73
  			Take the Songjiang No.16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang University Town station to Guilin Road Station, transfer to Metro Line 15 from Guilin Road Station to Shanghai West Railway Station.	2	3000	7	140	1.61
  			Take the Songjiang No.16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang University Town Station to Guilin Road Station, transfer to Metro Line 15 from Guilin Road Station to Shanghai West Railway Station.	2	3000	7	140	1.23
  11	2	4	Drive from the starting point to Songjiang University Town P&R Parking Lot, transfer to Metro Line 9 from Songjiang University Town Station to Xujiahui Road Station, transfer to Metro Line 11 from Xujiahui Road Station to Caoyang Road Station.	2	700	12	100	1.12
  			Take the Songjiang No.16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang Xincheng Station to Xujiahui Road Station, transfer to Metro Line 11 from Xujiahui Road Station to Caoyang Road Station.	2	2500	7	130	1.46
  12	2	5	Drive from the starting point to Songjiang University Town P&R Parking Lot, transfer to Metro Line 9 from Songjiang University Town Station to Yishan Road Station, transfer to Metro Line 3 from Yishan Road Station to Shanghai Railway Station.	2	500	12	100	1.35
  			Take the Songjiang No.16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang Xincheng Station to Yishan Road Station, transfer to Metro Line 3 from Yishan Road Station to Shanghai Railway Station.	2	2000	7	130	1.25
  			Take the Songjiang No.16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang Xincheng Station to Century Avenue Station, transfer to Metro Line 4 from Century Avenue Station to Shanghai Railway Station.	2	2000	7	150	1.27
  13	2	6	Drive from the starting point to Songjiang University Town P&R Parking Lot, transfer to Metro Line 9 from Songjiang University Town Station to Jiashan Road Station, transfer to Metro Line 12 from Jiashan Road Station to Donglu Road Station.	2	1000	14	110	1.21
  			Take the Songjiang No.16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang Xincheng Station to Jiashan Road Station, transfer to Metro Line 12 from Jiashan Road Station to Donglu Road Station.	2	2500	8	150	1.26
  14	2	7	Drive from the starting point to Songjiang University Town P&R Parking Lot, transfer to Metro Line 9 from Songjiang University Town Station to Lujiabang Road Station, transfer to Metro Line 8 from Lujiabang Road Station to People’s Square Station.	2	100	12	80	1.13
  			Take the Songjiang No.16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang Xincheng Station to Lujiabang Road Station, transfer to Metro Line 8 from Lujiabang Road Station to People’s Square Station.	2	1500	7	120	1.31
  15	2	8	Drive from the starting point to Songjiang University Town P&R Parking Lot, transfer to Metro Line 9 from Songjiang University Town Station to Century Avenue Station, transfer to Metro Line 2 from Century Avenue Station to Zhangjiang High tech Station.	2	500	14	100	1.24
  			Take the Songjiang No.16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang Xincheng Station to Century Avenue Station, transfer to Metro Line 2 from Century Avenue Station to Zhangjiang High tech Station.	2	2000	8	140	1.35
  16	2	9	Drive from the starting point to Songjiang University Town P&R Parking Lot, transfer to Metro Line 9 from Songjiang University Town Station to Lujiabang Road Station, transfer to Metro Line 8 from Lujiabang Road Station to Shiguang Road Station.	2	1600	14	110	1.32
  			Take the Songjiang No.16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang Xincheng Station to Lujiabang Road Station, transfer to Metro Line 8 from Lujiabang Road Station to Shiguang Road Station.	2	3000	8	170	1.43
  17	2	10	Drive from the starting point to Songjiang University Town P&R Parking Lot, transfer to Metro Line 9 from Songjiang University Town Station to Xujiahui Station, transfer to Metro Line 11 from Xujiahui Station to Longde Road Station, and transfer to Metro Line 13 from Longde Road Station to Fengzhuang Station.	3	1000	12	110	2.71
  			Take the Songjiang No.16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang University Town Station to Xujiahui Station, transfer to Metro Line 11 from Xujiahui Station to Longde Road Station, and transfer to Metro Line 13 from Longde Road Station to Fengzhuang Station.	3	2500	7	150	2.86
  18	3	4	Take No. 923 bus from Zhenhua Road Station to Caoyang Road Station.	0	900	2	36	0.37
  			Ride a shared bike from the starting point to Shanghai West Railway Station, and transfer to Metro Line 11 from Shanghai West Railway Station to Caoyang Road Station.	1	800	3	26	0.52
  19	3	5	Take No. 859 bus from Fuping Road Station to Shanghai Railway Station.	0	400	2	30	0.32
  			Take No. 117 bus from Jiaotong Road Station to Shanghai Railway Station.	0	600	2	34	0.35
  			Take No. 744 bus from Cotton Warehouse Station to Pushan Road Station.	0	1200	2	40	0.37
  20	3	6	Take No. 859 bus from Fuping Road to Jinyuan Road Station, and transfer to Metro Line 12 from Qufu Road Station to Donglu Road Station.	1	1500	6	80	0.49
  			Take Metro Line 11 from Shanghai West Railway Station to Caoyang Road Station, transfer to Metro Line 4 from Caoyang Road Station to Dalian Road Station, and transfer to Metro Line 12 from Dalian Road Station to Donglu Road Station.	2	1800	6	80	1.12
  21	3	7	Take No. 112 bus from Zhenhua Road Station to People’s Square Station.	0	800	2	68	0.35
  			Take No. 859 bus from Fuping Road Station to Zhongxing Road Station, and transfer to Metro Line 8 from Zhongxing Road Station to People’s Square Station.	1	1100	5	57	0.51
  			Ride a shared bike from the starting point to Shanghai West Railway Station, transfer to Metro Line 15 from Shanghai West Railway Station to Tongchuan Road Station, and transfer to Metro Line 14 from Tongchuan Road Station to Big World Station.	2	1000	4	45	1.14
  22	3	8	Ride a shared bike from the starting point to Shanghai West railway Station, transfer to Metro Line 11 from Shanghai West railway Station to Jiangsu Road Station, and transfer to Metro Line 2 from Jiangsu Road Station to Zhangjiang Hi-Tech Park Station.	2	1000	5	66	1.13
  			Take Changzheng No. 1 bus from Fuping Road Station to Caoyang Road Station, transfer to Metro Line 11 from Zhenru Station to Jiangsu Road Station, and transfer to Metro Line 2 from Jiangsu Road Station to Zhangjiang Hi-Tech Park Station.	2	1400	7	80	1.21
  23	3	9	Ride a shared bike from the starting point to Zhenru Station, transfer to Line 14 from Zhenru Station to Yuyuan Garden Station, transfer to Line 10 from Yuyuan Garden Station to Xinjiangwancheng Station, and then transfer to a shared bike to the destination.	3	350	6	78	2.35
  			Take No. 159 bus from Zhenhua Road Station to Changjiang West Road Station, and transfer to No. 726 bus from Changjiang Road Station to Zhayin Road Station.	1	1800	4	120	0.61
  24	3	10	Ride a shared bike from the starting point to Shanghai West Railway Station, transfer to Metro Line 15 from Shanghai West Railway Station to Daduhe Road Station, and transfer to Metro Line 13 from Daduhe Road Station to Fengzhuang Station.	2	1100	4	40	1.32
  			Take No. 923 bus from Zhenhua Road Station to Caoyang Road Station, and transfer to No. 717 bus from Caoyang Road Station to Fengzhuang Station.	1	400	4	72	0.53
  25	4	5	Take Metro Line 3 from Caoyang Road Station to Shanghai Railway Station.	0	500	3	17	0.35
  			Take Metro Line 4 from Caoyang Road Station to Shanghai Railway Station.	0	500	3	17	0.35
  			Take No. 837 bus from Wuning Xincun Station to Shanghai Railway Station.	0	600	2	37	0.35
  26	4	6	Take Metro Line 4 from Caoyang Road Station to Dalian Road Station, and transfer to Metro Line 12 from Dalian Road Station to Donglu Road Station.	1	1400	5	57	0.42
  			Take Metro Line 14 from Caoyang Road Station to Yuanshen Road Station, and transfer to Pudong No. 4 from Pudong Avenue Station to Dongbo Road Station.	1	700	6	72	0.41
  			Take Metro Line 14 from Caoyang Road Station to Xiepu Road Station, and transfer to Pudong No. 15 from Pudong Avenue Station to Dongbo Road Station.	1	950	6	70	0.42
  27	4	7	Take Metro Line 14 from Caoyang Road Station to Huangpi South Road Station, and transfer to a shared bike to reach the destination.	1	650	3	27	0.42
  			Take No. 01 bus from Wuning Xincun Station to Yan’an East Road Station.	0	900	2	66	0.37
  			Take Metro Line 14 from Caoyang Road Station to Huangpi South Road Station, and transfer to Metro Line 1 from Huangpi South Road Station to People’s Square Station	1	1100	3	33	0.45
  28	4	8	Take Metro Line 4 from Caoyang Road Station to CenturyAvenue Station, and transfer to Metro Line 2 from Century Avenue Station to Zhangjiang Hi-Tech Park Station.	1	900	5	54	0.45
  			Take Metro Line 14 from Caoyang Road Station to Jing’an Temple Station, and transfer to Metro Line 2 from Jing’an Temple Station to Zhangjiang Hi-Tech Park Station.	1	1200	5	54	0.46
  			Take No. 94 bus from Wuning Xincun Station to Jing’an Temple Station, and transfer to Metro Line 2 from Jing’an Temple Station to Zhangjiang Hi-Tech Park Station.	1	1100	6	67	0.46
  29	4	9	Take Metro Line 3 from Caoyang Road Station to Hongkou Football Stadium Station, and transfer to Metro Line 8 from Hongkou Football Stadium Station to Shiguang Road Station, and then transfer to a shared bike to the destination	.2	900	5	60	1.21
  			Take Metro Line 3 from Caoyang Road Station to Zhanghuabang Station, and transfer to No. 90 bus from Zhanghuabang Station to Zhayin Road Station.	1	1100	7	74	0.46
  30	4	10	Take No. 717 bus from Caoyang Road Station to Fengzhuang Station.	0	850	2	49	0.35
  			Take Metro Line 3 from Caoyang Road Station to Jinshajiang Road Station, and transfer to Metro Line 13 from Jinshajiang Road Station to Fengzhuang Station.	1	1400	4	37	0.46
  			Take Metro Line 11 from Caoyang Road Station to Longde Road Station, and transfer to Metro Line 13 from Longde Road Station to Fengzhuang Station.	1	1500	4	42	0.47
  31	5	6	Take Metro Line 4 from Shanghai Railway Station to Dalian Road Station, and transfer to Metro Line 12 from Dalian Road Station to Donglu Road Station.	1	900	4	43	0.45
  			Take Metro Line 1 from Shanghai Railway Station to Hanzhong Road Station, and transfer to Metro Line 12 from Hanzhong Road Station to Donglu Road Station.	1	1100	4	47	0.47
  			Take Tunnel Line 3 from Shanghai Railway Station to North Xizang Road Station, and transfer to Metro Line 12 from Qufu Road Station to Donglu Road Station.	1	1000	6	60	0.47
  32	5	7	Take Metro Line 1 from Shanghai Railway Station to People’s Square Station.	0	500	3	13	0.35
  			Take Tunnel Line 3 from Shanghai Railway Station to People’s Square Station.	0	200	2	20	0.35
  			Take No. 930 bus from Shanghai Railway Station to People’s Square Station.	0	200	2	20	0.35
  33	5	8	Take Metro Line 4 from Shanghai Railway Station to Century Avenue Station, and transfer to Metro Line 2 from Century Avenue Station to Zhangjiang Hi-Tech Park Station.	1	450	4	40	0.45
  			Take Metro Line 1 from Shanghai Railway Station to People’s Square Station, and transfer to Metro Line 2 from People’s Square Station to Zhangjiang Hi-Tech Park Station.	1	800	4	42	0.45
  			Take No. 41 bus from Hengfeng Road Station to Beijing West Road Station, and transfer to Metro Line 2 from West Nanjing Road Station to Zhangjiang Hi-Tech Park Station.	1	1200	6	63	0.45
  34	5	9	Take Metro Line 4 from Shanghai Railway Station to Hailun Road Station, and transfer to Metro Line 10 from Hailun Road Station to Xinjiangwancheng Station, and transfer a shared bike to the destination.	2	350	4	45	1.22
  			Take Metro Line 3 from Shanghai Railway Station to Zhanghuabang Station, and transfer to No. 90 bus from Zhanghuabang Station to Zhayin Road Station.	1	600	6	60	0.45
  			Take No. 942 bus from Shanghai Railway Station to Yinxing Road Station.	0	1000	2	80	0.35
  35	5	10	Take Metro Line 1 from Shanghai Railway Station to Hanzhong Road Station, and transfer to Metro Line 13 from Hanzhong Road Station to Fengzhuang Station.	1	900	4	40	0.45
  			Take Metro Line 3 from Shanghai Railway Station to Jinshajiang Road Station, and transfer to Metro Line 13 from Jinshajiang Road Station to Fengzhuang Station.	1	900	4	40	0.45
  			Take No.104 bus from Shanghai Railway Station to Hengfeng Road Station, and transfer to Metro Line 13 from Hanzhong Road Station to Fengzhuang Station.	1	1300	6	60	0.45
  36	6	7	Ride a shared bike to Donglu Road Station, transfer to Metro Line 12 from Donglu Road Station to Qufu Road Station, and transfer to Metro Line 8 from Qufu Road Station to People’s Square Station.	2	750	4	46	1.21
  			Take No. 455 bus from Wulian Road to Yan’an East Road Station.	0	1700	2	65	0.36
  			Take Metro Line 12 from Donglu Road Station to Qufu Road Station, and transfer to Tunnel Line 3 from North Xizang Road Station to People’s Square Station.	1	1200	6	60	0.47
  37	6	8	Take No. 778 bus from Laiyang Road Station to Zhangjiang Station.	0	1900	2	65	0.36
  			Take Metro Line 6 from Jufeng Road Station to Century Avenue Station, and transfer to Metro Line 2 from Century Avenue Station to Zhangjiang Hi-Tech Park Station.	1	1400	4	56	0.47
  			Take Pudong No.4 bus from Dongbo Road Station to Fushan Road Station, and transfer to Metro Line 2 from Century Avenue Station to Zhangjiang Hi-Tech Park Station.	1	850	6	66	0.45
  38	6	9	Take No. 405 bus from Dongbo Road Station to Xiangyin Road Station, transfer to Metro Line 8 from Xiangyin Road Station to Shiguang Road Station, and transfer to a shared bike to the destination.	2	500	5	57	1.22
  			Take No. 405 bus from Dongbo Road Station to Xiangyin Road Station, and transfer to No. 726 bus from Zhongyuan Road Station to Zhayin Road Station.	1	750	4	70	0.45
  			Take No. 405 bus from Dongbo Road Station to Xiangyin Road Station, and transfer to No. 870 bus from Zhongyuan Road Station to Xinjiangwancheng Station.	1	1300	4	75	0.47
  39	6	10	Ride a shared bike to Donglu Road Station, transfer to Metro Line 12 from Donglu Road Station to Hanzhong Road Station, and transfer to Metro Line 13 from Hanzhong Road Station to Fengzhuang Station.	2	900	5	70	1.22
  			Take Pudong No.4 bus from Dongbo Road Station to Pudong Avenue Station, and transfer to Metro Line 14 from Xiepu Road Station to Dingbian Road Station.	1	1700	7	95	0.47
  40	7	8	Take Metro Line 2 from People’s Square Station to Zhangjiang Hi-Tech Park Station.	0	1300	4	40	0.37
  			Take No. 451 bus from People’s Square Station to Pujian Road Station, and transfer to Pudong No. 11 bus from Pujian Road Station to Zhangjiang Station.	1	650	4	80	0.45
  41	7	9	Take Metro Line 8 from People’s Square Station to Shiguang Road Station, and transfer to a shared bike to the destination.	1	600	4	50	0.45
  			Take No. 537 bus from People’s Square Station to Zhongyuan Road Station.	0	2000	2	109	0.37
  			Take No. 537 bus from People’s Square Station to Changhai Road Station, and transfer to No. 90 bus from Hengren Road Station to Zhayin Road Station.	1	1100	4	100	0.46
  42	7	10	Take Metro Line 1 from People’s Square Station to Hanzhong Road Station, and transfer to Metro Line 13 from Hanzhong Road Station to Fengzhuang Station.	1	1400	4	50	0.47
  			Take No. 167 bus from People’s Square Station to Middle Huaihai Road Station, and transfer to Metro Line 13 from Middle Huaihai Road Station to Fengzhuang Station.	1	1000	6	66	0.46
  			Take No. 112 bus from People’s Square Station to Shanghai Television Station, and transfer to Metro Line 13 from West Nanjing Road Station to Fengzhuang Station.	1	1600	6	67	0.47
  43	8	9	Take Metro Line 2 from Zhangjiang Hi-Tech Park Station to East Nanjing Road Station, transfer to Metro Line 10 from East Nanjing Road Station to Xinjiangwancheng Station, and transfer to a shared bike to the destination.	2	800	5	70	1.21
  			Take Pudong No. 22 bus from Keyuan Road Station to Deping Road Station, transfer to Daqiao Line 3 from Deping Road Station to Shiji Road Station, and transfer to a shared bike to the destination.	2	400	4	110	1.21
  44	8	10	Take Metro Line 2 from Zhangjiang Hi-Tech Park Station to Songhong Road Station, and transfer to No. 121 bus from Tianshan West Road Station to Qingyu Road Station.	1	900	7	80	0.45
  			Take Metro Line 2 from Zhangjiang Hi-Tech Park Station to West Nanjing Road Station, and transfer to Metro Line 13 from West Nanjing Road Station to Fengzhuang Station.	1	1600	5	77	0.47
  			Take Bridge Line 6 from Zhangjiang Station to Shanghai Swimming Center Station, and transfer to No. 808 bus from Shanghai Swimming Center Station to Qingyu Road Station.	1	1200	4	150	0.47
  			Take Pudong No. 12 bus from Zu Chongzhi Road Station to Dongfang Road Station, transfer to No. 01 bus from Pujian Road Station to Caoyang Road Station, transfer to No. 717 bus from Caoyang Road Station to Fengzhuang Station.	2	650	6	160	1.24
  45	9	10	Ride a shared bike from the starting point to Shiguang Road Station, transfer to Metro Line 8 from Shiguang Road Station to Qufu Road Station, transfer to Metro Line 12 from Qufu Road Station to Hanzhong Road Station, and transfer to Metro Line 13 from Hanzhong Road Station to Fengzhuang Station.	3	900	5	80	2.76
  			Ride a shared bike from the starting point to Guohe Road Station, transfer to No. 966 bus from Guohe Road Station to Changshou Road Station, transfer to No. 717 bus from Changshou Road Station to Fengzhuang Station.	2	100	4	136	1.25

  of Appendix A, which demonstrates the time consumed for each scheme calculation, the execution environment of the algorithm here is the execution time of an ordinary PC standalone environment, and the efficiency of the algorithm execution can be further increased by using a network server and configuring load balancing.

4.1.4. Comparison of Path Service Algorithms with Other Electronic Maps

The two examples in Section 3.3 were cross-referenced with searches in Bing Maps and Amap. The travel plans provided by the two mapping services are outlined in

Table 5. Travel Plans in Bing Maps and Amap for two arithmetic cases.

Instances	Starting Point	Ending Point	Travel Plan	Number of Transfers	Walk Distance (m)	Cost (CNY)	Time (min)
Bing Maps	1	4	Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, transfer to Metro Line 11 from Nanxiang Station to Zhenru Station, and transfer to Metro Line 14 from Zhenru Station to Caoyang Road Station.	2	1800	6	118
			Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, transfer to Metro Line 11 from Nanxiang Station to Caoyang Road Station.	1	2300	6	123
	2	7	Take the Songjiang No. 10 bus from Zheng Tai Sheng Huo Qu Station to Rongle Road Station, transfer to Songjiang Tram Line 2 to Songjiang Sports Center, transfer to Metro Line 9 from Songjiang Sports Center to Lujiabang Road Station, and transfer to Metro Line 8 from Lujiabang Road Station to People’s Square Station.	3	1600	10	170
			Take the Songjiang No. 20 bus from Zheng Tai Sheng Huo Qu Station to Minle Xiao Qu Station, transfer to Song Zhu bus to Jiangzhong Xiao Qu Station, transfer to Songjiang No. 25 bus to Jia Song Gong Lu Station, transfer to Metro Line 9 from Songjiang Xincheng Station to Lujiabang Road Station, and transfer Metro Line 8 from Lujiabang Road Station to People’s Square Station.	4	1500	10	171
AMap	1	4	Take the Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, and transfer to Metro Line 11 from Nanxiang Station to Caoyang Road Station.	1	2500	6	92
			Take the Jiading No. 101 bus from Fengrao East Road Station to Malu Station, transfer to Metro Line 11 from Malu Station to Caoyang Road Station.	1	2200	6	100
			Take Jiading No. 58 bus from Fengrao East Road Station to Zhennan Road Station, and transfer to No. 62 bus from Zhennnan Road Station to Caoyang Road station	1	2300	6	138
	2	7	Take the Songjiang No. 14 bus from Sixian Road Station to Songjiang Sports Center Station, transfer to Metro Line 9 from Songjiang Sports Center Station to Lujiabang Road Station, and transfer to Metro Line 8 from Lujiabang Road Station to People’s Square Station.	2	1700	10	128
			Take the Songjiang No. 16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang Xincheng Station to Lujiabang Road Station, and transfer to Metro Line 8 from Lujiabang Road Station to People’s Square Station.	2	1800	10	130
			Take the Songjiang No. 16 bus from Sixian Road Station to Songjiang Xincheng Station, transfer to Metro Line 9 from Songjiang Xincheng Station to Xujiahui Station, and transfer to Metro Line 1 from Xujiahui Station to People’s Square Station.	2	1800	10	128

, and the preferred travel routes are illustrated in Figure 13 and Figure 14, respectively. Notably, both mapping services did not provide a P&R travel plan. On the one hand, it shows that P&R travel mode is not yet very popular in China and commercial navigation maps have not yet provided relevant services; on the other hand, it shows that software algorithms should also be adapted to P&R travel mode, with the continuous expansion and improvement of P&R car park hardware facilities, to guide users to adopt low-carbon travel. It also means that this aspect of the service has a greater potential for commercial application.

4.2. Conclusions

With the fast expansion of urban infrastructure and the continual upgrading of the urban public transportation network system, it is becoming increasingly important to give the optimal travel plan to travelers in restricted networks. This study proposes an improved A* algorithm for the optimal path analysis of the restricted networks to suit the demands of travelers regarding the transfer of public transportation networks. Furthermore, as urban satellite towns develop and the concept of low-carbon travel is implemented, the proliferation of P&R transfer parking lots and the demand for transfer travel in hybrid networks are on the rise. Based on the improved A* algorithm for path analysis of restricted networks, an A* algorithm for path analysis of hybrid networks is developed to fulfill the transfer travel demands of travelers combining private cars and public transportation. The following highlights are the properties of the improved A* algorithm proposed in this paper:

• The algorithm takes into account the diverse travel requirements of travelers, incorporating factors such as transfer numbers, travel time, and travel costs. A multivariate heuristic function is proposed to determine the priority of nodes during the node expansion operation. Finally, the optimal travel plan is determined by carefully addressing the various demands of travelers.
• The heap and search tree methods are introduced in the key step of the A* algorithm of expanding node operations, considerably improving the operational efficiency of the algorithm and achieving a better user experience.
• The spatial topological relationship between the public transportation stations and the road centerline network is established by determining the subordinate relationship between the stations and the centerline within a specified buffer zone. Thus, the topological relationship between the restricted and the unrestricted networks are formed, providing the essential data foundation for the implementation of the algorithm for path analysis of hybrid networks. As a result, the algorithm effectively addresses the transfer demand between private cars and public transportation.
• During the algorithm design process, buffer search is incorporated into the node expansion method. This allows the algorithm to calculate the demand for transfers between various forms of public transportation lines, such as rail transit, bus lines, airport express lines, ferry lines, tourist lines, trams, suburban special lines, and others.
• Currently, the wave of digital innovation and the integration of the sharing economy has been gradually changing the way people live and travel, such as the successive popularization and promotion of bike sharing, which provides more convenient options for people to travel [45]. This is particularly significant for such a cosmopolitan city like Shanghai, where bike sharing can address the last kilometer problem, providing a valuable supplement in public transportation travel. In future research, it is hoped that the bike-sharing-related data (parking points, electronic fences, vehicle service providers, etc.) can be integrated into the algorithm to provide more refined travel choices for travelers according to their preferences and more accurate positioning.

The improved A* algorithm proposed in this paper primarily addresses the optimal path analysis issue in restricted networks and hybrid networks. It solves the P&R transfer problem from private cars to public transportation in hybrid networks. In the future, commercial e-navigation maps, such as Amap, are expected to incorporate corresponding P&R travel path search navigation services for the combination of private cars and public transport to meet the growing demand for P&R travel. Additionally, with the popularity and promotion of shared bicycles in recent years, the use of shared bicycles for public transportation has become increasing convenience for travelers. This algorithm needs to be optimized to determine the optimal transfer plan for all options, from shared bicycles to public transportation. For example, it must also take into account the issues of shared bicycle parking, traffic constraints, and travelers’ choice of shared bicycle providers. To genuinely fulfill the demands of travelers, the algorithm must be adjusted and upgraded to match the needs of shared bicycle travel transport modes. This issue will be addressed further in subsequent algorithm research.