Path Optimization for Sortation Robots Using Hungarian Algorithm

Mobile robots (MR) for sortation in warehouses are becoming increasingly popular as they can help to improve efficiency, accuracy, and flexibility in the sorting process. These robots are typically autonomous and can navigate around a warehouse using sensors and mapping technology. Product managers and Software writers working on fleet management system (FMS) use all sort of methods for optimizing the path of a robot to improve the productivity per robot and system. However, what caught my eye was possible use of Hungarian method for calculating the shortest path for a robot to reach nearest induction point after sortation is completed.

Hungarian method must be familiar to all Mechanical, production and Industrial engineers and most of the Business graduates. It is one of easiest assignment algorithm to understand and softest target of students to score marks in exams :D.

What is an Hungarian method and how does it work?

The Hungarian method is an algorithm for solving the assignment problem, which is a special case of a linear program. The goal of the assignment problem is to find the optimal one-to-one assignment of a set of tasks to a set of workers (Robots in our case), such that the total cost (Travel distance in our case) of the assignments is minimized. The algorithm starts by creating a matrix of distances, where each cell represents the distance of assigning a specific induction point to a specific robot. It then uses a series of steps, such as finding the smallest element in each row and subtracting it from all elements in that row, and finding the smallest element in each column and subtracting it from all elements in that column, to create a "reduced 'distance' matrix". The algorithm then uses a combination of row and column reductions and augmentations to find the optimal induction point to robots.

Application of Hungarian method on sortation robots

This method requires a square matrix, which means the number of robots should be equal to number of induction points. Now this is not possible in almost every case. So, below are few common deviations that we can expect from standard requirement of Hungarian matrix.

Scenarios:

1. Robots less than induction point: A case where number of robots are less than induction points

2. Robots less than induction point:

• Almost every time there will be greater number of robots than the induction points

• There may not be one to one assignment of robots to induction points, but multiple robots are usually planned to queue a induction point to keep induction operator busy

Both of the above scenarios are typical case of unbalanced assignment problem, which need to be balanced with few adjustments in the given constraints.

Making an unbalanced problem a balanced one:

Robots less than induction point: Add dummy robots to make the matrix square and conduct the algorithm

Robots more than induction point: In a typical layout there is provision for at least three robots standing in queue. Which means three robots could be assigned to one induction point. So, all we have to do is repeat every induction point to number of robots being planned in a queue to make it as square matrix.

Hungarian method and a little modification made was to find the shortest path from sortation point to induction point. However while going back to the sortation point from induction station FMS won't have to worry about assigning the sort point as it is assigned randomly when an item is mapped to a robot for sortation. The only task of FMS would be finding the shortest non congested path for robots to reach their assigned sort points.

There could be many solutions and algorithm for assignment problems but to have an systematic start, Hungarian method could be one of the easiest model to understand.

Though it would be interesting to see how difficult it would be to implement this algorithm in simulation software and FMS because,

• System would have to continuously create the matrices for the robots asking for assignment to induction stations

• Size of matrices will always change based on how many number of robots are asking for assignment and how many induction stations are active