## 3 Algorithm Design
### Relative Algorithm
#### 3.2.1 Optimization of Method of Successive Averages (MSA)  
MSA is a traditional algorithm to solve the SUE problem. The general process is as follows:  
Step 1: Initialization. The free travel time is taken as the travel impedance to load the traffic, and the initial value is obtained \(\mathbf{x}^{(1)}\), the iteration count is defined as \(\tau=1\). Figure 1: Flowchart of the algorithm. Step 2: The impedance is updated from the previous section flow as \(t^{\tau}_{ij}=t(x^{(\tau)}_{ij})\), and then the auxiliary flow \(\mathbf{y}^{(\tau)}\) can be obtained by distributing the flow on the basis of the new impedance. Step 3: Calculating the search direction \(\mathbf{d}^{(\tau)}\), and the \"successive average\" movement is carried out as follows:  
\[\mathbf{d}^{(\tau)} =\mathbf{y}^{(\tau)}-\mathbf{x}^{(\tau)}\] \[\mathbf{x}^{(\tau+1)} =\mathbf{x}^{(\tau)}+\frac{1}{\tau}\mathbf{d}^{(\tau)}.\]  
Step 4: Convergence check. If satisfied, stop, otherwise continue with step 2. For traffic loading, dial algorithm can be used, which will not be discussed here. In terms of convergence conditions, in practical application, the number of times can be selected to judge regardless of the convergence situation; the following formula can also be used:  
\[\frac{\sqrt{\frac{\sum\limits_{i}\left(\mathbf{x}^{\tau+1}_{ij}- \mathbf{x}^{\tau}_{ij}\right)}{\mathbf{x}^{\tau}_{ij}}}}{\frac{\mathbf{x}^{ \tau}_{ij}}{\mathbf{x}^{\tau}_{ij}}}\leq\varphi,\] \[\overline{x}^{\tau}_{ij}=\frac{1}{n}(x^{\tau}_{ij}+x^{\tau-1}_{ ij}+\cdots x^{\tau-m+1}_{ij}),\]  
where \(\varphi\) can take a minimum constant. \(\tau>n\) and \(n\) can be taken as \(n=3\). It can be found that the original MSA algorithm does not involve the evaluation of the SUE model, and the step size is \"successive average sequence\" defined by itself. In self convergence, the speed is very slow, and the accuracy is difficult to guarantee by defining the convergence times. In terms of evaluation function, the SUE model based on origin avoids path enumeration, and can improve the convergence efficiency of MSA. [PERSON] has verified that the efficiency of the improved MSA is higher than the original by the Sioux Fall network and the Barcelona network [28]. Step 1: Initialization. Get the initial solutions \(\mathbf{x}^{(1)}\), let the count function \(\tau=1\). Step 2: Look for search directions. The auxiliary solution is found to satisfy the sub problem, which is:  
\[\min\hat{Z}(\mathbf{y})=\sum\limits_{(i,j)\in L}t_{ij}\Big{[}x^{ (\tau)}_{ij}\Big{]}y_{ij}+\frac{1}{\theta}\sum\limits_{o\in O}\left\{\sum \limits_{(i,j)\in L}y_{ij}^{o}\,Inv_{ij}^{o}-\sum\limits_{j\in N}\left[(\sum \limits_{(i,j)\in L}y_{ij}^{o})\,In(\sum\limits_{(i,j)\in L}y_{ij}^{o})\right]\right\}\] \[s.t.\sum\limits_{i}y^{o}_{ik}-\sum\limits_{j}y^{o}_{kj}+\sum \limits_{d}q_{ad}\delta_{ak}-\delta_{ak}q_{od}=0,\] \[y_{ij}=\sum\limits_{o}y^{o}_{ij},\] \[y^{o}_{ij}\geq 0.\]  
where \(y^{o}_{ij}\) represents the flow of the road section \((i,j)\) from the origin \(o\), and the descent direction can be similar to the original MSA. Step 3: Convergence check. If the convergence condition is reached, stop. Otherwise, proceed to step 4. Step 4: Update step size. The solution \(\mathbf{\mu}^{(\tau)}\) is nonnegative number and satisfies the following conditions:  
\[\min_{0\leq\mu\leq 1}Z\Big{[}\mathbf{x}^{(\tau)}+\mathbf{\mu}^{(\tau)}\mathbf{ d}^{(\tau)}\Big{]}.\]  
Step 5: Move. Get new traffic flow \(\mathbf{x}^{(\tau+1)}\):  
\[\mathbf{d}^{(\tau)} =\mathbf{y}^{(\tau)}-\mathbf{x}^{(\tau)}\]0  
Let \(\tau=\tau+1\), and go back to step 2. It can be found that the key of the new optimization algorithm is to solve the sub problem of step 2, where the dial or bell algorithm is used to load. Step 1 can also use travel time of zero flow to load bell second algorithm. The convergence criterion can be set to the following Equation (9).