## 4 The Proposed Problem Formulations
### Problem Data  
The formulation of the studied problem considers:  
* The planning period \([0,T]\), expressed in minutes.
* A set of bus lines \(I=\{i_{1},i_{2},\ldots,i_{n}\}\), whose routes are fixed and known beforehand.
* The total trips needed to perform in order to fulfill the demand for each line \(i\) within the planning period \([0,T]\) is \(f_{i}\). The demand considers both direct trips and transfers.
* A set of _synchronization nodes_, or _transfer zones_, \(B=\{b_{1},b_{2},\ldots,b_{m}\}\). Each transfer zone \(b\in B\) has three elements \(<\!\!i,j,d_{b}^{ij}\!\!>:i\) and \(j\) are the lines that may synchronize, and \(d_{b}^{ij}\) is the distance that separates the bus stops for lines \(i\) and \(j\) in \(b\). Each \(b\) considers two bus stops with transfer demand between lines \(i\) and \(j\), as described in Figure 1. The distance \(d_{b}^{ij}\) defines the time that a passenger must walk to transfer from the bus stop of line \(i\) to the bus stop of line \(j\) in the considered transfer zone.
* A _traveling time function_\(TT:I\times B\rightarrow\mathbf{Z}\). \(TT_{b}^{i}=TT(i,b)\) defining the time that buses in line \(i\) need to travel to reach the transfer zone \(b\). The time is measured from the departure of the line. The traveling time depends of the studied scenario and is affected by several factors such as the maximum allowed speed, the traffic in the city, the travel demands, etc.
* A _demand function_\(P:I\times I\times B\rightarrow\mathbf{Z}\). \(P_{b}^{ij}=P(i,j,b)\) defines how many passengers perform a transfer from line \(i\) to line \(j\) in transfer zone \(b\) in \([0,T]\). As described in the previous subsection, a hypothesis of uniform demand is assumed. Thus, an effective number transfers from a trip of line \(i\) to a trip of line \(j\) is properly defined, taking into account the time between two consecutive trips of buses in line \(i\). The uniform demand hypothesis is realistic for short periods, such as in the problem instances defined and solved for the addressed case study.
* The maximum time \(W_{b}^{ij}\) that passengers are willing to wait for line \(j\), after alighting from line \(i\) and walking to the corresponding stop of line \(j\) in a transfer zone \(b\). Two trips of line \(i\) and \(j\) are synchronized for transfers if and only if the waiting time of passengers that transfer from line \(i\) to line \(j\) is lower than or equal to \(W_{b}^{ij}\).
* A set of departing times of each trip \(r\) of line \(i\), \(X_{r}^{i}\), which define the _headways_ of the line as the time between two consecutive trips \(F_{r}^{i}=(X_{r}^{i}-X_{r-1}^{i})\). Headway values must be within a range of minimum (\(h_{i}\)) and maximum (\(H_{i}\)) headways for that line. Both extreme values are defined by the city administration or the bus system operator. The _offset_ of each line is the departing time of the first trip of the line (\(X_{i}^{i}\)). Withoutlosing generality, the model assumes \(X_{0}^{i}=0\). All trips of each line must start within the planning period \([0,T]\) (i.e., \(X_{f_{i}}^{i}\leq T\)).  
Considering the previously defined elements, two variants of the BSP are formulated, accounting for the optimization of just offsets and both offsets and headways for each line, respectively. The next subsections describe these two problem variants.