Software's take on the light bulb joke

Mar 12, 2010
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 , 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!

Explore further: Fully automated: Thousands of blood samples every hour

More information: Net-WMS project - net-wms.ercim.org/

add to favorites email to friend print save as pdf

Related Stories

Getting in gear for next generation cars

Apr 13, 2005

23 partners from across the European car industry worked together to develop a new software interface that will make the next generation of cars quicker to design and cheaper to bring to market while maintaining high quality ...

Software solution identifies skills gaps in the workplace

Aug 03, 2009

(PhysOrg.com) -- Training employees to do their jobs effectively is something many companies would like to - and need to - improve. Now European researchers are developing software tools to ensure skills gaps are identified ...

Getting a grip on school timetables

Jan 06, 2010

A new approach to solving the problem of school timetabling, known as a GRASP, has been developing by researchers in Brazil. They report details in a forthcoming issue of the International Journal of Operational Research.

Tough times, complex systems -- a modernisation story

May 04, 2009

(PhysOrg.com) -- Tough economic times call for tough measures to remain competitive. That goes for software modernisation as well. A European project has just released a prototype of a software engineering platform that could ...

No catastrophes please, it's software modelling

Jan 29, 2010

(PhysOrg.com) -- European researchers have created a development platform that will enable applications to tackle the enormous and increasing complexity of modern computer science. It promises better quality at a lower price.

Recommended for you

First drone in Nevada test program crashes in demo

8 hours ago

A drone testing program in Nevada is off to a bumpy start after the first unmanned aircraft authorized to fly without Federal Aviation Administration supervision crashed during a ceremony in Boulder City.

Fully automated: Thousands of blood samples every hour

16 hours ago

Siemens is supplying automation technology for the longest and one of the most cutting-edge sample processing lines in any clinical laboratory. The line, or automation track, 200 meters long, in Marlborough, ...

Explainer: What is 4-D printing?

16 hours ago

Additive manufacturing – or 3D printing – is 30 years old this year. Today, it's found not just in industry but in households, as the price of 3D printers has fallen below US$1,000. Knowing you can p ...

First series production vehicle with software control

17 hours ago

Siemens has unveiled the first electric series production vehicle with the central electronics and software architecture RACE. This technology, developed in the research project of the same name, replaces ...

Amputee puts limb system through its paces

19 hours ago

"Amputee Makes History with APL's Modular Prosthetic Limb" is the headline from Johns Hopkins Applied Physics Laboratory, where a team working on prosthetics observed a milestone when a double amputee showed ...

User comments : 1

Adjust slider to filter visible comments by rank

Display comments: newest first

Royale
1 / 5 (1) Mar 12, 2010
Adding that * in the beginning made me think they'd actually explain that places like GE need to form, handle, produce, ship, stock the bulb, etc. and then explain why 5 men. but then they give us probably the lamest joke ever. I've heard the joke SO many ways, this one has to be THE WORST version. ever.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.