Traveling Salesman Demo

Ho potuto mettere nuovamente online la mia demo per le euristiche del Traveling Salesman Problem, grazie a LeaningTech e al suo CheerpJ.
Questa tecnologia (proprietaria) si basa su un mix di WebAssembly, Javascript e Html5.
La prima volta, il caricamento delle librerie di CheerpJ richiederà un po’ di tempo, le successive sarà molto più veloce.

Ma cos’è Il T.S.P. o “Traveling Salesman Problem” ?
E’ uno dei problemi d’ottimizzazione combinatoria più conosciuti e studiati. Può essere espresso in questi termini:
“Date n città e le distanze tra esse, trovare il cammino, che attraversando ogni città esattamente una volta e ritornando a quella di partenza, abbia la lunghezza complessiva minima”.

Più di venti anni fa ho sviluppato come tesi di laurea un applet (sviluppata in Java, JDK 1.1.8) che mostrava il funzionamento di euristiche volte a costruire o migliorare soluzioni approssimate al problema del TSP Euclideo.

Nel frattempo sono cambiate molte cose.
La ricerca ha fatto molti passi in avanti. Sono uscite numerose pubblicazioni e studi sul perfezionamento dell’algoritmo Lin-Kernighan e Helsgaun. Ad oggi, alcune implementazioni di tecniche di Branch and cut al TSP stanno dando i migliori risultati.

Per quanto riguarda gli aspetti più tecnici, Oracle nel 2010 ha acquisito Sun (con Java dentro). A partire da Java SE 9 le applet sono state deprecate e a partire dalla versione 11 sono state definitivamente rimosse. Persino Java Web Start, una possibile alternativa alle applet, è stato rimosso da Java SE 11.

In ogni caso, se volete approfondire i piani futuri di Oracle per Java client, li potete trovare qui riassunti.

Di fatto, si è reso veramente complicato poter eseguire o richiedere l’esecuzione di codice Java, tramite un browser.

La possibilità di mettere nuovamente online la mia applicazione, mi ha spinto a rivederne i sorgenti, riscrivendo il codice deprecato e a sfruttare le funzionalità di Java SE 8. Adesso non è più un applet, ma una normale applicazione client-side Java, eseguibile direttamente con:

java -jar tspdemo-3.0.jar

I sorgenti sono liberamente scaricabili, nel file zip troverete anche uno script Maven per generare il file tspdemo-3.0.jar, e buona parte della famosa raccolta di istanze e percorsi TSPLIB95.

Se volete sfruttare a pieno la mia applicazione, vi consiglio di scaricare il file jar, avrete prestazioni migliori, potrete ingrandire la finestra a pieno schermo e leggere e salvare localmente istanze e percorsi TSP.

Subscribe
Notificami

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.

0 Commenti
Inline Feedbacks
View all comments