# Considering the Optimization Design of Urban Bus Network Scheduling
## 3 Model Solving
### The Yen's Shortest Path Algorithm-Based Traversal Algorithm  
This paper considers the situation where passengers choose which route to take during their travel. When calculating the total travel cost for passengers between various origindestination (OD) stations, it is assumed that passengers always choose the shortest path. However, in cases where there are multiple shortest paths between OD pairs, considering passengers' choices among these paths becomes necessary. Therefore, it is essential to analyze and compute the shortest paths between each OD pair. To address this analytical need, the [PERSON]'s shortest path algorithm is selected to analyze the shortest path scenarios between different OD pairs. The Yen algorithm, proposed by [PERSON] in 1971 for solving the KSP (K-Shortest Paths) problem, is based on the shortest path algorithm and computes the first K-shortest paths between OD stations. It is suitable for calculating the single-source K-shortest paths in directed acyclic graphs with non-negative weighted edges [38]. In this paper, the basic process of the Yen algorithm-based shortest path traversal is as follows:  
(1) Given the origin station o and destination station d, for the initial traversal, set the value of K to 1. This will find the first shortest path P\({}_{1}\) for the OD pair and the corresponding weight Y\({}_{\text{od}}^{1}\). (2) When seeking the second shortest path P\({}_{2}\) with K set to 2, the process is as follows:  
1 Update the shortest paths for each segment: Initially, set the weights of all segments on the P\({}_{1}\) path to infinity. Calculate the new shortest path for each segment by setting the weights of the segments on the P\({}_{1}\) path to infinity in sequence. Concatenate the resulting new shortest paths with the original P\({}_{1}\) path. The number of computations is equal to the number of segments in the path. 2 Initialize the candidate route set X. If the newly obtained paths from the previous step are non-empty and meet the conditions of non-repeating stations and being different from the previously selected path P\({}_{1}\), add them to the candidate route set X. Remove any duplicates from the candidate route set X. 3 Select the shortest route and update the candidate route set X. From the non-empty candidate route set X, select the path with the minimum weight as the second shortest path P\({}_{2}\), with a weight of Y\({}_{\text{od}}^{2}\). Remove this path from the candidate route set X. This process ensures that the second shortest path is found while considering non-repeating stations and avoiding duplication with the first selected path P\({}_{1}\). (3) When finding the i-th shortest path P\({}_{i}\) with K set to i, the process is as follows:  
1 Update the shortest paths for each segment: Start by setting the weights of all segments on the P\({}_{i-1}\) path to infinity. Calculate the new shortest path for each segment by setting the weights of the segments on the P\({}_{i-1}\) path to infinity in sequence. Concatenate the resulting new shortest paths with the original P\({}_{i-1}\) path. The number of computations is equal to the number of segments in the path. 2 Initialize the candidate route set X. If the newly obtained paths from the previous step are non-empty and meet the conditions of non-repeating stations and being different from the previously selected paths P\({}_{1}\) to P\({}_{i-1}\), add them to the candidate route set X. Remove any duplicates from the candidate route set X. 3 Select the shortest route and update the candidate route set X. From the non-empty candidate route set X, select the path with the minimum weight as the i-th shortest path P\({}_{i}\), with a weight of Y\({}_{\text{od}}^{i}\). Remove this path from the candidate route set X. If there are multiple paths with the same weight Y\({}_{\text{od}}^{i}\), repeat the above process for each path. (4) Compare the weight Y\({}_{\text{od}}^{i}\) of the i-th shortest path obtained with the weight Y\({}_{\text{od}}^{1}\) of the first shortest path.