Our first program used a local search technique. Simply start with a random delivery plan and try to improve it by simple transformations. The most obvious transformation in this problem was moving a location to another place in the plan. To go from one plan to another, either the BEST (most improving) or a RANDOM (any improving) transformation was selected; this could be specified by the user. The reason for the second possibility was that the path to a local minimum taken by the BEST option might be too deterministic, always proceding towards the same area of the solution space. When no more improvements were found the program would stop.
The above program had various results but often stopped around 1600. This is unacceptable, of course. The problem was that it got stuck in high local minima. So we introduced the zwiep, which did a random number (within specified bounds) of random transformations. The program no longer terminated, but simply applied a zwiep when it got stuck, and proceeded to optimize the resulting plan. This quickly resulted in a 1203.
The second improvement allowed the program to use existing plans to initialize from. This allowed us to try improving a plan by keeping track of the best plan and after a number of successive zwieps to reinitialize from this plan (or a better one, if found). This had the advantage of doing a pretty good search in a particular region of the solution space, but the disadvantage that one could get stuck in a good local minimum. Using this program we got our first 1183 (plan 2 below) and almost all runs took us under 1190.
With three weeks left to go we built in many other options and random factors into the program, ran it on around 130-140 Suns, but to no avail. We created new interesting transformations, but other than converging faster, the result was depressing. We found many different local minima many different times, and we were about to leave it at that. Then we found out that the average criterium meant "average delivery time", not "average route length" as our interpretation had been, and we decided to write a new program.
Our new program incorporated all the techniques of our first program, except we found a new way of doing transformations. We created a segment move and a segment swap, capable of moving entire parts of routes around. Using a little logic, a little randomness and around 15-20 local variables, we were able to implement these transformations is such a way that we could almost search through all posibilities in about the same speed as our other program checked only point transformations.
Another interesting new feature of this new program was the zwiep which was zo modified that it did a random reinitialization of circular regions in the plan. The radius and center of this region were chosen randomly. A short radius was made much more likely than a long radius, but the long radius was still possible once in a while.
This program quickly found the second 1183 (plan 1 below) which had a significantly better average (interpreted the proper way this time) than our first result. Also, since we had such drastic transformations, since we had so many computers doing the work for us, since our program determined random factors randomly and was started with random paramters on each machine, since we used 1.8 years of CPU time (on your average Sparc 5), and since we still found NOTHING BETTER, we were hopeful that no better plan existed. We had no knowledgeable enough mathematicians in our team to prove this intuition (a considerable project in itself), so we left it at that and sent in our solution.
| PLAN 1 (plan1.ps) | PLAN 2 (plan2.ps) | |||
| Route 1 | D 83 84 89 86 96 104 109 105 106 98 102 101 95 88 87 93 94 112 97 92 90 79 56 51 49 42 37 21 18 | 1173 | D 91 81 72 60 65 68 67 70 62 57 59 58 54 53 48 47 39 37 42 18 21 2 5 | 1172 |
| Route 2 | D 73 69 61 55 50 44 45 36 34 25 30 31 27 32 35 43 41 28 23 24 22 17 15 13 10 8 1 6 5 2 | 1178 | D 83 84 86 96 100 107 110 111 119 116 108 103 99 82 77 74 71 52 43 41 46 29 28 23 19 20 16 9 11 12 3 4 7 | 1175 |
| Route 3 | D 81 72 60 65 68 67 70 75 78 80 76 66 64 63 62 57 59 58 54 53 48 47 39 40 26 38 33 14 | 1183 | D 85 89 104 117 118 120 115 109 113 114 105 106 98 102 101 95 88 87 93 94 112 97 92 90 80 78 75 76 66 63 64 79 56 51 49 | 1180 |
| Route 4 | D 85 91 114 113 115 120 118 117 119 116 108 110 111 107 100 103 99 82 77 74 71 52 46 29 20 19 16 9 11 12 3 4 7 | 1183 | D 73 69 61 55 50 44 45 36 34 25 30 31 32 35 27 24 22 17 15 13 10 8 1 6 14 33 38 26 40 | 1183 |
| Longest Route Length | 1183 | 1183 | ||
| Average Delivery Time | 67058 / 120 = 558.82 | 69392 / 120 = 578.27 | ||
| Average Route Length | 4717 / 4 = 1179.25 | 4710 / 4 = 1177.50 | ||
After a month of scheming and secrecy going around at the TUE, we come the conclusion that it was a most enjoyable project. It is however, a relief to know that we no longer have to think about or worry about this project. After dreaming about solving this problem though an incredible shot in the game of billiards by discovering an isomorphism between the solution space and the paths of the billard balls, after dreaming about other people getting 1181's, after waking up with a bug fix in mind or having discovered a new and more clever approach, we can finally sleep peacefully again. Moreover, we can pick up our studies where we left of and try to fix the damage done by a month of neglect. But overall we learnt a lot and decided it well was worth the effort.