An Improved Approach for Solving Interval Shortest Path Problem

The shortest path (SP) problem concentrates on finding the path with minimum distance, time or cost from a source node to the destination node. However, the costs of many real world applications are not deterministic numbers. In these cases, using interval numbers for modeling the problem is quite appropriate, and the interval shortest path (ISP) problem appears in a natural way. An existing algorithm for solving ISP problem is based on the acceptability index for comparison of any two interval arc weights. Here it is shown that once the acceptability index is chosen, the ISP problem is converted into crisp one, which is easily solved by the standard SP algorithms

: Shortest path problem, Interval numbers, Acceptability index