by Abderrahmane Aggoun, KLS OPTIM, Nicolas Beldiceanu, Gilles Chabert, École des Mines de Nantes and François Fages, Inria
Constraint programming methods can be used to solve hard geometric placement and packing problems such as those encountered in the operational logistics and in the conception of packing plans.
Modern warehouse management systems (WMS) provide advanced management features and monitoring of movements of goods within a warehouse. They do not, however, satisfy the growing demand for digital processing - especially the processing required to achieve an agile supply chain model capable of handling custom commands whilst minimising cost and environmental impacts.
This subject was investigated within the French ANR funded Net-WMS-2 project [L1] (2011-2015) - an industrial project involving Inria Saclay, Ecole des Mines de Nantes and SME KLS OPTIM. This project was a follow-up of the EU FP6 STREP project Net-WMS which showed how constraint programming methods can substantially improve industrial box placement and packing problems, and identified problems including: the difficulties of placement with rotations, and the industrial need to handle complex shapes and curved objects.
The daily use of the application Optim Pallet (3D), which was developed from the earlier project (Net-WMS), resulted in an up to 15% reduction in transportation costs for one company. As a consequence of these encouraging results, our industrial partners were keen to engage in research on new innovative optimisation applications to assist with handling complex shapes.
Figure 1: ClpZinc model and approximate resolution using our CMAES backend for the placement of 20 rosettes defined by union and intersections of circles.
Our previous studies demonstrated the feasibility and the realisation of prototypes for handling complex shapes: mixtures of boxes, polyhedrons, cylinders, and curved objects defined by Bézier curves, with the development of new methods of modelling and solving discrete-continuous hybrid constraints. Constraint programming methods can address NP-hard optimisation problems and provide solutions that are often effective and easy to maintain. They are based firstly on a model of the problem as a set of constraints to satisfy, and secondly on a resolution that uses predefined constraint solvers and a generally heuristic enumerative search procedure.
As part of this project, the constraint solver Choco over discrete domains has been interfaced with the continuous constraint solver Ibex in order to deal with complex shapes in placement problems. We have shown that it is possible to define the search strategies themselves as search constraints [2], and have extended the MiniZinc modelling language, which is now a standard in the field, with Horn clauses for this purpose, and have shown that the best placement strategies for squares could be modelled declaratively in ClpZinc without loss of efficiency. However, these methods have proved inadequate for curved shapes, and the use of stochastic optimisation methods was necessary, in this case using the CMAES solver. We have therefore shown that the constraints of placement and non-overlap of complex objects can be modelled by error functions (e.g. penetration depths [3]) to minimise, and developed an original and general interface MiniZinc-CMAES for solving such problems over the reals [1].
Using these declarative modelling techniques, combined in an original way to stochastic optimisation methods, we were able to solve in an approximate way both mixed curved-square shapes placement problems, such as boxes and cylinders for truck loading problems, and complex shapes defined by Bézier curves for packing problems. We have also shown, on the problem of Korf for placing squares in a rectangle, that the exact resolution square shapes placement problems was done without significant loss of performance compared to the state of the art, but with a fully declarative modelling/programming in ClpZinc of the search strategy [2] which is very new. The software developed by academic partners is distributed with sources as free software. The project results have been developed as demonstration prototypes by KLS OPTIM company.
Link:
[L1] http://lifeware.inria.fr/wiki/Net-WMS-2
References:
[1] T. Martinez, F. Fages, A. Aggoun: “A Stochastic Continuous Optimization Backend for MiniZinc with Applications to Geometrical Placement Problems”, in Proc. of CPAIOR’16, LNCS, 2016.
[2] T. Martinez, F. Fages, S. Soliman: “Search by Constraint Propagation”, in Proc. of PPDP’15, ACM, 2015.
[3] I. Salas and G. Chabert: “Packing Curved Objects”, in Proc. of IJCAI, 2015.
Please contact:
François Fages, Inria, France
Tel: +33 (0)682822937
Abder Aggoun, KLS OPTIM, France
Tél : + 33(0)608864555
