# A Multi-Objective Path-Planning Approach for Multi-Scenario Urban Mobility Needs
## 3 Multi-Objective Path Planning
### Optimization Method  
In this experiment, a genetic algorithm is used for multi-objective optimization of path planning. The genetic algorithm is an evolutionary algorithm based on the principles of natural selection and genetics, evolving a population of paths through selection, crossover, and mutation operations to approximate the optimal solution in a multi-objective space. In the genetic algorithm optimization for multi-objective path planning, the diversity and rationality of the initial population are key factors influencing the final optimization effect. To generate an initial population that is both diverse and feasible, this study uses the A* algorithm to generate a set of feasible paths from the start node to the goal node. To avoid excessive concentration or convergence of the generated paths, a dynamic avoidance point strategy is introduced, which enhances the diversity of each path in the population while maintaining feasibility. This approach allows a more comprehensive coverage of the search space, facilitating crossover and mutation operations in subsequent genetic processing. For each generated path, the values of each objective attribute are calculated, which will be used in the subsequent multi-objective optimization process. Algorithm 2 describes the process of generating an initial population of paths. First, it accepts the road network graph \(G\), the start node \(n_{\text{start}}\), the end node \(n_{\text{end}}\), and the number of candidate paths \(M\) as inputs. To enhance path diversity, the algorithm temporarily removes nodes from the avoidance set \(P_{\text{avoid}}\) during each path generation to ensure that the generated paths are not completely identical. In each iteration, the algorithm uses the A* algorithm to search for the optimal path \(b_{k}\) from the start node to the end node in the road network graph. Then, the generated path \(b_{k}\) is added to the candidate path set \(P\), and a node from path \(b_{k}\) is selected and added to the avoidance set \(P_{\text{avoid}}\) to prevent this node from being included in subsequent path generations. After the path generation is completed, the nodes in \(P_{\text{avoid}}\) are restored to the road network graph \(G\) to ensure the integrity of the graph for the next path generation. Finally, the algorithm returns the initial population \(P\), which contains \(M\) paths. ```
Input: \(G\): Road network graph, \(n_{\text{start}}\): Start node, \(n_{\text{end}}\): End node, \(M\): Number of candidate paths to generate in the population Output: \(P\): Set of candidate paths in the initial population
1. Initialize population count: population \(\gets 0\)
2. \(P\leftarrow\varnothing\)
3. \(P_{\text{avoid}}\leftarrow\varnothing\)
4. for each\(k=(1,\ldots,M)\)do
5. Temporarily remove nodes in \(P_{\text{avoid}}\) from \(G\)
6. Use the A* algorithm in \(G\) to search for the optimal path \(b_{k}\) from \(n_{\text{start}}\) to \(n_{\text{end}}\)
7. Add the generated path \(b_{k}\) to the path set \(P\)
8. Select a node from \(b_{k}\) and add it to \(P_{\text{avoid}}\)
9. Restore nodes in \(P_{\text{avoid}}\) to \(G\)
10. endfor
11. return\(P\)
```  
**Algorithm 2**A* Initial Path Generation  
Algorithm 3 describes the process of using a genetic algorithm on the road network graph \(G\) to find the optimal path from the start node \(n_{\text{start}}\) to the end node \(n_{\text{end}}\). Unliketraditional genetic algorithms that rely on fixed weights, Algorithm 3 employs dynamic weights \(\alpha(t)\), \(\beta(t)\), \(\gamma(t)\), \(\delta(t)\), and \(\epsilon(t)\), allowing the algorithm to adapt to varying optimization priorities. In addition, the use of the A* algorithm ensures that paths generated during mutation remain valid and connected. The algorithm begins by generating an initial population of paths. For each path \(b_{k}\), its cost is calculated as the weighted sum of multiple objectives, including path length, congestion, time, energy consumption, and risk.