Implementazione del Travelling Salesman Problem in Scala e Spark

Il progetto è stato realizzato per implementare l'algoritmo per la risoluzione del problema del commesso viaggiatore con tecnica branch & bound.

L'algoritmo è stato scritto in linguaggio Scala, utilizzando la libreria Scala-Spark per la parallelizzazione di alcune procedure.

I run sono stati effettuati sulla piattaforma AWS importando il progetto in formato .jar. Successivamente sono stati analizzati i tempi di esecuzione al variare della quantità dei dati in input e del numero dei core.

Struttura del progetto

• src/main/
  • data/
    • dataPlace.csv: database contenente le distanze tra alcune delle città degli USA (rappresentate con id numerici);
    • sf12010placename.csv: mappa (id_città -> nome città);
    • data.csv: database generato dal programma che considera solo alcune città e le distanze tra tutte le coppie di esse;
  • scala/
    • GenerateData.scala: codice per la generazione di data.csv;
    • Main.scala: funzione principale che utilizza GenerateData.scala e TSP_SPARK.scala;
    • TSP.scala: implementazione sequenziale con tecnica branch & bound per TSP;
    • TSP_SPARK.scala: implementazione parallela con tecnica branch & bound per TSP;
• PresentazioneSCPMassimilianiVainigli.pdf: presentazione del progetto e dei risultati.