# Route Planning for Autonomous Driving Based on Traffic Information via Multi-Objective Optimization
## 3 Proposed Method
### Personal Preference  
Personal preference is the most important factor in our general framework of the route planning method, since the other three factors (travel time, travel distance and travel cost) are affected by personal preference. Personal preference should be entered into the auto drive system as known conditions before route planning begins, including: \(\alpha\), \(\beta\), \(\gamma\), \(x_{ij}\), \(y_{ij}\), \(z_{ij}\). \(\alpha\), \(\beta\), \(\gamma\) are the manually input variables of personal preference on the normalization values; \(x_{ij}\), \(y_{ij}\), \(z_{ij}\) represent the limited parameters of personal preference concerning time, distance and cost. \(\alpha\), \(\beta\), \(\gamma\) calculate the weight parameters of the comprehensive cost. \(x_{ij}\), \(y_{ij}\), \(z_{ij}\) represent drivers' more specific needs for time, distance and cost. For instance, \(x_{ij}\) could represent an upper limit value of the travel time of one traveler; \(y_{ij}\) limits whether the candidate planned route could be chosen; \(z_{ij}\) could be the expected value of fuel consumption. The constraints in this paper should be:  
\[\alpha,\beta,\gamma\in[0,1] \tag{12}\]  
\[\alpha+\beta+\gamma=1 \tag{13}\]  
\[x_{ij}=\begin{cases}\infty&t_{ij}>t_{limit}\\ 1&t_{ij}<t_{limit}\end{cases} \tag{14}\]  
\[y_{ij}=\begin{cases}\infty&d_{ij}>1.5d_{min}\\ 1&d_{ij}<1.5d_{min}\end{cases} \tag{15}\]  
\[z_{ij}=\begin{cases}\infty&E_{ij}>E_{limit}\\ 1&E_{ij}<E_{limit}\end{cases} \tag{16}\]  
where \(t_{limit}\) is the maximum travel time between nodes \((i,j)\) set by the driver, \(d_{min}\) is the minimum travel distance between nodes \((i,j)\) set by the driver and \(E_{limit}\) is the maximum travel cost between nodes \((i,j)\) set by the driver. Constraints (12) and (13) ensure that the weight parameters meet the basic conditions. Constraints (14)-(16) define the specific needs of autonomous driving.  
Through constraints (6)-(8), the travel time of a car under different traffic flows, intersections and turning directions can be limited and the set travel time is more reasonable. Through constraint (9), it is possible to check whether the travel distances meet the constraint after route planning and remove unreasonable routes. The travel cost under different driving conditions can be set by constraints (10) and (11). The weight values of personal preference can be defined by constraints (12) and (13) and the critical values of travel time, travel distance and travel cost can be set by constraints (14)-(16).  
As shown in Algorithm 1, after all possible paths and personal preference values are given, all possible paths are traversed and the travel times, travel distances and travel costs between nodes are calculated to obtain the comprehensive cost for a specific path, and then costs of all possible paths are sorted to return to the best path and the lowest cost.  
```
1:\(value\)
2:\(bestset\)
3:\(\alpha,\beta,\gamma,d_{min},E_{limit}\gets value\)
4:\(mincost,bestindex\gets Inf,0\)
5:\(n\leftarrow\) number of (the length of \(set\))
6:while\(i\leq n\)do
7:\(m\leftarrow\) number of (the length of \(set[i]\))
8:for\(j\) in \(m\)do
9:\(cost\leftarrow\alpha Nor(TT_{j})\times x_{j}+\beta Nor(TD_{j})\times y_{j}+ \gamma Nor(TC_{j})\times z_{j}\)
10:if\(mincost\leq cost\)then
11:\(mincost\gets cost\)
12:\(bestindex\gets i\)
13:endif
14:endfor
15:endwhile
16:\(bestset\gets set[i]\)
17:return\(bestset\)
```  
**Algorithm 1** Optimization method procedure