# Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects +
## 4 Multi-Objective Shortest Path  
Some studies approach the MOSP as static graphs. Where most of these MOSP works are focused on bi-objective problems [41; 42; 43; 44; 45], a small part of the works address tri-objective problems [46; 47; 48; 49], and few works approach many objectives [50; 51; 52]. A labeling technique extension, efficient for the single-objective purpose, is adopted by most part of these works to solve the MOSP problem [53]. Even using a generalization of the labeling technique to solve the MOSP problem, only one path indicating the best value for all criteria is not available. Therefore, solving an MOSP problem is fundamental to search for non-dominated paths in the graph (Pareto front of the MOSP). The labeling technique applied to the MOSP is iterative and employs the method of computing the one-to-all shortest paths, a single-source solution for the MOSP problem. We can divide the labeling technique into two: label-setting and label-correcting. Each of those labeling techniques has its own update procedure to reach the final optimal shortest paths. The key difference between both is in the estimation of the distance to the shortest path under evaluation regarding each vertex in each iteration. For the label-setting algorithms, the vertex under evaluation searches for the least-possible label value. Then, if the optimality principle holds, each vertex is scanned at most once to reach the optimal shortest path from the source vertex to the destination vertex [53]. This means that, in an MOSP problem, where the goal is a one-to-one optimal shortest path, the label-setting method finishes the search when it reaches the destination vertex, avoiding a more costly search in all graph vertices. In contrast, a label-correcting algorithm may select a vertex more than once and ends after finding the shortest path from the source vertex \(s\) to all other vertices \(i\in V\). This effect occurs since the label-correcting algorithm follows a policy to scan the graph's vertices, for instance First In, First Out (FIFO). Moreover, the shortest path distance computed at each interaction is temporary and converges to the one-for-all optimal shortest path distances. Therefore, this scan method of the label-correcting algorithm makes the computation time to find the shortest one-to-all paths the same as that of the shortest one-to-one path. An MOSP problem may also consider a dynamic change over time (time-dependency) regarding the objectives' cost over the edges [54]. This time-dependent approach to the MOSP problem considers the time window in a vertex under evaluation and the time spent to reach the neighbor vertices regarding the objectives' cost in the current window time. In this way, a time-dependent algorithm assesses the objectives' cost over time for each vertex under evaluation until it reaches the destination vertex [55]. This approach is appropriate for predictable changes in graphs over time, which is applicable, for example, to determine the shortest path in a road map regarding the traffic prediction in the length of the day. Another way to approach the MOSP problem is by using speedup techniques to search for the optimal shortest paths. This approach has a preprocessing phase that considers the objectives' costs and a query phase to search for the optimal shortest paths. The preprocessing phase sets the Pareto-optimal paths as the most costly phase. In contrast, the query phase is remarkably fast, receiving as inputs the source vertex, destiny vertex, and weights unknown a priori to search for the shortest path with the best trade-off between the objectives' cost and the user preferences [56]. [PERSON] et al. [57] classified speedup methods into three classes:  
1. _Hierarchical methods:_ As the name implies, this method extracts the dependent hierarchy information from the graph. The hierarchical method most used is the Contraction Hierarchies (CHs) proposed by [PERSON] et al. [58].