This application is an attempt to solve the Traveling Salesman Problem with a novel algorithm of the author's design called SetBuilder. In essence, this algorithm begins by finding small combinations of cities with optimally small distances, concatenates them to build longer partial solutions, and continues the upward concatenation process until it reaches an optimized full solution. While this method does not guarantee the discovery of the best solution, it produces good solutions in relatively short time frames and scales well for larger problems (those with many cities.)
Installation Instructions: Nothing unusual - simply run the enclosed executable.
Operation Instructions:
SetBuilder Algorithm: Some details about the algorithm will be helpful for understanding how to utilize it. This algorithm maintains a "pile": lists of partial solutions of varying sizes, sorted by shortest distances, in which larger solutions (those including more cities) are built out of smaller, optimized solutions. At the lowest level - the base of the pile - are two-city combinations, with the closest two cities at the head of the list, followed by the next closest two-city combination, etc. The list above it in the "pile" maintains a sorted list of three-city combinations. More importantly, these three-city combinations are comprised of a link to an optimal two-city combination with an additional city added. The four-city solutions may consist of either links to two two-city combinations, or a link to a three-city combination and an additional city. This combinatorial process continues up the pile, until, at the very top of the pile, a full solution is produced.
The algorithm functions by an iterative process. Initially, the entire pile is empty: it contains many empty lists. The algorithm first attempts to populate the lowest level of list by finding good two-city combinations. When a threshold number of two-city combinations exist in the list, the algorithm randomly creates a three-city combination by randomly choosing a two-city combination and tacking on an extra city. The algorithm continues searching for better two-city combinations while attempting to create better three-city combinations. When a threshold number of three-city combinations have been found, the algorithm begins generating four-city combinations (as well as two- and three-city combinations.) This stepwise generation of solutions continues to fill each successive list, until it eventually reaches the top of the pile - a full solution of all cities. The algorithm runs indefinitely, attempting to generate new and better solutions, until aborted by the user.
Two additional details must be mentioned.
First, each solution above two elements is built out of smaller solutions. These links are maintained, leading to an important phenomenon: the entries are optimizing. A partial solution of eight cities may consist of a smaller solution of five cities, plus a smaller solution of three cities. Later, a shorter route among these same five cities may be discovered. When it is added to the list, it actually replaces the previous route for these five cities - and the parent solution of eight cities is improved.
Second, each list has a maximum capacity. The user may specify the capacity of the lowest level (two-city combinations), and the top level - the full solution list - maintains exactly one entry. The capacities of the intermediate lists are tapered. Thus, the pile might be imagined as a cone. As noted previously, every list is maintained in sorted order; when a list exceeds its capacity, the worst (greatest-distance) entries in the list are removed. All longer solutions that relied on this solution are also removed. (This last comment produces one undesirable consequence: sometimes, a good solution may be lost if a smaller partial solution on which it relies is deleted.)
With this process aside, the following steps are required to use the SetBuilder algorithm:
Create a map: Simply click in the Map window to produce cities. Left-clicking on a city deletes it, and right-clicking on the city enables the user to move it around the map.
Configure the SetBuilder algorithm parameters: The size of the base (the set of two-city combinations) may be specified, as well as the "threshold" (the percentage of a layer that must be filled in order to begin filling the level above it.)
Apply the algorithm to produce a solution: First, you must initialize the SetBuilder list by clicking the "Initialize" button. Then, you may use the "Solve (Step)" and "Solve (Full)" buttons to use the SetBuilder algorithm to produce a solution. The former carries the algorithm one step toward a solution and displays the best solution (the longest one with the shortest distance) on the map. The latter runs the algorithm continuously, displaying the best solutions in periodic intervals. This runs indefinitely until aborted by the user, since the algorithm may be capable of producing a better full solution with continued optimization.
Comments: The algorithm description provided above notes the strengths and drawbacks of the SetBuilder algorithm. As noted, the algorithm does a good job of yielding pretty good solutions in a short time frame, can optimize solutions given more time, and is capable of scaling well to solve larger problems (maps with more cities.)
Research will continue in order to refine this algorithm. One observation that appears to reduce the performance of the algorithm: the higher levels of the pile appear to suffer from variety fatigue; i.e., the same clusters of small cities tend to appear in many or most of the higher solutions. This frustrates the process of constructing larger solutions, since overlap of cities in constituent solutions becomes more frequent.
Application History: This application was written as an experiment with a novel algorithm for solving the classic Traveling Salesman Problem. Although the problems mentioned above may be incapable of efficient resolution, the resulting algorithm is nevertheless competitive with alternative solutions for this problem.
Questions/Comments: Please contact David J. Stein, Esq. via email at djs10@po.cwru.edu.
Terms and Conditions of Use: Please see the enclosed "License.html" file for terms and conditions of use of this software package.