In abstract terms, intralogistics is formed by the flow of goods within a plant. These flows of goods can be broken down into individual transport tasks. One example is the transport task for picking components onto a pallet from the pallet warehouse, which is then transported to a machine for further processing. Depending on the size of the plant, such processes occur hundreds or thousands of times a day, or even more.
Complexity of intralogistic processes
With an increasing number of transport tasks and additional conditions, such as due dates or the ability to combine transport tasks, the optimization of processes and paths in between tasks gains more and more importance. The sequence determination in which the transport tasks should be processed can be done in a simple manner, for example, when the transports are processed on sight. If, on the other hand, additional information about the other transport tasks is included in the execution sequence of the transport tasks, it quickly becomes a complex matter to determine the ideal assignment sequence of the transport tasks as the number of transport tasks increases. Additionally, the transports in the system can be processed by different vehicles, which in turn also increases complexity.
Mathematical Background – The Vehicle Routing Problem
The problem is known as the Vehicle Routing Problem (VRP) in mathematics. The VRP is an extension of the multiple Traveling Sales Man problem (mTSP), which observes transport capacity restrictions alongside multiple instances that can perform orders in parallel.
The normal VRP assumes a central depot as the start and end point of each tour, but this cannot be assumed in intralogistics. It is necessary to take into account decentralized points for pickup and delivery. Additionally, there are limitations on the timeline due to due dates. The problem variant typical for intralogistics as an extension to the normal VRP is called Vehicle Routing Problem with Pickup and Delivery and with Time Windows (VRPPDTW).
Problem solving and approximation
The VRP is a NP-hard problem. This means that if the problem should be solved precisely, the runtime will increase faster than an exponential function as the size of the input increases. Wenn beispielsweise das exakte Lösen des Problems bei 10 Transportaufträgen If, for example, solving the problem precisely takes about 5 seconds for 10 transport tasks, solving 100 tasks precisely would take 3.86*10 31 years. That is why the precise solution is not calculated for such problems, but the best solution that can be found within a fixed period of time is selected.
Calculation methodology
This process can be divided into two steps, namely the search for an initial solution and the optimization of this solution. In order to be able to evaluate the different solutions, a function must be provided that makes the different solutions comparable by quality. The so-called evaluation function compares and evaluates variables such as the total covered distance and due date violations. One example would be to evaluate the extent to which a due date violation is acceptable if it leads to a sufficiently large reduction in the total covered distance.
The first step is to identify a valid solution that meets the previously defined criteria. This first solution is then used to attempt to find further improvements. Algorithms that are used for this purpose are called metaheuristics and some examples are the TABU-Search or the HillClimb algorithm. In order to find improvements, the existing solution is slightly modified, for example by switching actions or by attempting to insert actions in different places. The modification that yields the most significant improvements is adopted. Depending on the algorithm selected, more or less possibilities are experimented with and the best possible solution is eventually selected. Metaheuristics like TABU-Search can with foresight also maneuver out of local extremes values to achieve a global minimum or maximum.
Summary
Although this methodology cannot, overall, guarantee that the most ideal solution to the problem will always be found, it is much more important in practical application that this solution can be found within set amount of time. The premise in this respect is always: The faster the algorithm works, the more optimization potential is leveraged.
Author – Jonathan Hohm
Data Analyst & AI Developer
As part of his work at Flexus, he optimizes the intralogistics of our customers with the appropriate optimization algorithms. This is mainly applied in the optimization of forklifts, route train logics and the efficient control of AGVs.