Monday, December 30, 2013

Indian Intellectuals and the Fighter-Pilot Syndrome

Update: title changed

Legendary formula car racer Michael Schumacher suffered a serious injury in a skiing fall. As millions around the world pray for his safe recovery,  a troubling question was triggered by this sad news:

"How likely is it for a skiing enthusiast, who is known to have made a successful career in the superfast and dangerous world of Formula car racing, to meet with a skiing accident?"

Does this conditional probability increase or decrease? I am not aware that Schumi claimed he was a skiing expert or thought of himself as one. This is just a sample of one and could just be a tragic coincidence. The question remains open and the focus of this post is on a related topic.

Here's a wikipedia blurb on a US Air Force officer John Stapp:
"During his work at Holloman Air Force Base, Stapp became interested in the implications of his work for car safety. At the time, cars were generally not fitted with seatbelts, but Stapp had shown that a properly restrained human could survive far greater impacts than an unrestrained one. Many traffic-accident deaths were therefore avoidable but for the lack of seatbelts. Stapp became a strong advocate and publicist for this cause, frequently steering interviews onto the subject, organizing conferences, and staging demonstrations (including the first known use of automobile crash test dummies). At one point, the military objected to funding work they believed was outside their purview, but they were persuaded when Stapp gave them statistics showing that more Air Force pilots were killed in traffic accidents than in plane crashes. The culmination of his efforts came in 1966 when Stapp witnessed Lyndon B. Johnson sign the law making manufacture of cars with seatbelts (lapbelts at that time) compulsory..."

Controlling fast jets did not give those pilots additional skills that made them equally safe at driving cars at some speed. Is it possible that this 'fighter pilot effect' gave them a false sense of security while driving the much slower motor cars?  Similarly, safely driving ultra-fast cars shouldn't automatically make one an equally safe hi-speed skiing expert (update: initial reports indicate Schumacher was not going very fast). However, public belief in this 'fighter pilot syndrome' appears to exist at some level, and this is especially true in India. For example, if you win a Nobel Prize or for that matter, any prize in the west, then regardless of your field of expertise and your near-total ignorance about what makes India tick, you are given special powers that turn you into an expert on every topic under the sun (especially Indian culture and politics), overnight. Unlike Marxist economist Amartya Sen or India's egoistic movie stars, who don't need a second invitation, there are others who prefer not to make a fool of themselves in public. However, the Indian media does not spare them the embarrassment by demanding their "fighter pilot" advice on unrelated topics. This 'intellectual celebrity' feedback is then used to try and influence public opinion. A good example is the recent NDTV-25 debate panel on "secularism in India" compered by 2G-scam tainted journalist Barkha Dutt that included exactly one genuine expert, Arun Shourie, who knew what he was talking about, and bunch of other "experts".

All-weather experts and their Indian media co-pilots must be asked to wear their seat-belts and slow down before they take the Indian public for a ride.

Happy New Year. Drive Safe. Get well soon, Schumi.

Monday, December 9, 2013

Optimize Your In-store Holiday Shopping Route

Remember the last time you were not tired after holiday shopping in a busy mall, bulk shopping at a discount-club store, or weekend shopping at a crowded grocery store?

(source links: http://info.museumstoreassociation.org

Hopefully, the simple and preliminary 'operations research (O.R)' analysis in this post can help make the experience a little less stressful and maybe even let us enjoy a bit of retail therapy that we can't get online.  The shopping optimization problem addressed here is simple one, albeit with a twist. This post was triggered by an observation made after recent shopping expeditions to a nearby Costco outlet.

We have a long shopping list of L line-items (i) of various quantities N(i) that we have to pick up in a store. How should we optimally reorder our shopping list to reflect the sequence in which we pick up these items?

Version 1
The simple version aims to minimize total shopping time. For example, we can formulate this as an instance of the so-called traveling salesman problem (TSP) that finds the shortest sequence that starts at the entrance, visits each of the L 'cities' once, then the checkout counter, and ends at the store exit (entrance). A google search shows this 2009 research paper by researchers at UPenn, which shares the technical details and interesting results for this version.

To simplify our problem, we assume that the topology of the store is prior knowledge, and we can roughly pre-assign items in the same aisle to the same 'city'. The resultant problem is to find the order of visits to the aisles of interest to us. If the aisles are neatly arranged as node intersections in a rectangular grid, then we simply have to find the shortest rectilinear "Manhattan" distance tour in this grid. Depending on the type of the store, the store-layout itself may be optimized by the retailer based on the observed foot-traffic and 'heat-map' data. For example, it may be designed to retain the customer in the system to increase chances of purchase (exploratory tour, store selling expensive luxury/fashion products), or quickly out of the system (routine tour, obligatory products like groceries), or based on some other goal. Store space and layout problems are known to be commercially useful optimization problems in the retail industry.

Picture linked from an iTunesApp (Concorde) page of Prof. Bill Cook that solves TSPs :)

Version 2
Let us additionally assume that product attributes have an impact on our order. Suppose one or more items in our list is located in the frozen section at a grocery store, then we may prefer to get there at the end of our tour. Luckily, many stores appear to anticipate this (?), and locate this section towards the end of the store. Thus if 'maximum freshness' or 'minimum damage' is an additional consideration, this may alter the TSP route and the final ordering of items in our shopping list.

Version 3
This was the problem that was of immediate interest to me today. Costco sells stuff in bulk, so the items tend to be heavy, and considerable energy is expended moving the cart through the store. At the risk of mangling undergrad physics, let us proceed with our analysis...
Let μ be the (constant) coefficient of rolling friction between the wheels of the shopping cart and the store-floor. Then the work required to move mass m through distance d = force x displacement =μmgd, where g is the (constant) acceleration due to gravity. Thus a squeaky-wheeled cart will make us work extra hard. Speed of shopping is a consideration if we want to keep track of power (force x velocity). Covering the same tour length in half the time requires twice the power, i.e. the rate at which our body expends stored energy.

Carry versus Cart (reinventing the wheel)
If we had zero rolling friction, technically the only work involved is in lifting items and putting them in our cart. We can assume that this work is independent of our order of visit and is a fixed quantity. On the other hand, if we are not working with a wheeled-cart, but carry our stuff in a market-basket or shopping bags, then we have to raise the potential energy of the items to height 'h' (mgh) all the way until checkout, and also overcome the sliding friction between our shoes and the floor, which would probably be higher than the rolling friction, as illustrated below.

(link source

Why is a shopping experience increasingly stressful over time?
As we add items to our cart, the work done per unit time (power) required increases. In the continuous case, this problem closely resembles our 'optimal snow shoveling problem' analyzed during a February snow storm. The accumulated objective function cost there increases as the square of the distance. Here, we look at the discrete situation. When we visit city 'i' to pick up N(i) items each having mass m(i), we instantaneously add mass N(i) * m(i) that we have to lug around until checkout. After picking up k-1 items, my total work done will approximately be:
μg * sum (i = 0,... k-1) W(i) * d(i, i+1), where i = 0, represents the store entrance, m(0) represents the mass of an empty shopping cart, and
W(i) = sum(j = 0, .., i) N(j) * m(j) = total mass carried from city i to i+1.

In other words, the 'cost' accrued while traversing any pair of cities also depends on the items we picked up earlier, i.e., it is no longer memory-less and varies depending on the cities visited earlier.

Result: our shopping gets increasingly more tiring over time

If one of the items in our shopping list involve a heavy item, then our optimal solution may no longer be the shortest time tour.  We now have to solve a minimum-effort TSP. Operations Researchers have also looked at methods for solving a path-dependent TSP in the past. A simple heuristic approach would be to break the trip into two tours. The earliest items stay with us the longest, so we first find the optimal sequence through the light items, followed by the shortest tour through the heavy items. We also have to organize the shopping cart carefully enough to ensure that our light items do not get squished by heavy products, and our ice-cream doesn't melt. I'm sure there are better algorithms than the one provided here.

If we want to burn calories while shopping then a good way to do that, based on our previous discussion is (a) carry our items, (b) pick up the heaviest items first, and (c) take the longest route to maximize energy expenditure (d) walk briskly. This health-and-fitness article provides ten tips for exercising that includes these ideas. For the rest of us who are looking to minimize effort, we simply do the opposite:

We sort our shopping list items in decreasing order of expected weight (frozen stuff goes to the bottom too), while also ensuring that the aisles of adjacent items in the list are close to each other, and we are not revisiting aisles or zig-zagging much.  Some swapping may be required to find improved sequences. Many of us have probably evolved into efficient shoppers over time, and naturally take these steps and more, but if there an opportunity for improvement that the 'science of better' can uncover for us to make our shopping less stressful, let's take it.

Happy Holidays!

Update 1: December 17, 2013
IBM Smarter Retail article says:
"..... Most recently, Lowe’s has offered the customer a product location functionality that is integrated with their wish list. According to Ronnie Damron, .....Whether customers are browsing the store for ideas or searching for a specific item in a hurry, we think the Product Locator feature will simplify the shopping process, creating a better experience that encourages customers to come back again and again.”