The Traveling Salesman Problem (TSP) is a classic problem in combinatorial optimization. The problem is to plan a route for a traveling salesman to visit N different cities, so that he visits each city exactly once, returns to his point of origin, and travels the least number of miles. The TSP was once considered too difficult to solve for very large N, but with progress in optimization methods and faster computers, we can easily demonstrate this problem graphically for modest values of N. (Click on the image below to see it full size.)
To examine source code, build and run a Visual Basic application that solves the TSP for a set of cities that you choose, click to download Tsp.zip. You must have an archive program such as WinZip to extract the contents of this ZIP file, and you must have Visual Basic Version 5 or higher installed to build or run this application.
Once you've downloaded Tsp.zip, unzip its contents into a directory of your choice:
SaFrontmip.bas
Tsp.bas
Tsp.exe
Tsp.frm
Tsp.frx
Tsp.vbp
Tsp.vbw
You can double-click Tsp.exe to run the program and display the window shown above. Click two or more of the check boxes to select cities to include in the salesman's tour, then click the button Find Route. (You must have a copy of Frontmip.dll in your Windows directory or in the same directory as Tsp.exe.)
The Tsp application defines the optimization model using an alldifferent constraint. It uses the Evolutionary Solver to find the solution. Since the Evolutionary Solver cannot, in general, "prove optimality" for a solution, it will stop when no improved solution has been found in the number of seconds that you enter in the box at the bottom of the window.
Double-click Tsp.vbp to open the project in Visual Basic. In Tsp.frm, the subroutine Command1_Click() sets up the optimization model and calls the Solver DLL. In Tsp.bas, the function tspfunc() is called by the optimizer to compute the objective function, the total distance traveled. (There are no constraints except for bounds on the variables, and the alldifferent constraint.) Declarations of the Solver DLL routines are in SaFrontmip.bas.