# Integrated Framework for Bus Timetabling and Scheduling in Multi-Line Operation Mode
## 3 Methodology
### Solution Algorithm
#### 3.2.2 Phase 2: Optimize Solutions  
The neighborhood search algorithm is a typical local search algorithm [24]. The design of neighborhood search rules is flexible and can be easily combined with heuristic information related to the problem. Therefore, to optimize the M-TT/VS problem, we design a heuristic optimization algorithm based on the neighborhood search algorithm HNS.  
The HNS algorithm flowchart is shown in Figure 7. The differences in heuristic search algorithms are mainly reflected in the search rules. For example, a genetic algorithm generates candidate solutions by crossover and mutation, while a neighborhood search algorithm produces candidate solutions by detriment and repairment. We designed the \"destroy\" rule and \"repair\" rule. The \"destroy\" rule refers to the rule of selecting decision variables that need to be changed in a solution. We fused heuristic information \(cp_{j}^{i}\) to guide the selection probability. Heuristic information \(cp_{k}^{j}\) refers to the difference between the passenger number of trip carries and the base value. The more significant the difference is, the more likely it is to be selected. A roulette wheel is used to choose the target trip \(Tr_{j}^{i}\). We define those similar trips near the target trip as needing change. For example, suppose the trip \(Tr_{j}^{i}\) carries more than the base value. In that case, the trips \([k_{j}^{i}-R,k_{j}^{i}+R]\) of line \(l_{j^{\prime}}^{i}\) which also carries more than the base value, are the similar trips. The \"repair\" rule refers to the method of trip adjustment. For trips that need to be adjusted, we designed  
Figure 6: The flowchart of algorithm CEG.  
a comprehensive tabu table, requiring trips to be adjusted without breaking constraints. In addition, we require trip adjustment in line with practical experience limitations. If the number of passengers on a trip exceeds the baseline, we will adjust the departure interval as little as possible. The heuristic information and the comprehensive tabu table are described in detail below.  
**Heuristic information**\(cp_{j}^{i}\). Based on practical operational experience, service supply should conform to changes in demand. If the number of passengers on a trip exceeds the baseline, our optimization direction should reduce the number. The specific operation method is to reduce the departure interval, which means we should push forward the departure time of the next trip in the same direction and vice versa. Based on this idea, we propose heuristic information \(cp_{j}^{i}\). The numerical value of \(cd_{i}^{j}\) provides the probability the trip will be destroyed, and \(cp_{i}^{j}\) plus or minus tells us how to adjust trips.  
\[cp_{j}^{i}=np_{j}^{i}-\overline{np_{j}}_{j} \tag{18}\]  
\[cd_{j}^{i}=\left|cp_{j}^{i}\right| \tag{19}\]  
**Comprehensive tabu table**. In the optimization process, it is essential to ensure the feasibility of the solution, especially when there are many external constraints. We construct a comprehensive tabu table to confirm the validity of our solution. We can adjust solutions to the extent that the constraints allow. These constraints can be divided into two categories: (a) in the same line \(l_{j}^{i}\) of the target \(T_{rj}^{i}\), the forward and backward adjustment should be  
Figure 7: The flowchart of algorithm HNS.  
within a specific range to avoid repeated departure times and unreasonable departure intervals; (b) in the same vehicle \(j\) of the target \(T_{j}^{i}\), the connection between \(T_{j}^{i-1}\), \(T_{j}^{i}\) and \(T_{j}^{i+1}\) also limits the range of adjustment to avoid conflicting vehicle arrangements. \(ct_{l}^{i,j}\) and \(ctt_{r}^{i,j}\) are the boundaries where \(st_{i}^{j}\) can be adjusted forward and backward, respectively.  
\[ctt_{l}^{i,j}=\max\biggl{(}t_{min},lst_{j}^{i^{\prime}_{l}},\;st_{j}^{i-1}+rt_{ j}^{i-1}+ita_{min}\biggr{)} \tag{20}\]  
\[ctt_{r}^{i,j}=\min\biggl{(}t_{max},lst_{j^{\prime}_{l}+1}^{i^{\prime}_{l}},\; st_{j}^{i+1}-ita_{min}-rt_{j}^{i}\biggr{)} \tag{21}\]