## 2 Optimal Lane Change Path Planning Based on the NSGA-II and TOPSIS Algorithms
### Lane Change Trajectory Based on Polynomials  
In order to ensure that the velocity, acceleration, and curvature of the lane change trajectory are continuous and bounded and at the same time meet the boundary conditions at the beginning and end of the lane change, the lane change trajectory based on the quintic polynomial is adopted in this section, which can be expressed as:  
\[\left\{\begin{array}{l}x(t)=a_{0}+a_{1}t+a_{2}t^{2}+a_{3}t^{3}+a_{4}t^{4}+a_{5 }t^{5}\\ y(x)=b_{0}+b_{1}x+b_{2}x^{2}+b_{3}x^{3}+b_{4}x^{4}+b_{5}x^{5}\end{array}\right. \tag{1}\]  
where, \(a_{i},b_{i}(i=1,2\cdots 5)\) are coefficients to be determined. At the initial time \(t_{0}\) and the end time \(t_{f}\) of the lane changing, the longitudinal and lateral lane change boundary conditions meet Equations (2) and (3), respectively,  
\[\left\{\begin{array}{l}x(t_{0})=0,\dot{x}(t_{0})=v_{0},\ddot{x}(t_{0})=0\\ x\Big{(}t_{f}\Big{)}=x_{f},\ddot{x}\Big{(}t_{f}\Big{)}=v_{f},\ddot{x}\Big{(}t_ {f}\Big{)}=0\end{array}\right. \tag{2}\]  
\[\left\{\begin{array}{l}y(x_{0})=0,\dot{y}(x_{0})=0,\ddot{y}(x_{0})=0\\ y\Big{(}x_{f}\Big{)}=w,\dot{y}\Big{(}x_{f}\Big{)}=0,\ddot{y}\Big{(}x_{f}\Big{)}=0 \end{array}\right. \tag{3}\]  
In Equations (2) and (3), each state parameter and its definition are shown in Table 1. In order to simplify the calculation, \(t_{0}=0,w=3.75m\) are set in this study, in which \(w\) is the lateral displacement of lane changing, that is, the lane width. Longitudinal displacement \(\Delta x=x_{f}\) and lane change time \(\Delta t=t_{f}\) are variables that need to be optimized by the NSGA-II Algorithm.  
Through the lane changing boundary conditions in Equations (2) and (3), the quintic polynomial lane changing trajectory can be obtained. Assuming that the size of the ego vehicle and the surrounding traffic vehicles are the same, with a length of 4.2 m and a width of 1.82 m, the lane changing scene is as follows: The velocity of the ego vehicle is 50 km/h at the beginning of the lane change and 60 km/h at the end of the lane change. The velocity of the vehicle ahead in the current lane is 50 km/h, and the distance from the ego vehicle is 30 m. The velocity of the vehicle in front of the target lane is 60 km/h, and the distance from the ego vehicle is 50 m. The velocity of the vehicle behind the target lane is 55 km/h, and the distance from the ego vehicle is 30 m. The schematic diagram of the lane changing process is shown in Figure 1.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**State** & \\
**Parameters** & **Definition** \\ \hline \(x(t_{0})\) & The longitudinal coordinate of the ego vehicle at the beginning of the lane changing \\ \(\dot{x}(t_{0})\) & The longitudinal velocity of the ego vehicle at the beginning of the lane changing \\ \(\ddot{x}(t_{0})\) & The longitudinal acceleration of the ego vehicle at the beginning of the lane changing \\ \(x(t_{f})\) & The longitudinal coordinate of the ego vehicle at the end of the lane changing \\ \(\dot{x}(t_{f})\) & The longitudinal velocity of the ego vehicle at the end of the lane changing \\ \(\dot{x}(t_{f})\) & The longitudinal acceleration of the ego vehicle at the end of the lane changing
According to the experience, the lane change time \(\Delta t\) was selected as 4-8 s, and the longitudinal displacement of lane change \(\Delta x\) was 60-135 m, in which the lane change time was 0.2 s as the simulation step and the longitudinal displacement was 2 m as the simulation step for the simulation experiment. The unconstrained lane changing trajectory cluster is obtained, as shown in Figure 2.