Improve Warehouse Productivity using a Pathfinding Algorithm with Python

Implement a Pathfinding Algorithm with Google AI Operation Research Python Libraries.

Samir Saci
Towards Data Science
9 min readAug 14, 2020
Improve Warehouse Productivity using Pathfinding Algorithm with Python
Design Pathfinding Algorithm using Google AI to Improve Warehouse Productivity — (Image by Author)

In the highly competitive field of logistics, reducing costs through process optimization is critical.

Among the variable costs of handling goods, order picking is a significant area for cost reduction, mainly influenced by the walking distance covered by operators.

As data scientists, can we leverage path finding algorithms with Python to maximize warehouse picking productivity?

In this series of articles, we started by exploring grouping orders in batches and then introduced spatial clusters of locations picked together.

How many additional productivity points can you earn by implementing pathfinding algorithms with Python?

This article will now focus on designing a pathfinding function with Python to find a sequence of locations to minimize walking distance for warehouse picking.

I. Beyond the Next Closest Location Strategy
1. Introduction of the model
2. Limiting Factor: Next Closest Location Strategy
II. Travelling Salesman Problem Application
1. Google OR-Tools Solutions
2. OR-Tool Solution vs. Closest Next Location
III. Understand TSP Solution
1. Highest Gap: 60 m for 21 Picking Locations
2. Limits of Next Closest Location (NCL) Algorithm
IV. Conclusion
1. Container Loading Optimization with Python
2. Impact on your ESG scoring

How to Improve the Picking Path?

Introduction of the model

In the first article, we built a model to test several strategies of Orders Wave Creations to reduce the walking distance.

We started with Warehouse Mapping.

A visual representation of a warehouse layout with labeled aisles A01 to A19, and shelves in each aisle. The starting point is at the bottom left, and an order picker’s route starts from the ‘Start’ point and follows along a defined picking path. Coordinates are marked as (x, y) for picking locations in the aisles, showing the calculation of walking distance from the start to a specific item location.
Warehouse Layout with 2D Coordinates — (Image by Author)

We can link an order line with each picking location's associated warehouse location coordinate (x, y).

We added functions to calculate distances.

Different routes between two storage locations in the warehouse — (Image by Author)

This function calculates the walking distance from two locations in the picking path of an operator.

We then added a clustering module.

Two scatter plots show the spatial distribution of picking locations, each point representing a picking location in a warehouse. The left plot shows a vertical rectangular cluster around the middle of the plot, indicating locations that are grouped based on proximity. The right plot shows two horizontal rectangular clusters of picking locations, demonstrating a different clustering arrangement. The points are color-coded by a variable, likely representing the concentration of picking order lines
Two examples of picking locations clustering — (Image by Author)

The objective is to group orders by waves using geographical (x, y) clusters to reduce the maximum distance between two locations in the same picking route.

The entire workflow looks like that 👇

A flowchart illustrating the warehouse order processing model. It starts with order lines containing order number, reference ID, and picking location. Next is the picking location with coordinates and clusters, followed by grouping orders into waves. The wave orders listing shows the sequence of orders. Finally, the picking route by wave includes the optimized order picking sequence and total walking distance.
Process Flow for Picking Route Calculation — (Image by Author)

At this stage, we have orders grouped by waves to be picked together.

We have a list of picking locations for each wave that the Warehouse Picker must cover.

A warehouse layout with aisles labeled A01 to A19 and rows numbered 1 to 12. There are several highlighted picking routes in the warehouse, represented by dashed lines in different colors: A blue dashed line from START (bottom left) through A10 and back. A red dashed line from A04 and back. A black dashed line that connects multiple aisles in A10 and A08. The diagram highlights different picking locations and how the paths traverse the warehouse.
(1) Potential Routes for a Wave covering 3 Picking Locations — (Image by Author)

Limiting Factor: Next Closest Location Strategy

The first article presented an initial solution using the Next Closest Location Strategy.

A warehouse layout showing aisles A01 to A19 with shelves arranged in each aisle. Two picking locations, (xi, yi) and (xj, yj), are marked in red and blue, respectively, along with a dashed box highlighting the operator’s picking path between these two locations. The walking route is illustrated with lines, showing how the operator moves between the two points to retrieve items from the shelves. The objective is to calculate the walking distance between the two picking locations (i and j).
(2) Next Storage Location Scenario — (Image by Author)

This simple strategy does not require a high level of computation effort.

From a location j (xj, yj), this function will take as input a list of potential following locations [(xj, yj), (xk, yk), (xh, yh)].

The result will be the closest location, using a custom distance walking function, as the best candidate for the next location to cover.

Is it the most optimal solution for Picking Route Creation ?

While useful, the Next Closest Location Strategy becomes a bottleneck in maximizing productivity.

The next section highlights its limitations and the need for more advanced solutions.

Travelling Salesman Problem Application

Although the results presented in the previous article were promising, we need to grab additional gains to be satisfied.

Logistic operations constantly faces cost pressures, making daily savings a continual challenge.

We will then explore algorithms for creating picking routes using the Single Picker Routing Problem (SPRP) on a two-dimensional warehouse.

SPRP is a specific application of the general Traveling Salesman Problem (TSP) answering the question:

What is the shortest route that visits each storage location and returns to the depot?

Google OR-Tools Solutions

OR-Tools is an open-source collection of tools for combinatorial optimization.

The objective is to find the best solution out of many possible solutions.

Here, we will adapt their Travelling Salesman Problem use case for our specific problem.

Input Data

  • List of picking locations coordinates:
    List_Coord = [(xi, yi), (x2, y2), …, (x_n, y_n)]
  • Walking Distance Function
    f: ((x_i, y_i), (x_j, y_j)) -> distance(i,j)

Code

In Google OR’s example, a dictionary is created with:

  • Distance Matrix: [distance(i,j) for i in [1, n] for j in [1, n]]
  • Number of Vehicles: 1 vehicle for our scenario
  • Location for depot = start and end: start = end = List_Coord[0]

How much additional walking distance can we save if we implement this for pathfinding?

OR-Tool Solution vs. Next Closest Location

Let us consider that we keep the same order batching strategy and picking location clustering.

What is the impact on total walking distance if we use Google-OR instead of our initial Next Closest Location Solution?

Assumptions

  • Order lines: 20,000 Lines
  • Distance Threshold: Maximum distance between two picking locations in each cluster (distance_threshold = 35 m)
  • Orders per Wave: orders_number in [1, 9]

For the clustering, we will apply three methods

  • Method 1: Clustering is not applied
  • Method 2: Clustering applied on single-line orders only
  • Method 3: Clustering on single-line orders and centroids of multi-line orders

Have a look at the previous article if you need more details,

What were the previous results?

We have run multiple scenarios with several orders per wave, moving from one to nine orders per wave.

A bar chart of the walking distance for picking routes with different distance methods applied to 20,000 order lines, with a 35-meter distance threshold using Python. The x-axis is the number of orders per wave from 1 to 9. The y-axis shows the total walking distance in meters. Method 1, shows the highest walking distance without clustering. Method 2, applies clustering to single-line orders only, reducing the walking distance. Method 3, in blue, shows the lowest total walking distance.
Article 2: 20,000 Order Lines / 35 m distance Threshold — (Image by Author)

Method 3 (applying clustering to all orders) was the most efficient, with nine orders/Wave reducing the walking distance by 83%.

How much can we reduce walking distance by applying TSP-optimized solutions of Google-OR on top of this?

Let us implement this pathfinding solution with our picking route creation workflow.

Code

We now generate a picking route using

  • Next Closest Location: distance_init
  • TSP Optimized Solution of Google-OR: distance_or

We calculate the results

  • Distance Reduction (%): 100 * (distance_init-distance_or)/distance_init

Results for OR-Tools

Observations

  • Google's solution is more impactful when the number of orders per wave increases.
  • With clustering applied, the impact of the OR tool is reduced.
    [Method 3 vs. Method 1]

What is the best scenario?

It remains (Method 3, 9 orders/Wave) with the highest distance reduction with a slight improvement of 1.23% thanks to Google’s solution.

How can you support operations in implementing this solution?

👉You can find the complete code in my GitHub repository: Link

💡 Follow me on Medium for more articles related to 🏭 Supply Chain Analytics, 🌳 Sustainability and 🕜 Productivity.

Understand TSP Solution

For the optimal scenario, OR-Tool TSP Solution reduces the total Walking Distance by 1.23 %.

Why is it better than the initial next closest location strategy?

Let’s have a look at a specific example to understand.

Highest Gap: 60 m for 21 Picking Locations

A specific example of one picking wave with 21 Locations covered

  • OR-Tool TSP: Distance = 384 m
  • Next Closest Location: Distance = 444 m
  • Distance Reduction: 60 m
An animated scatter plot showing the Next Closest Location solution route for optimizing picking paths in a warehouse with Python. The plot shows numbered points representing warehouse locations connected by dashed lines indicating the sequence of the picking path. Locations are scattered across a grid with the route starting at point 1 and ending at point 21. The points are colored yellow.
(11) Next Closest Location Solution Route for 21 Locations (Distance: 444 m) — (Image by Author)
An animated scatter plot depicting the OR-Tool TSP (Traveling Salesman Problem) optimized solution route for warehouse picking paths with Python. Numbered points, representing picking locations in the warehouse, are connected by dashed lines illustrating the optimized path. The route starts at point 1 and ends at point 21. The points are colored orange, and the optimization improves the efficiency of the picking route compared to the Next Closest Location strategy.
(12) OR-Tool TSP Optimization Solution Route for 21 Locations (Distance: 384 m) — (Image by Author)

Limits of Next Closest Location (NCL) Algorithm

TSP Point 2 (Point A)
In this specific example, we can see the benefits of the TSP Optimization Solution for the second point (19.5, 21)

(13) Specific Example of NCL vs TSP — (Image by Author)

Starting at Point 1, the three closest points are {A, B, C}

  1. The closest point to Point 1 is A
  2. NCL Point is going directly to C, TSP starts from A
  3. TSP covers {A, B, C} covers in one time while NCL only covers {B, C} and let A for later
A comparison of two scatter plots with picking routes for warehouse optimization. The top plot shows the OR-Tool TSP Optimization Solution Route with numbered points representing warehouse locations connected by dashed lines. Locations A, B, and C are highlighted in red, indicating key points in the picking path, with point A located at coordinates (19.5, 21). The bottom plot shows the Next Closest Location Solution Route, with similar points connected by dashed lines. The OR-Tool TSP is better.
(14) Specific Example of NCL vs TSP — (Image by Author)

NCL Point 21
In the example above, after Point 20 (Point A), the warehouse picker still needs to cover Point 21 (Point D) before going to the depot (Point 1).

This extra distance significantly impacts NCL's efficiency for this wave.

Do you want to create animated graphs like the one below?

An animated scatter plot depicting the OR-Tool TSP (Traveling Salesman Problem) optimized solution route for warehouse picking paths with Python. Numbered points, representing picking locations in the warehouse, are connected by dashed lines illustrating the optimized path. The route starts at point 1 and ends at point 21. The points are colored orange, and the optimization improves the efficiency of the picking route compared to the Next Closest Location strategy.
Animated Plot generated by the Author using Pillow — (Image by Author)

Animate your Python Graphs with Pillow

As asked several times, I shared a simple workflow for generating these Python graph animations in another article.

The approach is straightforward: you generate frames combined in a gif using Python's Pillow library.

For more information, have a look at the article linked below

Conclusion

Applying the Travelling Salesman Problem Solution coupled with intelligent Order Wave Processing can optimize the picking sequence for waves with many picking locations.

You now have a collection of three different layers of optimization you can experiment with your datasets.

  • Order batching: group orders in waves
  • Spatial clustering: group orders by geographical clusters of Picking Locations to reduce pickers’ walking distance.
  • Overcome the next closest location strategy to its limits with Google OR-tool pathfinding solution.

After picking, can we optimize the loading process?

Containers Loading Optimization with Python

After the container shortage during COVID, optimizing container loading became a priority for logistics teams importing goods from overseas via sea freight.

A 3D graphical representation of two warehouse containers side by side. Both containers are shown from a top-down perspective, revealing blue boxes stacked neatly inside the containers. The first container has a larger volume of stacked blue boxes toward the front thanks to the container loading optimization algorithm, while the second container has a smaller stack. Two additional blue boxes are placed outside of the containers.

The example above shows the impact of a wrong loading strategy.

The operator who loaded the left container had two pallets on the side that could not be loaded.

Can we design an algorithm to help forklift drivers maximize the number of pallets loaded per container?

Yes, in another article, I share a case study using an application of the knapsack problem to find the optimal sequence of pallet loading.

A 2D schematic diagram representing a stacked layout in a container generated by the container loading algorithm developped in Python. The diagram shows rectangular sections stacked in rows. The bottom left sections are outlined in red, indicating a focus or highlighting specific rows compared to the rest, which are outlined in black.
Example of optimal loading plan generated by the algorithm — (Image by Author)

For more details, have a look at this article

Beyond reducing costs, these tools benefit operators by allowing them to reach their productivity targets with less effort.

What about the social impact of these algorithms?

Improve ESG Scoring

Environmental, Social and Governance (ESG) reporting is a method companies use to disclose their governance structures, societal impacts and ecological footprint.

A visual representation of the three pillars of ESG. Each pillar is displayed in a separate colored house-shaped section. The “Environmental” pillar covers carbon footprint reduction, climate change strategy, waste reduction, and energy efficiency. The “Social” pillar emphasizes fair living wages, equal job opportunities, health and safety, responsible suppliers, and respecting labor laws. The “Governance” pillar focuses on corporate governance, risk management, compliance, ethical business.
ESG Pillars Presentation — (Image by Author)

As stakeholders increasingly demand corporate social responsibility (CSR), ESG reporting has become critical to companies’ long-term strategies.

This image shows a high-level overview of ESG (Environmental, Social, Governance) reporting. Three sections are represented: the environmental section shows an icon representing the planet, the social section with an icon representing people, and the governance section with an icon of a building representing corporate governance. The ESG ($) indicator is shown in the middle, implying financial significance or considerations in relation to ESG factors.
Examples of ESG components

The social aspect is essential when we consider productivity and workforce costs.

How can you ensure good working conditions, fair wages and profitability?

The optimization solutions presented in this series of articles can be converted into savings and positive social impacts for the workforce.

  • ESG score improvements can be converted into financial gains
  • Social aspects gains can improve the reputation of your company

If you want to understand how to convert these gains,

About Me

Let’s connect on Linkedin and Twitter. I am a Supply Chain Engineer who uses data analytics to improve logistics operations and reduce costs.

For consulting or advice on analytics and sustainable supply chain transformation, feel free to contact me via Logigreen Consulting.

If you are interested in Data Analytics and Supply Chain, look at my website.

💌 New articles straight in your inbox for free: Newsletter
📘 Your complete guide for Supply Chain Analytics: Analytics Cheat Sheet

References

[1] Samir Saci, Improve Warehouse Productivity using Order Batching with Python, Link

[2] Samir Saci, Improve Warehouse Productivity using Spatial Clustering for Order Batching with Python Scipy, Link

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

Responses (1)

What are your thoughts?

Data science is an immensely powerful tool in our data-driven world. Call me idealistic, but I believe this tool should be used for more than getting people to click on ads or spend mor...

Exactly Many Industries are using this technique..Damn true

--

F1 score

Harmonic mean of precision and recall. Formula
F1 = (2*P*R)/(P+R)

--

Thanks very much for sharing your approach! I’ve added it to my Awesome Python for Social Good list.

--