Measurement functions to solve the Shortest Path Problem with intervals as costs

P. Suárez Dosantos, I. Mariñas-Collado, A. Bouchet, S. Montes Rodríguez

The shortest path problem (SPP) is one of the most important and classical optimization problem. In traditional SPPs, exact information about the parameters of the problem
(such as time, costs, and risk) is known. However, real-world environments require dealing with uncertainty. In the last decades, solutions have been proposed to solve the
problem with imprecise weights on the edges. In most cases, that imprecision is expressed using intervals. This work adapts the use of different interval value measurement
functions from the field of fuzzy logic, to represent the weights of the edges in a directed graph. More specifically, Measure over Interval of Membership values (MIM) are
presented, and their behavior is compared with different intervals. Subsequently, all of these functions are applied to a shortest path problem with this type of imprecision.
The different results obtained are presented based on the choice of the measurement function.

Keywords: Shortest path problem, Uncertainty, Intervals, Measurement functions

Operations Research Methods and Applications
November 9, 2023  3:30 PM
HC1: Canónigos Room 1

S. Molés Franch, J. F. Correcher

C. Ruiz Mora, A. Alcántara Mata

P. Huidobro Fernández, P. Alonso Velázquez, V. Janis, S. Montes Rodríguez