Cone stacking algorithim

Greetings all,

Last weekend I was at my son's football class (soccer). Every week they play this game where the coach scatters a bunch of cones across the field, and the kids pretend they are trees. The goal is to kick the ball from one end of the field to the other without hitting the cones. Anyway that is not what piqued my interest.

What did pique my interest was the time when everyone was made to clean up. What happened was this: The kids all scattered about picking up cones, each had one or two in their hands, then they would look at the kid next to them and they would combine their stacks and each kid would combine their stacks with other kids until the coach came by and added their little stacks to the master stack. But to complicate things, the kids would not stop gathering cones and stacking them, sometimes they would make a new stack, or sometimes they would add to a stack they created. Some kids would then go around and collect other kid's stacks and place them on to their stack. Or sometimes they would leave their stack alone and go collect somewhere else waiting for the coach or some other kid to pick theirs up.

So the question is, how could someone model this real world behavior in code? Does this behavior sound like any known algorithms?

It seemed like a modified merge sort to me, but I like to think of the kids as agent sorters so there must be some kind of recursive element to it. Also there has to be some work in deciding how many agents are optimal, and what is the maximum stack size. Also there is an element of "load balancing" where the little sorting agents will abandon their area if it is stacked and move to a more entropic area.

If anyone would like to start analyzing this behavior with me please add your thoughts.

re: Cone stacking algorithim

It's equivalent to a Capacitated Vehicle Routing Problem (CVRP); it's a filthier problem than just a few 'simple' Travelling Salesmen Problems (TSP) and can take hours to solve when the capacity restrictions vary per vehicle/child. If the coach/depot of the system is moving itself the catastrophy is imminent. Don't go there.

kind regards,

Jos

re: Cone stacking algorithim

Interesting reading. But from what I see a CVRP contains vehicles originating from one depot. So that means this would be particularly difficult since there would be multiple depots in the system.

If anyone has access to literature say from ACM or elsewhere or knows where to find full text research papers on this I would be very thankful if you would share.

re: Cone stacking algorithim

If there's only one coach and all the cones have to be handed over to him/her then this is also a single depot CVRP. The 'C' comes from the fact that kids can only carry so many cones maximum. Most of the time goes into solving a TSP per kid over and over again.

Those problems typically result in a 'flower shape' solution: the coach is the center of the flower and all the tours make up the leaves of the flower. Multiple depots add to the complexity of the CVRP. If the depots are moving I don't even want to try to solve this ;-)

A couple of Greek guys really worked on this problem: Bertsimas and Bertsekas and Papedimitriou come to mind (google for them and double check my spelling). Especially the last guy did quite a bit of work on the big-Oh aspect of these dirty problems. Also check Karel Lenstra and Alexander Schrijver (twp Dutchmen, yea!) who did a lot of work on 'local search' heuristics.

kind regards,

Jos