| Texto completo | |
| Autor(es): |
da Silva, Juarez M.
;
Ramos, Gabriel de O.
;
Barbosa, Jorge L., V
;
IEEE
Número total de Autores: 4
|
| Tipo de documento: | Artigo Científico |
| Fonte: | 2022 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC); v. N/A, p. 8-pg., 2022-01-01. |
| Resumo | |
Multi-objective decision-making and dynamic shortest paths are two areas of research widely studied and of great importance for computer science, engineering, and economics. Both areas have seen a remarkable evolution in their algorithms in the last decades and have contributed to several applications in real life. The applications range from cost reduction in the expansion of telecommunications and electrical networks to the accessibility of people and autonomous vehicles. However, despite their importance, the investigation of methods at the intersection of these two areas has not been explored in the literature. Problems at this intersection are characterized by graphs whose topology can change over time (i.e., edges can be inserted or deleted online) and whose edges' costs are defined by more than a single criterion or objective. In this paper, we introduce the multi-objective dynamic shortest path problem (MODSP) and present the first algorithm to solve it. In particular, we formally define the MODSP problem and explain its relation to multi-objective decision-making and dynamic shortest paths. Concerning the algorithm, we present the first single-source MODSP (SMDSP) approach as a first effort towards solving MODSP problems while avoiding the recomputation of the paths from scratch when the graph is updated. Finally, we perform an experimental evaluation of the SMDSP and a comparison with the state-of-art algorithm for multi-objective shortest path problems. The results of our experimental evaluation prove that in an environment subjected to constant updates, the SMDSP algorithm is more efficient. (AU) | |
| Processo FAPESP: | 20/05165-1 - Comunicação e aprendizado de máquina em mobilidade urbana: uma abordagem multiagente e multiobjetivo |
| Beneficiário: | Ana Lúcia Cetertich Bazzan |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |