## 4 The Proposed Problem Formulations
### Problem Variant #2: Headways Optimization  
The second problem variant proposes optimizing not only the offsets of each line but also the headways of each line. Headways are allowed to vary within a fixed range of the reference value \(F^{i}\). The interval for variation is defined by \(F^{i}(1-\alpha)\leq X^{i}_{r}-X^{i}_{r-1}\leq F^{i}(1+\alpha),\forall r\in 1,2,\ldots,f_{i}\). To work under the assumption of maintaining an appropriate quality of service for the transportation system, which is assumed to be fairly provided by the current situation (i.e., using the reference values for the time difference between consecutive trips of each line), small values of \(\alpha\) are considered (see a graphical description in Figure 3). Figure 3: Graphical representation of BSP variant #2. The offset (\(X^{i}_{1}\)) and headways (\(F^{i}_{r}\)) (in blue) are the control variables, and departures are separated by variable headway values. The mathematical model of BSP variant #2 as an MIP problem is formulated in Equations (6)-(13). maximize \[\sum_{b\in B}\big{(}\sum_{r=1}^{f_{1}}\sum_{s=1}^{f_{j}}Z_{rsb}^{ij} \big{)}\cdot\frac{P_{b}^{ij}\times(X_{r}^{i}-X_{r-1}^{i})}{T}\] (6) subject to \[Z_{rsb}^{ij}\leq 1+\frac{(A_{rb}^{i}+d_{b}^{ij}+W_{b}^{ij})-A_{sb}^{ j}}{M}, \forall b=<i,j,d_{b}^{ij}>\in B,\] (7) \[Z_{rsb}^{ij}\leq 1+\frac{A_{sb}^{j}-(A_{rb}^{ij}+d_{b}^{ij})}{M}, \forall b=<i,j,d_{b}^{ij}>\in B,\] \[\text{with }A_{rb}^{i}=X_{r}^{i}+TT_{b}^{i},\ A_{sb}^{j}=X_{s}^{j}+ TT_{b}^{j}\] \[\sum_{s=1}^{f_{j}}Z_{rsb}^{ij}\leq 1,\,\forall i,j\in I,1\leq r \leq f_{i}\] (9) \[\max(F^{i}(1-\alpha),h_{i})\leq X_{r}^{i}-X_{r-1}^{i}, \forall r\in 2,...,f_{i}\] (10) \[X_{r}^{i}-X_{r-1}^{i}\leq\min(F^{i}(1+\alpha),H_{i}), \forall r\in 2,...,f_{i}\] (11) \[T-H_{i}\leq X_{f_{i}}^{i}\leq T,\,\forall i\in I\] (12) \[Z_{rsb}^{ij}\in\{0,1\},0\leq X_{1}^{i}\leq\min(H_{i},mod(T,F^{i}))\] (13)  
In Equations (6)-(13), \(X_{r}^{i}\) is the time of departure of trip \(r\) of line \(i\), and \(F^{i}\) is the reference value for the time difference between consecutive trips of line \(i\), as defined in problem variant #1. In turn, \(\alpha\in[0,1]\) is the coefficient used for defining the allowed deviation of times between buses from the reference value \(F^{i}\). Finally, \(X_{f_{i}}^{i}\) is the departing time of the last trips of the line \(i\). The objective function is Equation (6), i.e., maximizing the number of successful transfers completed in every transfer zone in the planning period. In this case, the demand is split considering the (flexible) time between consecutive buses of line \(i\) (i.e., \(X_{r}^{i}-X_{r-1}^{i}\)). Equations (7)-(13) formulate the problem constraints. Equations (7) and (8) define a synchronization, as in the previous problem formulation. Equation (9) guarantees that every trip \(r\) of line \(i\) synchronizes with, at most, one trip \(s\) of line \(j\). The last point is necessary because headways are part of the control variables in this case. In the previous model, headways were known in advance, so they could be pre-filtered in the case where a headway was lower than the maximum time passengers are willing to wait at some stop. Conversely, in this model, Equation (9) prevents us from counting such synchronizations more than once. Constraints in Equations (10) and (11) impose the limits for headways, according to the allowed variation \(\alpha\). Constraints in Equation (12) guarantee that the last trip is within the specified maximum range. Finally, Equation (13) defines the domain for decision variables \(Z_{rsb}^{ij}\). The formulation in Equations (6)-(13) intuitively extends the previous to incorporate headways as control variables, but it has the drawback of being quadratic in its objective function due to the product of \(Z_{rsb}^{ij}(X_{r}^{i}-X_{r-1}^{i})\). However, it is linearized by a change of variables and additional constraints.