Complexity, heuristics, and the traveling salesman problem

Add this one to your long reads queue, because it’s well worth it: Tom Vanderbilt writes in Nautilus about the traveling salesman problem and how algorithmic optimization helps us understand human behavior more deeply. It’s a thorough and nuanced analysis of the various applications of algorithms to solve the traveling salesman problem — what’s the most efficient way (which you of course have to define, either in time or money or gasoline etc.) to deliver some number n of packages to some number d of destinations, given your number t of trucks/drivers? This is a tough problem for several reasons, and Vanderbilt’s discussion of those reasons is clear and interesting.

We can start with a simple transportation model with small numbers of packages, destinations, and trucks. But as the number of them increases, the problem to solve becomes increasingly complex, increasing at least exponentially if not more. Then think about what happens when the locations of the destinations change every day, as is the case for UPS and FedEx deliveries. Then think about what happens when you add in heterogeneity of the deliveries; Vanderbilt opens with a girl pointing out that her mother would never buy perishables and then leave them in the car all day, so the nature of the item changes the constraints on the definition of the efficient route.

Her comment reflects a basic truth about the math that runs underneath the surface of nearly every modern transportation system, from bike-share rebalancing to airline crew scheduling to grocery delivery services. Modeling a simplified version of a transportation problem presents one set of challenges (and they can be significant). But modeling the real world, with constraints like melting ice cream and idiosyncratic human behavior, is often where the real challenge lies. As mathematicians, operations research specialists, and corporate executives set out to mathematize and optimize the transportation networks that interconnect our modern world, they are re-discovering some of our most human quirks and capabilities.

One of the most intriguing aspects of implementing logistics that reflect good solutions to the TSP that Vanderbilt highlights is the humanity of the driver. Does the dispatcher know the driver, know that s/he is reliable or not? That may affect how to define the route, and how many stops or changes to put on that particular person’s schedule. Is the driver prone to fatigue, and how does that fatigue affect the driver’s decision-making? What are the heuristics or rules of thumb that different drivers use to make decisions in the face of uncertainty given the cognitive limitations of humans? How different will the different heuristics of different drivers be, and how to they affect the logistics of the system?

What Vanderbilt finds is that good logistics systems take the organic, emergent system that incorporates those heuristics into account when devising the TSP algorithm. They leave a human component in the logistics, but also use the human component to inform and change the algorithm. Another important element is data, because all such algorithms are going to work in conjunction with such data as location. GIS mapping capabilities improve the data used to establish, test, and monitor TSP algorithms.

Don’t bet against Netflix, at least not now

Michael Giberson

Jonathan Knee argues that Netflix is succeeding the way big media companies always have succeeded, in a time where such opportunities are less frequent than before. From The Atlantic:

The economic structure of the media business is not fundamentally different from that of business in general. The most-prevalent sources of industrial strength are the mutually reinforcing competitive advantages of scale and customer captivity. Content creation simply does not lend itself to either, while aggregation is amenable to both.

[...]

Netflix’s success in streaming video is therefore hardly paradoxical. The company sits squarely in the tradition of the most-successful media businesses: aggregators with strong economies of scale and customer captivity.

There is a lot more explication at the link.

Non-traffic causes of traffic congestion

Michael Giberson

Is this an unpriced external effect of shooting off fireworks on July 4?

July 5 tends to have an unusual number of animal-related traffic problems, as pets, spooked by the fireworks on the previous day, have a greater propensity to wander onto freeways.

From Eric Morris at the Freakonomicsblog, “Road Blocks: The Strange Things That Cause Traffic.”

Other non-traffic contributors to traffic congestion mentioned in the article: oil spills, antifreeze, oranges, lemons, livestock, wild animals, abandoned pets, suicides, homicides, discarded Christmas trees, and furniture and appliances including couches, chairs, refrigerators, and stoves.

Netflix recommendations: Deep or random?

Michael Giberson

I know that Netflix’s recommendation engine has some serious computation behind it, and it often offers up interesting and useful suggestions. But occasionally it puzzles me, and I wonder if it is incredibly deep in its analysis or simply somewhat random.

Case in point:

Suggested: American Experience: Into the Deep

American Experience: Into the Deep: America, Whaling & the World
Because you enjoyed:

It Might Get Loud

Yojimbo

The Last Picture Show

 

So let’s get this straight, because I enjoyed a documentary about rock guitarists from different generations, and a classic Kurwasowa movie about a masterless samurai, and a black-and-white period piece about growing up in a small town in Texas, the artificial genius of Netflix thinks I’d enjoy a riveting documentary on the history of whaling in the United States?

Well, actually, it does sound kind of interesting …

Also, if they have any films about a rock-and-roll samurai sushi chef coming to a small town in Texas, I’d want to see that too.

The natural gas that didn’t come in from the cold

Michael Giberson

Among the complications caused by the cold weather last week, short supply of natural gas throughout much of the southwest United States. Reports indicate some gas wells were freezing up and loss of electric power to gas production systems, but more of the problem was loss of power to natural gas pipelines. And, as mentioned here Friday, in some cases the rolling blackouts in Texas cut power to the natural gas system, resulting in inadequate gas supplies, resulting in some gas-fired power plants being cut off from supply, hampering efforts to end the rolling blackouts. But the shortage wasn’t just a supply-side issue, a gas company official said demand for gas was the highest its been for 30 years.

Sources: Dallas Morning News, “Freeze knocked out coal plants and natural gas supplies, leading to blackouts,” and Wall Street Journal, “Texas Power Outages Cause Natural Gas Shortages In US Southwest.”

Hard hit New Mexico saw lawmakers spring into action. U.S. Representative Ben Ray Lujan is asking the Federal Energy Regulatory Commission to investigate. A state legislative committee is holding hearings today on the outages in the state. Thousands of Arizona gas consumers also lost service. Southern California gas supplies were difficult, but San Diego Gas & Electric and Southern California Gas Co. were able to maintain service to firm customers by drawing on nearby storage supplies and cutting off interruptible customers. (Interruptible customers are typically large industrial consumers who choose to pay a lower rate in exchange for agreeing to be among the first to be cut off during emergencies.)

Texas regulators are also asking questions, “Texas to Probe Rolling Blackouts.”

Texas officials have ordered an investigation into rolling blackouts that struck the state’s electric grid last week, including whether market manipulation played a role along with harsh weather in disrupting natural-gas and electricity supplies to millions of people.

The Public Utility Commission of Texas asked the state’s independent energy-market monitor, Daniel Jones, to conduct a probe to see if power generators, pipeline companies or others broke market rules. …

To be sure, Texas set an all-time winter power demand record one day during the storm, placing historic pressure on power providers.

Electricity-grid officials said Mr. Jones’ team will look at price patterns and power-plant outages remembering that, in California’s energy crisis of 2000-2001, unscrupulous power generators feigned equipment problems to drive up the price of electricity. A significant number of plants in Texas failed last week, and wholesale electricity prices briefly spiked.

Some commentators linked the electric power-gas pipeline interdependency issue to environmental regulation. As this Energy Information Administration document on natural gas compressor stations explains, compressor stations can be either electric or natural gas-fueled. As of the November 2007 date, most compressors were gas fueled, drawing gas from the pipeline itself to run the compressor station, but in some areas of the country “all or some may be electrically powered primarily for environmental or security reasons.” (Note that the document is dated before the current administration took office, so you can’t blame the White House for it.)

Pipelines head north and east from Texas in addition to west, but no reports of supply problems anywhere else in the country.

U.S. Natural Gas Pipeline Compressor Stations Illustration, 2008

U.S. Natural Gas Pipeline Compressor Stations Illustration, 2008. (EIA)

Speed as a for-profit service

Michael Giberson

Wednesday’s Wall Street Journal included a story on HOT lanes and other ways commuters can buy through congestion, “American Idle: On the Road.” One excerpt:

In the early years of the nation, entrepreneurs built toll roads, offering travelers a faster carriage ride in return for money.

Now, the concept of the toll road is making a comeback. In Virginia, a key element of a $4 billion transportation package proposed by Gov. Bob McDonnell includes expanding the use of “HOT” lanes, an acronym for high-occupancy toll lanes. These fast lanes will be operated by a private company within the existing freeway system. Toll rates could fluctuate according to demand, or be set based on time of day as they are on Route 91 in Los Angeles. Such pay-to-roll roads are in operation or on the drawing board around the U.S.

Klein’s review of The Wealth of Networks

Lynne Kiesling

I like Peter Klein’s review in the Independent Review of Yochai Benkler’s The Wealth of Networks. Apart from giving a good overview of the Benkler work, Peter offers some original insights that are worth thinking about. For example:

To ensure open access to the networked economy, Benkler favors a public-ownership network infrastructure, loose enforcement of intellectual property rights, subsidized R&D, and “strategic regulatory interventions to negate monopoly control over essential resources in the digital environment” (p. 21).

This approach has some problems. First, although information itself cannot be “owned,” the tangible media in which information is embedded and transmitted are scarce economic goods. Information may yearn to be “free,” but cables, switches, routers, disk drives, microprocessors, and the like yearn to be owned. Such innovations do not spring from nowhere; they are the creations of profit-seeking entrepreneurs that consumers or other entrepreneurs purchase to use as they see fit. Of course, private property can be nationalized. Federal, state, and local governments can ownbroadband lines as they own streets and highways, or they can treat network infrastructure as a regulated public utility. If these resources are to be treated as public goods, then what about computers, iPods, and cell phones? Are these gateways to the Information Superhighway also part of the digital commons? If individuals can own cell phones, can they sign contracts with service providers to deliver whatever content is mutually agreed upon? Content providers and consumers are free to terminate their agreements if they are unhappy. In this sense, a private-property regime allows as much “autonomy,” in the libertarian sense, as a commons-based system. Moreover, if one takes into account the problems of collective ownership, about which Benkler is largely silent, the case for the commons becomes even more problematic.

There he articulates clearly one of the aspects of Benkler’s arguments that has always bothered me, but I couldn’t pull together clearly enough. Here he does. Peter also makes some observations about Benkler’s definition and concept of liberty and about the endogeneity of culture and opinion that are thought-provoking. A worthy read.

FCC and internet regulation: “lobbyists on both sides are already shopping for new vacation houses in Aspen”

Michael Giberson

From Regulation 2.0:

Frustrated by a federal appeals court ruling that the FCC had no authority to second-guess Comcast’s treatment of customers and under pressure from the Obama Administration to impose a net neutrality regime (whatever that truly means) on the broadband industry, FCC Chair Julius Genachowski is now asserting the commission’s right to regulate Internet access providers under the ancient rules that govern telephone landlines.

We don’t know whether Congress will let the FCC get away with it – lobbyists on both sides are already shopping for new vacation houses in Aspen — or what the commission would actually do with the authority if it wins the political battle.   But we do know this is very bad news for those who fear that the uncertainty will slow both the expansion of Internet capacity and the pace of innovation.

Links in original, of which this is just an excerpt. The whole thing is short; read it to see why “the specifics of this issue make it especially troubling.”

Fish leg counts: What the web knows and doesn’t know

Michael Giberson

David Pennock hears another another tick of the clock in the countdown to web sentience.

[In 2003] we trained a computer to answer questions from the then-hit game show by querying Google. We combined words from the questions with words from each answer in mildly clever ways, picking the question-answer pair with the most search results. For the most part (see below), it worked.

It was a classic example of “big data, shallow reasoning” and a sign of the times. Call it Google’s Law. With enough data nothing fancy can be done, but more importantly nothing fancy need be done: even simple algorithms can look brilliant. When in comes to, say, identifying synonyms, simple pattern matching across an enormous corpus of sentences beats the most sophisticated language models developed meticulously over decades of research.

Our Millionaire player was great at answering obscure and specific questions … It failed mostly on the warm-up questions that people find easy — the truly trivial trivia. The reason is simple. Factual answers like the year that Mozart was born appear all over web. Statements capturing common sense for the most part do not. Big data can only go so far.

In 2003 their best example of a question that they could not answer via websearch was “How many legs does a fish have?

Now, on the other hand, Pennock said:

I was recently explaining all this to a colleague. To make my point, we Googled that question. Low and behold, there it was: asked and answered — verbatim — on Yahoo! Answers. How many legs does a fish have? Zero. Apparently Yahoo! Answers also knows the number of legs of a crayfish, rabbit, dog, starfish, mosquito, caterpillar, crab, mealworm, and “about 133,000″ more.

Pennock links to Lance Fortnow’s related comments on IBM’s effort to write a Jeopardy-playing computer, and Fortnow suggests something that is going to remain hard for computers for a while: making sense of natural language in context. Fortnow, part of the group that wrote the Millionaire paper, said:

Humans have little trouble interpreting the meaning of the “answers” in Jeopardy, they are being tested on their knowledge of that material. The computer has access to all that knowledge but doesn’t know how to match it up to simple English sentences.

Why hasn’t the web revolutionized scholarly publication?

Michael Giberson

When Tim Berners-Lee created the Web in 1991, it was with the aim of better facilitating scientific communication and the dissemination of scientific research. Put another way, the Web was designed to disrupt scientific publishing. It was not designed to disrupt bookstores, telecommunications, matchmaking services, newspapers, pornography, stock trading, music distribution, or a great many other industries.

And yet it has.

[...] The one thing that one could have reasonably predicted in 1991, however, was that scientific communication—and the publishing industry that supports the dissemination of scientific research—would radically change over the next couple decades.

And yet it has not.

The article offers a detailed assessment of why the web has changed scientific publishing in some small ways without fundamentally disrupting the pre-existing system.  You may be tempted to say that it is just because academia is fundamentally a conservative, status-driven institution, but would not the same be true of many other industries that have been reshaped by the internet?

HT to Marginal Revolution.