A parallel simulated annealing approach to the K shortest loopless paths problem

The k shortest loopless paths problem is a significant combinatorial problem 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 heuristic 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.