## 3 Optimization Method
### Optimization of Lines Layout  
The genotype for the second sub-problem is a set of stations series. Each series corresponds to a single metro line (\(L_{i}\), lowercase letters correspond to successive stations) as follows:  
\[\{L_{1}:(e,f,\ldots,a);L_{2}:(p,a,\ldots,q);\ldots;L_{n}:(x,q,\ldots,y)\}. \tag{13}\]  
The number of the lines is the same for all individuals, and a station can appear at most once in a line (no loops). However, there are no other limitations apart the above: Any station can belong to many lines, so lines can go parallel and can cross each other.  
Because of the specific structure of this genotype, the special mutation operators were designed. There are six types of mutations, which allow for completely free changing of a genotype.  
1. Exchange of the position of two randomly selected station for a randomly selected line, as follows: \[\{\ldots;L_{i}:(p,\ldots,\boldsymbol{x},\ldots,\boldsymbol{y},\ldots,q);\ldots \}\stackrel{{ m1}}{{\rightarrow}}\{\ldots;L_{i}:(p,\ldots, \boldsymbol{y},\ldots,\boldsymbol{x},\ldots,q);\ldots\}\] (14)
2. The order reversion of the randomly selected sub-series of stations for a randomly selected line, as follows: \[\{\ldots;L_{i}:(p,\ldots,\boldsymbol{x},\boldsymbol{y},\boldsymbol{z}, \ldots,q);\ldots\}\stackrel{{ m2}}{{\rightarrow}}\{\ldots;L_{i}:(p,\ldots,\boldsymbol{z},\boldsymbol{y},\boldsymbol{x},\ldots,q);\ldots\}\] (15)
3. Exchange of a pair of randomly selected stations between randomly selected lines, as follows: \[\{\ldots;L_{i}:(\ldots,\boldsymbol{x},\ldots);\ldots L_{j}:(\ldots, \boldsymbol{y},\ldots);\ldots\}\stackrel{{ m3}}{{\rightarrow}}\{ \ldots;L_{i}:(\ldots,\boldsymbol{y},\ldots);\ldots L_{j}:(\ldots,\boldsymbol {x},\ldots);\ldots\}\] (16)
4. Transfer of a randomly selected station between a pair of randomly selected lines, as follows: \[\{\ldots;L_{i}:(\ldots,\boldsymbol{x},\ldots);\ldots L_{j}:(\ldots, \boldsymbol{y},\ldots);\ldots\}\stackrel{{ m4}}{{\rightarrow}}\{ \ldots;L_{i}:(\ldots,\ldots);\ldots L_{j}:(\ldots,\boldsymbol{x},\boldsymbol {y},\ldots);\ldots\}\] (17)
5. Removing of a randomly selected station from a randomly selected line, as follows: \[\{\ldots;L_{i}:(\ldots,\boldsymbol{x},\boldsymbol{y},\boldsymbol{z},\ldots); \ldots\}\stackrel{{ m5}}{{\rightarrow}}\{\ldots;L_{i}:(\ldots \boldsymbol{x},\boldsymbol{z},\ldots);\ldots\}\] (18)
6. Addition of a randomly selected station to a randomly selected line, as follows: \[\{\ldots;L_{i}:(\ldots,\boldsymbol{x},\boldsymbol{z},\ldots);\ldots\} \stackrel{{ m6}}{{\rightarrow}}\{\ldots;L_{i}:(\ldots \boldsymbol{x},\boldsymbol{y},\boldsymbol{z},\ldots);\ldots\}\] (19)  
The cross-over operation involves an exchange of a random single metro line between a pair of individuals, as follows:  
\[\begin{array}{l}\{L_{1}^{1},L_{2}^{1},\ldots,L_{i}^{1},\ldots,L_{n}^{1}\}\\ \{L_{1}^{2},L_{2}^{2},\ldots,L_{i}^{2},\ldots,L_{n}^{2}\}\end{array}\stackrel{{ X}}{{\rightarrow}}\begin{array}{l}\{L_{1}^{1},L_{2}^{1},\ldots,L_{i}^{2}, \ldots,L_{n}^{1}\}\\ \{L_{1}^{2},L_{2}^{2},\ldots,L_{i}^{1},\ldots,L_{n}^{2}\}.\end{array} \tag{20}\]  
After each operation of mutation or cross-over the network structure is checked, special attention is paid to its coherency. If the test fails, the operation is canceled.  
The shortest distance between a pair of stations (6) is calculated using fast [PERSON]'s algorithm with a priority queue implemented by the heap.