# Using GPS Trajectories to Adaptively Plan Bus Lanes
## 3 Problem Solving
### Solution Algorithm  
We proposed a three-stage algorithm to solve the problem. The stages included (1) initialization, i.e., coding road segments based on the genetic population and creating initial populations; (2) iteration, i.e., population iteration in the GA, including selection, crossover, and mutation; and (3) result output, i.e., output of the model results. These stages are explained as follows, and Algorithm 1 gives the pseudo-code of the solution algorithm. Initialization. First, it is the road segments coding of GA. In GA, there are three main types of individual coding: (1) binary encoding, (2) permutation encoding, and (3) value encoding. To map road segments to individual codes, binary encoding is selected, where 1 means that the road segment is selected as a bus lane candidate solution, and 0 means that it is not selected. In this sense, the initial solutions with size \(N\) are a set of binary characters corresponding to the road segment as the population \(P_{0}\). Figure 1 shows an example of candidate road segments and the corresponding GA encoding. After generating the initial solution, it should verify the feasibility of the solutions. Here we followed the constraint-domination method proposed in [37]. It calculates the constraint violation value \(CV(x)\) of each solution \(x\) using the following Equation (11):  
\[CV(x)=\sum_{j}\left\langle\overline{g}_{j}(x)\right\rangle+\sum_{k}\left| \overline{h}_{k}(x)\right| \tag{11}\]  
where \(g_{j}(x)\), which is inequality constraint, includes C\({}_{2}\), C\({}_{3}\), C\({}_{4}\), and C\({}_{5}\) constraints in the model, and \(h_{k}(x)\), which is equality constraint, includes C\({}_{1}\) constraint in the model. \(\overline{g}_{j}(x)\) and \(\overline{h}_{k}(x)\) are the normalized constraint functions. For \(\left\langle\alpha\right\rangle\), if \(\alpha<0\), \(\left\langle\alpha\right\rangle=0\), else \(\left\langle\alpha\right\rangle=\left|\alpha\right|\). The constraint violation value could be used in subsequent operations of elitist selection and creation of offspring population. Then, we calculate the multiobjective score of \(P_{0}\) and use the constraint violation value and multiobjective scores to obtain the individual nondominated sorting and crowding distance results. The details about nondominated sorting and crowding distance are discussed in [PERSON], [PERSON], [PERSON], and [PERSON] [34]. Iteration. In NSGA2, selection, crossover, and mutation are basic operators for finding optimum solution. First it is the elitist selection operator's role to choose two individuals from parent populations. It is based on the constraint violation value, nondominated sorting, and crowding distance. Then, it is the crossover operator which is used to exchange parts of the encodings of two parent individuals. Crossover operators include single-point, two-point, and uniform crossover functions. In this paper, two-point crossover is selected. The mutation operator enhances individual diversity by changing individual codings with a small probability. Here, the binary mutation operator determines whether the road segment should be selected as a bus lane. Then, it calculates the constraint violation value and multiobjective scores of the two offspring individuals. Finally, repeating the above operators occurs until generating the offspring population \(Q_{t}\) with size \(N\). ```
Input: road network \(G\), bus trajectory \(Tr\), budget \(B\), adjustment factor \(\alpha\), lanes' continuity constraints \(k_{c}\) and \(k_{nom}\), traffic flow threshold \(f\), number of population \(N\), Maximum generation \(T\). Output: Planning bus lanes \(E^{\prime}\). //Stage 1: Initialize
1: Eliminate invalid road segments. 2: Generate a group of initial solutions as population \(P_{0}\) with size \(N\) based on max budget \(B\) and binary encoding of \(G\). 3: Calculate objective function scores \(F(x)\) and constraint violation value \(CV(x)\). 4: Do non-domination sorting based on \(CV(x)\) and \(F(x)\) and calculate crowding distance, \(t=0\).