Currently, I’m working at create an algorithm for pooling order, this is a small note of mine after finish the first version of it.

1. Introduction

After reaching production testing stage of my pooling algorithm, I just randomly thought if it could be developed more futher, such as 3 or more order at the same time. Then, I just realize that the answer is “YES, IT COULD” and the solution is really simple.

2. Original idea of pooling 2 orders

The starting idea is just ordinary. If we want to deliver 2 orders or 2 packages at the same time (with difference in both pick up locations and drop off locations), the delivering route of 2 orders should be overlaped with each other.

Moreover if our driver tend to turn back, our customer who could observe our driver who deliver might have a bad experience which is not a good sign for our company. The original solution of this problem was shown by Lyft.

We implement our algorithm as below: (orderA is a new order, orderB is an order which hasn’t been accepted by any drivers)

triggered each new order (A) created

for each non-boarded order B:
    if (B overlap A):
        MIN = find_min(AsBsAeBe,AsBsBeAe, BsAsBeAe, BsAsAeBe)
        if MIN < AsAe+BsBe - 1km:
            add (AB,MIN) into selection(S)

Where s and e stands for start and end which are order pick-up location and drop-off location. selection(S) is a set of orders which can be pooled with orderA.

With final selection(S), we could find the best order to pool with orderA.

3. A development for 3-order pooling based on the original 2-order pooling

So, if we continue using the original ideas of pooling for 3 orders at the same time, which means we need to find not only the overlap but all the permutations of (As,Ae,Bs,Be,Cs,Ce) which is more than just 4 cases.

Instead of listing all the possible cases (which could be wrong or accidentally missed by human mistakes), there was a simpler idea came to my mind while I was having dinner.

If 3 oders could be pooled with each other, there will be at least 1 order that can be pooled with the other two. In other words, if A,B and C can be pooled then for example, B and C are in selection of A.

Therefore, if the length of a selection(S) is higher than 2, there will be a high chance that we could pool all 3 orders at once.

With this approach, the way we find 3 orders to pool is way easier than using main ideas with finding overlap and permutations and we can inherit our 2-order algorithm.

About the order of pick-up and drop-off location, we can have many way to do it, in this note I just sort our lattitude or longtitude to have a location order.

And our final 3-order algorithm:

if len(selection(S) of orderA) >= 2:
    for all S1 and S2 of selection(S):
        #This is my way of pool, could have another way like check S1 in selection of S2, etc
        location_order = sort(S1_s,S1_e,S2_s,S2_e,orderA_s,orderA_e)
    return pool orderA,S1,S2 with location_order

4. Further development in pooling algorithm

With this inherent way of improvement, we can have a 4-order algorithm just by changing the way we see 4 orders from A1,A2,A3,A4 to 2 stacks of 3 orders A1,A2,A3 and A2,A3,A4. Keep inheriting and we can have N-order pooling algorithm