# Record-breaking algorithm really packs them in

By Colin Barras Geeky holidaymakers wanting to take more on a trip, as well as delivery firms trying to maximise loads and storage, could benefit from a new algorithm that packs collections of differently sized 2D shapes into the smallest available space with unprecedented efficiency. This may seem like a more academic version of the video game Tetris, but the techniques developed can be applied to 3D problems in the real world. Increasing packing efficiency this way would lower the cost and also the environmental impact of shipping. Fitting a set of objects into the smallest amount of space is such a complex scientific problem that researchers have yet to calculate the single best solution if more than around 20 objects are involved. To get closer to that optimum fit, researchers pit their algorithms against each other in competitions to solve particular packing problems, such as fitting a collection of differently sized discs inside the smallest circle possible without overlaps. Johannes Schneider‘s team at the University of Mainz has just smashed all previous records in that disc-packing problem. Their new algorithm matched all the records for packing up to 23 different sized discs in the smallest possible circle and broke all those for packing between 26 and 50 discs – challenges set in a previous competition contested by 155 groups from 32 countries. The secret to the team’s success is their algorithm’s ability to take backward, as well as forward steps. Packing algorithms usually shuffle the discs again and again, aiming to reduce the space they occupy each time. But that’s rather like asking a mountaineer to find the highest point on Earth by always walking uphill, says Schneider. “Using this approach the mountaineer would climb to the top of a nearby hill, but there he would be stuck.” So Schneider and colleagues’ algorithm allows for occasional reverse steps that can unlock better solutions – disc arrangements that take up more space than the previous one, but lead to even more compact packs. The algorithm uses backward moves often at the start of a packing process but they become less frequent as it closes in on the final solution, he says. Although the new algorithm hasn’t solved the packing problem for good, it provides the best solutions to date. “Making the use of backtracking moves more explicit is certainly a merit, and one of the main reasons for the successful approach,” says Marco Locatelli at the University of Turin, a member of the team that previously held most of those records. However, he points out that packing algorithms improve fast and records rarely stand for long. Locatelli would like to see how the new algorithm performs in other packing problem scenarios, including in three dimensions, something that Schneider’s team plans to explore. “We now have an algorithm which is able to solve packing problems with [3D] goods of different sizes in general,” he says, making it applicable to real-world problems. “Shipping companies face the problem of packing trucks or ships in a way that as many goods as possible can be placed inside.” Schneider also plans to take the order in which objects are packed into account. “For example, the driver of a parcel delivery service must not unload half of his truck in order to get to the parcel which he should deliver to the next customer,” he says. Journal reference: Physical Review E (DOI: 10.1103/PhysRevE.79.021102) More on these topics: