## 2 The Bus Synchronization Problem
### The Bi-Objective Bus Synchronization Problem in Montevideo  
The target problem of this work is based on the public transport system in Montevideo, Uruguay, which is operated under the Metropolitan Transport System (STM) [19]. The STM was implemented to integrate all public transport services in Montevideo and its metropolitan area, including urban agglomerations in nearby departments, namely Canelones and San Jose. In total, the STM consists of 145 main bus lines, over a thousand line variants, and approximately five thousand bus stops across three departments [20]. These numbers are substantial for a city like Montevideo and emphasize the importance of effective planning to ensure a high-quality service for citizens relying on public transportation. Since its beginning, the STM has introduced various technologies to enhance the efficiency of public transport. One significant advancement was the implementation of a smart card payment system for trips [21; 22]. Apart from diverse practical advantages for users, the smart card enables the collection of relevant data and facilitates the extraction \begin{table}
\begin{tabular}{l l} \hline \hline \multicolumn{2}{c}{Cost model} \\ \hline \(VH\) & Operating hours of a bus \\ \(VKM\) & Distance traveled by a bus in kilometers \\ \(U_{VH}\) & Unitary cost per operating hour of buses \\ \(U_{VKM}\) & Unitary cost per kilometer traveled by a bus \\ \hline \multicolumn{2}{c}{Mathematical formulation of Bus Synchronization Problem} \\ \hline \(H\) & Set of bus lines \\ \hline \(B\) & Set of transfer zones \\ \hline \(R^{H}\) & Set of indices of available trips for bus line \(h\in H\) along the planning horizon \\ \hline \(T\) & Duration of the planning horizon, measured in minutes. \\ \hline \(Dem_{b}^{kg}\) & Estimated demand for transfers between lines \(h,g\in H\) at transfer zone \(b\in B\) during the whole planning horizon. \\ \hline \(Co^{h}\) & Cost per trip for bus line \(h\in H\) \\ \hline \(Wd_{b}^{kg}\) & Time that takes to users to walk between bus stops of bus lines \(h\in H\) and \(g\in H\) in transfer zone \(b\in B\). \\ \hline \(Tol_{b}^{kg}\) & maximum threshold time that users are willing to wait for a transfer from bus line \(h\in H\) to bus line \(g\in H\) in a transfer zone \(b\in B\). \\ \hline \(TT_{b}^{h}\) & Travel time that requires a bus line \(h\in H\) to travel from the departure station to transfer zone \(b\in B\). \\ \hline \(N_{h}\) & Minimum number of trips of bus line \(h\in H\) to guarantee the quality of service for users who do not transfer. \\ \hline \(Hd_{h}^{min}\) & Minimum bound for the headway of bus line \(h\in H\). \\ \hline \(Hd_{h}^{max}\) & Maximum bound for the headway of bus line \(h\in H\). \\ \hline \(a_{rb}^{h}\) & Continuous variable that indicates the time when users alight from the trip \(r\in R^{h}\) of bus line \(h\in H\) at the transfer zone \(b\in B\). \\ \hline \(d_{r}^{h}\) & Binary variable that is 1 when trip \(r\in R^{h}\) of line \(h\in H\) is to be scheduled. \\ \hline \(x_{r}^{h}\) & Continuous variable that indicates the departure time of trip \(r\in R^{h}\) of bus line \(h\in H\). \\ \hline \(z_{rsb}^{hg}\) & Binary variable that is 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. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: \(Cont.\)of valuable insights into the mobility patterns of Montevideo's citizens [18]. The STM system stores historical data on the number of trips, ticket sales, GPS records for each bus, and other relevant information [21]. These data have been utilized to develop official and third-party applications that provide accurate information and engage with users. Passengers using the STM have two main options to reach their destinations. They can choose the traditional \"direct\" trips, which involve traveling from the origin to the destination without any transfers.