Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/16/3/162 |
| _version_ | 1797613929142157312 |
|---|---|
| author | Juarez Machado da Silva Gabriel de Oliveira Ramos Jorge Luis Victória Barbosa |
| author_facet | Juarez Machado da Silva Gabriel de Oliveira Ramos Jorge Luis Victória Barbosa |
| author_sort | Juarez Machado da Silva |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T07:02:36Z |
| format | Article |
| id | doaj.art-7394ebcaa3c847b6b7958d032f33afb9 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-11T07:02:36Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-7394ebcaa3c847b6b7958d032f33afb92023-11-17T09:09:27ZengMDPI AGAlgorithms1999-48932023-03-0116316210.3390/a16030162Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and ProspectsJuarez Machado da Silva0Gabriel de Oliveira Ramos1Jorge Luis Victória Barbosa2Applied Computing Graduate Program, Universidade do Vale do Rio dos Sinos, Av. Unisinos, 950, Cristo Rei, São Leopoldo 93022-000, BrazilApplied Computing Graduate Program, Universidade do Vale do Rio dos Sinos, Av. Unisinos, 950, Cristo Rei, São Leopoldo 93022-000, BrazilApplied Computing Graduate Program, Universidade do Vale do Rio dos Sinos, Av. Unisinos, 950, Cristo Rei, São Leopoldo 93022-000, BrazilThe 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.https://www.mdpi.com/1999-4893/16/3/162multi-objectivedecision-makingshortest pathdynamic shortest pathmulti-objective shortest path |
| spellingShingle | Juarez Machado da Silva Gabriel de Oliveira Ramos Jorge Luis Victória Barbosa Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects Algorithms multi-objective decision-making shortest path dynamic shortest path multi-objective shortest path |
| title | Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects |
| title_full | Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects |
| title_fullStr | Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects |
| title_full_unstemmed | Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects |
| title_short | Multi-Objective Decision-Making Meets Dynamic Shortest Path: Challenges and Prospects |
| title_sort | multi objective decision making meets dynamic shortest path challenges and prospects |
| topic | multi-objective decision-making shortest path dynamic shortest path multi-objective shortest path |
| url | https://www.mdpi.com/1999-4893/16/3/162 |
| work_keys_str_mv | AT juarezmachadodasilva multiobjectivedecisionmakingmeetsdynamicshortestpathchallengesandprospects AT gabrieldeoliveiraramos multiobjectivedecisionmakingmeetsdynamicshortestpathchallengesandprospects AT jorgeluisvictoriabarbosa multiobjectivedecisionmakingmeetsdynamicshortestpathchallengesandprospects |