# Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects +
## 4 Multi-Objective Shortest Path
#### Representative Algorithms for MOSP  
In this section, we describe some representative algorithms for MOSP problems, which are the starting point of our research and guide us to the MODSP problem definition. Considering the reader interested in a deeper study of MOSP problems, a good starting point is the works from [PERSON] et al. [60] for speedup techniques and [PERSON] and [PERSON] [62] for applications using labeling techniques and time-dependent techniques.  
Regarding the label-setting algorithms, [PERSON] and [PERSON] [63] proposed a New Approach to Multi-Objective A* (NAMOA*). The algorithm provides exact results with lower-bound estimates exploring an optimal number of labels. However, tests and results are not present in the paper. After that, a dimensionality reduction technique for the NAMOA* algorithm was proposed by [PERSON] and [PERSON] [50]. The work reached the reduction of labeling processing time using the optimized dominance checks approach. Their work was tested with the New York road network with three, four, and five objectives. Finally, they achieved the best results, considering the selection order for the open labels for three different configurations of the NAMOA* algorithm.  
Regarding label correction algorithms, [PERSON] and [PERSON] [64] proposed an algorithm based on the work of [PERSON] and [PERSON] [65], considered efficient until the present for MOSP problems. Their algorithm works in a reverse way initializing the label information from the destination vertex and finding in a fast way to the shortest paths from an intermediate vertex to the destination one.  
The work by [PERSON] and [PERSON] [66] pointed out that the label-setting approach does not perform well when problems are composed of more than two objectives. Due to this, their work focused on label-correcting, presenting good results for real-world instances.  
Considering the time-dependent MOSP, [PERSON] et al. [67] introduced an algorithm able to tackle predictable dynamic changes. Their algorithm uses a Fully Polynomial-Time Approximation Scheme (FPTAS) for finding MOSP approximate solutions in \(O((n\log n+m)T)\) runtime, where \(T\) is the tensor size that stores the number of paths in each vertex. However, their approach does not accept a posteriori updates on the graph structure. This means that the algorithm proposed by [PERSON] et al. cannot solve MODSP problems without avoiding recomputation from scratch when unpredictable changes come.  
Looking at the speedup approaches, [PERSON] and [PERSON] [56] presented a CHs algorithm that supports weight changes to determine the trade-off between the multi-objective costs in the query phase. [PERSON] et al. [57] presented an example of a combination of the CHs and ALT methods for route planning with flexible objective functions. However, the design of those speedup algorithms is for the MOSP problem. Then, if there is any change in the graph structure regarding objectives' costs or the insertion of a new unforeseen vertex, the pre-processing phase needs to be performed from scratch.  
After presenting the perspectives of the DSP and MODM problems, as well as the difference between the MOSP and MODSP problems, the next section is entirely dedicated to the description of the MODSP problem.