Software's take on the light bulb joke

(PhysOrg.com) -- It takes five men to change a light bulb*, even more to pack a shipping crate. After all, filling space is very hard. But a European project has developed tools to optimise packing problems in just a few seconds -- no joking...

Packing problems tend to be extremely complex. Even the apparently simple task of filling an empty crate with boxes of light 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 realise 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 optimisation 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.

Academic expertise, real-world experience

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.

Net-WMS 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 optimisation.

“We decided to focus our attention in the area of spatial optimisation 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.”

Efficient algorithms

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,” claims 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 visualisation - are all interconnected so that it is possible to create a seamless software solution to model, simulate and optimise 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 optimisation has a massive knock-on 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.”

Pick your tool

Although optimisation software does already exist, KLS Optim has a compelling proposition. Licences for competitive products cost around €20,000, but Aggoun says that his software will cost between €3000 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.”

Other industrial partners in the project, in particular Peugeot Citroen Automobiles (PSA) and Fiat's research centre, 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 optimise production schedules.

* One to force it with a hammer, four to go out and buy another bulb!