# Lane assignment algorithm

We need to match orders to the best drivethrough lane based on the new order and the contents of each lane.

The overview of the algorithm is:

1. if a lane is empty, assign the next order there
2. ignore lanes that are full
2. if no lanes are empty, calculate the scores for all lanes and the new order
3. place the order in the lane with the closest score to the score of the order
4. if there is a tie between lanes, place the order in the tied lane that has the lowest total order score
5. if there is a tie in order score, place the order in the lane with the fewest items

## Introductory order score

Calculate the score of the new order and the orders in the lanes based on their cost (ranges have been chosen based on pickup order code):

0-5000 SAR = 5
5000-10000 SAR = 10
10000+ SAR = 20

Normalised the order score to always fall between 0 and 1 by dividing by 20.

The exact groups do not need to stay fixed like this as long as the score can be normalised to between 0 and 1, so that it is comparable with other values in this document.

We have discussed storing an exact value for the preparation of each product in the database, and adding up all the products in an order in order to determine an order score. That approach can be implemented after launch if it is helpful.

## Lane score formula
This formula has been designed to give a higher value when there are larger size orders in the lane (high average), but to reduce as more orders are added to the lane.

`max(0, average normalised order score - 0.25 * utilisation)`

Where

* average normalised order score = `sum of orders in lane / number of orders in lane`
* utilisation = `number of orders in lane / max capacity of lane`

This formula should produce a value between 0 and 1 for a lane so that it can be compared with a new order's score.

This formula should be refined as time goes on, ideally with proper simulation (Connor has offered to help with this).

## Implementing the changes to current albaik-web code

This is a plan for making a series of small changes to our current code.

- implement a score calculation for an individual order based on [order score](#introductory-order-score) (suggestion: a small DriveThruOrderScore class might be good)
- add a `MAX_CAPACITY` constant to Lane. This will be the same for all lanes, which might not match reality. A customisable value can be added after the whole algorithm has been implemented.
- update `LaneAssignment` to ignore lanes that are full (use the `MAX_CAPACITY` constant)
- update `LaneAssignment` to automatically choose the first empty lane if any are available
- implement a lane utilisation calculation based on the hardcoded `MAX_CAPACITY`
- implement the lane score calculation (suggestion: a method on `Lane`)
- update `LaneAssignment` to take in an order score and return the lane with the closest lane score based on the formula above.

---

# Modelling

I (Connor) didn't make as much progress as I would have liked. Partly because it took a while to get my machine set up, partly because my brain was rusty, and partly because it's an even longer while since I used numpy/scipy instead of matlab.

Having said that, I did make some progress and I hope this can lay the groundwork for future work.

Broadly what we want to achieve is:
- Evaluate lane assignment algorithms for suitability
- Improve algorithms/order score weights

Given a lane assignment algorithm, we can optimise the weightings/order score ratings to minimise “unfulfilled” orders —where an unfulfilled order corresponds to an order not being placed due to all lanes being full. In reality these orders would likely be moved to waiting bays, but this metric is a useful heuristic for measuring how well lane assignment is facilitating order throughput.

## What we have done so far
1. Rejected outliers from historical order data using modified Z-score
2. Approximated the probability distribution of order subtotal based on a subset of historical order data.
3. Used this distribution to calculate the probability an order has a subtotal in the bins defined by the order score (i.e 0-5000, 5000-10000, 10000+ SAR).
4. Guessed the range of “time to serve” each order subtotal bin corresponds to.
5. Run crude a time-stepping simulation to predict “unfulfilled orders”.

## Simulation assumptions (simplifications)
### Time to serve an order is linked to order subtotal
Order subtotal is the basis upon which orders are scored, and a time to serve value is assigned to each order so that orders can be popped from the each lane queue over time. Orders with higher scores correspond to orders that take longer to serve. A time is chosen at random from a range of times, for each order. This could be improved if we had more accurate data (e.g similarly to how we used order subtotal data to obtain an approximate probability distribution for order subtotal). We might find that the existing order subtotal bins (which are used to estimate pickup preparation collection time) aren’t appropriate for predicting drive thru preparation collection times.

### Orders are placed regularly (i.e every X seconds) over a given time period.
I doubt this is accurate, though. A simple, but quick, improvement might be to break down the model into “chunks”, whereby each time period has a different fixed order rate. This would account broadly for peaks in demand, and this might be good enough. A more complicated approach might use the probability an order is placed at any given time of day in a given branch to place orders irregularly (but more realistically).

### Unfulfilled orders are never fulfilled
Rather than modelling waiting bays, this counts the number of unfulfilled orders. In reality, orders would go into a waiting area and be fulfilled at some point (i.e there is another queue). There might be a relationship between unfulfilled orders and future order rate (i.e when there are 5 unfilled orders, these need to be placed ASAP), but I’m not sure we should worry too much about this.

### Defined variables in simulation
The below variables should be adjusted to reasonable values
- Lane capacity (assumed equal across lanes)
- Number of lanes
- Order rate (assumed fixed)

## Next steps
- Refine the code so we can optimise the algorithms/weights
- Optimise algorithms/scoring weights for minimum unfulfilled orders
- Explore order items as an indicator of order complexity

## Resources

[GitHub repo](https://github.com/thoughtbot/albaik-lane-assignment)