## 6 Experimental Evaluation
### Numerical Results
#### 6.2.2 Problem Variant #2: Offset and Headways Optimization  
Problem variant #2 imposes a significantly harder challenge for the studied optimization algorithms. Control variables, originally spanning a sole variable per line (offsets), also incorporate several more variables per line (headways). In addition, as mentioned in Section 4.3, in the exact model, the number of variables increases not only because of control variables (i.e., offsets and headways) but also because of auxiliary variables (i.e., synchronizations and the objective's contributions), half of which are Boolean. In turn, for the EA, the number of variables increased more than 20 times, and a correction procedure is needed to repair non-feasible solutions generated by the evolutionary operators. Both facts result in a larger and more complex search space for optimization. Table 6 reports the results of the exact algorithm for BSP variant #2. Each scenario has an associated row in the table. Columns _#vars_, _#varsCell_, and _#varsBool_, respectively, correspond to the total number of variables, the number of control variables (all of which are real variables), and the number of Boolean variables. The column named _best-sol_ reports the value of the objective function for the best solution found before timeout. Column _GAP_ corresponds to the estimated worst-case gap to the optimum, that is, the relative gap between the reported solution and the lowest upper bound for the optimum estimated up to that moment. Finally, column _time to solution_ shows the time required for the solver to find that solution. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline _Scenario_ & _\#vars_ & _\#varsCell_ & _\#varsBool_ & _Best-Sol_ & _GAP_ & _Time to Solution_ \\ \hline  
\hline \hline \end{tabular}
\end{table} 
Table 6: Summary of results of the exact algorithm for BSP variant #2. Since no instance was solved to optimality when \(\alpha=0.3\), the overall runtime was 7200 s for all instances. For example, in instance 30.40.50.4, the best solution was found in 328 seconds, and it was not improved in the remaining 6872 seconds. The rest of the processing was spent to improve the gap to the lower bound. GAPs reported in Table 6 are always best-gaps, i.e., the lowest gap, the last reported in logs before timeout. The remarkable facts of the results in Table 6 are: (i) control variables only represent between 2.5% and 5.3% of all variables, meaning that most resources in the exact approach are put into the auxiliary variables needed to reach the linear mixed integer programming formulation; (ii) the total number of variables is highly correlated with both the number of lines and bus stops; and (iii) although gap and time to solution are both correlated with the number of control and total variables, those correlations are higher for the total number of variables. The last two observations arise from computing Pearson's linear correlation coefficient over the whole set of instances used as a dataset: number of bus stops, number of lines, #_vars_, #_vars_Ctl_, _GAP_, and _time to solution_, as in Table 6.  
The most notorious difference between variant #1 and variant #2 comes from the value of \(\alpha\), not from the higher number of variables. The number and type of variables in Equations (6)-(13) are not affected by \(\alpha\), but CPLEX time-to-optimal is in the order of the second for \(\alpha=0\) (no headway tolerance at all). Conversely, when \(\alpha=0.3\), none of the solutions is proven optimal within the 2 h timeout period, and only in 7 out of the 75 instances could the best solution be found before 20 min. Thus, the increased size and complexity of the search space coming from higher values of \(\alpha\) have a much higher impact in the performance than the number of variables.