# Research on Optimization of Multi-Objective Regional Public Transportation Scheduling
## 4 Solution Algorithms
### The NSGA-II Algorithm  
The NSGA-II algorithm is one of the most commonly used multi-objective optimization algorithms, but it has some drawbacks of an uneven convergence of the population and the ease of falling into the local optimal solution [31]. In order to avoid premature convergence of Genetic algorithm, it is necessary to keep the diversity of population. According to the characteristics of this model, an adaptive adjusted model of the crossoverand the mutation probability is introduced, and an adaptive crossover operator for judging the similarity of chromosomes and multipoint mutation operator are designed. (1) Construction of chromosomes  
Chromosome \(X=(X_{1},X_{2},\cdots,X_{N})\) is designed by a positive integer, where gene \(X_{i}=(A_{1},A_{2},\cdots,A_{x_{i}})\) of the chromosome represents the set of the departure time for each bus of line \(i\). Figure 1 illustrates the specific structure of a randomized chromosome. The process of generating a chromosome is as follows:  
Step 1: Let \(x_{i}=1\) and \(A_{1}=r_{0}(I_{\max}-I_{\min})+I_{\min}+T_{1}\) (where \(r_{0}\) is a random number obeying 0-1 uniform distribution). Step 2: \(x_{i}=x_{i}+1\), if \(A_{x_{i}-1}+r_{0}(I_{\max}-I_{\min})+I_{\min}\leq T_{2}\), let \(A_{x_{i}}=A_{x_{i}-1}+r_{0}(I_{\max}-I_{\min})+I_{\min}\), return to Step 2. Otherwise, go to Step 3. Step 3: if \(i<N\), \(i=i+1\), return to Step 2. Otherwise, stop. (2) Select operator  
The selection of the parental population is using binary tournament method calculate the performing non-dominated sorting and crowding calculation of the parental population. (3) Adaptive adjusted model for crossover and mutation probability  
In order to improve the search performance of the algorithm and avoid falling into the local optimal solution, an adjusted model is adopted to adjust the crossover probability and mutation probability. The crossover probability can be adjusted by the following method. \[P_{c}=\left\{ \begin{array}{ll}\frac{\delta_{1}-g}{4\delta_{1}}+P_{c1},0\leq g \leq g_{1},\\ \frac{g_{2}-g}{4\delta_{(2}-g_{1})}+P_{c2},g_{1}\leq g\leq g_{2},\\ \frac{g_{\max}-g}{2(g_{\max}-g_{2})(1-g)}+P_{c2}\beta,g_{2}\leq g\leq g_{\max},\end{array} \right. \tag{13}\]  
where \(P_{c1}\), \(P_{c2}\) are the crossover probability for different generations, \(\beta\) is the adjustment coefficient of crossover and mutation probability in the later stage of evolution. \(g\) is the current evolutionary generation, \(g_{1},g_{2}\) are the dividing points of the early stage and the middle stage, and \(g_{\max}\) is the total maximum evolution generation. Furthermore, the mutation probability can be adjusted by the following method according to the running phase. \[P_{m}=\left\{ \begin{array}{ll}\frac{(P_{m1}-\frac{1}{c})(g_{1}-g)}{g_{1}}+ \frac{1}{c_{c}},0\leq g\leq g_{1},\\ \frac{(\frac{1}{c}-\frac{P_{m1}}{c})(g_{2}-g)}{g_{2}-g_{1}}+\frac{P_{m1}}{f_{ c}},g_{1}\leq g\leq g_{2},\\ \frac{P_{m1}}{f_{c2}}(g_{\max}-g)}+\frac{P_{m1}}{f_{c}}\beta,g_{2}\leq g\leq g _{\max}.\end{array} \right. \tag{14}\]  
where \(L_{c}\) represents the total number of bus departures for all lines in a chromosome, \(P_{m1}\) is the maximum mutation probability. (4) Crossover operator  
According to the character of the chromosome structure, the traditional single-point crossover is easy to fall into the local optimal solution. Therefore, an adaptive crossover operator is designed through judging the similarity of chromosomes. The process of adaptive crossover operator is stated as follows:  
Step1: Let \(i=1,k=0\). Figure 1: An example of a chromosome. Step2: If \(i>N\), then go to step 4. Otherwise, compare the number of bus departures of a line for the two selected chromosomes, if the departure times are equal, let the departure times of line \(i\) be \(x_{i}\) and go to Step3, otherwise, let \(i=i+1\), return to Step2. Step3: Count the number \(Z\) of equal departure time of lines \(i\) of the two chromosomes.