# Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects +
## 3 Multi-Objective Decision-Making
### Representative Algorithms for MODM  
Representative algorithms for MODM can be divided into three classes: classical mathematical-programming-based, evolutionary algorithms, and sequential decision-making algorithms with reinforcement learning. Mathematical-programming-based algorithms provide an optimal Pareto solution at each iteration. Two widely used classical methods are: the weighted sum approach [32; 33] and the \(\varepsilon\)-constraint method [34; 35]. A major drawback of these methods is that they need expert-level knowledge about the problem to define the objective weighting factor. Otherwise, there is no guarantee that the solution will be acceptable.  
Evolutionary algorithms or Multi-Objective Evolutionary Algorithms (MOEAs) define a set of candidate solutions in each new iteration using a Pareto-based classification scheme. At the end of each iteration, those algorithms find a set of candidate solutions to compose the Pareto front. A strong point of using MOEAs to find the Pareto front is the capability of finding multiple Pareto-optimal solutions in just one simulation. However, MOEAs need attention on the algorithm choice and its parameterization since, quite often, the tuning of the parameters is necessary to reach the best results with reliability, robustness, and accuracy [36]. In addition to parameterization, there is also the issue of avoiding the local optimal solutions using fitness functions. Some of the most-important algorithms here include Non-dominated Sorting Genetic Algorithm II (NSGA-II) [37], Strength Pareto Evolutionary Algorithm 2 (SPEA-2) [38], the Multi-Objective Ant Colony System (MOACS) [39], and Multi-Objective Particle Swarm Optimization (MOPSO) [40].  
Another form to address the multi-objective problems is using Sequential Decision-Making (SDM) algorithms, where the problem is modeled as a Markov Decision Process (MDP) [24]. An MDP can be defined as a tuple \(\langle S,A,P,R,\gamma,\mu_{\phi}\rangle\), where:  
* \(S\) is the state space, i.e., the set of all possible states in the environment;
* \(A\) represents the action space, i.e., the set of actions the agent can take;
* \(P\) specifies the transition probability function, which provides the probability of a state \(s\) subjected to action \(a\) at time step \(t\) changing to the next state \(s^{\prime}\) at time \(t+1\);
* \(R\) is the reward function, specifying the reward signal obtained when performing action \(a\) in state \(s\) and transitioning to state \(s^{\prime}\);
* \(0\leq\gamma<1\) represents a discount factor, specifying the relative importance between future rewards and immediate rewards;
* \(\mu_{\phi}\) denotes the initial state distribution.  
An SDM algorithm concerns the decision process in a given time step. This decision is dependenton the next states. Then, at each state, the SDM algorithm predicts the next best action in that state at that particular time step. SDM algorithms work with Reinforcement Learning (RL) and can produce globally optimal decision sequences, identifying the value of decisions with long-term perspectives [26].  
When the model of the environment is not available a priori, the SDM with RL approach has the advantage of learning about the dynamics of the environment during the interactions. However, this approach also has drawbacks, since the mathematical and the evolutionary methods find complete solutions, while RL needs to build solutions interactively.  
The disadvantage of MODM for dealing with an MODSP problem is its inefficiency in dealing with changing environments. In particular, the insertion/deletion of a graph's vertex or edge makes the problem non-stationary. If such a change occurs during a decision-making process, MODM will lose part of the knowledge acquired until that moment, and a systematic exploration may be necessary. With the SP, DSP, and MODM problems introduced until now, the following section presents the MOSP problem before the introduction to the MODSP for a better comprehension of the dynamic difference between both problems.