# Research on the Optimization Method of Bus Travel Safety Considering Drivers' Risk Characteristics
## 3 Simulated Annealing Algorithm Based on [PERSON]'s Approximation Method for Solution [33; 34]  
Firstly, [PERSON]'s approximation method is utilized to reconstruct the original scheduling table, obtaining a relatively optimal initial feasible solution. Subsequently, an improved simulated annealing algorithm is employed to transform the current solution, assess its feasibility, and filter the solution that optimizes the objective function value. This process is iterated to progressively optimize the driver scheduling table until the model converges.  
The scheduling optimization algorithm proposed in this paper for the safety operation of buses consists of three main modules: solution initialization, new solution generation, and feasibility assessment of solutions.  
(1) Solution Initialization  
To find an initial feasible solution that satisfies hard constraints and has a relatively optimal objective function value, this paper extends the commonly used preoptimization method, [PERSON]'s approximation method, to the bus driver scheduling optimization problem. The basic idea is that when a driver cannot match suitable working time periods, their driving safety will be significantly compromised. Therefore, priority should be given to placing them in the scheduling table. Conversely, if a suitable time period is available, there is no need to prioritize them. In this case, the initialized result will be significantly better than a random strategy. The specific steps are as follows.  
Step 1: Initialize parameters. Set the iteration count \(k=1\).  
Step 2: Calculate the safety values for each driver in different time period chains and sort them in descending order [f\({}_{1}\), f\({}_{2}\), \(\ldots\), f\({}_{n}\)].  
Step 3: Calculate the differential sequence of safety values for each driver [d\({}_{\rm f1}\), d\({}_{\rm f2}\), \(\ldots\), d\({}_{\rm fn-1}\), d\({}_{\rm fn}\)], where d\({}_{\rm fn}=0\).  
Step 4: Sort the drivers in ascending order based on d\({}_{\rm fk}\).  
Step 5: While ensuring the feasibility of the scheduling table, prioritize placing the drivers at the front of the sorted list into the schedule. Match the time period corresponding to the maximum safety value of the driver with the respective shift. Record the number of unmatched shifts for each driver. If all drivers are matched, terminate.  
Step 6: Set \(k=k+1\) and go back to Step 4.  
(2) Generation of new solutions  
Considering that row and column transformations of the schedule can change the driving weather and traffic time periods for drivers, a roulette wheel selection method is applied to perform row-column crossover or mutation on the old solution, generating new solutions.  
(3) Feasibility assessment  
Based on a neighborhood search method, the feasibility of shift chains is assessed. It iterates through the shift chains at the transformed positions in the new solution, checking whether there is a working time overlap within the minimum number of shifts above and below. If an overlap exists, a new solution is generated; otherwise, the current feasible solution is retained.