# Ship Type Selection and Cost Optimization of Marine Container Ships Based on Genetic Algorithm
## 2 Establishment of the Bi-Level Programming Model
### Model Solution  
For the bi-level planning model discussed in this paper, we first analyze the lower-level planning model: based on the objective function of minimizing carbon emissions, the coefficients of the objective function correspond to the ship's EEDI (Energy Efficiency Design Index), the 0-1 variable for ship type selection, the distance that ship type \(i\) provides logistics services to the destination, and the quantity of logistics transported by ship type \(i\). Among these variables, all except the 0-1 variable for ship type selection and the logistics transportation quantity assigned to ship type \(i\) are constants. The 0-1 variable for ship type selection is derived from the optimal planning model for minimizing the upper-level shipping company's costs. In summary, this model can be solved through linear planning. The ship type selection plan is solved using a genetic algorithm. The overall algorithm design for the bi-level programming model in this paper is shown in Figure 1.  
1. Encoding Strategy  
Using a binary encoding strategy, let \(\lambda=(\lambda_{1},\lambda_{2},\lambda_{3},\ldots,\lambda_{n})\) represent a chromosome, where each \(\lambda_{i}\) is a 0-1 variable. If a ship type is assigned to a route, \(\lambda_{i}\) is 1; otherwise, it is 0. Each random sequence corresponds to an individual in the population. For example, if \(\lambda=(0,1,1,0,1,0,0)\), it represents that the company selects ship types 2, 3, and 5 to complete the current voyage. 2. Random Initialization of Population  
Set the total number of individuals in each generation \(N\) and the maximum number of generations \(T\). Use the decision variable \(\lambda=(\lambda_{1},\lambda_{2},\lambda_{3},\ldots,\lambda_{n})\) as the chromosome encoding, and randomly generate \(N\) initial individuals to form the initial population \(p(0)\). 3. Fitness Calculation  
Based on the constraint conditions and the upper-level planning target function, calculate the transportation scheme for the company's current voyage corresponding to the ship type configuration. Let \(X_{i}=(x_{1},x_{2},x_{3},\ldots,x_{n})\) represent the solution for each individual. The fitness of each individual is then calculated, which corresponds to the shipping cost:  
\[F=\sum_{i=1}^{n}\lambda_{i}a_{i}\kappa_{i}x_{i}+\sum_{i=1}^{n}\lambda_{i}\beta _{i}x_{i}+\sum_{i=1}^{n}\lambda_{i}\eta_{i} \tag{8}\]  
Figure 1: Genetic algorithm flow chart. (4) Selection of crossover operation  
Our crossover operation adopts a single-point crossover. The design is as follows: For two selected parent genotypes \(\lambda_{1}=(\lambda_{1},\lambda_{2},\lambda_{3},\dots,\lambda_{n}),\ \lambda_{2}=( \lambda_{1},\lambda_{2},\lambda_{3},\dots,\lambda_{n})\), we randomly select the \(t\)-th gene as the crossover point. After the crossover operation, the child genotypes obtained are \(S_{1}\) and \(S_{2}\). The genes of \(S_{1}\) before the crossover point come from the first \(t\) genes of \(\lambda_{1}\), and after the crossover point come from the last \(n-t\) genes of \(\lambda_{2}\). Similarly, the genes of \(S_{2}\) before the crossover point come from the first \(t\) genes of \(\lambda_{2}\), and after the crossover point come from the last \(n-t\) genes of \(\lambda_{1}\). For example:  
\[\lambda_{1}=(0,1,0,1,0,1,0,1),\ \lambda_{2}=(1,1,0,1,0,0,0,1)\]  
If the crossover point is set at the fourth gene position, then:  
\[\lambda_{1}=(0,1,0,1,0,0,0,1),\ \lambda_{2}=(1,1,0,1,0,1,0,1)\]  
There are many different ways to perform crossover operations, and we should try to choose the best crossover method to ensure that the offspring can inherit the favorable traits of the parents. At the same time, this crossover operation also acts as a mutation operation. (5) Mutation Operation  
Mutation is also a method to achieve population diversity, and at the same time, it is a guarantee for global optimization.