# Ferry Scheduling Optimization Considering Arrival Time Uncertainty and In-Place Time Differences
## 3 Problem Transformation and Model Solving
### Genetic Algorithm Design  
The ferry scheduling under the uncertainty of the arrival time of the ferry service considering the difference in in-place time is a complex problem. A SAA dynamic programming model is constructed with the minimum number of ferry usage as the optimization objective. To solve the model, a GA method based on Monte Carlo random sampling is designed, where \(w\) represents the current number of samples and \(|W|\) represents the size of the sample set. \(iNum\) and \(iMax\) represent the current iteration number and the maximum iteration number, respectively. The detailed steps of GA are as follows. Step 1: chromosome encoding and population initialization. The ferry scheduling scheme contains service chains of multiple ferries. To easily transform the service chains into gene segments of chromosomes, a positive integer order encoding is used to denote all ferry sub-services to be assigned with \(J\). Each ferry service \(j\) has \(u_{j}\) sub-services, each of which corresponds to a different gene, and different gene orders represent different scheduling schemes. The initialization process of the population is to generate many chromosomes with randomly arranged genes. Step 2: chromosome decoding and fitness evaluation. Chromosome decoding is the process of transforming a chromosome into a scheduling solution. For example, there are 10 ferry sub-services \(\{1,\,2,\,\,...,\,10\}\) to be assigned, and one randomly generated chromosome is \(A=\{3,6,2,1,7,5,9,4,8,10\}\). Assume that all ferries have the same state, that the airport has a parking lot denoted by 0 and that each ferry departs from the parking lot and eventually returns to it. All constraint-conflict-freesub-services such as \(\{3,6,1,10\}\) are assigned to ferry 1 according to the gene order on chromosome A. By this analogy, we can obtain the ferry service chain \(f_{1}\) as \(0-1-3-6-10-0\); the service chain \(f_{2}\) as \(0-2-4-7-0\); and the service chain \(f_{3}\) as \(0-5-8-9-0\). The combination of all service chains is the scheduling scheme. To evaluate the advantages and disadvantages of the scheduling scheme, the chromosome needs to be evaluated for fitness, which is the inverse of the number of service chains. Step 3: selection operation. The core idea of the selection operation is survival of the fittest. The purpose is to select the excellent individuals in the population and eliminate the inferior individuals. The fitness value of an individual is converted into the probability of the individual being selected. Commonly used selection operators are roulette selection, random traversal sampling, etc., the former of which is used in this paper. Step 4: crossover operation. The purpose of the crossover operation is to increase the diversity of the population and prevent premature convergence to a local optimum. The crossover operation will change the gene combinations of individuals to generate new individuals. Based on the positive integer arrangement coding method used in this paper, it is necessary to ensure that the chromosome genes are complete and not duplicated. If the conventional single-point crossover or multi-point crossover is used, it will generate non-compliant chromosomes with great probability. To address this problem, the crossover operator in this paper uses order crossover. The region between two randomly generated crossover points is defined as the crossover gene segment. After copying the crossover gene fragments, the remaining genes of the child chromosome are filled, and the complete child individual is obtained. For example, crossover is performed on paternal chromosome \(A=\{3,6,2,1,7,5,9,4,8,10\}\) and paternal chromosome \(B=\{7,9,3,10,8,5,6,2,4,1\}\). Step 4.1: Duplicate crossover gene segments. Randomly select crossover points 4 and 8 and copy the crossover gene fragments from the paternal chromosomes A and B to the child chromosomes C and D, respectively, as shown in Figure 4.  
Step 4.2: Fill in the remaining genes of the child's chromosome.