## 5 Exact and Evolutionary Computation Methods for the BSP
### Evolutionary Algorithm  
The EA was developed using the Malva library (github.com/themalvaproject, accessed on 15 June 2021) in the C++ programming language. The main implementation details are described in the next subsections.  
Solution Encoding  
For both problem variants, candidate solutions are represented using integer vectors. Next, both representations are explained.  
Problem variant #1: offset optimizationFor problem variant #1, each integer value in the solution representation indicates the offset for each bus line, i.e., the time elapsed between time zero (start of the planning period) and the time when the first trip of the line departs. A candidate solution of the BSP is represented by a vector \(X=\{X_{1}^{1},X_{1}^{2},\ldots X_{1}^{n}\}\) (\(n\) is the number of lines in the instance), \(X_{0}^{i}\in\mathbf{Z}^{+}\), and \(0\leq X_{0}^{i}\leq T\mod H^{i}\). Figure 4 describes the solution representation for a problem instance with \(n\) bus lines.  
Problem variant 2: headways optimizationFor problem variant #2, integer values in the solution representation represent, for each bus line, the offset (in minutes) and the subsequent headway values (also in minutes). A candidate solution of the BSP is represented by a vector \(X=\{X_{1}^{1},X_{2}^{1},\cdots,X_{f_{1}}^{1},X_{1}^{2},X_{2}^{2}\cdots,X_{f_{ 2}}^{2},\cdots,X_{1}^{n},\cdots,X_{1}^{n},\cdots,X_{f_{n}}^{n}\}\), where \(X_{0}^{i}\in\mathbf{Z}^{+}\cup 0\), and \(X_{k_{i}}^{i}\in\mathbf{Z}^{+}\), with \(k_{i}\in\{1,\cdots,f_{i}\}\). Figure 5 describes the solution representation for a problem instance with \(n\) bus lines (offset values for each line are marked in blue font).  
Evolution modelThe EA follows the (\(\mu+\lambda\)) evolution model [20]. \(\lambda\) offsprings are generated from \(\mu\) parents, and all compete among themselves to select the solutions to include in the population in a new generation. The (\(\mu+\lambda\)) evolution model computed better and more diverse solutions than a standard generational model in configuration experiments.  
Initialization operatorThe initialization generates random solutions, selecting integer values within the corresponding ranges and taking into account the problem constraints. The random initialization operator is conceived to generate an appropriate diversity for the evolutionary process.  
Selection operatorA tournament method is used for selecting individuals during the evolutionary search. A tournament size of three individuals was used (just one individual survives). The tournament operator outperformed the standard proportional selection in configuration experiments, providing a proper selection pressure for candidate solutions during the evolutionary process.  
Recombination operatorAn ad hoc variant of the well-known two-point crossover operator was designed. Crossover points are randomly selected in \([1,n{-}1]\), and information from both parents is exchanged between the crossover points. The main idea is to maintain those features of bus lines synchronized in the parent to be used as relevant information for offspring generation. The recombination probability is \(p_{R}\). A correction procedure is applied to guarantee the feasibility of the generated solutions by properly shifting conflicting offset and/or headway values.  
Mutation operatorAn ad hoc variant of Gaussian mutation is applied. Selected position(s) in an individual are changed according to a Gaussian distribution and considering  
Figure 4: Solution representation for BSP variant #1.  
Figure 5: Solution representation for BSP variant #2.  
the limits (minimum and maximum) defined for both offsets and headways of each line. The mutation probability is \(p_{M}\).