Traveling Salesman Problem Demo with CheerpJ

I was able to put my demo for TSP or “Traveling Salesman Problem” heuristics online again, thanks to LeaningTech and its CheerpJ.
This (proprietary) technology is based on a mix of WebAssembly, Javascript and Html5.
The first time, loading the CheerpJ libraries will take a while, subsequent times will be much faster.

But what is the Traveling Salesman Problem ?
It is one of the best known and most studied combinatorial optimization problems. It can be expressed in these terms:
“Given n cities and the distances between them, find the path, which by traversing each city exactly once and returning to the starting city, has the minimum total length.”

More than twenty years ago I developed as my thesis an applet (developed in Java, JDK 1.1.8) that demonstrated the operation of heuristics designed to construct or improve approximate solutions to the Euclidean TSP problem.

Many things have changed in the meantime.
Research has made many steps forward. Numerous publications and studies on refining the Lin-Kernighan and Helsgaun algorithm have come out. To date, some implementations of Branch and cut techniques at TSP are yielding the best results.

On the more technical side, Oracle in 2010 acquired Sun (with Java in it). Starting with Java SE 9, applets were deprecated and starting with version 11 they were permanently removed. Even Java Web Start, a possible alternative to applets, was removed from Java SE 11.

In any case, if you want to learn more about Oracle’s future plans for Java client, you can find them summarized here.

it became really complicated to execute or request the execution of Java code, via a browser.

The possibility of having my application online again, gave me the idea of reviewing its sources, rewriting the deprecated code using the features of Java SE 8.
Now it is no longer an applet, but a normal client-side Java application, executable directly with:

java -jar tspdemo-3.0.jar

The sources are freely available on GitHub, you will also find a Maven script to generate the tspdemo-3.0.jar file, and much of the famous TSPLIB95 collection of instances and paths.

If you want to take full advantage of my application, I recommend using the client-side version directly, with the jar file, you will have better performance. You will be able to enlarge the window to full screen and read and save TSP instances and paths locally.

Notify of

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Commenti
Inline Feedbacks
View all comments