Geometric optimisation as a solution to industrial challenges
As a strategic research centre for the manufacturing industry, Flanders Make supports the Flemish industry with innovative methods, research and techniques. Our research is conducted to achieve faster optimal designs of drive trains, components, flexible assembly cells and production plants. Knowledge in mathematical modelling and optimisation support this research. How these techniques are applied is illustrated in this article with 2 examples: optimisation of an assembly cell and positioning optimisation of tables and seats in the restaurant sector.
1. Optimisation of a manufacturing process and assembly cell
When planning a production process and design of an assembly cell, not only resources (operators, robots and other tools) should be considered, but also physical space and freedom of movement during the assembly process. To arrive at the optimal solution, we combine knowledge about production processes (problem domain) with that of mathematical optimisation techniques (solution domain).
In a first step, tasks have to be assigned to a certain resource (e.g. a robot picks up a part). For this allocation, a mathematical model was set up that finds several good allocations in a few minutes and visualizes them in terms of cost and production lead time. Afterwards, via a second mathematical model, in the second step, the selected resources were positioned in the assembly cell. Both (Mixed Integer Programming) models were implemented in Gurobi. This software tool (solver) solved the initial problems in an average of 3 minutes. Other alternatives like CBC and SCIP required 3 to 12 hours of time to achieve the same solution.
Below are two examples of a positioning of the selected resources (blue circles: 2 operators, 2 robots, 2 tables, 3 containers) and of the components that are part of the final product (red circles: 1 housing, 1 cover, 2*3 bolts).
The first one indicates a starting position:
- The housing and cover are each on their own table
- The bolts are in 3 containers (trays)
The second positioning shows the situation 10 seconds later:
- Robot 1 holds the cover
- Operator 1 applies the bolts
- Robot 2 offers operator 2 the other housing
- Operator 2 slides the housing under the cover
2. Covid-safe placement of tables and chairs in the restaurant/event sector
In a second project, we implemented an optimisation model and algorithms for a web-based tool to support the restaurant, event, healthcare and education sectors to obtain covid-safe table and/or seat placement. Of course, we take social distancing into account. A mathematical optimisation model is the basis of this tool. An important aspect to get the tool usable is the calculation time. It must be low enough so that the user does not have to wait hours for a particular table configuration. Current benchmarks indicate that an automatic table setting is possible in a calculation time of a few seconds. This allows us to use the tool web-based or via an app.
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 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 restaurant with more free zones for entrances and exits, buffets, columns and heaters along the walls is given in the figure below.
An optimal solution, in this case a solution with 109 seats, was found here after a computation time of 20 seconds. The first solution was found after 2 seconds and already reached 80% of this optimal number.
The table and seat positioning project is funded by VLAIO through the grant COVID-COOCK.
Flanders Make can help the Flemish industry by mathematically formulating problems to find a solution that meets all hard rules or requirements and thus (1) is valid, and (2) possibly optimises at the same time a KPI or a combination of several KPIs. Mathematical optimisation and the use of Gurobi as a solver tool helps us to find good solutions quickly.
Thanks to the project colleagues: Sofie Burggraeve, Emma Claeys, Bieke Decraemer, Ine Melckenbeeck, Joren Sips, Barry Swevels and Suzanne Van Poppel.