# Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects +
## 5 Multi-Objective Dynamic Shortest Path
### MODSP Taxonomy  
In order to make the MODSP problem more visible as a class of problems, Figure 5 shows a taxonomy, with our view of the problem classes that deal with the shortest path problems. Starting the taxonomy analysis by segregating the five classes involved in the Venn diagram, we can observe that the three problem classes, the MODSP, DSP, and MODM, are well delimited in the taxonomy. We represent the MOSP problem class in the taxonomy as the intersection between the MODM and MODSP problem classes. Our claim that the MOSP is the intersection between MODM and the MODSP implies that the MOSP definition can neither represent dynamic structural changes in the graph over time nor represent graph-less problems with multiple objectives. In the same way, the SP problem class is presented in the taxonomy as an intersection area between the DSP and MOSP class of problems. As the SP problem is a subclass of the DSP and MOSP class of problems, the SP problem class does not have the multiple objectives from the MOSP problem class and does not have the dynamic graph structural changes over time from the DSP problem class.  
By analyzing the taxonomy, it is possible to observe that the SP and MOSP problems are subclasses of the MODM since they can be solved using multi-objective reinforcement learning methods [30]. Furthermore, the MODM problem class can solve other non-graph-related problems, as represented in Figure 5, by the area that does not intersect with the MODSP problem class. However, the MODM problem class cannot solve graph problems with dynamic changes like the MODSP and DSP problems due to the possibility of inserting or removing vertices and edges at any time [1; 12]. Taking the analysis to the bias of the MODSP problem class, it is possible to observe that the MODSP methods can solve all problems related to graphs since the DSP, MOSP, and SP problem classes are subclasses of the MODSP problem class. Our taxonomy of the MODSP problem class sheds light on a challenging problem in emerging areas, such as the evolution of telecommunications networks and autonomous vehicles. These emerging areas make MODSP more evident  
Figure 4: Bi-dimensional objective space with the Pareto front using the path nomenclature on the solutions.  
in real-world situations, requiring attention to be resolved appropriately and avoiding delayed and inaccurate responses.  
To the best of our knowledge, until our previous work [3], no others in the literature dealt completely with MODSP. The closest works considered only MOSP approaches [41; 42; 43; 46; 47; 48; 50; 51]. The MODSP distinguishes itself from the MOSP since it requires a solution or an update after an online structural change on the graph. Due to the absence of the dynamic and unpredictable update component in the problem formulation, the MOSP needs to recalculate the shortest paths from scratch when the insertion or deletion of a route in the graph occurs. However, recalculating optimal routes from scratch is inefficient since changes in the graph may occur at exclusive points. Thus, in the MODSP algorithmic perspective, the graph changes are evaluated, and the update is executed only on the affected paths. Concerning the problem's complexity, the MOSP is NP-hard [68; 69], which also makes the MODSP at least NP-hard.