Solving the Shortest Path Problem with Intervals as Costs Through Aggregation Functions

  1. Dosantos, Pelayo S. 1
  2. Bouchet, Agustina 1
  3. Mariñas-Collado, Irene 1
  4. Montes, Susana 1
  1. 1 Department of Statistics and Operation Research and Mathematics Didactics, 33007 Oviedo, Spain
Actas:
Intelligent Management of Data and Information in Decision Making

Año de publicación: 2024

Páginas: 359-366

Tipo: Aportación congreso

DOI: 10.1142/9789811294631_0045 GOOGLE SCHOLAR lock_openAcceso abierto editor

Resumen

The interval shortest path problem emerges as a variant of the shortest path problem when cost uncertainties are present, introducing a range of possible values instead of fixed costs. This variation of the problem allows an appropriate adjustment to real-world situations. However, it is important to recognize that operating with intervals is not trivial. To solve the interval shortest path problem, this chapter proposes a variation of Dijkstra’s algorithm that includes the use of either averaging functions or admissible orders. These techniques, along with the usual interval arithmetic, provide good solutions to the problem and can be adapted according to the context to best deal with the corresponding imprecision.