LITMIR.BIZ

Скачать книгу

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 to predict.) “When she gets to the customer, she unloads the needed amount of the truck’s liquid, keeping track of how much time it takes to do that and how much is left in the truck. Then she goes back to the list of customers she hasn’t visited yet.” And so on, and so on, until all the customers have been visited and assigned to a route.

      At this point, the ant computes the quality of the solution and lays down a pheromone trail according to its quality. This process is repeated, ant after ant, thousands of times. “The nice part is that, when you’re near the finish, you will see that the ants have left a clear distribution of pheromones around your system,” Donati says. Each new solution is compared to the best previous one. If it’s better, it becomes the best one. It’s all a matter of balance between exploration and exploitation, he says.

      The pilot project was a big hit at Air Liquide, proving to managers that an ant-based model was flexible enough to handle the complexities of their routing problem. But what Air Liquide really wanted was to optimize production, since the cost of producing gas was ten times that of delivering it. So they enlisted Bios Group, which by then had merged with a company called NuTech Solutions, to develop a tool to optimize production. That tool, completed in 2004, is the one Air Liquide uses to guide its business today.

      Technicians in the control center run this optimizer every night. They begin at eight p.m. by entering new data about plant schedules, truck availabilities, and customer needs into the model. A telemetry-based system called SCADA (Supervisory Control and Data Acquisition) feeds real-time information about the efficiency of each plant, gas levels in storage tanks, and the cost of power, among other factors. A neural network forecast engine provides estimates of which customers must get deliveries right away, based on telemetry readings and previous customer-usage patterns. Weather forecasts by the hour are entered, as are estimated power costs for the next week. Finally, any miscellaneous information is added that might affect schedules, such as which plants need maintenance in the near future.

      The optimizer is then asked to consider every permutation—millions of possible decisions and outcomes—to come up with a plan for the next seven days. To do so, it combines the ant-based algorithm with other problem-solving techniques, weighing which plants should produce how much of which gas. To speed up run times, technicians divide the country into three regions: west of the Rockies, Gulf Coast, and the eastern states. Then they run the model three times for each region. By the time the day crew arrives at work at six a.m., the optimizer has solutions for each region.

      People still make all the decisions. But now, at least, they know where they need to

Скачать книгу