Algorithm for stacked orders in food delivery (Pick up and deliveries)

Question

I am trying to implement stacking orders

While the most optimal solution would be to consider picking up orders from nearby restaurants that have similar food prep time AND nearby delivery locations.

I'd like to start off with something slightly easier - that is stacking orders only from the SAME restaurants that have similar food prep time to multiple deliver points. (Deliveroo example: https://riders.deliveroo.com.sg/en/tech-round-up-stacking-orders)

The scale is about 200k orders hourly and 5000 riders, 5000 restaurants. Run time is important here ~ ideally less than 1 minute (on demand service)

What I have in mind is this:

(1) Collect orders per few minutes interval and sort all orders by their prep time O(nlogn)

(2) group orders by restaurant O(n)

(3) Starting from the order that has the smallest remaining prep time, look for any orders in the same restaurant within the time window (let's say 3-5 mins), if exists group them as a stack. O(1).

• locations of delivery points are not considered here to reduce computations - most delivery points are within 3km in a given zone.
• not so interested in global optima for computational time. Picking the order that has the smallest remaining prep time is to avoid considering all combinations for rider - orders permutation matching.

(4) Run simulated annealing for semi-optimal TSP for vehicle routing. (ex. Pickup order A, B, C from the same restaurants -> deliver C to A to B)

I understand for multiple PICKUP and Dropoff the problem would translate into VRPTW - a hard problem to solve in real-time.

A somewhat easier problem - single Pickup and multiple Drop off would there be any better way than what I have in mind right now?

Many thanks in advance.

Answer 1

I have implemented your algorithm

(1) Collect orders per few minutes interval and sort all orders by their prep time

(2) group orders by restaurant

(3) Starting from the order that has the smallest remaining prep time, look for any orders in the same restaurant within the time window (let's say 3-5 mins), if exists group them as a stack.

Running my implementation with a configuration as follows

theConfig.OrdersPerHour = 20000;        // incoming order per hour
theConfig.GroupTimeMins = 5;            // order collection time
theConfig.ResterauntCount = 1000;       // number of resteraunts
theConfig.PickupWindowMins = 5;         // pickup window time
theConfig.MaxPrepTimeMins = 15;         // maximum order preparation time

815 order stacks are generated in about 1/3 second

C:\Users\James\code\pickup\bin>pickup.exe
Pickup
815 order stacks created
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        0.329374        0.329374        stack

You can inspect the code at https://github.com/JamesBremner/pickup

Note that this time does NOT include the time to generate the drivers' routes. This should not take too long since each driver will be visiting less than half a dozen sites. It depends a lot on the size of the graph being searched. If you can partition the graph around each restaurant, then it will go very quickly. If each search can be completed in a third of a second and the searching is done in series then you will need 5 mins to perform 800 routes.

As an initial experiment I have assumed:

1. Partition search graph to 5km by 5km with restaurant at center
2. Manhattan distances
3. Deliveries to furthest corners, or near to furthest corners

Using the following input to the Pathfinder travelling salesman implementation.

format sales
manhatten 0 0 0
c 0.0 0.0 rest
c 2.5 2.5 topright
c -2.5 2.5 topleft
c 2.5 -2.5 bottomright
c 2 2 neartopright

gives

This takes 0.4 milliseconds.

pickup timer test
manhatten 0 0 0
c 0.0 0.0 rest
c 2.5 2.5 topright
c -2.5 2.5 topleft
c 2.5 -2.5 bottomright
c 2 2 neartopright

route rest -> topright -> neartopright -> topleft -> bottomright -> rest ->
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        0.0003218       0.0003218       TravellingSalesManCalculation
       1        2.23e-05        2.23e-05        CalculateManhattenDistances

For 800 order stacks that is 1/3 second when processed in series. Adding the order stacking time shown above, gives total calculation time of less than a second. You will have to add the time taken to receive the order data from your server and then send the routes to the drivers which will depend on your server and network, but I would guess you will need just a few more seconds. ( You still haven't posted your runtime requirement!!! )

Note: I am assuming that all that the drivers need is a list of delivery locations in optimal order, when they can use their own GPS device to find the detailed route to the next delivery. If this is not the case, and the drivers need detailed routing ( left right, second left ... ) then this will take longer. Please let me know how you want this to work.

I have increased the number of restaurants to 5000

C:\Users\James\code\pickup\bin>pickup.exe
Pickup
Orders per hour                20000
Order collection time mins     5
Restaurants                    5000
Pickup window mins             5
Maximum order preparation mins 15
1416 order stacks created
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        2.80843         2.80843         stack

Since the order rate has not increased, the number of order per restaurant is reduced and so is the opportuniy to stack orders - result is an significant increase in calculation time.