Geometric Optimisation for Industrial Challenges
with Gurobi as the Model Solver
As a consultant to FlandersMake, I get to help the Flemish Industry with innovation. In particular, the FM CodesignS department offers mathematical optimisation experience to calculate optimal solutions to industry problems. We present two examples from different projects for different sectors, where we find optimal or near-optimal solutions to geometric puzzles.
Optimization of a Production Process
The manufacturing industry needs to plan (1) which resources (operators, robots and other tools) need to be deployed in the different production steps that are part of the entire production process towards one or more end products. (2) These resources must also be able to carry out this assembly process with sufficient freedom of movement in a space that has to be constrained in size. In order to plan this process ‘optimally’, FlandersMake can leverage its knowledge of production processes (problem domain) as well as mathematical optimization techniques (solution domain).
Specifically, in the FlexAs project, a mathematical model was set up for the task-to-resource allocation, which finds various good allocations in a few minutes and visualizes them in terms of cost and production turnaround time. For each of these solutions, an efficient solution for the spatial positioning of these resources was also found via a second mathematical model. Both (Mixed Integer Programming) models were implemented in Gurobi. This commercial solver solved the first problems in an average of 3 minutes while the open source alternatives CBC and SCIP took 3 to 12 hours to achieve the same solution.
As for solutions to the second problem, two examples of a positioning of resources (blue circles: 2 operators, 2 robots, 2 tables, 3 recipients) and also of the components that are part of the final product (red circles: 1 housing, 1 cover, 2*3 bolts) are shown below. The yellow circles represent the reach of the entity. The reach of a table is the table surface itself. The reach of a human operator corresponds to a circle with radius equal to his arm’s length. The first one indicates a starting position where all helper-resources like recipients as well as all components are present. Housing and cover are each on their own table and the bolts are in trays per 3.
The relationship of what ‘parent-entity’ is holding what ‘child-entity’ is represented by a tree data structure, and this for each time step, but without unnecessary duplication of nodes nor edges. This temporal graph evolves from event to the next event. An event occurs whenever an entity is picked up by another one or mounted on another one.
A second positioning, some events later, is presented below. It occurs 10 seconds later, where one robot is holding the cover, where next, the operator has to insert the bolts and another robot transfers the housing to the other operator who will slide it under the cover later.
For each event we will output a positioning, also taking care that all entities can move with a speed below their maximum speed (which is 0m/s for tables), from one positioning to the next within the room (cell) and unhindered by other entities. The result is a complete plan of steps that directly leads to a production plan.
Covid-19 Proof Placement of Tables and Chairs
For a second project, the question is whether for the restaurant, event, healthcare and educational sector, automatically, for example via a website, a corona-proof table and seat setting can be generated according to the current corona rules. In Belgium, for example, people at different tables, have to be kept at least 1.5 meters apart. With FM CodesignS, we modeled this problem. Our current benchmarks indicate that automatic table-positioning is indeed possible for typical restaurant settings, in a calculation time of a few seconds, which is workable in a website context. This can help the restaurant and event sector to place people safely and thus avoid fines for the organizer.
An example of Covid-safe table placement in a restaurant is shown below. This is a table and chair placement for a restaurant with a fixed buffet in the center, an open kitchen on the lower left, and 5 table types: 3 rectangular tables (for 4, 6 and 9 people, assuming that bubbles up to 9 people are allowed) and 2 round tables (for 5 and 6 people). The restaurant owner has more tables than can be placed because the new Covid distance rules make that the restaurant capacity decreases. The round table for 5 people was not even used in this example. The objective is to still be able to seat as many people as possible. Here, the tool calculates that we can install 1 table for 9 people, 4 tables for 6 people and 3 tables for 4 people. Resulting in a total capacity of 45 people. Our tool also shows that there is no solution with more seats. Thus, the restaurant owner is assured of maximum utilisation of the available space according to the rules. The social rules such as the maximum bubble size and the minimum spacing between people from different bubbles, are captured as input parameters for our model. This means that, even if the rules change, our tool can still be used.
Calculating this optimal table setting took less than 2 seconds. It took into account 45 chairs, different table types and different zones where no tables can be placed. The social distancing, where we keep people at different tables at least one and a half meters apart, is ensured by forbidding overlap between their respective yellow circles.
A more complex setting with more door zones, buffets, pillars and heating spaces along the walls is given in the picture below.
Conclusion
Mathematical optimisation can help the industry with problems by mathematically formulating goals and constraints to then find a solution that meets all these ‘soft’ and ‘hard’ requirements and is therefore (1) valid, and (2) optimizes a KPI or a combination of several KPIs at the same time. Gurobi as a solver tool helps us to quickly find these good or even optimal solutions.
This story was also published by Flanders Make on their blog.
