The travelling salesman problem in order picking

Definition of the Travelling Salesman Problem

The travelling salesman problem (TSP) was mathematically formulated in the 19^th century independently by William Hamilton and Thomas Kirkman. Originally, the challenge was  to find the Hamiltonian cycle in a graph, that is, a path that visits each vertex of the graph exactly once. Finding the Hamiltonian cycle with smallest weight sum of its edges is known today as the solution to the travelling salesman problem.

Moving away from mathematical theory, the problem can be presented as that of a salesman who has to visit several cities by taking the shortest route and passing through each city only once.

The definition of the problem itself, as you can see, is simple, but the calculations behind it are both time consuming and complex.

Application of the Travelling Salesman Problem in Logistics

In 2020, the R&D team at Arvato Supply Chain Solutions looked into ways of applying the travelling salesman problem in logistics. First, we focused on optimizing the order picking process. In order to determine the picking route, we needed to implement TSP solutions into the product batch building algorithm, as well as the algorithm for determining the shortest route between picking locations.

Figure 1. The process of optimizing picking locations in the order picking process at Arvato Supply Chain Solutions

The batch-building algorithm is responsible for grouping orders in such a way that they can be picked together by a single employee and that the collection time corresponds to the KPIs agreed on with the customer. The TSP algorithm, on the other hand, is used for determining the optimum picking route for such a batch.

Whilst the team had no difficulty in applying these algorithms, performing such a large number of computations within an acceptable timeframe presented a major challenge. Optimization of the solution took several months. In July 2020, we went live with our first version of the TSP solution.

As a result, we achieved a 13 percent reduction in the distance travelled by the picker, while increasing process efficiency by 8 percent. There is still potential in continuing our work on TSP in the future.

The majority of solutions for improving TSP in logistics focus on distance as the basic metric and it is largely distance that is optimized. Our R&D team goes one step further and is currently working on optimizing TSP based on “picking cost” (the effort that goes into a single unit pick).

Taking into account factors such as the width of aisles in the warehouse, the weight of the cart or even the preferences of workers is quite a challenge both in terms of collecting such data and putting it to use in an algorithm.

We manage warehouses with wider aisles, offering easier navigation with a cart, as well as those with narrower aisles, where carts need to be smaller and moving around is less convenient.

Questions arise:

• is it reasonable to map a slightly longer route, but along a wider aisle (in this case one where the picker can move faster)
• or, perhaps, better stick to a shorter route, but with a narrower aisle?

This is where we reach a decision point in the algorithm. In mathematical terms, the answer is simple – choose the one that takes less time.  Process-wise, however, we need to factor in the picker’s preferences, natural fatigue and predispositions. And these differ from individual to individual. An additional challenge is to optimize calculations in such a way that they do not slow down communication between our systems. Ultimately, such an approach will allow us to optimize the picking algorithm for logistic processes while taking into account individual differences in specific warehouses.

The opportunities for TSP optimization do not end here. Certainly, more can be done in this area, for example, you can take into account the changes in factors over time that affect the efficiency of the process, such as the changing weight of the cart as pickers add products, which in turn affects worker fatigue.

The question we need to ask, is how far we should go in TSP optimization? This pursuit of perfection resembles a bit the constant struggle to reduce the weight of equipment in some sports (cycling, motorcycle racing or Formula 1 racing).

What we need to do is strike a balance and decide how much we are willing to pay for an extra percent of optimization.