Communications of the ACM
Software's Take on the Light Bulb Joke
Credit: International Transaction Systems
How many men does it take to change a light bulb? Putting the punchline aside a moment, consider that it takes even more to pack a shipping crate. Now a European project has developed tools to optimize the packing of boxes of light bulbs in just a few seconds—no joking.
Packing problems can be extremely complex. Even the apparently simple task of filling an empty crate with boxes of bulbs is harder than it looks. Lie them all down or stand them all up? Add in different sizes or odd shapes and you get a major headache. And just when you thought you were doing well, you realize that certain bulbs must be at the top of the crate and the crate has a maximum weight!
Computers are the powerhouses for solving this kind of optimization problem. They use advanced mathematics to churn through the numbers, check every solution against all the constraints and eventually—probably in less than a minute, actually—find the best fit.
Mixing Math and Expertise
An EU-funded project has done just this to develop tools that will be welcomed by thousands of companies across Europe who struggle to pack efficiently on a daily basis. In just a few seconds the tools can improve on what specialist packing teams might have taken a week to design.
The Net-WMS project has taken a healthy mix of pure mathematics, added in some real-world complexity, and managed to create functional tools with immediate commercial applications.
The Net-WMS consortium pooled the expertise of some of Europe's best research departments in the field of optimization.
"We decided to focus our attention in the area of spatial optimization because there was an obvious commercial opportunity," explains François Fages, the project's scientific coordinator. "Many firms cannot afford expensive software, but even small improvements in the way they pack shipping pallets or use warehouse space, for example, can make an enormous difference to their profitability and competitiveness."
Pushing Boundaries
The basic research has produced algorithms that really push the boundaries in this field. The algorithms use what is called a 'constraint programming approach.' Simply, this is a two-step approach. First, you apply all the various constraints (in various combinations) as a way to shrink the 'search space'—i.e. all the possible solutions to the problem that you need to look at more closely—to try and find the optimal answer. This 'pruning' of the search space remains active in the next stage—the actual search for the optimal solution—and makes it much faster and more efficient.
Researchers also developed a novel way to eliminate 'forbidden regions'—approaches to the problem that will inevitably lead to a dead-end or an impossible solution.
"The algorithms developed in the project are quite unique," says Fages. "We've really broken ground with this project. Our scientific results have been published in eight peer-reviewed scientific journals and presented at several international conferences."
The project also developed an entire language to express the constraints of a problem, including business constraints such as maximum weights or stability constraints for a pallet.
The different modules of the Net-WMS system—the spatial algorithms, rule program and a virtual reality module for better visualization—are all interconnected so that it is possible to create a seamless software solution to model, simulate and optimize the packing process.
The Perfect Package
One of the Net-WMS commercial partners, KLS Optim, has been working with the Net-WMS tools and building them into a commercial product. The French company is a start-up, established to exploit the output from the project. KLS has tested its software with a number of clients and produced some remarkable results. Abder Aggoun, technical manager of Net-WMS and CEO of KLS Optim, reports that his company's software can improve packing solutions by between 5 and 15 percent.
For one client this level of improvement means that its warehouse uses two fewer pallets each day. Over the year this adds up to a considerable cost saving.
Aggoun also describes how rapid optimization has a massive secondary effect across an entire logistics operation. "In most warehouses today you don't know until you've finished packing exactly how many pallets you are going to ship. That means you can't confirm with the transport company the size of vehicle they need to send until the very last moment."
"Using the KLS Optim software, you know exactly which products are going to be packed and in which pallets. Within a minute of receiving an order you can already be contacting the logistics provider to book space for a specific number of pallets."
Although optimization software does already exist, KLS Optim has a compelling proposition. Licenses for competitive products cost around €20,000, but Aggoun says that his software will cost between €3,000 and €10,000. "As part of the Net-WMS project we identified different classes of problem. We developed a dedicated engine for each class. So you only need to buy the module for your class of problem—and that saves you money."
Further Refinements
Other industrial partners in the project, in particular Peugeot Citroen Automobiles (PSA) and Fiat's research center, are backing a follow-on FP7 project which they hope will look at more refinements to the work completed by Net-WMS. In particular, the tools need to be refined to improve on solutions for packing complex, irregular shapes (e.g. car silencers). User-interfaces also need to be improved, for example to explain why sometimes no solution can be found.
The algorithm will also be adapted for tools that will be used to plan how to cut shapes in a 2D sheet, stack shelves and even optimize production schedules.
Net-WMS received funding from the ICT strand of the EU's Sixth Framework Program for research.
For the record, it takes five men to change a light bulb: one to force it with a hammer, four to go buy another bulb.
From ICT Results
No entries found