speed up telephone calls. Using a simulation of British Telecom’s network, they dispatched antlike agents into the system to leave pheromone-like signals at routing stations, which function as intersections for traveling messages. If a station accumulated too much digital pheromone, it meant that traffic there was too congested, and messages were routed around it. Since the pheromone evaporated over time, the system was also able to adapt to changing traffic patterns as soon as congested stations opened up again.
What did an ant-based algorithm offer that other techniques didn’t? The answer goes back to the foragers from Colony 550. If conditions in the desert changed while the ants were out searching for seeds—if something unpredictable disrupted the normal flow of events, such as a hungry lizard slurping down ants—then the colony as a whole reacted quickly: foragers raced back to the nest empty-handed; other ants didn’t go out. They didn’t wait for news about the disruption to travel up a chain of command to a manager, who evaluated the situation before issuing orders that traveled back down the chain to workers, as might happen in a human organization. The colony’s decision making was decentralized, distributed among hundreds of foragers, who responded instantly to local information. In the same way, virtual ants racing through the telephone network responded instantly to congested traffic. In both cases, an ant-based algorithm offered a flexible response to an unpredictable environment, and it did so using the principles of self-organization.
An obvious application of this approach would be to develop an algorithm—or set of algorithms—that would enable a business enterprise to respond to changes in its environment as quickly and effectively as ant colonies do. That’s exactly what a company in Texas set out to accomplish.
The Yellow Brick Road
Charles Harper looked out his office window at the flat landscape south of Houston. As director of national supply and pipeline operations at American Air Liquide, a subsidiary of a $12 billion industrial group based in Paris, he supervised a team monitoring a hundred or so plants producing medical and industrial gases. This was a daunting task on the best of days. The company’s operations were so complex that no two situations ever looked the same.
Air Liquide sold different types of gas to a wide range of customers. Hospitals bought oxygen, as did paper mills and plastics manufacturers. Ice cream makers used liquid nitrogen to freeze their goods. So did berry packers and crawfish shippers. Soft drink companies purchased carbon dioxide to add fizz to their beverages. Oil refineries took several gases, as did steel mills. All told, Air Liquide delivered gas products to more than fifteen thousand customers across the United States, using a fleet of seven hundred trucks, three hundred rail cars, and a 2,200-mile network of pipelines.
All these moving parts, however, were just the beginning of the business problem. The real complexity came from the variables the company had to cope with. The cost of energy, for example, fluctuated constantly. In Texas, where the power industry was deregulated in 2002, the price of electricity changed every fifteen minutes. “For an industrial customer, a megawatt might cost $18 at three a.m., then shoot up to $103 the following afternoon,” Harper says. Since energy was one of Air Liquide’s biggest expenses, accounting for up to 70 percent of the cost of production, these ups and downs had a huge impact on the bottom line.
Other factors affected production costs. Each of the plants producing gaseous or liquid gases had a different efficiency level, different cost profile, and different capacity. Many, for example, could produce either liquid oxygen or liquid nitrogen in varying combinations. For customers who needed delivery by truck, a plant could pump liquid gases into cryogenic trailers. For those on pipelines, it could vaporize the gases and send them that way.
Customer demand was yet another variable. Although some customers, usually the largest ones, took the same amount of gas every week, many others were unpredictable. A small company might order gas only when it got a big contract, then order none for months. About 20 to 30 percent of Air Liquide’s customers made a habit of calling in special requests. “If a big medical center calls us up and says, hey, we need a delivery of oxygen right away, we’re going to make sure they don’t run out,” Harper says. But such requests put a strain on scheduling.
Combine all these factors—fluctuating energy prices, changing production costs, varying delivery modes, and uncertain customer demand—and you’ve got a difficult situation to manage. Sooner or later, something unpredictable, like a mechanical problem at a plant, is going to put you in a bind, and you won’t have enough gas to serve customers in that region. “We were always having incidents like that,” says Clarke Hayes, Air Liquide’s real-time operations manager. “It finally got to the point where we said, you know what, we need a tool that helps us organize better.”
The company already had special-purpose programs to optimize particular aspects of their operations, but it didn’t have a way to pull it all together. In late 1999, a team from Bios Group, a consulting firm from Santa Fe, New Mexico, founded by complexity scientists, came to Air Liquide with an unorthodox proposal. Why not build a computer model based on the self-organizing principles of an ant colony? This model, they suggested, would take into account all the variables that were making planning so difficult as a way to help managers find solutions to day-to-day challenges. As a start, they suggested tackling the company’s truck-routing problem—the question of which truck should pick up gas from which plant and deliver it to which customer to be most profitable for the company. If ants had evolved a clever way to move things from one place to another, they said, why not apply that knowledge to Air Liquide’s trucks?
“The scientists were wonderful to talk to,” Harper says. “But the issue for us was, can they understand the industrial gas business? So we took a small piece of our geography and asked them to digitize that. To show us they understood the complexity of the trucks, the drivers, the depot costs, the miles per gallon, all the anomalies. What if a customer’s tank was on a hill? If you pull up in the wrong direction, or if your truck’s not full, the liquid won’t get in the pump and you can’t fill the tank. So you have to make that customer the first stop on your route. There are hundreds of those kinds of things, and they drive you crazy. But they all needed to be in the model.”
Alberto Donati was one of the scientists at Bios Group assigned to work on the Air Liquide pilot project. Because he had previous experience with ant-based algorithms, he was asked to work on the distribution side of the decision-support system. The approach he took was inspired by the one Marco Dorigo and Eric Bonabeau, another computer scientist, had developed for the traveling salesman problem and similar difficult problems.
“The ant algorithm was a very good choice in this case, because it creates a step-by-step procedure to find the best routing solution,” Donati says. At every step, even the most complex situation could be taken into account. Each ant had a sort of “to do” list that it kept working on until the list was complete, he explained. Let’s say the list was of Air Liquide customers that need deliveries today. “Imagine the ant starts at the depot,” Donati says. “First she has to choose a truck. So she looks at the available list of trucks, and then she picks a driver. So what does she do next? Maybe she goes to the facility to fill up the truck. Now she considers all the possible customers that need that kind of gas. She calculates the time it would take to reach each customer’s site. Perhaps there are some customers with restricted time windows for deliveries, or others with high priority for deliveries. Then the ant looks at each customer using what we call a greedy function.” The term greedy, in this case, refers to a decision-making rule that delivers the best results in a short time frame. “Choose the nearest customer,” for example, is a typical greedy function. “She also takes into account the pheromone trail,” Donati says. “Other ants may have chosen the same path and left some pheromone. So she multiplies the greedy factors by the pheromone factor to determine which customer to choose next.” (This decision is modified by a small degree of randomness to occasionally allow choices that would be hard
