# Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects +
###### Abstract  
The Shortest Path (SP) problem resembles a variety of real-world situations where one needs to find paths between origins and destinations. A generalization of the SP is the Dynamic Shortest Path (DSP) problem, which also models changes in the graph at any time. When a graph changes, DSP algorithms partially recompute the paths while taking advantage of the previous computations. Although the DSP problem represents many real situations, it leaves out some fundamental aspects of decision-making. One of these aspects is the existence of multiple, potentially conflicting objectives that must be optimized simultaneously. Recently, we performed a first incursion on the so-called Multi-Objective Dynamic Shortest Path (MODSP), presenting the first algorithm able to take the MODM perspective into account when solving a DSP problem. In this paper, we go beyond and formally define the MODSP problem, thus establishing and clarifying it with respect to its simpler counterparts. In particular, we start with a brief overview of the related literature and then present a complete formalization of the MODSP problem class, highlighting its distinguishing features as compared to similar problems and representing their relationship through a novel taxonomy. This work also motivates the relevance of the MODSP problem by enumerating real-world scenarios that involve all its ingredients, such as multiple objectives and dynamically updated graph topologies. Finally, we discuss the challenges and open questions for this new class of shortest path problems, aiming at future work directions. We hope this work sheds light on the theme and contributes to leveraging relevant research on the topic. multi-objective; decision-making; shortest path; dynamic shortest path; multi-objective shortest path +
Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/py/4.0/](https://creativecommons.org/licenses/py/4.0/)]([https://creativecommons.org/licenses/py/4.0/](https://creativecommons.org/licenses/py/4.0/))). Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/py/4.0/0/](https://creativecommons.org/licenses/py/4.0/0/)]([https://creativecommons.org/licenses/py/4.0/0/](https://creativecommons.org/licenses/py/4.0/0/))). Footnote †: This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license ([[https://creativecommons.org/licenses/py/4](https://creativecommons.org/licenses/py/4)]([https://creativecommons.org/licenses/py/4](https://creativecommons.org/licenses/py/4)). objectives and the preferences of the user or the system. MODM problems emerge in several real-life situations, such as the economic market, pathfinding, and project definitions [2]. However, applying MODM in the shortest path problem has been treated in the literature in the static form, also known as the Multi-Objective Shortest Path (MOSP) problem. MOSP algorithms are unsuitable for solving the DSP problem, as any real-time update on the graph forwards the recalculation of the solution from scratch. Some works solve this problem by applying the MOSP with a time-dependent approach if the problem can be modeled with graph changes following a pattern. However, in a time-dependent MOSP problem, the variation in the values of the objectives is linked to time and conditions well-known a priori, such as rush hour on a highway. In this way, the time-dependent MOSP problem also does not allow real-time updates or unmapped conditions a priori without recomputing the entire solution from scratch. Therefore, the approaches to MOSP problems are not able to solve unpredictable changes in the graph.