# Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects +
## 5 Multi-Objective Dynamic Shortest Path
### Problem Definition  
The Multi-Objective Dynamic Shortest Path (MODSP) problem is characterized as a graph \(G=(V,E)\), where \(V\) is the set of vertices and \(E\) is the set of edges of the graph. An edge \(e\in E\) has its traversing cost \(\mathbf{c}_{e}\) addressed by \(d\) objectives \(\mathbf{c}_{e}=[c_{e1},c_{e2},\ldots,c_{ed}]\). The trade-off between the objectives is regulated by the decision variable vector \(\mathbf{w}\) composed of \(q\) decision variables \(\mathbf{w}=[w_{1},w_{2},\ldots,w_{q}]\), resulting in Equation (1). Then, with the cost vector \(\mathbf{c}_{e}\) (from an edge or a path) and the decision variable vector \(\mathbf{w}\), it is possible to designate a linear scalarization function and compute the inner product from both vectors \(c_{e}(\mathbf{w})=\mathbf{c}_{e}\cdot\mathbf{w}\). We can express the vertex sequence of a path \(\pi_{xy}\) from vertex \(x\) to vertex \(y\) by \(\pi_{xy}=\langle x_{0},x_{1},\ldots,x_{k}\rangle\), \(x_{0}=x\), \(x_{k}=y\), and \((x_{i},x_{i+1})\in E\) for each \(i\), \(0\leq i<k\). Observing the edge \((u,v)\in E\) from Figure 3, its multi-objective cost to traverse the vertex \(u\) to \(v\) is expressed by \(\mathbf{c}_{uv}\). Moreover, we can denote the multi-objective cost of a path \(\pi_{xy}\in G\) by \(\mathbf{c}_{\pi_{xy}}=\sum\limits_{i=0}^{k-1}\mathbf{c}_{x_{i}x_{i+1}}\) and its linear scalarization regarding the decision variables by \(c_{\pi_{xy}}(\mathbf{w})=\mathbf{c}(\pi_{xy})\cdot\mathbf{w}\). A special case in modeling the MODSP problem is a path from a vertex \(x\) to itself \(\pi_{xx}=\langle x\rangle\), where all the objectives' costs are equal to zero. Observing Figure 3, a concatenation between the paths \(\pi_{xx}=\langle x,\ldots,x^{\prime},v\rangle\) and \(\pi_{vy}=\langle v,y^{\prime},\ldots,y\rangle\) can be written as \(\pi_{xx}\cdot\pi_{vy}=\langle x,\ldots,x^{\prime},v,y^{\prime},\ldots,y\rangle\). Finally, we denote the path \(\pi_{xb}\) as the left subpath \(\ell(\pi_{xy})\) to compose the path \(\pi_{xy}=\pi_{xb}\cdot\langle b,y\rangle\) in the same way and the path \(\pi_{ay}\) as the right subpath \(r(\pi_{xy})\) to compose the path \(\pi_{xy}=\langle x,a\rangle\cdot\pi_{ay}\). We can observe two moments for choosing a path \(\pi_{xy}\) in Figure 3. In the first moment, assume that vertices \(f\) and \(g\) do not exist in the graph. In this case, the possible path is through vertices \(a,u,v,b\). Choosing this unique available path results in a cost denoted by \(\mathbf{c}_{xa}(\mathbf{w})+\mathbf{c}_{au}(\mathbf{w})+\mathbf{c}_{uv}( \mathbf{w})+\mathbf{c}_{vb}(\mathbf{w})+\mathbf{c}_{by}(\mathbf{w})\), which can be expressed as \(\pi_{xy}\cdot\pi_{vy}\). In the second moment, assuming new vertices \(f\) and \(g\) are inserted in the graph, it is necessary to consider the newly available path through the new vertices verifying if the solution is non-dominated. In this case, the new path has a cost denoted by \(\mathbf{c}_{xf}(\mathbf{w})+\mathbf{c}_{fg}(\mathbf{w})+\mathbf{c}_{gy}( \mathbf{w})\) or \(\pi_{xg}\cdot\pi_{gy}\). As we mentioned before, an MODSP problem is subjected to an unforeseen sequence of vertex updates. To maintain these properties, the MODSP problem is subject to the following operations:  
* update \((v,E_{v},\mathbf{c}^{\prime})\): This procedure allows dynamic changes in the graph structure, updating, inserting, or removing the vertex \(v\) and the cost vector \(\mathbf{c}^{\prime}\) of all edges \(E_{v}\) connected to the vertex \(v\).