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


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.