The 4th tool in the Combinatorial Junior Toolkit No.1, is the TSP tool. It can be used to look for the 'shortest' round tours of up to 2000 'cities'. The input textarea accepts data in TSPLIB formats EUC_2D, GEO, and EXPLICIT (FULL_MATRIX). |
||
|
If you want to run a quick trial, click here to open a demo input file. Copy the whole file (ctrl-a ctrl-c), click on the input text area, and paste it (ctrl-a ctrl-v). Press the LOAD/RELOAD INPUT button to load it, and then the OBTAIN BEST TOUR button to optimise the tour. With the target set to zero, it will run for 10,000 iterations, unless you stop it. Alternatively, being informed in advance that the optimum tour size is 1508, you could set that as the target. It will then stop when it reaches it. Loaded list of weights When the LOAD/RELOAD INPUT button is pressed, the middle text area shows the distances between each pair of cities. These are either calculated according to the TSPLIB specification (in the case of EUC_2D or GEO) or taken directly from the input (in the case of EXPLICIT). The latter will normally be used for assymetric TSPs. In this case they are more likely to be times, or costs, or some other measure, rather than distances. For this reason I refer to them as 'weights'. Log of changes When the OBTAIN BEST TOUR button is pressed, the list of weights is replaced by the log of changes. An entry is added to this whenever an iteration results in a reduced difference. It also shows the segment size that was used to produce that result. I'll say more about segments later. Best tour so far Details of the best tour so far are displayed in the bottom text area when the target is reached, or when the maximum number of iterations have been completed, or when you stop the process. It shows each leg of the best tour along with its distance (or weight). You can copy and paste the whole of this content to check the result with a speadsheet, or keep it in your notepad. If the input has coordinates (EUC_2D or GEO) this output also has the coordinates of the end cities for each leg. This is so that it can be copied into the applet further down this page to show the route magnified 2.5 times. There's no real use for this applet but I like to use it. Whether the output has coordinates or not, it can also be used to continue the trial on another occasion. All you do is copy and paste it into the input area after the TSPLIB input. Stopping This is the first applet that I've written that has a STOP button (ex-OBTAIN BEST TOUR button). I hadn't programmed that very desirable control into the others because of a reluctance to get into multi-threading. It's a must with this applet when you trial the larger tours. Each iteration can take many seconds, and if you've set a higher number of maximum iterations than you meant to, it gets to be a real pain. But, it wasn't too difficult once I got down to it, so you'll probably see stop buttons added to the other tools before many summers have passed. You will notice with the big tours that the STOP button changes to STOPPING while it completes the iteration that it's working on. Maximum Iterations ITERATIONS MAX. is a necessary control field with the other tools because they have no stop button. With this applet you will still find it useful if you are running comparative trials. It goes hand in hand with the segment length control below. Set it to whatever value you want (up to 10,000,000,000). Segment Length This applet uses an arbitrary insertion heuristic. I read about it in this paper*. This is my implementation and variation of the algorithm. It certainly is not as fast as the one described. I wouldn't have written it as an applet with a dynamic graphics display if I'd wanted to break any speed records. But it works well enough. When the tour is loaded the range of segment lengths is set to vary between 1 and n-1 (where n is the number of cities). If you have a large number cities, the iterations can take a long time. You may even think the applet is hanging. But, if you stay with it, and watch the log of changes, you'll notice that although the reductions may initially result from some large segment sizes, they will more and more, as the process continues, arise from medium, and then eventually quite small segment sizes. The Segment Length Control fields can be used to stop the applet wasting time with large segments, as they become increasingly unlikely to yield reductions, Conversely, they can be used to ensure that large segments are used intially. For example, you could start a 1200-city tour with 5 iterations with min and max both set to 1199. After that you might do a hundred iterations with a segment range of 1-400. By watching the changes log you can decide what looks the most efficient setting for the iterations ahead. Perhaps, you might finish with a few thousand iterations with segments in the range 1-50. * Janez Brest and Janez Žerovnik (2005) A Heuristic for the Asymmetric Traveling Salesman Problem Target tour size When you load a new tour the target size is set to zero. This is the setting that you need if you want to find the lowest value that can be found in the time you are going to let the applet to run. If you set another target it will stay at that value until you change it, or until a new tour is loaded. If the target is exactly reached the process stops. The graphics The dynamic graphics display of the tour will only appear for EUC_2D and GEO problems. In the case of the latter the distances will be more or less distorted...but it's something to look at. Normally, the graphics show the current shape of the tour as light grey or orange legs, along with the ghost of the previous shape with light grey or deep blue legs. The grey legs are the those that have not changed. A parameter (GHOST=ORIGINAL) can be inserted in the input after the EOF line to alter the display so that the the current image is ghosted with the originally loaded shape (see the section on the tour generator below).DISCLAIMER: As with all the tools on these pages, if you are using them for some serious purpose, it is up to you to check the result. You can use a spreadsheet to easily check that the 'distances' add up correctly. You should also check that all your input has been accepted, and correctly interpreted. Also, it needs to be understood that the best results produced by the applets are not necessarily the optimum results. EUC_2D tour generator
This applet will produce some input for the TSP applets (above and below). All you need to do is click the mouse in the white rectangle to place some cities (up to 2000 them),and click the LIST EUC_2D button to get a TSPLIB-style list to copy and paste.
|
||
|
Spoilt for choice The little map at the start of the Wiki article on TSP illustrates an important aspect of this problem. It can be visualised. (Update: Unfortunately the map is no longer part of the article.) We are told that there are 43,589,145,600 possible tours of the 15 cities. Looking at the simple convex shape of the shortest tour, it's hard to accept that there are billions of others to choose from. If we were working it out with a pencil, a ruler, and a map, only a handful of the arrangements would come to mind. The rest would remain outside of our thoughts, uncounted and unimagined. The TSP applets don't rule out any of the possible permutations without first trying them. Yet, they can single out the best without doing so. In some cases you will be able to do as well as they do. Sometimes, you may do better than the vertex swapping applet below (more about that later). Usually, I think, your tours will be around 10-15 % longer than those produced by the top applet. Here's something you can try....
Of course, we're not likely to be talking about real cities with these neat 2-dimensional problems. We don't generally travel between one city and another in a single straight line. Even airways don't do that. Roads twist and turn around around hills and lakes, or are directed upstream and downstream to crossing points, or just meander for the hell of it. The coordinates of the cities are then of little use to us. Moreover,the distance to be travelled may be directly translatable into mileage costs, but not into time. One part of the route might be using a motorway, another a mule track. To top it all, neither distances nor other measures will necessarily be the same in both directions. In such cases, the problem can neither be expressed nor visualised in the same way. Instead of a list of cities and their coordinates the problem is described through a list of explicit measures between pairs of cities. Conventionally, this list is expressed as a matrix. Visualisation may be possible, but it won't be straight forward, and it won't as easily lend itself to an intuitive manual appraisal. But for the applets, the problem is no more, nor less difficult. Their input routines convert the coordinate input to an explicit full matrix. Once that is done, the coordinates are redundant. The best tour is obtained through processing a full matrix. The process uses arithmetic rather than geometry, and makes no distinction between symmetric and assymetric problems. TSPLIB TSPLIB is a valuable resource known to everyone who has worked on the problem. My page is not primarily addressed to such folk. As an ordinary punter with a Windows PC, I find it a little off-putting that the data it has collected is presented only as archived (.gz) files. These files can be easily unpacked using gzip if you are used to using it, or if you want to read about it and download it. But who wants the hassle? This is the the 21st century. So here are a few examples of TSP and ATSP from the TSPLIB that you can easily copy and paste. As far as I know TSPLIB is public domain, but if anyone objects to my having the copies here, can they please let me know. Just click on the links to bring up the text file. 52 locations in Berlin (Groetschel)
130 city problem (Churritz)
136-city problem (Padberg/Rinaldi)
Drilling problem (Reinelt)
America-Subproblem of 666-city TSP (Groetschel)
Asymmetric TSP (Fischetti)
Stacker crane application (Ascheuer)
Horses for courses As I was saying in the main article, I had intended the TSP tool to use a similar algorithm to that used by the sudoku, partition, subset sum, and clique applets. I wrote it, and tested it with some of the TSPLIB examples, and found that it worked tolerably well. I didn't expect it to seriously compete with programs that had been developed and refined by TSP professionals over the last quarter of a century. Then I had a go at adapting it to use the arbitrary insertion heuristic that I'd read about, and found that this worked very much better. At first, I was reluctant to include an applet that didn't conform with the broad notion that you only had to swap components around to solve any combinatorial problem without working out how to. The arbitrary insertion heuristic was more thought-out than I felt comfortable with. In the end though, I decided that that it would good policy to start my page with a TSP solver that works. But, in one way the original applet works better.....So I'm including it here I'm not being patronising when I say that it is very good at obtaining tours that are not close to optimum. It will obtain tours with the exact 'time' or 'cost' specified. Suppose that the germany15 tour was a circular bus route that needed to take exactly 20 minutes. If you load germany15 into the applet below, and set the target to 1200 (seconds), it will quickly find a tour of that size. Clique the obtain button again, and it will find another. Change the target to 1201, or whatever length you like (so long as it's not closer to the optimum than it is capable of reaching), and it will find the tour. Or, perhaps you want to synchronise production cycles, or work out aircraft cycles for a set of itineraries. With these sorts of applications the problem is more likely to be assymetric than symetric. The applet works because there will usually be a large number permutations that fit. It doesn't solve problems that are 'hard' in computing terms, but it's a useful tool. The arbitrary insertion applet at the top will most often find the task impossible. It might happen upon the tour size on its way, but the dominant force of its logic is toward the optimum. |
||
|
Tour Display Applet
If you want to take a closer look at the graphical presentation of a tour, you can copy and paste the whole content of the output textarea of the applets into the input text area of the applet below. It magnifies the graph 2.5 times. Not a lot, but for larger intricate tours it's quite effective. |
||