# A Multi-Objective Path-Planning Approach for Multi-Scenario Urban Mobility Needs
## 3 Multi-Objective Path Planning
### Optimization Method
The paths are then sorted by their costs, and the lowest-cost half is selected as parents for reproduction. ```
Inputs: Road network graph \(G\), start node \(n_{\text{start}}\), end node \(n_{\text{end}}\), initial population size \(N\), maximum iterations \(T\), mutation rate \(k\). Output:\(B\): Optimal path after crossover and mutation. 1. \(globalBest\leftarrow\) None
2. \(minCost\leftarrow\infty\)
3. for each candidate path \(b_{k}\) in the initial population \(P\)do
4. \(cost\)\(\leftarrow\)\(\alpha(t)\cdot f_{\text{length}}(b_{k})+\beta(t)\cdot f_{\text{congestion}}(b_{k})\)\(+\gamma(t)\cdot f_{\text{time}}(b_{k})+\delta(t)\cdot f_{\text{energy}}(b_{k})+\epsilon(t) \cdot f_{\text{risk}}(b_{k})\)
5. endfor
6. selected \(\leftarrow\) Select top \(N/2\) paths based on \(cost\)
7. \(P_{\text{new}}\leftarrow\varnothing\)
8. for each pair of paths (path1, path2) in selecteddo
9. Select random crossover point \(c\)
10. child1 \(\leftarrow\) path1[0:c] + path2[c+1:]
11. child2 \(\leftarrow\) path2[0:c] + path1[c+1:]
12. Add child1 and child2 to \(P_{\text{new}}\)
13. endfor
14. for each path in \(P_{\text{new}}\)do
15. if random probability < mutation rate
16. Select path[m] as mutation point
17. Select new node connected to path[m] and insert after path[m]
18. if path[m+1] and new node are not directly connected
19. Generate \(pathlink\leftarrow\)A*search (G, new node, path[m+1])
20. Insert \(pathlink\) into path
21. endif
22. endif
23. endfor
24. \(B\leftarrow\) Select the path with the minimum \(cost\) in \(P_{\text{new}}\)
25. if\(cost(B)<minCost\)
26. globalBest\(\gets B\)
27. \(minCost\gets cost(B)\)
28. endif
29. generation \(\leftarrow\) generation \(+1\)
30. if generation \(\geq T\)
31. return globalBest
32. endif
```  
**Algorithm 3**Path Optimization Algorithm  
Next, the selected paths are shuffled and paired for crossover operations. For each pair of parent paths, path1 and path2, a random crossover point \(c\) along the path length is selected. Two child paths are created by combining the first half of path1 with the second half of path2 to form child1 and the first half of path2 with the second half of path1 to form child2. These child paths are added to the new population \(P_{\text{new}}\) to increase diversity. Subsequently, each path in \(P_{\text{new}}\) undergoes a mutation operation with a certain probability. If a mutation occurs, a random node \(m\) in the path is selected as the mutation point, and a new node connected to \(m\) is selected as the insertion node. If the new node is not adjacent to the next node in the path, the A* algorithm is used to generate a sub-path (referred to as \"pathlink\") connecting the insertion node to the subsequent node in the original path, ensuring the connectivity and validity of the path. After each iteration, the path \(B\) with the minimum cost in the population is selected. If \(B\)'s cost is lower than the global minimum cost minCost, \(B\) is marked as the global best path, referred to as \"globalBest\". The algorithm continues until the maximum number of iterations \(T\) is reached, at which point, it outputs the globalBest path. This algorithm ensures diversity in the optimized paths through crossover and mutation operations, enabling the generation of solutions that satisfy multi-objective constraints. It ensures the generated paths meet the required targets while exhibiting optimal trade-offs and characteristics.