Agent based modeling

I came across two articles on the "wisdom of swarms":
1. Swarm Theory in NGS:
"Ants aren't smart," Gordon says. "Ant colonies are." A colony can solve problems unthinkable for individual ants, such as finding the shortest path to the best food source, allocating workers to different tasks, or defending a territory from neighbors. As individuals, ants might be tiny dummies, but as colonies they respond quickly and effectively to their environment. They do it with something called swarm intelligence.

Where this intelligence comes from raises a fundamental question in nature: How do the simple actions of individuals add up to the complex behavior of a group? How do hundreds of honeybees make a critical decision about their hive if many of them disagree? What enables a school of herring to coordinate its movements so precisely it can change direction in a flash, like a single, silvery organism? The collective abilities of such animals—none of which grasps the big picture, but each of which contributes to the group's success—seem miraculous even to the biologists who know them best. Yet during the past few decades, researchers have come up with intriguing insights.

One key to an ant colony, for example, is that no one's in charge. No generals command ant warriors. No managers boss ant workers. The queen plays no role except to lay eggs. Even with half a million ants, a colony functions just fine with no management at all—at least none that we would recognize. It relies instead upon countless interactions between individual ants, each of which is following simple rules of thumb. Scientists describe such a system as self-organizing.
...
That's how swarm intelligence works: simple creatures following simple rules, each one acting on local information. No ant sees the big picture. No ant tells any other ant what to do. Some ant species may go about this with more sophistication than others. (Temnothorax albipennis, for example, can rate the quality of a potential nest site using multiple criteria.) But the bottom line, says Iain Couzin, a biologist at Oxford and Princeton Universities, is that no leadership is required. "Even complex behavior may be coordinated by relatively simple interactions," he says.

Inspired by the elegance of this idea, Marco Dorigo, a computer scientist at the Université Libre in Brussels, used his knowledge of ant behavior in 1991 to create mathematical procedures for solving particularly complex human problems, such as routing trucks, scheduling airlines, or guiding military robots.

In Houston, for example, a company named American Air Liquide has been using an ant-based strategy to manage a complex business problem. The company produces industrial and medical gases, mostly nitrogen, oxygen, and hydrogen, at about a hundred locations in the United States and delivers them to 6,000 sites, using pipelines, railcars, and 400 trucks. Deregulated power markets in some regions (the price of electricity changes every 15 minutes in parts of Texas) add yet another layer of complexity.
...
Ants had evolved an efficient method to find the best routes in their neighborhoods. Why not follow their example? So Air Liquide combined the ant approach with other artificial intelligence techniques to consider every permutation of plant scheduling, weather, and truck routing—millions of possible decisions and outcomes a day. Every night, forecasts of customer demand and manufacturing costs are fed into the model.

"It takes four hours to run, even with the biggest computers we have," Harper says. "But at six o'clock every morning we get a solution that says how we're going to manage our day."
For truck drivers, the new system took some getting used to. Instead of delivering gas from the plant closest to a customer, as they used to do, drivers were now asked to pick up shipments from whichever plant was making gas at the lowest delivered price, even if it was farther away.
"You want me to drive a hundred miles? To the drivers, it wasn't intuitive," Harper says. But for the company, the savings have been impressive. "It's huge. It's actually huge."

Other companies also have profited by imitating ants. In Italy and Switzerland, fleets of trucks carrying milk and dairy products, heating oil, and groceries all use ant-foraging rules to find the best routes for deliveries. In England and France, telephone companies have made calls go through faster on their networks by programming messages to deposit virtual pheromones at switching stations, just as ants leave signals for other ants to show them the best trails.

In the U.S., Southwest Airlines has tested an ant-based model to improve service at Sky Harbor International Airport in Phoenix. With about 200 aircraft a day taking off and landing on two runways and using gates at three concourses, the company wanted to make sure that each plane got in and out as quickly as possible, even if it arrived early or late.

"People don't like being only 500 yards away from a gate and having to sit out there until another aircraft leaves," says Doug Lawson of Southwest. So Lawson created a computer model of the airport, giving each aircraft the ability to remember how long it took to get into and away from each gate. Then he set the model in motion to simulate a day's activity.

"The planes are like ants searching for the best gate," he says. But rather than leaving virtual pheromones along the way, each aircraft remembers the faster gates and forgets the slower ones. After many simulations, using real data to vary arrival and departure times, each plane learned how to avoid an intolerable wait on the tarmac. Southwest was so pleased with the outcome, it may use a similar model to study the ticket counter area.

2. James Fallows on Dayjet which has recently filed for bankruptcy:
Jim Herriott and Bruce Sawhill, computer scientists in their 40s, are the ant farmers. They have worked together for 10 years—the first five at the Santa Fe Institute in New Mexico and the past five at DayJet. When we met, they had a comedy-team manner, with Herriott playing the straight man, carefully explaining the principles, and Sawhill the mad scientist, exclaiming about the elegance of the underlying math. Their job has been to determine exactly how many people might pay to use an air taxi, and where they would want to go. Their answers have come through ant farming, which could less colorfully be called inductive reasoning.

For instance, to predict how many Floridians would pay to fly from Pensacola to Naples, they start not by gathering gross-travel or population figures but by trying to simulate the decisions that hundreds of thousands of individual travelers will make. Their computer models resemble a much more complex version of an “artificial life” computerized game like SimCity or SimLife—or, to explain the nickname they gave themselves, programs that simulate the paths a colony of ants will take across a floor as they discover and retrieve pieces of food. This process is also known as “agent-based modeling.” The ants, or agents, in DayJet’s model are the 500,000 people per day in the seven southeastern states who take business trips of 100 miles or more. Some 80 percent of these trips are now made by car. Commercial airlines account for most of the rest, with trains, buses, charter flights, etc. making up the remainder. (In the Northeast, commercial airlines represent less of the total, and trains more.)

Herriott and Sawhill have developed a model to simulate the individual decisions that go into every one of these business trips. The model starts with the likelihood that a person in any one city, let’s say Mobile, will want to go to another, say Savannah, on any given weekday (for now, DayJet is a weekday-only service). These predictions are based on average income in each city, business relations, and other factors, and are constantly tuned to reflect real data. “It’s like the pull between two planetary bodies,” Herriott said. “Almost a Newtonian law!” (He was joking.)

The DayJet model factors in all relevant variables that could affect the traveler’s decision—something that is hard enough for a real person in real time. It contains up-to-date listings of all flights offered by all commercial airlines serving the region, and the prices for short-term bookings and seven- or 14-day advance-purchase fares. It has average highway-speed and congestion data for the routes people would drive between any two cities, and real-world travel time from different parts of a city to the nearest airport. It includes lodging and restaurant costs, if a driving trip means an overnight stay, and rental-car and gas rates.

Also, crucially, it tries to place some value on people’s time. Time value obviously varies: being three hours late for a wedding is different from being three hours late for a meeting on a Thursday afternoon. Because its target customers are business travelers earning from $75,000 to several hundred thousand dollars a year, income levels at which the time savings are worth the cost, the model uses salary to approximate the business value of time. (People making even more, it assumes, might use “normal” corporate jets.)

With this information and more plugged in, the ant farmers run the model—over and over and over. While we watched on a big-screen map projection from Herriott’s computer, the whole possible range of trips taken by one typical day’s 500,000 business travelers whizzed by in a few minutes: Miami-Atlanta, Key West–Jacksonville, Savannah-Biloxi. The point was not to predict exactly which trips travelers would take on any particular day but instead to see which patterns of travel emerged and where there might be a market for air taxis. In theory, DayJet could offer service from any airport to any other airport within the plane’s 650-mile nonstop range. But to minimize the number of empty “deadhead” legs its planes might have to fly back from remote locations and to maximize the number of paying flights each plane could make per day, the company planned to start in a concentrated area and then expand as it became sure there was more demand.

For every simulated trip, the computer was comparing all the alternatives—take the whole trip by car, take a train if there was one, drive to the nearest major airport and take Delta or JetBlue—and predicting whether a traveler would choose any of them over a possible flight with DayJet. A counter continuously tallied how many trips would be made using each option. For people taking one of the “trunk routes,” like Atlanta to Miami, the airlines were the obvious choice. But enough people heading from one small place to another created a market DayJet could tap.
(I had hopes for this company because I thought their model could stand the market test.)