mem·o·ry·less·ness

This is an interesting discussion of queueing theory as it applies to pumpkin patches.

This weekend, my family and I went to a pumpkin patch. Everyone else had the same idea. The line stretched out of the pumpkin patch gates and through the parking lot. We waited in line for ten minutes and then balked. When we left, about 90% of those that were leaving did not have pumpkins. We arrived in the morning on Sunday. It was only going to get busier. I cannot imagine the amount of revenue that was lost. We found out later that it took nearly two hours to get through the line.

During our short wait and on our drive to another orchard, we discussed queuing and pumpkin patches.

This link is an interesting perspective on Little’s Law, L = λW (a fundamental law in queueing theory), which turns 50 this year. (Strictly speaking, it’s the proof of the law that’s turning 50.)

According to the editors of Operations Research:

Little proves that under very general conditions, the average length of a queue, in steady state, will be equal to the arrival rate into the queue times the average wait in the queue. Remarkably, this relationship is not influenced by the arrival process distribution, the service distribution, the service order, or practically anything else. Nor does it depend on the structure of the queueing system: “Little’s Law” holds not just at the individual queue level but also at the system level.

More:  John Little’s new paper about his law - “Little’s Law as Viewed on Its 50th Anniversary”

petzoldt:

The “Traveling Sales Man Problem” is a classic in Operations Research. It asked for the shortest round trip through a set of cities given the distances beween them. For 20 cities there are already 2.432.902.008.176.640.000 of such tours. A computer able to calculate a trip length in A computer able to calculate a trip length in one milliseconds would still need 240 billion years checking all of them.

Its fascinating to see how researchers keep pushing the limits when solving ever larger problems using methods from mathematical optimization and Operations Research, such as William Cook who claims to have calculated the best tour visting 1.9 million cities.

This site features VBA operations research add-ins for Excel.  These would likely come in handy for small-scale (and not-so-small-scale) O.R. modeling.  Dr. Paul Jensen, Professor Emeritus at the University of Texas, gave a keynote presentation on these tools yesterday at INFORMS 2010.

Bees solve the Traveling Salesman Problem everyday.

The TSP is heavily used in theoretical compute science and in operations research, and is classified as a NP-hard problem.

In its original formulation, the solver is given a list of cities, and their pairwise distances, and is then tasked with finding the shortest possible distance that will allow them to visit each of the cities exactly once.

…

“Foraging bees solve traveling salesman problems every day. They visit flowers at multiple locations and, because bees use lots of energy to fly, they find a route which keeps flying to a minimum,” explains Dr Nigel Raine.

…

“Despite their tiny brains bees are capable of extraordinary feats of behavior. We need to understand how they can solve the Traveling Salesman Problem without a computer. What short-cuts do they use?” Raine says.

The new investigation could have significant implications for agriculture, because bee pollination patterns are critically important for next year’s crops.

(image source)

My original thesis project in graduate school related to optimal ambulance routing. It’s good to see people using operations research in that manner, and it’s not surprising how lucrative it can be.

“It’s about how you match the resources you have got available most effectively to the emergency calls that are coming in and it’s not just matching the ambulance to the call but also matching it from a geographic sense as well,” said Mackay. “It’s a very difficult thing for somebody to do in their head which is typically what happens in most dispatch centres.”

…

In the United States there are 15,000 individual ambulance providers and another 30,000 fire providers.

“North America alone for us is potentially a billion dollar market. Even if we can get 5 per cent of that we’ll be doing well.”