WIT Press


A Parallel Simulated Annealing Approach To The K Shortest Loopless Paths Problem

Price

Free (open access)

Paper DOI

10.2495/HPC970131

Volume

18

Pages

12

Published

1997

Size

1,496 kb

Author(s)

D. Andria, V. Lacagnina, A. Lino & A. Pecorella

Abstract

The k shortest loopless paths problem is a significant combinatorial prob- lem which arises in many contexts. When the size of the networks is very large the exact algorithms fail to find the best solution in a reasonable time. The aim of this paper is to suggest parallel efficient algorithms to obtain a good approximation of the solution to the k shortest loopless paths problem between two arbitrary nodes, when the network size is large. The heuris- tic used is known in literature as Simulated Annealing. Preliminary tests have been conducted for evaluating the validity of the proposed algorithms. The quality of the obtained results represents a significant base for further experimentations. 1 Introduction The K Shortes

Keywords