Optimize pick path in a warehouse
As you probably already are aware of I have shown you earlier a vba macro I made that finds the shortest path between two points. There are obstacles between these two points to make it more difficult.
The problem with that macro is that it could only show a path that moves up, down, left or right. So I had to change it so it can move in eight directions.
Instead of using 6 movements it now uses 3 movements, it can now go diagonal from A to B. This is more realistic, of course.
Calculating all possible paths between 15 locations
The following animated picture shows you 9600 storage locations, named item 1 to 9600. Each black dot is a storage location in this warehouse.
There is a start point almost at the top of this picture. I have chosen 14 random locations and the macro shows the shortest path and calculates the distance in the table at the bottom of this picture.
Find the shortest pick path
Now that we have all distances between 15 locations we can use the Excel Solver to find the shortest path. First we need to setup a sheet.
Formula in cell C4:
=INDEX(Items!$H$4:$H$17, MATCH('Optimize total path'!B4, Items!$G$4:$G$17, 0))
Formula in cell D4:
=INDEX(Paths!$C$3:$Q$17, MATCH('Optimize total path'!C3, Paths!$B$3:$B$17, 0), MATCH('Optimize total path'!C4, Paths!$C$2:$Q$2, 0))
Formula in cell D19:
=SUM(D3:D18)
Now it is time for the excel solver to find the optimal path. If you need more detailed instructions, check out this page: Travelling Salesman Problem in Excel Solver
After a few minutes this sequence is shown with the shortest total distance.
Optimal path
Here is the shortest path. It begins with the start point almost at the top and goes through all 14 storage locations and then back to start point.
Read more interesting posts:
- A quicker A * pathfinding algorithm
- Finding the shortest path – A * pathfinding
- Build a maze
- Solve a maze
- Identify numbers in sum using solver
- Excel udf: Find numbers in sum
Get excel *.xlsm file
Optimize-pick-path-in-a-warehouse1.xlsm
Pathfinding category
Two months ago I posted some interesting stuff I found: Shortest path. Let me explain, someone created a workbook that calculated […]
3 weeks ago I showed you a A* pathfinding algorithm. It was extremely slow and sluggish and I have now made it […]
Solver category
Here is a useful feature I recently found googling for Excel solver examples. I have summed some random values from […]
I found this excel question: I am a Controller in a multinational company. We have many transactions (sales, credits, debits, […]
The COMBIN function returns the number of combinations for a specific number of elements out of a larger number of […]
Excel categories
11 Responses to “Optimize pick path in a warehouse”
Leave a Reply
How to comment
How to add a formula to your comment
<code>Insert your formula here.</code>
Convert less than and larger than signs
Use html character entities instead of less than and larger than signs.
< becomes < and > becomes >
How to add VBA code to your comment
[vb 1="vbnet" language=","]
Put your VBA code here.
[/vb]
How to add a picture to your comment:
Upload picture to postimage.org or imgur
Paste image link to your comment.
It is a great job, however the diagonal steps (1.41 meter) on the grid are longer than the vertical or horizontal steps (1 meter). That is not taken into account in this code, so the lenghts in the distance matrix are not exact. So, I was wondering whether it is possible to include the extra diagonal distances as well and how to do it in the code.
Krnja,
What a great question! I did not think of that.
I made these changes to the code:
and
Select Case Nf Case Gv(0) tr = tr + 1 Rng(tr + 1, tc + 1) = "W" i = i + 1 Case Gv(1) tc = tc + 1 Rng(tr + 1, tc + 1) = "W" i = i + 1 Case Gv(2) tr = tr - 1 Rng(tr + 1, tc + 1) = "W" i = i + 1 Case Gv(3) tc = tc - 1 Rng(tr + 1, tc + 1) = "W" i = i + 1 Case Gv(4) tr = tr + 1 tc = tc + 1 Rng(tr + 1, tc + 1) = "W" i = i + Sqr(2) Case Gv(5) tr = tr - 1 tc = tc + 1 Rng(tr + 1, tc + 1) = "W" i = i + Sqr(2) Case Gv(6) tr = tr - 1 tc = tc - 1 Rng(tr + 1, tc + 1) = "W" i = i + Sqr(2) Case Gv(7) tr = tr + 1 tc = tc - 1 Rng(tr + 1, tc + 1) = "W" i = i + Sqr(2) End SelectYou can get the workbook here:
Optimize-pick-path-in-a-warehouse-Krnja.xlsm
See sheet Paths, the old values are in cell range A25:Q41 and the new are in B2:Q17.
Great, gets it way more realistic. Another thing I noticed is that the distance matrix is not perfectly assymetric. Start to article 4124 for example. And the difference sometimes grows (to 10-20 metres) when there is no small aisles but more free paths like in the example below. If you have buildings and walls and you want the distance matrix of it:
https://oi57.tinypic.com/2pqw5s9.jpg
OK, I turned the heuristics to 0 to return to the classic Dijkstra algorithm and the table is way more assymetric as you can see in the link below:
https://oi62.tinypic.com/eb632r.jpg
So seems like a heuristic related issue. However, even with Dijkstra few are not matching as shown in the same link. As I'm a beginner with VBA coding, the exploring goes slow :)
Hi Kmja
First of all I should say Hats-off great job. secondly, I am very new to excel VBA coding and I am trying to understand if this application can be used for pallet racks in a warehouse. If yes, could you please help me understand.
Appreciate it!
Best Regards
Is there an easy way to convert the meters into feet in the code? I'm not entirely familiar with Dijkstra algorithm, and and VBA script is very arcane to me.
Thank you for this awesome script.
If the items are next to each other then the code gives wrong distances and in the MAP sheet the walls become open paths leading to wrong distances. Can you tell as to why this happens and what should be done to avoid this?
Prometheus,
Try this file:
Optimize-pick-path-in-a-warehouse1.xlsm
Thank you for the update, however the Show Optimal Path Function still fails and the walls become open paths. The distances are now correct, however the path shown is still incorrect.
Thank you for the update, however the Show Optimal Path Function still fails.
For the new file also, the distances calculated from (start to item 4641, 5 to 5886, 7 to 5886, 4124 to 7603, etc) have also become 1, which shouldn't be the case. Could you please look into the same and recheck