This paper addresses the Forward Shortest Path Tour Problem (FSPTP). Given a weighted directed graph, whose nodes are partitioned into clusters, the FSPTP consists of finding a shortest path from a source node to a destination node and which crosses all the clusters in a fixed order. We propose a polynomial time algorithm to solve the problem and show that our algorithm can be easily adapted to solve the shortest path tour problem, a slightly different variant of the FSPTP. Moreover, we carried out some preliminary computational tests to verify how the performance of the algorithm is affected by parameters of the instances.

On the Forward Shortest Path Tour Problem

Carrabs, Francesco;Cerulli, Raffaele;LAUREANA, FEDERICA
2017-01-01

Abstract

This paper addresses the Forward Shortest Path Tour Problem (FSPTP). Given a weighted directed graph, whose nodes are partitioned into clusters, the FSPTP consists of finding a shortest path from a source node to a destination node and which crosses all the clusters in a fixed order. We propose a polynomial time algorithm to solve the problem and show that our algorithm can be easily adapted to solve the shortest path tour problem, a slightly different variant of the FSPTP. Moreover, we carried out some preliminary computational tests to verify how the performance of the algorithm is affected by parameters of the instances.
2017
9783319673073
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/11386/4702742
 Attenzione

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

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