# Integrated Framework for Bus Timetabling and Scheduling in Multi-Line Operation Mode
## 2 Problem Description
### Solution Structure (Output)  
As mentioned above, the departure times of trips and the vehicles of trips should be decision variables for the integration of TT and VS. We relate these two groups of decision variables by constructing the multiple vehicles' trip-link chains with departure time information, as shown in Figure 3. A complete vehicle-based solution structure \(TS\) contains multiple vehicles' trip-link chains \(VC\), represented as \(TS=\{VC_{1},VC_{2},\ldots,VC_{nc}\}\). Every vehicle \(i\) has a trip-link chain \(VC_{i}\), which contains multiple chronologically ordered trips \(Tr\), represented as \(VC_{i}=\{Tr_{1}^{i},Tr_{2}^{i},\ldots,Tr_{ntr_{c}}^{i}\}\). Both decision variables and servo variables can be included as elements in \(Tr\).The \(j\)th trip of vehicle \(i\) is represented as \(Tr_{j}^{i}=\left\{i_{j}^{i},st_{j}^{i},rt_{j}^{i},np_{j}^{i},o_{j}^{i}\right\}\), which is marked in light blue in Figure 3. Among them, the line numbers \(l\) and the departure times \(st\) are decision variables. The line numbers satisfies \(l\in L\) unless \(l=\varnothing\). The vehicles of trips are implicit in the structure as the indexes. Thus, an integrated solution that includes both TT decisions and VS decisions is organized. The servo variables include run time \(rt\), passenger number \(np\), and chronological order number \(o\). \(rt\) and \(np\) are determined by the input data \(ftr_{t}^{l}\) and \(fnp_{t}^{l}\) (described in Section 2.2), which satisfy the Equations (2) and (3). Thus, a vehicle-based solution structure can be represented as \(TS=\left\{\left(l_{j}^{i},st_{j}^{i},rt_{j}^{i},np_{j}^{i},o_{j}^{i}\right) \middle|i\in\{1,2,\ldots,nc\},\,j\in\{1,2,..,ntr_{c}\}\right\}\).  
\[rt_{j}^{i}=frt_{st_{j}^{i}}^{i} \tag{2}\]  
\[np_{j}^{i}=\sum_{z=ta}^{tb-1}np_{z}^{i}\,\left(ta=lst_{o_{j}^{i}-1}^{i},tb=lst_ {o_{j}^{i}}^{i}\right) \tag{3}\]  
\[lst_{o_{j}^{i}}^{i}=st_{j}^{i} \tag{4}\]  
Compared with the line-based structure used in other typical papers [14; 16], the vehicle-based structure can significantly reduce search complexity and improve optimization efficiency, because we can calculate and judge the performability of trips and availability of vehicles more directly with the vehicle-based structure, as shown in Figure 4. This will be explained in detail as follows.  
Figure 3: Vehicle-based solution structure for M-TT/VS.  
In the optimization process, there are two indispensable and frequent processes: **(1)** judging whether the operation plan of each vehicle can be implemented; **(2)** assessing the feasible range for adjustment through two continuous trips of a vehicle. These processes are based on a sub-search process: for any trip \(j\) of vehicle \(i\), find the next trip \(j+1\) of vehicle \(i\). In the line-based structure, the lines' trip-link includes the decision variables, represented as \(LC_{k}=\left\{\left.\left(lst_{j}^{k},c_{j}^{k}\right)\right|j\in\left\{1,2,.., ntr_{l}\right\}\right\}\) for the single line \(k\). A complete line-based solution structure \(LS\) contains multiple lines' trip-link chains \(LC\). We should do additional searches and calculations for the sub-search process with this line-based structure, as shown in Table 2. The time complexity with the line-based structure is estimated to be \(O(nl\times ntr_{l}+nl+ntr_{c}\times ntr_{c})\) for a sub-search task. But in the vehicle-based structure, we can get the next trip \(T_{j+1}^{i}\) directly by indexing with time complexity \(O(1)\). Obviously, the use of a line-based structure will cause a significant time cost in the optimization process, especially in the multi-line operation mode. Because the search task's time complexity, the line-based structure increases with the number of lines \(nl\). Therefore, we use the vehicle-based structure to improve search and calculation efficiency in the optimization process. Of course, after the optimization process, the vehicle-based solution can be re-organized as the line-based solution.