| Full text | |
| Author(s): |
da Silva, Juarez M.
;
Ramos, Gabriel de O.
;
Barbosa, Jorge L., V
;
IEEE
Total Authors: 4
|
| Document type: | Journal article |
| Source: | 2022 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC); v. N/A, p. 8-pg., 2022-01-01. |
| Abstract | |
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) | |
| FAPESP's process: | 20/05165-1 - Communication and machine learning in urban mobility: a multiagent and multiobjective approach |
| Grantee: | Ana Lúcia Cetertich Bazzan |
| Support Opportunities: | Regular Research Grants |