Improve Warehouse Productivity using a Pathfinding Algorithm with Python

Implement a Pathfinding Algorithm based on a Travelling Salesman Problem Designed with Google AI Operation Research Libraries.

Design Pathfinding Algorithm using Google AI to Improve Warehouse Productivity — (Image by Author)

This article is part of a series about Warehouse Operations Optimization with Python. (Part 1, Part 2)

In the first articles, we built a model to test several strategies of Orders Wave Creations to reduce the walking distance for picking by

• Warehouse Mapping: Link each order line with the associated picking location coordinate (x, y) in your warehouse
• Distance Calculation: a function calculating walking distance from two picking locations
• Picking Locations Clustering: functions grouping orders by waves using geographical (x, y) clusters to reduce the maximum distance between two locations in the same picking route

(0) Process Flow for Picking Route Calculation — (Image by Author)

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

For each wave, we have a list of picking locations that need to be covered by the Warehouse Picker.

(1) Potential Routes for a Wave covering 3 Picking Locations — (Image by Author)

The next target is to design a function to find a sequence of locations that will minimize walking distance.

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

I. Beyond the Next Closest Location Strategy
II. Travelling Salesman Problem Application
1. Adapt Google-OR Model
2. Simulation: OR-Tool Solution vs. Closest Next Location
3. 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. Impact on the ESG Scoring
Improve wages and working conditions with advanced analytics

I. Beyond the Next Closest Location Strategy

Initial Solution: Next Closest Location Strategy

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

(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 next locations [(xj, yj), (xk, yk), (xh, yh)].

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

Question: Is it the most optimal solution for Picking Route Creation ?

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

II. Travelling Salesman Problem Application

Objective: Find the optimal algorithm for picking route creation using the Single Picker Routing Problem (SPRP) for a two-dimensional warehouse.

SPRP is a specific application of the general Traveling Salesman Problem (TSP) answering the question:
“Given a list of storage locations and the distances between each pair of locations, what is the shortest possible route that visits each storage location and returns to the depot ?”

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

The objective is to find the best solution out of a very large set of possible solutions.

OR-Tools part of Google AI Solutions — (Source: Google AI Logo, Link)

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

Adapt Google-OR Model

The only adaptation we need to do

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)

You can find the full code in my GitHub repository: Link
My portfolio with other projects: Samir Saci

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]

Simulation: OR-Tool Solution vs. Closest Next Location

The target is to estimate the impact on total walking distance if we use the TSP Optimized Solution of Google-OR vs. our initial Closest Next Location Solution.

We’re going to use the part 2 method to simulate scenarios

• 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]
• 3 Methods for Clustering
  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;

(10) Article 2: 20,000 Order Lines / 35 m distance Threshold — (Image by Author)

Best Performance
Method 3 for 9 orders/Wave with 83% reduction of Walking Distance

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

Code

OR-Tool Solution vs. Closest Next Location

After running Waves using these three methods, we estimate picking route using:

• Next Closest Location: distance_init
• TSP Optimized Solution of Google-OR: distance_or
• Distance Reduction (%): 100 * (distance_init-distance_or)/distance_init

Few Insights

• Orders per Wave: when orders number per wave OR-Tools is more impactful
• Methods: when clustering for Wave Processing is added, OR-tools impact is lower

Best Scenario Result
Method 3 (Clustering for all orders) impacts -1.23 % of the total Walking Distance.

Learn more about Voice Picking Systems to implement this solution.

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

III. Understand TSP Solution

For Method 3 (Clustering for all orders), OR-Tool TSP Solution reduces the total Walking Distance by 1.23 %.

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

(11) Next Closest Location Solution Route for 21 Locations (Distance: 444 m) — (Image by Author)

(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

(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 greatly impacts NCL's efficiency for this wave.

IV. Conclusion

Improve ESG Scoring

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

ESG Pillars Presentation — (Image by Author)

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

Examples of ESG components

The social aspect is very important 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,

What is ESG Reporting?

Conclusion

Applying the Travelling Salesman Problem Solution to the Picking Route Creation can reduce total Walking Distance and improve overall productivity.

Coupled with smart Order Wave Processing, it can optimize the picking sequence for waves with many picking locations by finding the shortest path to cover a maximum number of locations.

About Me

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

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

Samir Saci | Data Science & Productivity

References

[1] Google OR-Tools, Solving a TSP with OR-Tools, Link

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

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