Warehousing Operations

Improve Warehouse Productivity using Spatial Clustering with Python

Improve Warehouse Picking Productivity by Grouping Orders in Batches using Picking Location Spatial Clusters

Article originally published on Medium.

I. Two levers of Optimization

In the first article we built the basis to estimate the total picking route walking distance for a set of orders using:

Warehouse Mapping: link each order line with the associated picking location coordinate (x, y) in your warehouse
Distance Calculating: function calculating walking distance from two picking location

We also decided to take a simple approach for

Picking Route Design: given a choice of several picking locations, the warehouse picker will always choose to go to the closest (Next Closest Location Strategy)
Order Waving: orders are ordered and grouped in waves by receiving time from OMS (TimeStamp)

Two levers for improving our solution performance — (Image by Author)

Before looking at complex algorithms, we can try to find insights on how to optimize our algorithm with simple solutions.

🔗

You can find the full code in my GitHub repository: Link

II. Order Wave using Picking Locations Clustering

Single-line orders have the advantage to be located in a single storage location; grouping several single-line orders by cluster can ensure that our picker will stay in a delimited zone.

Where single-line orders are located?

(2) Order Lines DataFrame — (Image by Author)

Function: Calculating the number of single-line orders per storage Location (%)

Code

(1) Distribution of single-line orders lines per storage location — 5,000 order lines (%)

Insights: let us take the example of Distribution above

Scope: 5,000 order lines for 23 aisles
Single line orders: 49% of orders located in alleys A11, A10, and A09

1. Picking locations clustering using Scipy

(3) Order Lines Processing for Order Wave Picking using Clustering by Picking Location — (Image by Author)

Idea: Picking Locations Clusters
Group picking locations by clusters to reduce the walking distance for each picking route. (Example: the maximum walking distance between two locations is <15 m)

Spatial clustering is the task of grouping together a set of points in a way that objects in the same cluster are more similar to each other than to objects in other clusters.

(4) Example of three Picking Locations Clusters — (Image by Author)

Here, the similarity metric will be walking distance from one location to another.

For instance, I would like to group locations ensuring that the maximum walking distance between two locations is 10 m.

1| Challenge 1: Euclidian Distance vs. Walking Distance

For our specific model, we cannot use conventional clustering methods using Euclidian Distance. Indeed, walking distance (using distance_picking function) is different from Euclidian Distance.

(5) Euclidian vs. Custom Distance Example — (Image by Author)

For this specific example, Euclidian distances between i (xi, Yi) and the two points p (x_p, y_p) and j (x_j, y_j) are equal. But, if we compare picker Walking Distance, p (x_p, y_p) is closer.

For this model, Picker Walking Distance is the specific metric that we want to reduce. Therefore clustering algorithm should use our custom-made distance_walking function for better performance.

Example: Locations Clustering within 25 m distance (5,000 order lines)

(6) Left [Clustering using Walking Distance] / Right [Clustering using Euclidian Distance] — (Image by Author)

The left example using Walking Distance is grouping locations within the same aisle reducing picking route distance; while the right example can group locations covering several aisles.

2 | Function: Clusters for Single Line Orders using Walking Distance

For a set of orders, lines extract single lines (df_orderlines) orders and create clusters of storage locations within a distance (dist_method) using the custom distance function (dist_method).

Python code below is using Scipy’s ward and fcluster functions to create clusters of Picking locations using the distance_func metric (walking distance).

Code

3| Function: Single Line Orders Mapping with ClusterID

For a set of order, lines extract single lines (df) orders, clusters id and orders number this function you map your Dataframe with cluster ID for wave creation.

Code

2. Picking locations clustering for Multi-line Orders

Function: Centroid for every multi-line order

Unlike single-line orders, multi-line orders can cover several picking locations. However, we can apply the same methodology applied to the centroids of storage locations.

Example: Order with 3 lines covering 3 different picking locations

(7) Centroid of three Picking Locations — (Image by Author)

Code

After using this function we come back to the mono-line orders situation with a single point (x, y) per order.

We can then apply clustering to these points trying to group order per geographical zone with maximum distance conditions.

II. Model Simulation

To sum up, our model construction, see the chart below, we have several steps before Picking Routes Creation using Wave Processing.

At each step, we have a collection of parameters that can be tuned to improve performance:

(8) Model Construction with Parameters — (Image by Author)

1. Comparing 3 methods of Wave Processing

(9) Three Methods for Wave Processing — (Image by Author)

We’ll start first by assessing the impact of Order Wave processing by clusters of picking locations on total walking distance.

We’ll be testing three different methods.

Method 1: we do not apply clustering (i.e Initial Scenario)
Method 2: we apply clustering on single-line orders only
Method 3: we apply clustering to single-line orders and centroids of multiline orders.

Scenario for Simulation

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

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

Results

Best Performance: Method 3 for 9 orders/Wave with 83% reduction of walking distance
Method 2 vs. Method 1: Clustering for mono-line orders reduce the walking distance by 34%
Method 3 vs. Method 2: Clustering for mono-line orders reduce the walking distance by 10%

2. Tuning Distance Threshold for Clustering

Now that we validated our first assumption that Method3 is the best for our particular scenario (20,000 order lines, 35 m Distance Threshold).

Let us have a look at the Distance Threshold impact on total walking distance.

(10) Different distance threshold for Picking Location Clustering — (Image by Author)

The trade-off between Walking Distance between two locations and Wave Size:

Low Distance: The walking distance between two locations is low but you have fewer orders per wave (more waves)
High Distance: The walking distance between two locations is higher but you have more orders per wave (fewer waves)