How many newsvendors?

Last October in India, I was traveling with my father on a day-train from Bangalore to Chennai. About halfway into the journey is a station called Jolarpet, where the train stops for about 10 minutes. As at other stations, there are dozens of vendors – each with a simple wheeled stall, or a wooden basket or a steel container – engaged in a frenzy of small scale entrepreneurship. They hawk all sorts of stuff: snacks, tea, coffee, water, bananas, flowers, and cheap Chinese goods - toys, combs, and, in what became a curiosity among our fellow travelers, pens that double as flashlights. But my father was most interested in those who sold vadas, a South Indian specialty, a round fried snack with a hole in middle – like a donut, but not sweet – made from a batter of rice flour and white lentils (I’ve described just one variety). My father feels the vadas sold by vendors at the Jolarpet station are very good, better than those made in the train’s pantry. They are piping hot, the texture is perfect, and the timing – late afternoon – is just right to munch on them and wash them down with coffee.

Three fairly busy trains – including the Bangalore-Chennai Brindavan Express on which we were traveling that day – arrive at Jolarpet station at about the same time late in the afternoon. That’s boom time for vendors selling vadas. “How many get sold?” my father wondered. “Maybe a thousand of them, maybe even more.”

As soon as he said this, I began in my own nerdy way to think about the newsvendor problem. For those who might not be aware, the newsvendor problem is stylized situation but one that arises in myriad forms and in varied contexts all over the world. Here’s the simplest form of the problem: How many newspapers should a newsvendor decide to produce given that demand for newspapers is uncertain on any day? If she underproduces she loses the opportunity cost; if she overproduces, the cost of producing those extra newspapers is wasted – they can’t be sold the next day as the news will by then be old. If she has some idea of the distribution of the demand, the optimal number of newspapers will be that point on the demand distribution curve that will balance the expected lost opportunity cost and the expected wasted production cost.

In selling vadas too vendors at Jolarpet station must face a similar dilemma: how much should one make? Just as newspapers are useless the next day, vadas need to be sold immediately, since nobody will buy them cold. The timing – more specifically the decision of when to make the batter and fry them –is as important as the decision of how many to produce. The ingredients – cooking oil, rice and lentil flour – aren’t perishable (in other words they can last a long time), but once a vada is made, it is perishable, since a cold vada is unacceptable.

How do these vendors do their planning? I am guessing it’s informal, based on intuition, and sharpened by experience. But I wouldn’t be surprised if the more competitive among them kept records of how much they sell each day, so they can get a sense of the demand distribution, which is, of course, directly related to how full the trains are, which in turn is related to the time of the year. Festival seasons mean packed trains, and more sales; there are probably periods of relative lull as well.

There’s also the aggregate planning component about how much lentils, rice flour and cooking oil to buy. And the operational level decisions: listening to the announcements at the station, and using that information adequately – such as to delay the frying based on whether a train is late.

There’s a certain beauty in this sort of informal decision-making. The vendor at Jolarpet station probably isn’t rich. He most likely does not have access to computers or Excel that might allow him to collect data and analyze it (though I could be wrong about that assumption). But he’s still using some model - however obscure it may be to us - and he’s adapting all the time.

When you look situations this way, it would seem elements of operations research are omniscient. Consider just the newsvendor problem. Imagine how the thousands of restaurants all over the world, small and large, might do their daily planning of perishable products. Think of how manufacturers order their raw materials subject to uncertain customer orders, how hospital emergency rooms might plan their staffing given uncertainty in patient arrivals.

In each of these applications, some sort of planning, however crude, is being used. Which makes me wonder: How many newsvendor-like problems are solved each day?

My algorithms class

One of my favorite classes during my doctoral studies at Arizona State University was Design and Analysis of Algorithms. This was back in the fall of 2002. Goran Konjevod was the instructor.

Goran had a penchant for stimulating thought and that showed in the sort of questions he chose from textbooks for his assignments and exams. Here’s one I remember enjoying very much. I like it particularly because of its dark, authoritarian overtones – it brings out the Stalin in you. Not the mass-murdering Stalin but a clinical and efficient one. I am joking, of course, but you'll see what I mean when you read this:

An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison king’s wine. Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle. Unfortunately, they don’t know which one. To make matters worse, the poison the spy used was very deadly; just one drop diluted even a billion to one will still kill someone. Even so, the poison works slowly; it take a full month for the person to die. Design a scheme that allows the evil king to determine exactly which one of his wine bottles was poisoned in just one month’s time while expending at most O (log n) of his taste testers.

And no, the answer is not that we need a human rights commission to investigate this, though that might be a tempting lateral-thinking answer! Don’t ask me for the solution to the question either; I’ve long forgotten it!

What I do want to state is that I was quite inspired by the class. I was doing a PhD in Industrial engineering, but the class taught me the computer science way of looking at problems, and illustrated how intelligent one could be in designing algorithms. Without a doubt, the class was why I eventually went to write a dissertation on algorithmic complexity of certain scheduling problems. Thanks very much, Goran. All the troubles – the poor grades, the hobble to the final exam dodging a nail* – were certainly worth it!

A lot of Goran's papers, many of them OR papers on approximation algorithms and polyhedral theory, are available on his site. He also has an origami gallery.

* I overslept on the morning of the final exam. The exam was scheduled for 7:40 am, but I woke at 7:45 am. When I saw the clock, I screamed; my roommate woke with a start. As luck would have it, I’d left my bike at school the previous night. I had no time to brush. I had no time to wear my shoes either; so I chose an old pair of sandals, one of which incidentally had an iron nail inextricably lodged in it. I hobbled a mile to the exam, making sure I did not step on the portion of the sandal that had the nail. I was in my nightclothes, but mercifully at the time, my nightclothes didn’t differ much from what I wore during the day. I got to the exam at about 8:05 am, and did what I could in the time I had. It shall suffice to say that I somehow scraped through.