Obviously we couldn't resist the temptation to solve this problem when
CMG
announced it. Though we didn't start immediately after the announcement, we
did spend close to a month on the problem, some days more intensely than
others. Assuming about 10 man-hours of work a day for 20-25 days, we
spent about 200-250 hours on this project in total. This of course is
NOTHING compared to the amount of computer-hours we spent, which is
around 15,000 hours!
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 so 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 paramaters 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.
The Technique
The First Program
Improvements to the Program
The Second Program (route.tar.gz)
The Solutions
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.