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.

Andria, D., Lacagnina, V., Lino, A., Pecorella, A. (1997). A parallel simulated annealing approach to the K shortest loopless paths problem. In H. Power, J.J. Casares Long (a cura di), Applications of high performance computing in engineering V (pp. 123-134). Southampton : Computational mechanics publications [10.2495/HPC970131].

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

LACAGNINA, Valerio;PECORELLA, Antonio
1997-01-01

Abstract

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.
Settore SECS-S/06 -Metodi Mat. dell'Economia e d. Scienze Attuariali e Finanz.
Andria, D., Lacagnina, V., Lino, A., Pecorella, A. (1997). A parallel simulated annealing approach to the K shortest loopless paths problem. In H. Power, J.J. Casares Long (a cura di), Applications of high performance computing in engineering V (pp. 123-134). Southampton : Computational mechanics publications [10.2495/HPC970131].
File in questo prodotto:
File Dimensione Formato  
1997_AParallelSimulatedAnnealingApproachToTheKShortestLooplessPathsProblem .pdf

Solo gestori archvio

Descrizione: Articolo
Dimensione 1.5 MB
Formato Adobe PDF
1.5 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/10447/54384
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact