## 2 The Bus Synchronization Problem
### Mathematical Formulation
#### Variables  
\(a_{rb}^{h}=\) (continuous) time when users alight from the trip \(r\in R^{h}\) of bus line \(h\in H\) at the transfer zone \(b\in B\). \(q_{r}^{h}=\) (binary) 1 when trip \(r\in R^{h}\) of line \(h\in H\) is to be scheduled. \(x_{r}^{h}=\) (continuous) departure time of trip \(r\in R^{h}\) of bus line \(h\in H\). \(z_{rb}^{hg}=\) (binary) 1 when the trip \(r\in R^{h}\) of line \(h\in H\) and the trip \(s\in R^{g}\) of line \(g\in H\) are synchronized at transfer zone \(b\in B\) and 0 otherwise. A relevant feature is that the model does not assume a predefined number of trips per bus line. Although there is a maximum number of possible trips for each bus line \(h\in H\), i.e., \(|R^{g}|\), not all the trips have to be used. Conversely, the model aims at obtaining good headways and offset within the minimum and maximum specified headways' bounds, i.e., \(Hd_{h}^{min}\) and \(Hd_{h}^{max}\). The utmost time interval that passengers are willing to wait before boarding line \(j\), subsequent to alighting from line \(i\) and traversing to the relevant stop of line \(j\) at transfer zone \(b\), is designated as \(W_{b}^{ij}\). Then, it is considered that two trips, one of line \(i\) and the other of line \(j\), are synchronized when the following conditions hold: (i) passengers are able to alight from line \(i\) and reach the second bus stop in time to catch the trip of line \(j\); (ii) the waiting time for these passengers at the bus stop awaiting the transfer is less than or equal to \(W_{b}^{ij}\); and (iii) both of the previous conditions occur within the defined planning period. With these elements, the MILP model formulation can be presented as follows:  
\[\text{max}\quad FO_{t}=\sum_{b\in B}\ \sum_{h_{g}\in H}\ \sum_{r\in R^{h},r>1}\ \sum_{s\in R^{g}}\left(z_{rsb}^{hg}\cdot\frac{Dem_{b}^{hg} \times(x_{r}^{h}-x_{r-1}^{h})}{T}\right) \tag{1}\] \[\text{min}\quad FO_{c}=\sum_{h\in H}\mathcal{C}b^{h}\cdot\left( \sum_{r\in R^{h}}q_{r}^{i}\right) \tag{2}\]  
\[\text{s.t.}\quad z_{rsb}^{hg}\leq 1+\frac{(a_{rb}^{h}+Wd_{b}^{hg}+ Tol_{b}^{hg})-a_{sb}^{g}}{BigM},\ \forall\ h,g\in H,r\in R^{h}, \tag{3}\] \[z_{rsb}^{hg}\leq 1+\frac{a_{sb}^{g}-(a_{rb}^{h}+Wd_{b}^{hg})}{BigM}, \forall\ h,g\in H,r\in R^{h},\] (4) \[a_{rb}^{h}=x_{r}^{h}+TT_{b}^{h}, \forall\ h\in H,r\in R^{h}\] (5) \[\sum_{s\in R^{g}}z_{rsb}^{hg}\leq 1, \forall\ h,g\in H,r\in R^{h},\] (6) \[\frac{T+1-x_{r}^{h}}{T+1}\leq q_{r}^{h}, \forall\ h\in H,r\in R^{h}\] (7) \[q_{r}^{h}\leq 1+\frac{T-x_{r}^{h}}{N}, \forall\ h\in H,r\in R^{h}\] (8) \[z_{rsb}^{hg}\leq q_{s}^{g}, \forall h,g\in H,r\in R^{h},\] (9) \[s\in R^{g},b\in B\] (10) \[\text{min}\quad FO_{c}=\sum_{h\in H}\mathcal{C}b^{h}\cdot\left( \sum_{r\in R^{h}}q_{r}^{i}\right) \tag{2}\]0 (11) \[\text{min}\quad FO_{c}=\sum_{h\in H}\mathcal{C}b^{h}\cdot\left( \sum_{r\in R^{h}}q_{r}^{i}\right) \tag{2}\]1 (12) \[\text{min}\quad FO_{c}=\sum_{h\in H}\mathcal{C}b^{h}\cdot\left( \sum_{r\in R^{h}}q_{r}^{i}\right) \tag{2}\]2 (13) \[\text{min}\quad FO_{c}=\sum_{h\in H}\mathcal{C}b^{h}\cdot\left( \sum_{r\in R^{h}}q_{r}^{i}\right) \tag{2}\]3 (14) \[\text{min}\quad FO_{c}=\sum_{h\in H}\mathcal{C}b^{h}\cdot\left( \sum_{r\in R^{h}}q_{r}^{i}\right) \tag{2}\]4  
The objective function outlined in Equation (1) aims at maximizing the demand fulfilled by the successful transfers throughout the planning period by considering the transfer between all the trips of any pair of bus lines in all the transfer zones. The demand is calculated under the assumption of uniform distribution in the planning horizon and thus is directly proportional to the interval of time between two consecutive trips (\(x_{r}^{h}-x_{r-1}^{h}\)) as long as a successful transfer was achieved (\(z_{rsb}^{hg}=1\)). The objective function (2) aims at minimizing the cost of the system in which each bus line is multiplied by a cost parameter \(\mathcal{C}b^{h}\) estimated with the cost model described in Section 2.3. Clearly, both objective functions represent conflicting goals.