Premium
An enhanced exact procedure for the absolute robust shortest path problem
Author(s) -
Bruni Maria Elena,
Guerriero Francesca
Publication year - 2010
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00702.x
Subject(s) - shortest path problem , heuristic , mathematical optimization , consistent heuristic , computer science , path (computing) , incremental heuristic search , range (aeronautics) , algorithm , mathematics , search algorithm , beam search , theoretical computer science , graph , materials science , composite material , programming language
The aim of this paper is to investigate the use of heuristic information to efficiently solve to optimality the robust shortest path problem. Starting from the exact algorithm proposed by Murty and Her, we describe how this algorithm can be enhanced by using heuristic rules and evaluation functions to guide the search. The efficiency of the proposed enhanced approach is tested over a range of random generated instances. Our computational results indicate that the use of heuristic criteria is able to speed up considerably the search and that the enhanced exact solution method outperforms the state‐of‐the‐art algorithm proposed by Murty and Her in most of the instances.