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.

An Enhanced Exact Procedure for the absolute robust shortest path problem

GUERRIERO, Francesca;BRUNI, Maria Elena
2010

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/125637
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact