Where are you based?

[Arch]

I know folk on here have expressed interest, but if you could just bung a quick 'me too' in the jersey thread, we can keep track...

 

[magnatom]

I believe that it would necessarily be an approximation as there is no true solution to this problem.

Actually, if wikipedia is right (and that is sometimes questionable!) it would appear with enough computing power and time you can find exact solutions. It would appear that we need over 200 points on the map to at least give bonj a proper challenge!

 

[Danny]

I know folk on here have expressed interest, but if you could just bung a quick 'me too' in the jersey thread, we can keep track...

Perhaps it would be simpler if one person - say Arch - volunteered to start, and then PMs the people closest to them to find out who is willing to take it next.

 

[bonj2]

I always thought the traveling salesman problem was a difficult one to solve, especially when there are a large number of stops (such as in this case). Just out of interest bonj, how would you go about solving it? Would it be a true solution or an approximation?

It's difficult. The best way of doing it would be to use some sort of 'tree' algorithm, similar to the algorithm that's used in a chess computer.
Consider the brute-force case whereby you work out the distance from each person to each other person, so you have (n^2 + n)/2 possible individual routes. But the number of ways of arranging these routes is analogous to the total number of possible ways of ordering the participants, therefore the number of possible solutions is equal to the permutations of n participants out of a total of n, therefore N = n!/(n - n)! = n!. (where N = number of possible solutions, and n = number of participants.
So if there were 1500 participants, there would be 1500! possible solutions. The brute force case would be to analyse the total distance covered by each of these solutions, and pick the one with the lowest. However, 1500! is appropximately 4.8x10^4114 ( ) an absolutely unimaginably large number, and the most powerful supercomputer could not even make a dent in it in many many years. (Especially when you consider that it's probably got to make use of a third party routing engine to calculate the actual routes along suitable roads - it's not just a case of doing a few numerical sums...)
So what has to be done, is 'pruning'. This is whereby you stop considering a certain solution early on if it's showing signs of being crap.
Going back to the chess analogy, for example the brute force algorithm would consider ALL possibilities of what could happen over the next 10 moves. But it will chuck away instantly all branches which involve, say, the computer sacrificing his queen after only 1 move, and won't even bother to look 10 moves ahead, because he knows that's crap straight away and is wasting time proving that's the case by considering all possibilities of what could happen over the next 9 moves after that.
I would guess a good implementation of the solution to find the best arrangement of routes would go something along the lines of that.
However, a computer is never as good as a human at foresight, and we can spot instantly what it might take a computer ages to work out, as the computer has no actual spatial perception as such, it only knows distances between points, and eastings and northings. Also, as Arch says - we might want to take into account things like who would prefer to cycle more and less, would anyone prefer to cycle with other people, would you want to stop off at a pub, etc etc.! Something that even the most beautiful finely crafted algorithm in the world couldn't give us! So I would recommend Arch's pen-and-paper and common-sense solution, interesting though it may be to come up with an elegant algorithm...

 

[bonj2]

I believe that it would necessarily be an approximation as there is no true solution to this problem.

w.r.t my post above - I believe there may be a true solution - but finding it is another matter! e.g. I believe the answer to the question 'can you program a computer to FIND the true solution' is analogous to the question 'can you program a computer to be a perfect chess player'. Yes, technically - but how fast a computer do you need?

 

[magnatom]

I do believe that bonj might actually know what he is talking about here!!

 

[Arch]

Perhaps it would be simpler if one person - say Arch - volunteered to start, and then PMs the people closest to them to find out who is willing to take it next.

Absolutely, I think that's the best way for it to proceed (by PM or posts in the thread) - in fact having just looked at the thread, we may have our first rendezvous, in Jersey, tentatively arranged, if the shirt can be got to McD in time.... Otherwise, Admin might be a good place to start, as he's requested a friedly jersey just for this purpose....

 

[Christopher]

PM sent to bonj for the map. I'm in Preston, PR1...

 

[Andy in Sig]

Why not just post the shirt to whoever is furthest away (probably Keith Oates) and he then does a leg to the next furthest away or passes it on to somebody who's doing a world tour and so it finds it way home ... eventually.

 

[Arch]

Surely the key thing is the route choice. I do a lot of navigating in different forms, and solutions to route problems are never as easy as they seem. So I am all for the big map on the wall and a pen solution route. If several people are similar distances from the intended drop-off, it's important to bear in mind the old chest-nut "x is only 75 miles away, but I wouldn't start from here!"

oooh, ooooh! Could we get a great big table, with a huge map stuck down on it, and a little model of a cyclist and I'l dress as a WRAF and push it about with a stick....

 

[TheDoctor]

*imagines Arch dressed as WRAF with big stick*

 

[magnatom]

oooh, ooooh! Could we get a great big table, with a huge map stuck down on it, and a little model of a cyclist and I'l dress as a WRAF and push it about with a stick....

Can I be Winston Churchill.....

"We shall go on to the end, we shall pass the jersey to France, we shall pass the jersey over the seas and oceans, we shall cycle with growing confidence and growing strength in the legs, we shall cycle our Island, whatever the cost may be, we shall cycle on the A roads, we shall cycle on the B roads, we shall cycle in the C roads and in the local streets, we shall cycle in the hills; we shall never surrender to the bonk, and even if, which I do not for a moment believe, these cyclists or a few of them were knackered and starving, then our Forum members on the internet, protected and guarded by a virus checker, would carry on the journey, until, in God's good time, the Forum members, with all their leg power and might, cycle forth to the pass the jersey like the C+ of the old...."

 

[Arch]

Can I be Winston Churchill.....

"We shall go on to the end, we shall pass the jersey to France, we shall pass the jersey over the seas and oceans, we shall cycle with growing confidence and growing strength in the legs, we shall cycle our Island, whatever the cost may be, we shall cycle on the A roads, we shall cycle on the B roads, we shall cycle in the C roads and in the local streets, we shall cycle in the hills; we shall never surrender to the bonk, and even if, which I do not for a moment believe, these cyclists or a few of them were knackered and starving, then our Forum members on the internet, protected and guarded by a virus checker, would carry on the journey, until, in God's good time, the Forum members, with all their leg power and might, cycle forth to the pass the jersey like the C+ of the old...."

<weeps patriotic tears into Union flag hanky>

In the words of Humphrey in one of the Church Mouse books, I have nothing to offer you but blood, sweat and a few jellybeans once we get back to the vestry...

We few, we happy few....

 

[TheDoctor]

<weeps patriotic tears into Union flag hanky>

In the words of Humphrey in one of the Church Mouse books, I have nothing to offer you but blood, sweat and a few jellybeans once we get back to the vestry...

We few, we happy few....

I was actually reminded of a line from Jeremy Clarksons' book, 'I know you got soul'. Yes, I know, but bear with me. It was describing the dark days of WW2, and he mentioned Churchills' speech on the radio, and dashing, handsome young men fighting unbelievable hardships on a daily basis, to defend everything we believe in, and the rest of us thinking 'Yes, we can really do this'. Maybe, just maybe, this was the finest machine ever built.

He was talking about the Spitfire rather than the bicycle, but he's got a point.

*wells up with patriotic pride*

 

[ChrisKH]

<weeps patriotic tears into Union flag hanky>

In the words of Humphrey in one of the Church Mouse books, I have nothing to offer you but blood, sweat and a few jellybeans once we get back to the vestry...

We few, we happy few....

.....we band of brothers ( & sisters).