Optimizing rubber reuse an innovative CHIP application from MICHELIN

MICHELIN is one of the world's largest producer of vehicle tyres, averaging 655000 per day ! Find out how a CHIP application allows this company to reuse scrap rubber lots and make huge savings !

Optimizing Rubber Reincorporation with CHIP

Introduction

Building tyres requires both natural and synthetic rubber of many different kinds. During the production process, various amounts of rubber may remain unused, and are ejected from the process mainstream. Because rubber is expensive, such lots are not thrown away and are tagged to indicate their nature, and stocked for possible subsequent reuse.

The scrap lots should be reintegrated according to their composition. These lots can of course be reincorporated into the process for making the same product mix, but compatibility between mixes allow various combinations of reincorporation. This strategy allows to reincorporate more and so is economically interesting. A huge table of authorized reincorporations has been created, based on very stringent tests that ensure that the resulting product do possess the desired characteristics. The plan to reincorporate various mixes must take into account the production plan and specific recycling conditions and optimizing gain.

The linear model

Such a problem can be considered to be a special case of the so-called “assignment problem”. Given a state of the scrap inventory, it must be decided where to reincorporate the lots in the production plan, taking into account the authorization table and respecting proportions. As stated, this problem can be modelled by a set of linear equations whose matrix is totally unimodular. This model with no additionnal constraints, can be solved with a linear programming package, and maximizes a given profit function.

The non linear model

However, additionnal constraints complicate the problem some what, rendering it non-linear. Rubber mixes are built by batch. When it is decided to reincorporate a scrap mix of type A into a rubber mix type B, not to reincorporate anything else is a condition. Moreover, even a given proportion is a condition, and must not vary for a given couple of types. Note also that the exact quantity added into B depends on the weight of B. So, for a given number of B blocks to be made, it must be decided how many (discrete) of them will receive A loads, and there are many such A's and B's. This situation destroys the unimodularity of the equation matrix. Finally, it must be taken into account that reincorporation to build the same mix is preferred.

This problem is clearly non-convex due to the discreteness, but however not too hard to solve. It has fortunately good properties. For example, doing nothing is a trivial, feasible solution, although not economical. Another good property for this problem is that any sub-use of a solution is also feasible. This means that, for any solution, reincorporating less than stated is a solution, although economically less interesting. One can easily imagine the shape of the search space: a sort of embossed potato (i.e. almost convex).

Technological Choice

The usual methods cannot solve this non-trivial combinatorial problem. For example, a regular mixed integer programming (MIP) package using branch and bound (B&B) cannot be used because hundreds of possibilities have to be taken into account, each of which generates a possible integer variable, possibly ranging from zero to a few dozens.

That is why CHIP V4 was choosen. CHIP has the advantage of having both rational and discrete domains. The idea was to use both of them. First step was a linear program relaxing integrality constraints. Rounding the solution gives a feasible solution, however not optimal. This “raw” solution has consumed a certain amount of recycled mixes and batches to be produced. The problem can then be restated for the rest of the inventory and of the remaining batches, using discrete variables. This second problem is small enough to be handled to optimality, using a CHIP B&B (minmax/1). The global solution is the concatenation of both solutions. Additionnal techniques are used to deal with the self reincorporation priority (A in A, B in B...).

Optimality

This heuristic method is of course not optimal in all cases. Complete solvers have been used to measure the remaining distance to optimality. With real life data, this distance happens to be zero most of the time. When not optimal, the given solution is however very good (less than 0.1% from optimum).

The alternatives were either a complete solver, or another better heuristic method (such as a genetic algorithm method, which was successfully tested). We chose the CHIP approach, because the CHIP code for handling the problem is only a few hundred lines and the response time is only a few minutes on a PC. The main reason for our choice is maintenance. An ad-hoc heuristic method or solver needs enormous efforts for maintenance. On the contrary, constraint logic programmes are very evolutive. For example, an additionnal feature recently requested by the user, was easily implemented within three days into CHIP, in an incremental fashion. In contrast, modifying a genetic algorithm would have needed a complete re-think of the chromosome coding structure.

Conclusion

This application improved the reuse of rubber by 8% in cost on previous manual methods. It is currently used everyday in many MICHELIN plants in Europe.

Author: Georges Henri Moll, Service Informatique MICHELIN.

MICHELIN is one of the largest producer of tyres in the world, with about 20% of the world market
125,000 people in 69 plants in 15 countries contribute to the development of the group Of the 3,500+ types of tyres, the daily production averages some 655,000 tires and 170,000 tubes With a consolided revenu of 66.8 billion french francs, the MICHELIN group is commercially present in more than 170 countries.