Analytic picking route

In my previous post I showed how to use analytic rolling sums to do FIFO picking of items. But the final picking list of the solution had a weakness - the forklift driver picking the items would have to drive back and start from the beginning of each aisle in the warehouse.

In this post I show how to use analytic ranking to create a better more optimized picking route for our forklift driver to keep him happy :-)





First we setup a couple of tables with some data (this is the same tables and data as the other post):

SQL> create table inventory (
  2     item  varchar2(10),  -- identification of the item
  3     loc   varchar2(10),  -- identification of the location
  4     qty   number,        -- quantity present at that location
  5     purch date           -- date that quantity was purchased
  6  )
  7  /

Table created.

SQL> begin
  2     insert into inventory values('A1', '1-A-20', 18, DATE '2004-11-01');
  3     insert into inventory values('A1', '1-A-31', 12, DATE '2004-11-05');
  4     insert into inventory values('A1', '1-C-05', 18, DATE '2004-11-03');
  5     insert into inventory values('A1', '2-A-02', 24, DATE '2004-11-02');
  6     insert into inventory values('A1', '2-D-07',  9, DATE '2004-11-04');
  7     insert into inventory values('B1', '1-A-02', 18, DATE '2004-11-06');
  8     insert into inventory values('B1', '1-B-11',  4, DATE '2004-11-05');
  9     insert into inventory values('B1', '1-C-04', 12, DATE '2004-11-03');
 10     insert into inventory values('B1', '1-B-15',  2, DATE '2004-11-02');
 11     insert into inventory values('B1', '2-D-23',  1, DATE '2004-11-04');
 12     commit;
 13  end;
 14  /

PL/SQL procedure successfully completed.

SQL> create table orderline (
  2     ordno number,        /* id-number of the order     */
  3     item  varchar2(10),  /* identification of the item */
  4     qty   number         /* quantity ordered           */
  5  )
  6  /

Table created.

SQL> begin
  2     insert into orderline values (1,'A1',24);
  3     insert into orderline values (1,'B1',18);
  4     commit;
  5  end;
  6  /

PL/SQL procedure successfully completed.

We are now ready to start...

We will pick items for sales order number 1.

SQL> variable pick_order number;
SQL> 
SQL> begin
  2     :pick_order := 1;
  3  end;
  4  /

PL/SQL procedure successfully completed.

First let us recap the FIFO picking list from the Analytic fifo picking post:

SQL> select
  2  s.loc,
  3  s.item,
  4  least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
  5  from (
  6   select
  7   o.item,
  8   o.qty ord_qty,
  9   i.loc,
 10   i.purch,
 11   i.qty loc_qty,
 12   nvl(sum(i.qty) over (
 13      partition by i.item
 14      order by i.purch, i.loc
 15      rows between unbounded preceding and 1 preceding
 16   ),0) sum_prv_qty
 17   from orderline o
 18   join inventory i
 19      on i.item = o.item
 20   where o.ordno = :pick_order
 21  ) s
 22  where s.sum_prv_qty < s.ord_qty
 23  order by
 24  s.loc;

LOC        ITEM         PICK_QTY                                              
---------- ---------- ----------                                              
1-A-20     A1                 18                                              
1-B-11     B1                  3                                              
1-B-15     B1                  2                                              
1-C-04     B1                 12                                              
2-A-02     A1                  6                                              
2-D-23     B1                  1                                              

6 rows selected.

We see that in aisle B of warehouse 1 the driver would be better of by going in the other direction.

For the sake of making this routing demo more clear, let us use another version of the SQL from the other post - the version that does not do FIFO picking, but cleans out small quantities of items first. This gives us more locations so we better can see what happens:

SQL> select
  2  s.loc,
  3  s.item,
  4  least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
  5  from (
  6   select
  7   o.item,
  8   o.qty ord_qty,
  9   i.loc,
 10   i.purch,
 11   i.qty loc_qty,
 12   nvl(sum(i.qty) over (
 13      partition by i.item
 14      order by i.qty, i.loc   -- << changed this line
 15      rows between unbounded preceding and 1 preceding
 16   ),0) sum_prv_qty
 17   from orderline o
 18   join inventory i
 19      on i.item = o.item
 20   where o.ordno = :pick_order
 21  ) s
 22  where s.sum_prv_qty < s.ord_qty
 23  order by
 24  s.loc;

LOC        ITEM         PICK_QTY                                              
---------- ---------- ----------                                              
1-A-20     A1                  3                                              
1-A-31     A1                 12                                              
1-B-11     B1                  4                                              
1-B-15     B1                  2                                              
1-C-04     B1                 11                                              
2-D-07     A1                  9                                              
2-D-23     B1                  1                                              

7 rows selected.

To drive optimally our driver should go up aisle 1-A, down aisle 1-B, up aisle 1-C and down aisle 2D. In other words, our select should "switch direction" on every other aisle.

First let us split the location into warehouse / aisle / position:

SQL> select
  2  to_number(substr(s.loc,1,1)) warehouse,
  3  substr(s.loc,3,1) aisle,
  4  to_number(substr(s.loc,5,2)) position,
  5  s.loc,
  6  s.item,
  7  least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
  8  from (
  9   select
 10   o.item,
 11   o.qty ord_qty,
 12   i.loc,
 13   i.purch,
 14   i.qty loc_qty,
 15   nvl(sum(i.qty) over (
 16      partition by i.item
 17      order by i.qty, i.loc
 18      rows between unbounded preceding and 1 preceding
 19   ),0) sum_prv_qty
 20   from orderline o
 21   join inventory i
 22      on i.item = o.item
 23   where o.ordno = :pick_order
 24  ) s
 25  where s.sum_prv_qty < s.ord_qty
 26  order by
 27  s.loc;

 WAREHOUSE A   POSITION LOC        ITEM         PICK_QTY                      
---------- - ---------- ---------- ---------- ----------                      
         1 A         20 1-A-20     A1                  3                      
         1 A         31 1-A-31     A1                 12                      
         1 B         11 1-B-11     B1                  4                      
         1 B         15 1-B-15     B1                  2                      
         1 C          4 1-C-04     B1                 11                      
         2 D          7 2-D-07     A1                  9                      
         2 D         23 2-D-23     B1                  1                      

7 rows selected.

Forklift driver will visit 4 aisles here. Now we will number the aisles consecutively for that purpose:

SQL> select
  2  to_number(substr(s.loc,1,1)) warehouse,
  3  substr(s.loc,3,1) aisle,
  4  dense_rank() over (
  5   order by
  6   to_number(substr(s.loc,1,1)),  -- warehouse
  7   substr(s.loc,3,1)   -- aisle
  8  ) aisle_no,
  9  to_number(substr(s.loc,5,2)) position,
 10  s.loc,
 11  s.item,
 12  least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
 13  from (
 14   select
 15   o.item,
 16   o.qty ord_qty,
 17   i.loc,
 18   i.purch,
 19   i.qty loc_qty,
 20   nvl(sum(i.qty) over (
 21      partition by i.item
 22      order by i.qty, i.loc
 23      rows between unbounded preceding and 1 preceding
 24   ),0) sum_prv_qty
 25   from orderline o
 26   join inventory i
 27      on i.item = o.item
 28   where o.ordno = :pick_order
 29  ) s
 30  where s.sum_prv_qty < s.ord_qty
 31  order by
 32  s.loc;

 WAREHOUSE A   AISLE_NO   POSITION LOC        ITEM         PICK_QTY            
---------- - ---------- ---------- ---------- ---------- ----------            
         1 A          1         20 1-A-20     A1                  3            
         1 A          1         31 1-A-31     A1                 12            
         1 B          2         11 1-B-11     B1                  4            
         1 B          2         15 1-B-15     B1                  2            
         1 C          3          4 1-C-04     B1                 11            
         2 D          4          7 2-D-07     A1                  9            
         2 D          4         23 2-D-23     B1                  1            

7 rows selected.

Analytic function dense_rank() ranks the data in the order we specify in the ORDER BY of the OVER clause, and those records with samme values receive the same rank. So column AISLE_NO tells us, that 1-B is the second aisle we visit, while 1-C is the third aisle, etc.

And so we can do a better picking list for our forklift driver:

SQL> select
  2  s2.warehouse,
  3  s2.aisle,
  4  s2.aisle_no,
  5  s2.position,
  6  s2.loc,
  7  s2.item,
  8  s2.pick_qty
  9  from (
 10  select
 11   to_number(substr(s.loc,1,1)) warehouse,
 12   substr(s.loc,3,1) aisle,
 13   dense_rank() over (
 14      order by
 15      to_number(substr(s.loc,1,1)),    -- warehouse
 16      substr(s.loc,3,1)      -- aisle
 17   ) aisle_no,
 18   to_number(substr(s.loc,5,2)) position,
 19   s.loc,
 20   s.item,
 21   least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
 22   from (
 23      select
 24      o.item,
 25      o.qty ord_qty,
 26      i.loc,
 27      i.purch,
 28      i.qty loc_qty,
 29      nvl(sum(i.qty) over (
 30         partition by i.item
 31         order by i.qty, i.loc
 32         rows between unbounded preceding and 1 preceding
 33      ),0) sum_prv_qty
 34      from orderline o
 35      join inventory i
 36         on i.item = o.item
 37      where o.ordno = :pick_order
 38   ) s
 39   where s.sum_prv_qty < s.ord_qty
 40  ) s2
 41  order by
 42  s2.warehouse,
 43  s2.aisle_no,
 44  case
 45   when mod(s2.aisle_no,2) = 1 then
 46      s2.position
 47   else
 48      -s2.position
 49  end;

 WAREHOUSE A   AISLE_NO   POSITION LOC        ITEM         PICK_QTY            
---------- - ---------- ---------- ---------- ---------- ----------            
         1 A          1         20 1-A-20     A1                  3            
         1 A          1         31 1-A-31     A1                 12            
         1 B          2         15 1-B-15     B1                  2            
         1 B          2         11 1-B-11     B1                  4            
         1 C          3          4 1-C-04     B1                 11            
         2 D          4         23 2-D-23     B1                  1            
         2 D          4          7 2-D-07     A1                  9            

7 rows selected.

That's it - we have ordered our picking list first by warehouse, then by aisle, and lastly we order odd aisles ascending and even aisles descending.

Now this assumes we have a door between warehouses both in the "lower" end and the "upper" end of the warehouses, so he can drive from warehouse 1 to warehouse 2 in the "upper" end in order to drive descending through aisle 2-D. If we only have doors between the warehouses in the "lower" end, we need to "re-start" numbering our aisles in each warehouse, so the first aisle for each warehouse always is odd numbered:

SQL> select
  2  s2.warehouse,
  3  s2.aisle,
  4  s2.aisle_no,
  5  s2.position,
  6  s2.loc,
  7  s2.item,
  8  s2.pick_qty
  9  from (
 10  select
 11   to_number(substr(s.loc,1,1)) warehouse,
 12   substr(s.loc,3,1) aisle,
 13   dense_rank() over (
 14      partition by
 15      to_number(substr(s.loc,1,1))     -- warehouse
 16      order by
 17      substr(s.loc,3,1)      -- aisle
 18   ) aisle_no,
 19   to_number(substr(s.loc,5,2)) position,
 20   s.loc,
 21   s.item,
 22   least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
 23   from (
 24      select
 25      o.item,
 26      o.qty ord_qty,
 27      i.loc,
 28      i.purch,
 29      i.qty loc_qty,
 30      nvl(sum(i.qty) over (
 31         partition by i.item
 32         order by i.qty, i.loc
 33         rows between unbounded preceding and 1 preceding
 34      ),0) sum_prv_qty
 35      from orderline o
 36      join inventory i
 37         on i.item = o.item
 38      where o.ordno = :pick_order
 39   ) s
 40   where s.sum_prv_qty < s.ord_qty
 41  ) s2
 42  order by
 43  s2.warehouse,
 44  s2.aisle_no,
 45  case
 46   when mod(s2.aisle_no,2) = 1 then
 47      s2.position
 48   else
 49      -s2.position
 50  end;

 WAREHOUSE A   AISLE_NO   POSITION LOC        ITEM         PICK_QTY            
---------- - ---------- ---------- ---------- ---------- ----------            
         1 A          1         20 1-A-20     A1                  3            
         1 A          1         31 1-A-31     A1                 12            
         1 B          2         15 1-B-15     B1                  2            
         1 B          2         11 1-B-11     B1                  4            
         1 C          3          4 1-C-04     B1                 11            
         2 D          1          7 2-D-07     A1                  9            
         2 D          1         23 2-D-23     B1                  1            

7 rows selected.

By using partition by in the dense_rank function we "re-start" our aisle numbering for each warehouse. Aisle 2-D thus is number 1 within warehouse 2, therefore it is ordered by ascending position because it is odd number.

The splitting of location in this simple case is easy - warehouse is always 1 digit, aisle 1 letter and position 2 digits. In real life you must use your own rules to split locations. Another way in this example could be:

SQL> select
  2  s2.warehouse,
  3  s2.aisle,
  4  s2.aisle_no,
  5  s2.position,
  6  s2.loc,
  7  s2.item,
  8  s2.pick_qty
  9  from (
 10  select
 11   to_number(regexp_substr(s.loc,'^([[:digit:]]+)\-',1,1,null,1)) warehouse,
 12   regexp_substr(s.loc,'(\-)([[:alpha:]]+)(\-)',1,1,null,2) aisle,
 13   dense_rank() over (
 14      partition by
 15      to_number(regexp_substr(s.loc,'^([[:digit:]]+)\-',1,1,null,1))
 16      order by
 17      regexp_substr(s.loc,'(\-)([[:alpha:]]+)(\-)',1,1,null,2)
 18   ) aisle_no,
 19   to_number(regexp_substr(s.loc,'(\-)([[:digit:]]+)$',1,1,null,2)) position,
 20   s.loc,
 21   s.item,
 22   least(s.loc_qty, s.ord_qty - s.sum_prv_qty) pick_qty
 23   from (
 24      select
 25      o.item,
 26      o.qty ord_qty,
 27      i.loc,
 28      i.purch,
 29      i.qty loc_qty,
 30      nvl(sum(i.qty) over (
 31         partition by i.item
 32         order by i.qty, i.loc
 33         rows between unbounded preceding and 1 preceding
 34      ),0) sum_prv_qty
 35      from orderline o
 36      join inventory i
 37         on i.item = o.item
 38      where o.ordno = :pick_order
 39   ) s
 40   where s.sum_prv_qty < s.ord_qty
 41  ) s2
 42  order by
 43  s2.warehouse,
 44  s2.aisle_no,
 45  case
 46   when mod(s2.aisle_no,2) = 1 then
 47      s2.position
 48   else
 49      -s2.position
 50  end;

 WAREHOUSE AISLE        AISLE_NO   POSITION LOC        ITEM         PICK_QTY  
---------- ---------- ---------- ---------- ---------- ---------- ----------  
         1 A                   1         20 1-A-20     A1                  3  
         1 A                   1         31 1-A-31     A1                 12  
         1 B                   2         15 1-B-15     B1                  2  
         1 B                   2         11 1-B-11     B1                  4  
         1 C                   3          4 1-C-04     B1                 11  
         2 D                   1          7 2-D-07     A1                  9  
         2 D                   1         23 2-D-23     B1                  1  

7 rows selected.

The regexp_substr expressions can handle locations where warehouse is one or more digits, aisle is one or more letters and position one or more digits. Use your imagination for other flexible splitting :-)


The complete script of all of the above can be found here, and a sample spool output of running the script is here. Oracle documentation tells you all syntax on analytic functions and specifically DENSE_RANK.

Comments