# Route Planning for Autonomous Driving Based on Traffic Information via Multi-Objective Optimization
## 4 Experiments and Results  
In this section, we evaluate the effectiveness of the general framework of the route planning method based on multi-objective optimization on a real-world transportation network of Sioux Falls, the largest city in South Dakota, USA [29]. We introduce network analysis into the traffic network. The intersections are abstracted as nodes and the streets are abstracted as links; there are a total of 24 nodes, 76 links and 360,600 trips in the Sioux Falls network, which is shown in Figure 1 as the network structure in the map and the complex network model. Figure 2 shows basic statistics for the traffic network used in our paper, where traffic flow is given in the number of vehicles per day. The number of branches at an intersection is called the degree to describe the complexity of the intersection. In Figure 2a, the degree of the nodes in the traffic network is 2, 3, 4, 5, respectively, and only node 10 has the largest degree of 5. More than half of the nodes have degree 3; the complexity distribution of nodes is reasonable. The ratio of the number of times that a node acts as the intermediate node of the shortest path between other nodes to the total number of paths is called betweenness; it indicates the importance of one node to other nodes. In Figure 2b, most of the nodes' betweenness is less than 0.15 and only two nodes have a betweenness between 0.21 and 0.24; this shows that the number of times each node acts as the center is uniform. In Figure 2c, as for traffic flow in the network, the numbers distribute from 4000 to 24,000, and 25 links is the only the number of links with flow between 8000 and 10,000; this is the only one that occupies more than 10 links. The data used in this paper have obvious characteristics of urban traffic network, information flow and so on and can be used as a dataset to verify autonomous driving route planning. To show the effectiveness of our work on different trips in the transportation network, we evaluate the methods with six different OD (Origin Destination) pairs, (7, 24), (1, 20), (1, 19), (2, 22), (9, 19), (16, 24). Since personal preference would significantly influence the comprehensive cost of the route planning process, which is the objective function of our method, the same \(t_{limit}\), \(d_{min}\) and \(E_{limit}\) are used to compare the cost under different typical weights \(\alpha\), \(\beta\), \(\gamma\) in this experiment. We search for all the candidate routes by performing a variant of Breath-First Search on each OD pair. Table 1 presents the optimal comprehensive costs for six different OD pairs with four parameter settings, which are (0.33, 0.33, 0.33), (0.2, 0.4, 0.4), (0.3, 0.2, 0.5), (0.5, 0.3, 0.2). After comparing the values with different parameters, it is shown that the optimal comprehensive costs of the same OD pair with different parameters are quite different. In addition, the optimal comprehensive costs of different OD pairs with the same parameter setting are very similar in the table. It is notable that the parameter of \(\alpha\), which is related to the total distance of the route, has the most influence on the values, since the traffic jam data are missing in the dataset and this would influence the travel time and travel cost seriously. Figure 3 visualizes the optimal routes for six different OD pairs with parameters of (0.3, 0.3, 0.3). After a series of optimization operations, we obtained the optimal route of the six OD pairs shown in Figure 3 when the parameter is set to (0.3, 0.3, 0.3). In the experiment shown in the figure, we set the influence weight parameters of travel distance, travel time and travel cost on the optimization objectives to be equal and the route scheme under this parameter setting is more in line with the situation that people need to measure and consider many aspects in their daily life.